Category Archives: Uncategorized

Spoj(SUBSUMS) Subset sums

0
Posted on by

Link: http://www.spoj.com/problems/SUBSUMS/

Generating all subsets (bruteforce) will result in TLE.

Is there a optimized solution for this problem ?

Yes! Divide the array into 2 halfs. Generate all subset sums and store it in a vector for each half of the given array.

We are doing this because 2*2^17 is much better than 2^34(Note: n<=34) Now using binary search we have to find all  subsets that will provide a sum in the range [A,B]

How can we do that ?

Let variable “ans” holds the number of subsets whose sum lies within the range [A,B]

For each element i in 2nd half array , Search for lowerbound of A-arr[i](name it as low) and upperbound of B-arr[i](name it as high) in 1st half array.Now add high-low to ans variable.

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <climits>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
#define REP(i,n) for(int i=0; i<n; i++)
#define FOR(i,st,end) for(int i=st;i<end;i++)
#define db(x) cout << (#x) << " = " << x << endl;
#define mp make_pair
#define pb push_back
typedef long long int ll;
int main(){
ll n,a,b;
ll arr[40];
ll subSetSize;
vector<ll>sum1;
vector<ll>sum2;
scanf("%lld%lld%lld",&n,&a,&b);
REP(i,n){
scanf("%lld",&arr[i]);
}
ll powerSetSize=1<<n/2;
subSetSize=n/2;
//finding subset sum for first half
for(ll i=0;i<powerSetSize;i++){
ll sum=0;
REP(j,subSetSize){
if(i&(1<<j)){
sum+=arr[j];
}
}
sum1.pb(sum);
}
//this is to classify even and odd n cases
if((n&1)==1){
subSetSize=n/2+1;
powerSetSize=1<<subSetSize;
}
else{
subSetSize=n/2;
powerSetSize=1<<subSetSize;
}
//finding subset sum for 2nd half
for(ll i=0;i<powerSetSize;i++){
ll sum=0;
REP(j,subSetSize){
if(i&(1<<j)){
sum+=arr[n/2+j];
}
}
sum2.pb(sum);
}
sort(sum1.begin(),sum1.end());
vector<ll>::iterator low,high;
ll ans=0;
//use STL functions to find lower bounds and upper bounds(which internally uses binary search)
REP(i,sum2.size()){
low=lower_bound(sum1.begin(),sum1.end(),a-sum2[i]);
high=upper_bound(sum1.begin(),sum1.end(),b-sum2[i]);
ans+=(high-low);
}
printf("%lld\n",ans);
}
view raw SUBSUMS.cpp hosted with ❤ by GitHub

Spoj(DCEPC206) Its a Murder!

1
Posted on by

Problem link: http://www.spoj.com/problems/DCEPC206/

There is an nlogn solution for this problem. If you have already come across Inversion Count problem www.spoj.com/problems/INVCNT/ you will find this easy to solve.

All you have to do is to add 1 extra line in merge sort algorithm. In merge sort, we divide the array into subarrays recursively until there are just 2 elements in a subarray. We then arrange the subarray in sorted order and merge it with other subarrays.

Consider 2 subarrays arr[l…mid-1] and arr[mid…r] in the merge function which are sorted seperately and are ready to merge

i varies from l to mid-1

j varies from mid to r

i<j always

Let sum be the variable which holds the sum of all the numbers previously seen on the stairs which are smaller than the present number.

if(arr[i]<arr[j])

arr[i] comes before arr[j] in the input array and arr[i] is less than arr[j]. So we have to add arr[i] to sum.

Since arr[i]<arr[j], arr[i]<(arr[j+1], arr[j+2],….,arr[r]) because the subarrays to be merged are sorted.

So on the whole (r-j+1) times of arr[i] is added to the sum.

If you havnt understood still, kindly comment your doubts. Let me help you out.

#include<iostream>
using namespace std;
typedef long long int ll;
ll sum=0;
void merge(ll arr[],ll temp[],ll l,ll mid,ll r){
ll i=l,j=mid,k=l;
while(i<=mid-1&&j<=r){
if(arr[i]< arr[j]){
sum+=arr[i]*(ll)(r-j+1);
temp[k++]=arr[i++];
}
else{
temp[k++]=arr[j++];
}
}
while(i<=mid-1){
temp[k++]=arr[i++];
}
while(j<=r){
temp[k++]=arr[j++];
}
for(i=l;i<=r;i++){
arr[i]=temp[i];
}
}
void mergeSort(ll arr[],ll temp[],ll l,ll r){
ll mid;
if(l<r){
mid=l+(r-l)/2;
mergeSort(arr,temp,l,mid);
mergeSort(arr,temp,mid+1,r);
merge(arr,temp,l,mid+1,r);
}
}
void merge1(long long int arr[], long long int temp[], long long int n){
mergeSort(arr,temp,0, n-1);
}
int main(){
long long int t;
long long int arr[100005],temp[100005];
cin>>t;
while(t--){
long long int i,n;
cin>>n;
for( i=0; i<n; i++)
cin>>arr[i];
sum=0;
merge1(arr,temp,n);
cout<<sum<<endl;
}
return 0;
}
view raw DCEPC206.cpp hosted with ❤ by GitHub

Spoj(BUREAU) Bureaucracy

0
Posted on by

http://www.spoj.com/problems/BUREAU/

Use an array to store all the law.

Assign arr[i]=1 if ith law is just a declaration.

Assign arr[i]= -j if ith law is to cancel jth law.

After that process the laws from last to first(i.e nth law to 1st law)

if arr[i] = -j then make arr[abs(j)]=0

Finally all valids laws will have value 1 and the rest will have value 0.

Could the valid laws and print it in ascending order.

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <climits>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
#define REP(i,n) for(int i=0; i<n; i++)
#define FOR(i,st,end) for(int i=st;i<end;i++)
#define db(x) cout << (#x) << " = " << x << endl;
#define mp make_pair
#define pb push_back
typedef long long int ll;
vector<ll> arr;
vector<ll> temp;
int nextint(){
char r;
bool start=false,neg=false;
int ret=0;
while(true){
r=getchar();
if((r-'0'<0 || r-'0'>9) && r!='-' && !start){
continue;
}
if((r-'0'<0 || r-'0'>9) && r!='-' && start){
break;
}
if(start)ret*=10;
start=true;
if(r=='-')neg=true;
else ret+=r-'0';
}
if(!neg)
return ret;
else
return -ret;
}
int main(){
int t,n;
int m[100001];
set<int> s;
char str[50];
int num;
t=nextint();
while(t--){
n=nextint();
s.clear();
FOR(i,1,n+1){
scanf("%s",str);
if(str[0]=='d'){
m[i]=1;
}
else{
num=nextint();
m[i]=-num;
}
}
int ans=0;
for(int i=n;i>=1;i--){
if(m[i]<=-1){
m[abs(m[i])]=0;
m[i]=1;
}
if(m[i]==1){
ans++;
s.insert(i);
}
}
printf("%d\n",ans);
for(set<int>:: iterator it=s.begin();it!=s.end();it++)
printf("%d ",*it);
printf("\n");
}
}
view raw BUREAU.cpp hosted with ❤ by GitHub

The Sum Of Two Squares

0
Posted on by

Programming Praxis

If you like to program math puzzles, you probably know about Project Euler; in fact, it was that site that inspired Programming Praxis. We don’t usually do math puzzles here, because Project Euler does them better, but the occasional math puzzle can be entertaining, and lead to some fun programming. Hence, today’s exercise.

Your task is to write a function that, given a number n, finds all pairs of numbers x and y, with x ? y ? 0, such that x + y = n; for instance, 50 = 7 + 1 = 5 + 5, 48612265 = 6972 + 59 = 6971 + 132 = ?, and 999 has no solutions. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Brute force search over all…

View original post 438 more words

Minimum number of swaps required to make an array sorted

0
Posted on by

A swap means removing any element from the array and appending it to the back of the same array. Given an array of integers find the minimum number of swaps needed to sort the array.

[gist https://gist.github.com/vishnujayvel/9593128 ]

 

Example :

A[3]=  3 , 2 , 1

B[3]= 1, 2, 3

i=0 j=0

A[0]!=B[0]

So swap ++ ( Whenever you increment assume that A[i] is removed and appended at the end )

i++

Now i=1 j=0

A[1]!=B[0]

So swap++

i++

Now i=2 j=0

A[2]==B[0]

Now j++

i == n now and hence break the loop

No. of swaps = 2

(Hackerrank) Snakes and Ladders: The Quickest Way Up

0
Posted on by

Found this problem in graph theory section of hackerrank and had so much fun solving it 🙂

             https://www.hackerrank.com/challenges/the-quickest-way-up

Its about finding the least number of rolls of the die in which one can able to reach the destination square (Square Number 100) after having started at the base square (Square Number 1) provided one has the power to get any number (1-6) on the die when one rolls it.

 Solution :

Connect vertex i with i+1,i+2,i+3,i+4,i+5,i+6 ( denoting that from square i you can move to square i+1(when you get 1 when rolling the die),i+2(when you get 2 when rolling the die) and so on)

Similarly consider the starting and ending square of ladder , starting and ending square of the snake as vertices in the graph considered

Apply Floyd warshall algorithm and find minimum distance between square 1 to 100. 

Spoj(NITT8) Dating Rishi

0
Posted on by

http://www.spoj.com/problems/NITT8/

Theres a nlogn solution for this.

Store the (height,position) array as a vector of pairs

Now our aim is to maximize the friend quotient(i,e maximize both terms a and b in the formula given down)

FQ = minimum height of the 2 girls {term a}* absolute diff of the position of the 2 girls{term b}

Sort the vector based on height

 After sorting , considering each height element h of the pair (starting from the maximum. i.e is right side) as the candidate for the minimum height .Let its postion be i.

We have to maximize the difference too.(maximize b). So for each position i ( position where our candidate height h is located) find the value that is most maximum than it and store it in max1.also find the value that is most minimum that it and store it in min1.

You will find out that you have to check only the right side of the position i to find the max1 and min1 since if we go left our height value will be reduced. 

Calculate the F.Q at each iteration and store the maximum F.Q in a variable and update the variable at each stage.

[gist https://gist.github.com/vishnujayvel/8996647]

Spoj(FARIDA) – Princess Farida

0
Posted on by

This is an interesting and easy DP problem. I solved this in less than 5 minutes.(Trust me ! Its that easy)

Let

dp[i] –> maximum coin sum till i monsters

dp[i]=max(arr[i]+solve(i+2),solve(i+1));

Case 1:

if you choose the ith monster’s coins you cannot choose the next so you
move to the i+2th monster.

Case 2:

if you do not choose the ith monster’s coins you still have a chance to choose i+1th monster’s coins.So you move to i+1th monster

[gist https://gist.github.com/anonymous/8433780]