Re: [algogeeks] Candy_splitting in GCJ

[kumar anurag]

sorry, i mean smallest( not sum of smallest, as smallest means a single
element)
2
5 5
101->5
101->5
--
000  -> xor
=0 hence has a solution
so ans=(total sum -smallest)
total sum=5+5=10
smallest=5 -> as minimun(5,5)=5
so ans=(10-5)=5

2nd ex
3 5 6
011->3
101->3
---xor
110
110->6
--xor
000
=0, so has a solution
so ans=(total sum -smallest)
total sum=3+5+6=14
smallest=5 -> as minimun(3,5,6)=3
so ans=(14-3)=11

Is that clear?


On Mon, May 9, 2011 at 12:04 PM, Nikhil Agarwal
wrote:

> @Anurag  What do you mean by sum of smallest...please explain.In
>
> 2
> 5 5
>
> and
>
> 3
> 3 5 6
>
> On Mon, May 9, 2011 at 12:10 AM, kumar anurag 
> wrote:
>
>> find xor of all elements - if its equal to zeo then Case has solution
>> otherwise NO
>> for finding the soltuion just sort all the elements and find the (sum of
>> all -sum of smallest)..
>>
>>
>>
>> On Sun, May 8, 2011 at 9:50 PM, Kunal Patil  wrote:
>>
>>> Can anybody tell me How to solve candy splitting problem appeared in
>>> Google Code Jam Qualification round?
>>> I know there is solution, if XOR of all elements comes to be zero.
>>> But i wasn't able to proceed from there as I couldn't think of way how to
>>> partition that elements.
>>> (I have read solutions from other contestants but as expected they are
>>> dirty for the one who doesn't know logic behind program)
>>> So plz help...
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>
>>
>> --
>> Kumar Anurag
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> Thanks & Regards
> Nikhil Agarwal
> B.Tech. in Computer Science & Engineering
> National Institute Of Technology, Durgapur,India
> http://tech-nikk.blogspot.com
> http://beta.freshersworld.com/communities/nitd
>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Kumar Anurag

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Candy_splitting in GCJ

[Nikhil Agarwal]

@Anurag  What do you mean by sum of smallest...please explain.In

2
5 5

and

3
3 5 6

On Mon, May 9, 2011 at 12:10 AM, kumar anurag wrote:

> find xor of all elements - if its equal to zeo then Case has solution
> otherwise NO
> for finding the soltuion just sort all the elements and find the (sum of
> all -sum of smallest)..
>
>
>
> On Sun, May 8, 2011 at 9:50 PM, Kunal Patil  wrote:
>
>> Can anybody tell me How to solve candy splitting problem appeared in
>> Google Code Jam Qualification round?
>> I know there is solution, if XOR of all elements comes to be zero.
>> But i wasn't able to proceed from there as I couldn't think of way how to
>> partition that elements.
>> (I have read solutions from other contestants but as expected they are
>> dirty for the one who doesn't know logic behind program)
>> So plz help...
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> Kumar Anurag
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Thanks & Regards
Nikhil Agarwal
B.Tech. in Computer Science & Engineering
National Institute Of Technology, Durgapur,India
http://tech-nikk.blogspot.com
http://beta.freshersworld.com/communities/nitd

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Candy_splitting in GCJ

[abhijith reddy]

Let *E(n)* be the *expected* number of hits needed sort *'n'*
*misplaced*numbers.
The optimal strategy is to hold the numbers that are already in place and
shuffle the remaining.
Now after a shuffle assume that x numbers are still out of place.
Hence we get the following recurrence.

E(n) = Sum[ ((nCx * !x)/n!) * E(x) ] x=0 ... N

Where !x is the number of
de-arrangementsof x.

Hope this helps.


On Mon, May 9, 2011 at 9:51 PM, Rahul Singal wrote:

> abhijith can you explain , how you got E(n) = N ,
>
> Thanks in advance
>
> Rahul Singal
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Candy_splitting in GCJ

[Rahul Singal]

abhijith can you explain , how you got E(n) = N ,

Thanks in advance

Rahul Singal

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Candy_splitting in GCJ

[Anand]

Can guys specify the problem statement.

On Mon, May 9, 2011 at 2:46 AM, abhijith reddy wrote:

> Gorosort is equally easy, but only after you do the math.
> For gorosort you get E(n) = N. Hence ans is just the number of out-of-place
> elements.
>
>
> On Mon, May 9, 2011 at 1:00 PM, kumar anurag wrote:
>
>> GoroSort , i think was tougher, after seeing the number of people solved ,
>> i even didi not read the problem statement...
>>
>> Woking code for Candy Splitting is below, u can check it for both Small
>> and Large tests, it passes all
>>
>> --
>> #include 
>> #include
>> #include
>> #include
>> #include
>> #include
>> using namespace std;
>>
>> int main()
>> {
>> FILE *p=fopen("input.in","r");
>> FILE *p2=fopen("output.txt","w");
>>
>> int cases;
>> //cin>>cases;
>> fscanf(p,"%d",&cases);
>> int cs=0;
>> while(cases--)
>> {
>>
>>   //cin>>N;
>>   int N;
>>   fscanf(p,"%d",&N);
>>
>>   int total_sum=0,xors=0;
>>   int array[N+1];
>>  //main work starts here...
>>   for(int i=0;i>   {
>> fscanf(p,"%d",&array[i]);
>> total_sum+=array[i];
>> xors^=array[i];
>>   }
>>
>>  sort(array,array+N);
>>
>>  if(xors!=0)
>>  fprintf(p2,"Case #%d: NO\n",++cs);
>>  else
>>  fprintf(p2,"Case #%d: %d\n",++cs,total_sum-array[0]);
>>
>>}//while
>>
>>fclose(p);
>>fclose(p2);
>>
>> return 0;
>> }
>>
>> -
>>
>>
>>
>>
>>
>>
>>
>> On Mon, May 9, 2011 at 12:01 PM, Abioy Sun  wrote:
>>
>>> And the last one, GoroSort?
>>>
>>>
>>> 2011/5/9 kumar anurag 
>>>
 find xor of all elements - if its equal to zeo then Case has solution
 otherwise NO
 for finding the soltuion just sort all the elements and find the (sum of
 all -sum of smallest)..



 On Sun, May 8, 2011 at 9:50 PM, Kunal Patil  wrote:

> Can anybody tell me How to solve candy splitting problem appeared in
> Google Code Jam Qualification round?
> I know there is solution, if XOR of all elements comes to be zero.
> But i wasn't able to proceed from there as I couldn't think of way how
> to partition that elements.
> (I have read solutions from other contestants but as expected they are
> dirty for the one who doesn't know logic behind program)
> So plz help...
>
> --
> You received this message because you are subscribed to the Google
> Groups "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



 --
 Kumar Anurag

  --
 You received this message because you are subscribed to the Google
 Groups "Algorithm Geeks" group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.

>>>
>>>  --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>
>>
>> --
>> Kumar Anurag
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Candy_splitting in GCJ

[abhijith reddy]

Gorosort is equally easy, but only after you do the math.
For gorosort you get E(n) = N. Hence ans is just the number of out-of-place
elements.

On Mon, May 9, 2011 at 1:00 PM, kumar anurag wrote:

> GoroSort , i think was tougher, after seeing the number of people solved ,
> i even didi not read the problem statement...
>
> Woking code for Candy Splitting is below, u can check it for both Small and
> Large tests, it passes all
>
> --
> #include 
> #include
> #include
> #include
> #include
> #include
> using namespace std;
>
> int main()
> {
> FILE *p=fopen("input.in","r");
> FILE *p2=fopen("output.txt","w");
>
> int cases;
> //cin>>cases;
> fscanf(p,"%d",&cases);
> int cs=0;
> while(cases--)
> {
>
>   //cin>>N;
>   int N;
>   fscanf(p,"%d",&N);
>
>   int total_sum=0,xors=0;
>   int array[N+1];
>  //main work starts here...
>   for(int i=0;i   {
> fscanf(p,"%d",&array[i]);
> total_sum+=array[i];
> xors^=array[i];
>   }
>
>  sort(array,array+N);
>
>  if(xors!=0)
>  fprintf(p2,"Case #%d: NO\n",++cs);
>  else
>  fprintf(p2,"Case #%d: %d\n",++cs,total_sum-array[0]);
>
>}//while
>
>fclose(p);
>fclose(p2);
>
> return 0;
> }
>
> -
>
>
>
>
>
>
>
> On Mon, May 9, 2011 at 12:01 PM, Abioy Sun  wrote:
>
>> And the last one, GoroSort?
>>
>>
>> 2011/5/9 kumar anurag 
>>
>>> find xor of all elements - if its equal to zeo then Case has solution
>>> otherwise NO
>>> for finding the soltuion just sort all the elements and find the (sum of
>>> all -sum of smallest)..
>>>
>>>
>>>
>>> On Sun, May 8, 2011 at 9:50 PM, Kunal Patil  wrote:
>>>
 Can anybody tell me How to solve candy splitting problem appeared in
 Google Code Jam Qualification round?
 I know there is solution, if XOR of all elements comes to be zero.
 But i wasn't able to proceed from there as I couldn't think of way how
 to partition that elements.
 (I have read solutions from other contestants but as expected they are
 dirty for the one who doesn't know logic behind program)
 So plz help...

 --
 You received this message because you are subscribed to the Google
 Groups "Algorithm Geeks" group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.

>>>
>>>
>>>
>>> --
>>> Kumar Anurag
>>>
>>>  --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> Kumar Anurag
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Candy_splitting in GCJ

[kumar anurag]

GoroSort , i think was tougher, after seeing the number of people solved , i
even didi not read the problem statement...

Woking code for Candy Splitting is below, u can check it for both Small and
Large tests, it passes all

--
#include 
#include
#include
#include
#include
#include
using namespace std;

int main()
{
FILE *p=fopen("input.in","r");
FILE *p2=fopen("output.txt","w");

int cases;
//cin>>cases;
fscanf(p,"%d",&cases);
int cs=0;
while(cases--)
{

  //cin>>N;
  int N;
  fscanf(p,"%d",&N);

  int total_sum=0,xors=0;
  int array[N+1];
 //main work starts here...
  for(int i=0;i wrote:

> And the last one, GoroSort?
>
>
> 2011/5/9 kumar anurag 
>
>> find xor of all elements - if its equal to zeo then Case has solution
>> otherwise NO
>> for finding the soltuion just sort all the elements and find the (sum of
>> all -sum of smallest)..
>>
>>
>>
>> On Sun, May 8, 2011 at 9:50 PM, Kunal Patil  wrote:
>>
>>> Can anybody tell me How to solve candy splitting problem appeared in
>>> Google Code Jam Qualification round?
>>> I know there is solution, if XOR of all elements comes to be zero.
>>> But i wasn't able to proceed from there as I couldn't think of way how to
>>> partition that elements.
>>> (I have read solutions from other contestants but as expected they are
>>> dirty for the one who doesn't know logic behind program)
>>> So plz help...
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>
>>
>> --
>> Kumar Anurag
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Kumar Anurag

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Candy_splitting in GCJ

[Abioy Sun]

And the last one, GoroSort?

2011/5/9 kumar anurag 

> find xor of all elements - if its equal to zeo then Case has solution
> otherwise NO
> for finding the soltuion just sort all the elements and find the (sum of
> all -sum of smallest)..
>
>
>
> On Sun, May 8, 2011 at 9:50 PM, Kunal Patil  wrote:
>
>> Can anybody tell me How to solve candy splitting problem appeared in
>> Google Code Jam Qualification round?
>> I know there is solution, if XOR of all elements comes to be zero.
>> But i wasn't able to proceed from there as I couldn't think of way how to
>> partition that elements.
>> (I have read solutions from other contestants but as expected they are
>> dirty for the one who doesn't know logic behind program)
>> So plz help...
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> Kumar Anurag
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Candy_splitting in GCJ

[kumar anurag]

find xor of all elements - if its equal to zeo then Case has solution
otherwise NO
for finding the soltuion just sort all the elements and find the (sum of all
-sum of smallest)..


On Sun, May 8, 2011 at 9:50 PM, Kunal Patil  wrote:

> Can anybody tell me How to solve candy splitting problem appeared in Google
> Code Jam Qualification round?
> I know there is solution, if XOR of all elements comes to be zero.
> But i wasn't able to proceed from there as I couldn't think of way how to
> partition that elements.
> (I have read solutions from other contestants but as expected they are
> dirty for the one who doesn't know logic behind program)
> So plz help...
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Kumar Anurag

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Candy_splitting in GCJ

[Kunal Patil]

Can anybody tell me How to solve candy splitting problem appeared in Google
Code Jam Qualification round?
I know there is solution, if XOR of all elements comes to be zero.
But i wasn't able to proceed from there as I couldn't think of way how to
partition that elements.
(I have read solutions from other contestants but as expected they are dirty
for the one who doesn't know logic behind program)
So plz help...

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.