First Comment

Ok.

Why isn't unrated participation allowed this time?

No score distribution?

I mean generally, all div2's have score distribution, right?

upvote?

These divs are my favorite keep going

Goodluck to everyone!

God, please don't make me fumble this one and let me become specialist for the first time.

Good luck!

I am curious why the exact number of problems is not given in the announcement? it's always sth like x or (x+1) problems.

Damnnnnn I was so close to solving D in time. I can't figure out what exactly is wrong with my implementation.. failed on test 2.

UPD: figured out what was wrong. needed to separate the left-hand answers and right-hand answers and add them up to avoid extraneous previously seen segments' left bounds.

I don't usually like problems in educational rounds, but this time problems were very good and the problemset was balanced, except for the difficulty jump in D->E.

As a participant, I can only solve A and B. Anyway how to solve C?

Thank you very much guys for the round.

did anyone do C using segment tree and binary search ?

How to Solve C ?

Can somebody please share their approach for solving problem C, I tried a lot but couldn't solve it...

Can anyone pls tell me what's wrong with my approach for prob B

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second

int n, a[1000005];
map<int,int>mp;
int ceil1(int x1)
{
    return (x1+1)/2;
}
void solve()
{
    set<int>marble;
    for(int i=1; i<=n; i+=1) marble.insert(a[i]);
    if(marble.size()>=ceil1(n))
    {
        int conquer=0;
        for(int i=1; i<=n; i+=1)
        {
            if(conquer>=ceil1(n)) break;
            if(mp[a[i]]==1) conquer++;
            if(conquer>=ceil1(n)) break;
        }
        cout<<ceil1(n)+conquer<<'\n';
    }
    else
    {
        int score=marble.size(), conquer=0, cnt=score;
        multiset<int>ms;
        for(auto i:mp)
        {
            ms.insert(i.se);
        }
        while(cnt<=ceil1(n) && ms.size())
        {
            conquer++;
            cnt+=*ms.begin()-1;
            auto z=ms.begin();
            ms.erase(z);
        }
        if(cnt<=ceil1(n)-score)
        {
            cout<<score+conquer<<'\n';
        }
        else
        {
            cout<<score+conquer-1<<'\n';
        }
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
    int test=1;
    cin>>test;
    while(test--)
    {
        mp.clear();
        cin>>n;
        for(int i=1; i<=n; i+=1) cin>>a[i];
        for(int i=1; i<=n; i+=1) mp[a[i]]++;
        solve();
    }
}

AAAAAAAAHHHHHHH Why o why is problem F so much easier than E? I didnt look at the scoreboard, and hence spent 3/4 of the contest implementing E instead of F :(. Anyway, nice problems (especially A,B,C)

Why is $$$n \leq 1000$$$ in B?

can anyone share their approach to C in a detailed way?

What is the logic behind unrated participants still being official for educational rounds?

I really like E (although I haven't solved it). It's the kind of problem you can solve step by step.

C — super good.
D — boring in general (good for edu)

What is the logic behind unrated participants being counted as official in educational rounds?

so hard for me. Just A and B are solved. Hope next time better.

omg i couldn't solve C! for 1:45 hours!

Who put problem E at this position?

I have an approach to C, but its failing (Wrong answer) in the test case 2 and I don't really know why. Can someone help with this one point out some flaw in this one.

Approach:

It would be best if we look at the difference of scores of alice and bob as that's what only matters. Let's call it score.

Initialize an array, arr. Then, we start from end of the string and 1. if we find a 0, then keep traversing towards the left as long as the count of 1s and 0s is not equal in this group. When a block of equal 0s and 1s found, then insert a 0 in arr(signifying that the contribution of this group is 0). 2. if we find a 1, then make it a separate group and then insert a 1 in arr(signifying that the contribution of this group is > 0).

So, we try to make groups such that each group has an equal number of 0s and 1s (so this block doesn't contribute to the score difference), and only the group of single 1s contribute to the score.

Since we inserted in arr in reverse order, we reverse the arr and then assign the indices from the start and find the score. I think this would be the maximum possible score.

For example: (taking something other than sample testcases) s = "100110101101"

then final array(after reversing) looks like (0 1 0 0 1 0 1).

Now, I can loop over it and find the score as (group number * contribution).

So, score = 0 * 0 + 1 * 1 + 2 * 0 + 3 * 0 + 4 * 1 + 5 * 0 + 6 * 1 = 11

If this score < k, then -1 is ans. Otherwise, we can try to merge groups from the right. I used binary search here, to find a suffix till after which we merge all the groups into single one and then calculate the score of array and compare it with k to minimize group count.

Is this line of thinking correct or is there a mistake in here?

Problem C was too tough. Edu div 2 is more harder than div 2. Edu Div 2>>>>>>>>>>>>>>>>>> Div 2

Why it is TLE?

https://codeforces.net/contest/2042/submission/294472150

Can anyone please explain logic for the problem C

A: sort {a[i]} and find the maximum suffix sum with value at most k. The answer is k minus this sum.

B: Let k1 be the count of colors with only 1 occurence, and k2 be the count of colors with at least 2 occurence. For each time Alice pick ball from k1 she will gain 2 points, and when she pick from k2 she will gain 1 point. Also Alice cannot get 2 potins from k2, because Bob can take the ball with same color after Alice pick the first ball from that color. So the optimal move for Alice and Bob is take balls from k1 first, then Alice will take a ball for all colors in k2. Therefore the answer is k2+2*ceil(k1/2).

C: For each 1<=i<n, if we separate the array at the "gap" between i and i+1, the score of fishes on [i+1, n] will increase by 1, so the value of (Bob's score — Alice's score) will increase by (number of '1' in [i+1, n] — number of '0' in [i+1, n]), so we can calculate the change of balance for 1<=i<n by suffix sums, sort them and pick from the greatest to smallest.

D: Let's find the number of strongly recommended tracks with number > r[i] for each 1<=i<=n first. So we can sort users by l[i], and for each i we need to find the minimum value of r[j], for all j such that l[j]<=l[i] and r[j]>=r[i]. Here the first condition is satisfied from the non-decreasing order of l[i], then we need to find the minimum r[j] by lower_bound on std::multiset. Then we need to find the number of strongly recommended tracks with number < r[i], we can do this by {l[i], r[i]} := {-r[i], -l[i]} and do the same steps as previous case.

F: We can solve the problem by segment tree. The merge function of segment tree is something like this:

info merger(const info& L,const info& R){
	if(L.sum<=-inf) return R;
	if(R.sum<=-inf) return L;
	info I;
	I.sum=L.sum+R.sum;
	I.La=max(L.La,L.sum+R.La);
	I.Ra=max(R.Ra,R.sum+L.Ra);
	I.ans=max(max(L.ans,R.ans),L.Ra+R.La);
	I.LD=max(max(L.LD,L.sum+R.LD),max(L.La+R.ans,L.LRD+R.La));
	I.RD=max(max(R.RD,R.sum+L.RD),max(R.Ra+L.ans,R.LRD+L.Ra));
	I.LRD=max(L.La+R.Ra,max(L.LRD+R.sum,R.LRD+L.sum));
	I.D=max(L.ans+R.ans,max(L.RD+R.La,R.LD+L.Ra));
	I.D=max(I.D,max(L.D,R.D));
	return I;
}

Where: (Assuming the range represented by I is [x, y], Denoting sum(x, y) = a[x]+a[x+1]+...+a[y-1]+a[y])

• I.sum means sum(x, y)

• I.La means maximum value of (sum(x, j)+b[j]) for x<=j<=y

• I.Ra means maximum value of (b[j]+sum(j, y)) for x<=j<=y

• I.ans means maximum value of (sum(j, k)+b[j]+b[k]) for x<=j<=k<=y

• I.D means the needed answer for the range (which is maximum value of (sum(j, k) + b[j]+b[k] + sum(p, q) + b[p]+b[q]) for x<=j<=k<p<=q<=y)

• I.LD means maximum value of (sum(x, j)+b[j] + sum(k, p)+b[k]+b[p]) for x<=j<k<=p<=y

• I.RD means maximum value of (sum(j, k)+b[j]+b[k] + b[p]+sum(p, y)) for x<=j<=k<p<=y

• I.LRD means maximum value of (sum(x, j)+b[j] + b[k]+sum(k, y)) for x<=j<k<=y

The merge function is similar as what we do when finding maximum subarray sum by divide & conquer.

Why is problem C tagged geometry?

Why is problem C tagged geometry?

why sorting all the values of the suffix in descending order works?

Why the suffix works in C?

B. Game with Colored Marbles

for above question i have write code in c++ now i am using same approach to solve question in both the code with difference of taking input and counting at incrementing at the same loop in code with addition checking the size of map. WHICH I SUBMITTED DURING CONTEST WHICH PASSED GIVEN TEST CASES AND DOES NOT PASSED HIDDEN TEST CASES

after contest i use same code but counting frequency using another loop which passed all test cases so can someone explain me why this happend i asked chapgpt and got reply both code will generate same output. but why my very first submission of code did not worked

code 1: -

~~~~~~~~~~~~~~~~

include

include <bits/stdc++.h>

using namespace std;

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

while(t--){

    int n;
    cin >> n;

    vector<int> marb(n);
    map<int,int> mp;
    for(int i = 0; i < n; i++){
        cin >> marb[i];
        mp[marb[i]]++;
    }

    if(mp.size() == 1){
        cout << 1 << endl;
        continue;
    }else{
        int uni = 0, nonuni = 0;
        for(auto it : mp){
            if(it.second == 1){
                uni++;
            }else{
                nonuni++;
            }
        }

        int mxsc = 0;
        mxsc += (uni & 1 == 1 ? (uni/2 + 1)*2 : (uni/2)*2 ); 
        // cout << (uni/2 + 1)*2 << endl;
        mxsc += nonuni;

        cout << mxsc << endl;

    }

    // vector<pair<int,int>> vec(mp.begin(), mp.end());

    // sort(vec.begin(), vec.end(), [](const pair<int, int> &a, const pair<int, int> &b) {
    //     return a.second < b.second;
    // });

    // mp.clear();
    // for (const auto &pair : vec) {
    //     mp.insert(pair);
    // }



}

return 0;

} ~~~~~~~~~~~

CODE 2 :-

~~~~~~~~~~~~~~~

include

include <bits/stdc++.h>

using namespace std;

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

while(t--){

    int n;
    cin >> n;

    vector<int> marb(n);
    for(int i = 0; i < n; i++){
        cin >> marb[i];
    }


    map<int,int> mp;
    for(int i = 0; i < n; i++){
        mp[marb[i]]++;
    }


    int uni = 0, nonuni = 0;
    for(auto it : mp){
        if(it.second == 1){
            uni++;
        }else{
            nonuni++;
        }
    }

    int mxsc = 0;
    mxsc += (uni & 1 == 1 ? (uni/2 + 1)*2 : (uni/2)*2);

    mxsc += nonuni;    

    cout << mxsc << endl;

}


return 0;

} ~~~~~~~~~~~~~~

Did anyone solve C using binary search?

What's the hack for C?

Normal round. But C is very easy and D has bad hard realization for me. I think, in Edu Rounds C and D normal but for div2 it is not good.

Bro, really?

why I wrong awnser in C in test 2? see the checker, it may be because I cout<<-1, but it is feasible. https://codeforces.net/contest/2042/submission/294520912

#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(2e5)+10;
ll n,T,k;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while (T--) {
		cin>>n>>k;
		vector<ll> A(n+10,0);
		for(int i=1;i<=n;++i){
			char a;
			cin>>a;
			A[i]=a-'0';
		}
		// 0 indicates captured by Alice, 1 indicates captured by Bob
		// How to divide such that Bob's score is at least `k` more than Alice's score while minimizing the number of groups?
		vector<ll> Cnt1(n+10,0);
		vector<ll> Cnt0(n+10,0);
		for(int i=n;i>=1;--i){
			if(A[i]){
				Cnt1[i]=Cnt1[i+1]+1;
				Cnt0[i]=Cnt0[i+1];
			}else{
				Cnt0[i]=Cnt0[i+1]+1;
				Cnt1[i]=Cnt1[i+1];
			}
		}
		ll upS=n+1,curBob=0,curAli=0,cnt1Up=0,cnt0Up=0,cntSplit=1;
		vector<ll> C1,C0;	// Records the number of 1s or 0s in different segments
		for(int i=n;i>=2;--i){
			if(Cnt1[i]-Cnt1[upS]>Cnt0[i]-Cnt0[upS]){
				// Add all previously counted 1s again
				curBob+=Cnt1[i]-Cnt1[upS]+cnt1Up;	
				cnt1Up+=Cnt1[i]-Cnt1[upS];
				C1.push_back(cnt1Up);
				curAli+=Cnt0[i]-Cnt0[upS]+cnt0Up;
				cnt0Up+=Cnt0[i]-Cnt0[upS];
				C0.push_back(cnt0Up);
				cntSplit+=1;
				upS=i;
			}
		}
		if(curBob-curAli<k){
			cout<<-1<<endl;
			continue;
		}
		for(int i=0;i<C1.size();++i){
			curBob-=C1[i];
			curAli-=C0[i];
			if(curBob-curAli==k){
				cout<<cntSplit-i-1<<endl;
				break;
			}else if(curBob-curAli<k){
				cout<<cntSplit-i<<endl;
				break;
			}
		}
	}
	return 0;
}

Can someone share idea of question C ?

why unrated

.

Why I didn't recive any elo yet?

Thanks for the round, I finally reached CM after a year. Hope you get there as well :) P/s: I just saw a post of an expert frustrated with FST on problem C in the round. Honestly, if you didn't see that the calculations could get a value of > 2^32 then yeah stay at expert and train more.

(written) editorial waiting room, hopefully it gets updated soon

(Div-2(D)) What is the reason for the tle ?

void solve(){
    int n;
    cin>>n;

    vector<array<int, 2>> v(n);
    for(auto &curr: v)
        for(auto &it: curr)
            cin>>it;

    vector<array<int, 3>> a(n);
    map<array<int, 2>, int> m;
    for(int i=0; i<n; ++i)
        a[i][0] = v[i][0], a[i][1] = v[i][1], a[i][2] = i, ++m[v[i]];

    vector<int> ans(n);
    sort(a.begin(), a.end(), [&](const array<int, 3> &a1, const array<int, 3> &a2){
        if(a1[0] < a2[0]) return true;
        if(a1[0] > a2[0]) return false;
        return a1[1] >= a2[1];
    });

    set<int> s;
    s.insert(a[0][1]);
    for(int i=1; i<n; ++i){
        int currS = a[i][0], currE = a[i][1], idx = a[i][2];

        auto it = s.lower_bound(currE);
        if(it == s.end()){
            s.insert(currE);
            continue;
        }

        ans[idx] += (*it - currE);
        s.insert(currE);
    }

    sort(a.begin(), a.end(), [&](const array<int, 3> &a1, const array<int, 3> &a2){
        if(a1[1] < a2[1]) return false;
        if(a1[1] > a2[1]) return true;
        return a1[0] <= a2[0];
    });

    s.clear();
    s.insert(a[0][0]);
    for(int i=1; i<n; ++i){
        int currS = a[i][0], currE = a[i][1], idx = a[i][2];

        auto it = s.upper_bound(currS);
        if(it == s.begin()){
            s.insert(currS);
            continue;
        }
        --it;

        ans[idx] += (currS - *it);
        s.insert(currS);
    }

    for(int i=0; i<n; ++i)
        if(m[v[i]] > 1)
            ans[i] = 0;

    for(int i=0; i<n; ++i)
        cout<<ans[i]<<"\n";
}

I am a new user of Codeforces and was not aware of all the rules and potential issues. I believe this situation might have occurred because I used ideone in public mode, not realizing that someone could copy my code from there. I apologize for my mistake and assure you that I will be more careful in the future to prevent such incidents.

Please give me a chance and do not take any strict action. I am committed to following the rules and maintaining the integrity of the competition.

xD