TOWIN - Editorial

PROBLEM LINK:

Practice
Div-2 Contest

Author: Tanmay Rustagi

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Greedy, Sorting

PROBLEM:

Given an array and two persons P1 and P2, we need to find the pickup option that P1 should choose (first / second / draw) so as to get more score (which is the sum of the elements they take from the array) such that both of them pick elements alternatively and the one that goes second can take two elements in his/her initial turn.

QUICK EXPLANATION:

Sort the array in descending order, then calculate the sum of elements for both choices (going first and second) and then make the optimal choice for P1.

EXPLANATION:

Since both P1 and P2 want to maximize their score, they will pick the maximum element from the array. For this, sort the array in descending order and find separately the scores of the people who will go first and who will go second.

Also as all the elements are positive, then the second person will always choose to take two elements (even if he/she can take 1 element).

Let S1 be the score of the person who will go first and S2 the score of who will go second.
S1 = sum of elements with index 0, 3, 5, 7, …
S2 = sum of elements with index 1, 2, 4, 6, …

If S1 is greater than S2, then P1 should go “first”.
If S2 is greater than S1, then P1 should go “second”.
If S1 is equal to S2, then the output is “draw”.

SOLUTION:

C++
#include<bits/stdc++.h>
using namespace std;

int main()
{
    // For fast input/output
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    // Input the no. of tests
    int t; cin >> t;
    while(t--)
    {
        // Input the size of array
        int n; cin >> n;

        // Input the array
        vector<int> a(n);
        for(int i=0;i<n;i++) cin >> a[i];

        // Sort the array in descending order.
        sort(a.rbegin(), a.rend());

        // first_sum : Maximum sum obtainable by player who plays first
        // second_sum : Maximum sum obtainable by player who plays second 
        long long int first_sum = 0, second_sum = 0;
        
        first_sum += a[0]; // n >= 1
        for(int i = 3; i < n; i+=2)
        {
            first_sum += a[i];
        }

        if(n>=2) second_sum += a[1];
        if(n>=3) second_sum += a[2];
        for(int i = 4; i < n; i+=2)
        {
            second_sum += a[i];
        }

        // Output the resutls
        if(first_sum > second_sum)
        {
            cout << "first" << endl;
        }
        else if(first_sum == second_sum)
        {
            cout << "draw" << endl;
        }
        else
        {
            cout << "second" << endl;
        }
    }

    return 0;
}
1 Like

can somebody tell where im going wrong

#include<bits/stdc++.h>
#define ll long long
#define PI 3.14
#define pb push_back
#define pop pop_back
#define MOD 1000000007
#define fi first
#define se second
#define mp make_pair
using namespace std;

int main() 
{ 
    ll t,n,v;
    cin>>t;
     
      
   
    while(t--)
    {
        ll  cnt1=0,cnt2=0;
        cin>>n;
       vector<ll>v1;
       
     for(int  i=0;i<n;i++)
       {
           cin>>v;
           v1.pb(v);
       }
       if(n==1)
       {
           cout<<"first"<<endl;
       }
       else  if(n==2)
       {
           if(v1[0]>v1[1])
           {
               cout<<"first"<<endl;
           }
           else
           cout<<"second"<<endl;
       }
       else
       {
           cnt1=v1[0];
           cnt2=v1[1]+v1[2];
       for(int  i=3;i<v1.size();i++)
       {
           if(i%2==1)
           {
              cnt1++; 
           }
           else
           cnt2++;
           
       }
      
       if(cnt1==cnt2)
      {
          cout<<"draw"<<endl;
       }
       else  if(cnt1>cnt2)
        {
          cout<<"first"<<endl;
       }
       else
        {
          cout<<"second"<<endl;
       }
       }
    }
	
	return 0; 
} 

im getting WA

Consider the test input:

1
2
1 1
1 Like

i wrote condition for draw but then also wa

Link, please :slight_smile:

2 Likes

https://www.codechef.com/viewsolution/37127896

1 Like
1
11
2 1 1 5 1 5 1 5 1 5 1 
2 Likes

see i got one mistake that i was doing cnt1++ instead of cnt1=cnt1+v1[i] now i changed it but then also wrong

#include<bits/stdc++.h>
#define ll long long
#define PI 3.14
#define pb push_back
#define pop pop_back
#define MOD 1000000007
#define fi first
#define se second
#define mp make_pair
using namespace std;

int main() 
{ 
    ll t,n,v;
    cin>>t;
     
      
   
    while(t--)
    {
        ll  cnt1=0,cnt2=0;
        cin>>n;
       vector<ll>v1;
       
     for(int  i=0;i<n;i++)
       {
           cin>>v;
           v1.pb(v);
       }
       if(n==1)
       {
           cout<<"first"<<endl;
       }
       else  if(n==2)
       {
           if(v1[0]>v1[1])
           {
               cout<<"first"<<endl;
           }
           else if(v1[1]>v1[0])
           cout<<"second"<<endl;
           else
          {
              cout<<"draw"<<endl;
          }
       }
       else
       {
           cnt1=v1[0];
           cnt2=v1[1]+v1[2];
       for(int  i=3;i<v1.size();i++)
       {
           if(i%2==1)
           {
              cnt1=cnt1+v1[i]; 
           }
           else
           cnt2=cnt2+v1[i];
           
       }
      
       if(cnt1==cnt2)
      {
          cout<<"draw"<<endl;
       }
       else  if(cnt1>cnt2)
        {
          cout<<"first"<<endl;
       }
       else
        {
          cout<<"second"<<endl;
       }
       }
    }
	
	return 0; 
} 

The answer for the test input:

1
11
2 1 1 5 1 5 1 5 1 5 1 

should be second.

3 Likes

how second …here sum of second type=6 first type=22 so first will be answer ?

Read the Editorial :slight_smile:

Hint:

First player gets 13 points; second player gets 15.

3 Likes

i misunderstood the question now got my mistake @ssjgz :grinning:

1 Like

#include <bits/stdc++.h>

using namespace std;

int main()
{
int t,n;
cin>>t;

while(t–)
{ cin>>n;

   int arr[n], even =0,odd=0;
   for(int i=0;i<n;i++)
   {
       cin>>arr[i];
   }
   sort(arr,arr+n,greater<int>());
   odd += arr[0];
   even  +=arr[1]+arr[2];
   if(n>=3)
   {
   for(int i =3;i<n;i++)
   {
       if (i % 2 == 0) 
        even += arr[i]; 
    else
        odd += arr[i]; 
   }
   if(even == odd)
   cout<<"draw"<<endl;
   else if (odd > even)
   cout<<"first"<<endl;
   else
   cout<<"second"<<endl;
   }

}
}

please correct me where am I wrong!

//Remeber choose the turns wisely so that P1 wins(we r on P1s side)

string whoWillWin(int n,int a[]){

int P1=0,P2=0;

if(n==1)

    P1+=a[0];

if(n==2){

    P1+=a[0];

    P2+=a[1];

}

 if(n>=3){

     P1+=a[0];

     P2+=a[1];

     P2+=a[2];

     for(int i=3;i<n;i+=2){

         P1+=a[i];

         if(i>3)

         P2+=a[i-1];

     }

     

 }

if(P1>P2)

    return "first";

else if(P1<P2)

    return "second";

else 

    return "draw";

}

int main(){

int T;

cin>>T;

for(int i=0;i<T;i++){

    int n;

    cin>>n;

    int a[n];

    sort(a,a+n,greater<int>());

for(int j=0;j<n;j++){

    cin>>a[j];

}

  string st=whoWillWin(n,a);

    cout<<st<<endl;

}

return 0;

}

Please Let me know where i am wrong???

//Remeber choose the turns wisely so that P1 wins(we r on P1s side)

string whoWillWin(int n,int a[]){

int P1=0,P2=0;

if(n==1)

    P1+=a[0];

if(n==2){

    P1+=a[0];

    P2+=a[1];

}

 if(n>=3){

     P1+=a[0];

     P2+=a[1];

     P2+=a[2];

     for(int i=3;i<n;i+=2){

         P1+=a[i];

         if(i>3)

         P2+=a[i-1];

     }

     

 }

if(P1>P2)

    return "first";

else if(P1<P2)

    return "second";

else 

    return "draw";

}

int main(){

int T;

cin>>T;

for(int i=0;i<T;i++){

    int n;

    cin>>n;

    int a[n];

    sort(a,a+n,greater<int>());

for(int j=0;j<n;j++){

    cin>>a[j];

}

  string st=whoWillWin(n,a);

    cout<<st<<endl;

}

return 0;

}

Please let me know where i am wrong???

/* package codechef; // don’t place package name! */

import java.util.Scanner;
import java.lang.;
import java.io.
;

/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc=new Scanner(System.in);
int t=sc.nextInt(); //testcase input
int i;
int c1,c2;
while(t>0){
c1=0; c2=0; //chance 1, chance 2
int n=sc.nextInt();
int a[]=new int[n];
for(i=0;i<n;i++){
a[i]=sc.nextInt();
}
c1=c1+a[0];
for(i=3;i<n;i=i+2){
c1=c1+a[i];
}
c2=c2+a[1];
for(i=2;i<n;i=i+2){
c2=c2+a[i];
}
if(c1>c2){
System.out.println(“first”);
}
else if(c1<c2){
System.out.println(“second”);
}
else if(c1==c2){
System.out.println(“draw”);
}
t=t-1;
}
}
}

I am getting a NZEC runtime error, can someone pls tell me what is wrong?

Please either format your code or (better!) link to your submission - the forum software has mangled it and it won’t compile! :slight_smile:

1 Like

Here is the link to my submission
https://www.codechef.com/viewsolution/37374791

And thanks a lot for taking the initiative to check my code.

Consider the test input:

1
1
1
1 Like