CHEFA - Editorial

editorial
, , ,
1

Problem link:

[contest][1]
[practice][2]

Difficulty :

Cakewalk

Pre-requisites :

None

Problem:

You are given N numbers. Two players alternatively choose numbers. Both players want to maximize the score of numbers picked by them. Chef plays first.
Find out maximum score of the Chef if both players play optimally.

Quick Explanation

Find the sum of alternate numbers starting from the last when the array is sorted in increasing order.

Explanation

Let us first play this game before we proceed to the final algorithm.

We will first play it for even numbers.

Game 1:

Let N = 2 and a1 < a2 be two numbers.

if Chef chooses a1 , then Roma will choose a2 and Chef will be left with total sum a1.
If Chef chooses a2 , then Roma will choose a1 and Chef will be left with total sum a2 which is better than a1. Hence the answer will be a2.

In other words, as Chef plays first, he will pick the maximum of the numbers a1 and a2 (i.e. a2).

Game 2:

Let N = 4 and a1 < a2 < a3 < a4.

Suppose chef chooses any number expect a4, then Roma will select a4 [ as he plays optimally ] . For the remaining two numbers chef takes the maximum one [ as seen above ].
Out of all three possible cases, the maximum sum that Chef can get is a3 + a2.

If Chef chooses a4 , then Roma chooses a3. Chef chooses a2 and Roma chooses a1. Now a4 + a3 > a3 + a2.

Similarly we can prove by induction that in the optimal strategy, both the players should pick the maximum number available for picking.

Final Algorithm

We will sort the array in increasing order and the answer will be the sum of alternate numbers starting from the last.
How ?

Proof:

Proof immediately follows from by the assertion that in the optimal strategy, both the players should pick the maximum number available for picking.

Pseudo Code


	Read(N)
	for i in [1,N]
		Read(A[i])
	Sort(A+1,A+N+1)		//Sort all numbers
	for(int i=N ;i>0;i-=2 )
		Answer = Answer + A[i]
	Return Answer

Subtasks

Subtask 1:
As we need to sort the array. We can apply any O(N2) eg. selection, insertion, bubble sorting algorithm.

Subtask 2:
We need to use O(n log n) sorting algorithm like quick, merge, heap sort.
We can also use O(105) bucket sort Algorithm.

Some Interesting Readings

[Merge Sort in O(N*log N) time][5]
[Bucket Sort Algorithm in O(Max_Number)][6]

Setter and Tester Solutions:

[setter][3]
[tester][4]
[1]: http://www.codechef.com/LTIME16/problems/CHEFA
[2]: http://www.codechef.com/problems/CHEFA
[3]: http://www.codechef.com/download/Solutions/LTIME16/Setter/CHEFA.cpp
[4]: http://www.codechef.com/download/Solutions/LTIME16/Tester/CHEFA.cpp
[5]: Merge Sort Algorithm
[6]: https://www.cs.cmu.edu/~adamchik/15-121/lectures/Sorting%20Algorithms/sorting.html

2

Can anyone explain me why i get wrong answer for my code. I thought my code will work atleast for subtask1. Here is the link to my solution http://www.codechef.com/viewsolution/4911872

3

or,you could just sort !!!

1 Like
4

dude! i did exactly the same thing but I used bubble sort, it gave me wrong answer.
Please explain why?

5

i understood the problem. My question is why did i get wrong answer @asif_mak. Please would you explain me that

6

I have done the same thing. I used Quick sort, but I got a wrong answer. Can anyone tell me my mistake. The link to my solution http://www.codechef.com/viewsolution/4909080

7

Your max should be of long long type instead of int. Hope it helps :slight_smile:

8

My algorithm Does Exactly The Same and Works For Sample input !!! Why the Hell was the result Wrong Answer !! http://www.codechef.com/viewsolution/4913917

 #include<stdio.h>
#include<string.h>
#include<stdlib.h>
void quick_sort(long int arr[],long int low,long int high);
int main()
{
	long int t, *results;
	scanf("%ld",&t);
	results=(long int *)malloc(t* sizeof(long int ));
	for(long int i=0;i<t;i++)
	{
		long int N,*piles,ct=0,max=0;
		scanf("%ld",&N);
		piles =(long int*) malloc(N*sizeof(long int));
		for(long int k=0;k<N;k++)scanf("%ld",&piles[k]);
		quick_sort(piles,0,N-1);
		if(N%2==0)ct=N/2;
		else ct=(N+1)/2;
		for(long int k=N;k>0&&ct>0;k-=2)
		{
			max+=piles[k-1];
			ct--;
		}
		results[i]=max;
	}
	for(long int i=0;i<t;i++)printf("%ld \n",results[i]);
 
}
void quick_sort(long int arr[],long int low,long int high)
{
 long int pivot,j,temp,i;
 if(low<high)
 {
  pivot = low;
  i = low;
  j = high;
 
  while(i<j)
  {
   while((arr[i]<=arr[pivot])&&(i<high))
   {
    i++;
   }
 
   while(arr[j]>arr[pivot])
   {
    j--;
   }
 
   if(i<j)
   { 
    temp=arr[i];
    arr[i]=arr[j];
    arr[j]=temp;
   }
  }
 
  temp=arr[pivot];
  arr[pivot]=arr[j];
  arr[j]=temp;
  quick_sort(arr,low,j-1);
  quick_sort(arr,j+1,high);
 }
}
9

what’s d problem in this?

#include
int main()
{
long int t,i,j;
long int n;
scanf("%ld",&t);
while(t–)
{
long int temp=0,sum=0;
scanf("%ld",&n);
long int a[n];
for(i=0;i<n;i++)
{
scanf("%ld",&a[i]);
}
for(i=0;i<n;i++)
if(a[i]>=1){
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i]<a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}}
for(i=0;i<n;i++)
{
if((i%2)==0)
sum=sum+a[i];
}
printf("%ld",sum);
printf("\n");}
else
break;
}
return 0;
}

10

Yeah I Noticed My Mistake , i Shouldv’e Used Long long int instead of Long int i completed this thing in 5 mins bam … shouldve been obvious !!! :’(

11

GOD!! :frowning: ! thanks

12

Your solution will work for the first subtask.
Since the given constraints are: 1<= A <=10^9 , your soln. results in overflow. Use long long int and it works.
For the next subtask, use merge sort or STL sort(arr,arr+n).

1 Like
13

I really need help regarding this! Can anyone plz help in finding out where the error is? I have tested my code for many test cases and it is turning out to give the correct answer,but when I submitted,it showed WRONG ANSWER
Here’s the link to my solution
http://www.codechef.com/viewsolution/4913538

14

a[i]<=10^9 and u r taking int data type for sum instead of long long …

15

plzz guys help me out…my code worked on dev cpp but it was not accepted in the contest. I have used quick sort technique for sorting. My solution is given in the link http://www.codechef.com/viewsolution/4913844

16

i don’t know why this code is not being accepted,can someone please help me with this…

#include
using namespace std;
#include<stdio.h>
#include
int main()
{ int t;
scanf("%d",&t);
while(t–)
{

  long	int n;
scanf("%ld",&n);
long int arr[n];
for(long int i=0;i<n;i++)
  scanf("%ld",&arr[i]);
sort(arr,arr+n);
reverse(arr,arr+n);
long int sum=0;
for(long int j=0;j<n;j=j+2)
 {
 	
 	  sum=sum+arr[j];
 }
printf("%ld\n",sum);

}

return 0;
}