Monthly Archives: August 2013

Spoj (MAXSUB) Maximum Subset of Array

0
Posted on by

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

This one though looks like a complicated problem invoiving many cases , can actually be broken down into just 3 cases

1. All numbers are negative
2. At least one number is 0 but there is no number >0
3. There is at least one number >0

In first case, the best possible sum is the largest number. The number of possibilities is the number of times that number appears in the arrray.

In second case, the best possible sum is 0. The number of possibilities is 2^K – 1 where K is the number of zeros in the array.

In the third case, the best possible sum is the sum of all positive numbers in the array. Number of possibilities is 2^K where K is the number of zeros in the array.

#include<iostream>
#include<cstdio>
#include<deque>
#include<algorithm>
#include<math.h>
#define MOD 1000000009
using namespace std;
typedef long long int L;
int main(){
int t;
L n;
scanf("%d",&t);
while(t--){
scanf("%lld",&n);
L arr[51000],sum=0LL;
L cnt=1LL;
L zeroCount=0LL;
int allNegative=1;
for(int i=0;i<n;i++){
scanf("%lld",&arr[i]);
if(arr[i]>0){
sum+=(long long)arr[i];
allNegative=0;
}
else if(arr[i]==0){
allNegative=0;
zeroCount++;
}
}
sort(arr,arr+n);
if(sum==0){//this is to check if there is no +ve num
if(allNegative==1){//if array contains only -ve numbers
sum=arr[n-1];
for(int j=n-2;j>=0;j--){
if(sum==arr[j])
cnt++;
else
break;
}
}else{//if there exist 0's
L num=1;
for(L k=0;k<zeroCount;k++){
num=(L)(num*2)%MOD;// num of subset is 2^zeroCount-1
}//decrementing 1 from 2^zeroCount since we should exclude null set according to the prob
cnt=num-1;
}
}
else{//if the array contains +ve numbers
L num=1;
for(L k=0;k<zeroCount;k++){
num=(L)(num*2)%MOD;// num of subset is 2^zeroCount
}
cnt=num;
}
cnt=cnt%MOD;
printf("%lld %lld\n",sum,cnt);
}
}
view raw maxsub.cpp hosted with ❤ by GitHub

Spoj-Aggressive cows

2
Posted on by

After a long time ,i started solving spoj problems.I came across this interesting problem

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

Here is the approach

lets have a function

f(x) which will return 1 if gap between the cow stalls can be atleast of length x( i.e. all cows can occupy the stalls which are placed x distance  from ajacent stalls)

or return 0 if the gap between the stalls cannot be of length x

iff(x) ==0 then f(y) is also 0 such that y>x . We should code a function which can check

if x is can be allowed distance between each stall.

Our task is to find the largest minimum distance between the stalls.(i.e largest value of the allowed minimum distance)

How to do that ??

Well,You can always place cows such that the minimum distance is 0, while almost always, you cannot achieve minimum distance = N-1. For each number ‘x’ between 0 and N-1, you can either place the cows with minimum distance = ‘x’ or not.
If you list whether you can place the cows with a given distance ‘x’ you have check one by one
0 – Yes
1 – Yes
2 – Yes
.
.
.
x1 – Yes
x2 – No
x2+1 – No
.
.
.
N-1 – No

Our task is to find x1

This can be done using a simple binary search!

f(0)………………………………………………………..f(N-1) will be like

1 1 1 1 1 1 1 0 0 0 0 0 0…………………………..0 0 0

we have to find the last occuring 1

let

start=0

end=n-1

mid =(start+end)/2

if f(mid)=0 then x1 occurs within start and mid

if f(mid)=1 then x1 occurs within mid+1 and end

Search accordingly using divide and conquer strategy

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

There is a temple, whose premises have a garden and a pond. It has 4 idols, each of Ram, Shiv, Vishnu and Durga. The priest plucks x flowers from the garden and places them in the pond. The number of flowers doubles up, and he picks y flowers out of them and goes to offer it to Lord Ram. By the time he reaches to the pond, he finds the remaining flowers also have doubled up in the meantime, so he again picks up y from the pond and goes to Lord Shiv.This process is repeated till all the Gods have y flowers offered to them, such that in the end no flower is left in the pond. Find x and y.

0
Posted on by

Let initial flowers=x
dey get double up that is nw we get 2x
let y flowers be offered to GOD 1
remaining are 2x-y which doubled that is 4x-2y
again y flowers offered to GOD 2
remainin are 4x-3y which doubled again that is 8x-6y
again y flowers offered to GOD 3
remainin are 8x-7y which doubled again that is 16x-14y
again y flowers offered to GOD 4
remainin are 16x-15y

no flowers should b left after
therefore 16x-15y=0
–> x/y=15/16

so x=15 n y =16 atleast

15*2=30,16 offer to god1
14*2=28,16 offer to god2
12*2=24,16 offer to god3
8*2=16,16 offer to god4
0 left

Converting Binary Tree to Doubly Linked List

0
Posted on by

1. If left subtree exists, process the left subtree
…..1.a) Recursively convert the left subtree to DLL.
…..1.b) Then find inorder predecessor of root in left subtree (inorder predecessor is rightmost node in left subtree).
…..1.c) Make inorder predecessor as previous of root and root as next of inorder predecessor.
2. If right subtree exists, process the right subtree (Below 3 steps are similar to left subtree).
…..2.a) Recursively convert the right subtree to DLL.
…..2.b) Then find inorder successor of root in right subtree (inorder successor is leftmost node in right subtree).
…..2.c) Make inorder successor as next of root and root as previous of inorder successor.
3. Find the leftmost node and return it (the leftmost node is always head of converted DLL)

#include<iostream>
#include<queue>
#include<map>
#include<climits>
#include<stack>
#include<stdio.h>
using namespace std;
struct node{
int data;
struct node* left;
struct node* right;
};
struct node* newNode(int data){
struct node* node=new(struct node);
node->data=data;
node->left=node->right=NULL;
return node;
}
struct node* insert(struct node* node,int data){
if(node==NULL)
return (newNode(data));
if(data<=node->data)
node->left=insert(node->left,data);
else
node->right=insert(node->right,data);
return node;
}
node* binToList(node* root){
if(root==NULL)
return root;
if(root->left!=NULL){
node* left;
left=binToList(root->left);
for(;left->right!=NULL;left=left->right);
left->right=root;
root->left=left;
}
if(root->right!=NULL){
node* right;
right=binToList(root->right);
for(;right->left!=NULL;right=right->left);
root->right=right;
right->left=root;
}
return root;
}
node* convertToDLL(node* root){
if(root==NULL)
return root;
root=binToList(root);
for(;root->left!=NULL;root=root->left);
return root;
}
int main(){
struct node* root=NULL;
root=insert(root,4);
root=insert(root,2);
root=insert(root,5);
root=insert(root,1);
root=insert(root,3);
node* list=convertToDLL(root);
for(;list!=NULL;list=list->right)
cout<<list->data<<" ";
}
view raw BSTToDLL.cpp hosted with ❤ by GitHub

Thanks to geeksforgeeks for providing such an awesome approach