Day 28 | Educational Round 135 A, B | C++

I notice that rather than randomly picking up problems from the Codeforces, we can pick contests one by one and upsolve them. So we will be solving the first two problems of Educational Round 135 A and B

Colored Balls: Revisited

Problem Statement -

Solution -

A fun thing to notice here is that sum of all balls is odd.

Let us take one color which has the highest count and call it X and its count as cnt[X]

Now if you don't consider this color but do the same operation with other colors, then you will again be left with one color in end (not including color X we didn't consider)

Now there are two colors left, X (which we didn't consider in operations till now) and Y (let's call another color this).

Notice these points

• The Sum of all colors was odd, and we removed them in pairs, thus the sum of the remaining ball of the remaining two colors must be odd as well. In other words, cnt[X] + cnt[Y] is odd.

• cnt[Y] <= cnt[X], because cnt[X] was the maximum value since start

• if cnt[Y] = cnt[X], then cnt[X] + cnt[Y] will be even so this is not possible

• cnt[Y] < cnt[X], hence if we make pair of Y with X, in the end X will be left

Thus X will be the answer. So any color with maximum frequency is the answer.

You can implement it like this

#include<iostream>
using namespace std;

int main(){
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        int max_val = 0, max_index = 0;
        for(int i = 1; i <= n; i++){
            int x;
            cin >> x;
            if(x > max_val){
                max_val = x;
                max_index = i;
            }
        }
        cout << max_index << "\n";
    }
}

You can implement it more quickly using STL

#include <bits/stdc++.h>
using namespace std;
 
void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int &i: a)cin >> i;
    cout << max_element(a.begin(), a.end()) - a.begin() + 1 << "\n"; 
}
 
int main(){
	int t ;
	cin >> t;
	while(t--)solve();
}

Best Permutation

Problem Statement -

Solution -

This is an interesting problem as well. I don't know I find every problem interesting, you can say that I have a problem LOL.

In this problem, if we are including N in the end, then x before it cannot be >= X, otherwise the value will become 0.

Therefore max value before including N is N-1, and thus including it after, it will become N*2 - 1.

So, we last two values will be N-1, and N, and before it, I have to make it 0, otherwise it can exceed or equal N if even 1 is added.

One practice to make x = 0 at some i, is to place a bigger value at i-1

So if we place like this

. . . N-2 , N - 3, N-1, N [Last two are fixed]

then every number at the even position will be 0

Like

P - 2 , 1, 4, 3, . . . , N - 2, N - 3, N - 1, N

X - 2, 0 , 4, 0, . . . , N - 2, 0, N - 1, N*2 - 1

But this is only applicable to Even size of permutations

If you notice a property that in 3 consequtive number a,b, and c, a + b > c So if we order last 5 in such

. . . {If last 5 are after, the before this block there are even} N - 4, N - 3, N - 2, N - 1, N

Like

P - 2 , 1, 4, 3, . . . , N- 4, N - 3, N - 2, N - 1, N

X - 2, 0 , 4, 0, . . . , N - 4, 2*N - 7, 0, N - 1, N*2 - 1

Thus you can implement it like -

void solve(){
    int n;
    cin >> n;
    vector<int> ans(n);
    iota(ans.begin(),ans.end(),1);
    if(n % 2 == 0){
        // i = n-3 because last index is n-1
        for(int i = n-3; i >= 0; i-=2){
            swap(ans[i],ans[i-1]);
        }
    }else{
        for(int i = n-6; i >= 0; i-=2){
            swap(ans[i],ans[i-1]);
        }
    }
    for(int i: ans)cout << i << " ";
    cout << "\n";
}

Please like and share my posts if they are helpful.