TWINGFT - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Daanish Mahajan
Tester: Riley Borgard
Editorialist: Aman Dwivedi

DIFFICULTY

Cakewalk

PREREQUISITES

None

PROBLEM

Given an array of size, N determine the maximum total cost sum that you can achieve by alternately choosing K costliest gifts where 2 \times K+1\leq N.The one starting second gets to keep one more gift.

QUICK EXPLANATION

Choosing maximum value gifts results in maximum total cost sum. Let the maximum total cost sum by you and your twin is sum1 and sum2 respectively. Now, maximum of sum1 and sum2 is answer.

EXPLANATION

  • Now in order to calculate sum1 and sum2, we need to choose gifts in such a way that it maximizes the total cost of gifts.
  • In each turn choosing the costliest gift from the array and adding it, results in the maximum total cost of gifts.
  • So we sort the array in decreasing order of their cost and alternately choose elements starting from the beginning of the array and add it to their respective sums.

Let’s take an example to understand it better.

  • a= [4,2,1,3,5,6], K=2 and sum1=0,sum2=0

  • Sort the array, a = [6,5,4,3,2,1]

  • Let’s suppose you start first.

  • It’s your turn and you choose the costliest gift i.e a[0] =6 and sum1=6

  • It’s your twin’s turn and he chooses the costliest gift i.e a[1]=5 and sum2=5

  • It’s your turn and you choose the costliest gift i.e a[2]=4 and sum1=6+4=10

  • It’s your twin’s turn and he choose the costliest gift i.e a[3]=3 and sum2=5+3=8

  • Since your twin started second, therefore he gets choose one more gift and choose the costliest gift i.e a[4]=2 and sum2=8+2=10.

  • Now if sum2 is greater than sum1, then you would want to start second and vice-versa. Therefore, the maximum of sum1 and sum2 is the answer.

TIME COMPLEXITY

The time complexity is O(N*logN) per test case.

SOLUTIONS

Setter's Solution
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
 
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    ll TC;
    cin >> TC;
    while (TC--)
    {
        ll n, k; cin >> n >> k;
        vector<ll> arr(n);
        for (auto &x : arr) cin >> x;
        ll s1 = 0, s2 = 0;
        sort(arr.begin(), arr.end());
        while (k--) {
            s1 += arr.back(); arr.pop_back();
            s2 += arr.back(); arr.pop_back();
        }
        s2 += arr.back();
        cout << max(s1, s2) << '\n';
    }
 
 
    return 0;
}
Tester's Solution
#include <bits/stdc++.h>
 
#define ll long long
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define pii pair<int, int>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
 
void solve() {
    int n, k;
    cin >> n >> k;
    vector<ll> a(n);
    for(auto &x : a) cin >> x;
    sort(all(a), greater<>());
    ll A = 0, B = 0;
    rep(i, 0, 2 * k) {
        (i % 2 == 0 ? A : B) += a[i];
    }
    B += a[2 * k];
    cout << max(A, B) << '\n';
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int te;
    cin >> te;
    while(te--) solve();
}
Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
 
#define int long long int
 
void solve()
{
  int n, k;
  cin >> n >> k;
  int a[n];
  for (int i = 0; i < n; i++)
    cin >> a[i];
 
  sort(a, a + n);
  int sum1 = 0, sum2 = 0;
  int i = n - 1;
  while (k--)
  {
    sum1 += a[i];
    sum2 += a[i - 1];
    i -= 2;
  }
  sum2 += a[i];
  cout << max(sum1, sum2) << endl;
}
int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
 
  int t;
  cin >> t;
 
  while (t--)
    solve();
 
  return 0;
}
5 Likes

Hey,
I have a preety simple code for this ,
Can anyone please suggest me what am I doing wrong here.
Link to my code
DONT IGNORE PLEASE, I BELEIVE YOU CAN HELP ME :slight_smile:

bro ur code is wrong because u considered all vlaues till N

lets say N=8 and k=2

array : 8 7 6 5 4 3 2 1

max 1 =8+6
max 2= 7+5+4

ans = max(max 1, max 2)= 16

but what u did u considered till N , so u didnt consider k ,

no of steps will be 2*k+1 not exactly N
@sam_khanna

2 Likes

@longtimenoshe2 can u please check this code what’s wrong.I am getting all the correct output but still it fails to some cases.

#include <bits/stdc++.h>

using namespace std;

#define fori(i, n) for (int i = 0; i < n; i++)
#define ll long long

int main()
{

#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif //

int t;
std::cin >> t;
while (t–)
{
int n, c;
std::cin >> n >> c;
vector v;
for (size_t i = 0; i < n; i++)
{
int data;
std::cin >> data;
v.push_back(data);
}
sort(v.begin(), v.end(), greater());

int sum1 = 0;
int sum2 = 0;
int chance = 0;

for (size_t i = 0; i < v.size() && chance < c; i += 2)
{
  sum1 += v[i];
  chance++;
}
chance = 0;

for (size_t i = 1; i < v.size(); i += 2)
{
  sum2 += v[i];
  chance++;
  if (chance == c && i < v.size() - 1)
  {
    sum2 += v[i + 1];
    break;
  }
}

std::cout << max(sum1, sum2) << std::endl;

}

return 0;
}

can u format the code or the paste the code here p.ip.fi/
or give ur submission link

Ya sure, Here is the link

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

meanwhile , see my implementation preety easy
https://www.codechef.com/viewsolution/47280450

ur code logic was right, but u got WA because of int overflow
// the max value of A[i] is 1e9 and multiplied by n i.e 10^3 in worst case
becomes 1e12 so u getting WA in those test cases.
Always use long long , i replaced ur int sum1 and int sum2 by ll and got AC
https://www.codechef.com/viewsolution/47280796

1 Like

Oh! Thanks a lot for the help sir. I wasted my 1 hour in the contest to debug this code. :sweat_smile:

2 Likes

cool no issues!
Just keep in mind : don’t take risk of using int unless there are memory limitations

okay! :smiley:

i guess the problem is with that the type of sum ,it would be long long int and not int , that’s why its showing wrong ans

Hey can anyone help me with my code. I guess it’s correct but still I’m getting error. I am not able to find error

#include
#include
using namespace std;
#define ll long long
bool compare(ll a ,ll b)
{
return a>b;

}
int main()
{
int t;
cin>>t;
while(t–)
{
ll n,k, turn1=0 , turn2 = 0,i=0;
cin>>n>>k;
ll ar[n];

    for(int i=0;i<n;i++)
    {
        cin>>ar[i];
    }
    
    sort(ar , ar+n , compare);
    
    
    for(i=0;i<n-1;i++)
    {
        if(i == 2*k + 1)
        break;
        
        turn1 += ar[i];
        i++;
        
        turn2 += ar[i];
        
        
        
    }
    turn2 = turn2 + ar[2*k];
   cout<<max(turn1,turn2)<<endl;
    
    
   
}

}

Hey ! can someone please help me to find the error in this. It would be of great help.
I submitted it but got WA during the contest.

Here is the code …
https://www.codechef.com/viewsolution/47222891

@longtimenoshe2 Thankyou sir

1 Like

Testcase
5 1
6 4 3 1 2
O/p
7

Can someone explain for this/it’s wrong

Plz tell me whats wrong in my code
https://www.codechef.com/viewplaintext/47270977

PLLZZ tell me what’s wrong with my code.

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

int main() {
// your code goes here
int t;
cin>>t;
while(t–){
int n,k;
cin>>n>>k;
int arr[n];
for(int i=0;i<n;i++) cin>>arr[i];
sort(arr,arr+n);
int j=1;
int i=n-1;
int c1=0;
int c2=arr[n-(2k)-1];
while(j<=2
k){
if(j%2==1) c1+=arr[i];
else c2+=arr[i];
++j;
–i;
}
cout<<max(c1,c2)<<endl;
}
return 0;
}

PLLZZ reply to the earliest

hello, will you please look into my code. I’m getting wrong answer.

code link

https://www.codechef.com/viewsolution/47160002
why this give WA
`
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define ull unsigned long long int
#define pb push_back

#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define MOD 1000000007;

void solve()
{
int n,k;
cin>>n>>k;
vector arr(n,0);
for (int i = 0; i < n; i++)
{
cin>>arr[i];
}
sort(arr.rbegin(),arr.rend());
int a=0,b=0;
for (int i = 1; i <2k+1 ; i++)
{
if(i==2
k)
{
b+=arr[i-1];
b+=arr[i];

    }
    else if(i%2!=0)
    {
        a+=arr[i-1];
    }
    else 
    {
        b+=arr[i-1];
    }

}
cout<<max(a,b)<<endl;

}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// #ifndef yash
// freopen(“input.txt”,“r”,stdin);
// freopen(“output.txt”,“w”,stdout);
// #endif // !yash
int test;

cin>>test;
while (test--)
{
    solve();
}
return 0;

}

`