awoo's blog

Educational Codeforces Round 172 [Rated for Div. 2]
By awoo, history, 6 weeks ago, translation, In English

Neapolis University Pafos

Hello Codeforces!

The series of Educational Rounds continues thanks to the support of the Neapolis University Pafos. They offer a BSc in Computer Science and AI with JetBrains Scholarships. Gain cutting-edge skills in AI and machine learning, preparing you for high-demand tech careers. Curious? Check out the CSAI curriculum now. Limited scholarships available — don't miss your chance to study in Europe for free!

On Dec/02/2024 17:35 (Moscow time) Educational Codeforces Round 172 (Rated for Div. 2) will start.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest, you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also, huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

UPD: Editorial is out

  • Vote: I like it
  • +168
  • Vote: I do not like it

»
6 weeks ago, # |
← Rev. 5   Vote: I like it -94 Vote: I do not like it

Ok.

→ Reply
»
6 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

Why isn't unrated participation allowed this time?

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

No score distribution?

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

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Educational rounds don’t have scoring distributions since they are held on ICPC rules(ranked by # of problems solved then penalty) unlike regular div 2 rounds.

    → Reply
»
6 weeks ago, # |
  Vote: I like it -29 Vote: I do not like it

upvote?

→ Reply
»
6 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck!

→ Reply
»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    How does that affect you lmao.

    Seriously now, I think that it is because educational round are only prepared by 4 people and are held quite often so it is quite hard to make 6 or 7 problems before the round.

    → Reply
»
6 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    What do you mean by "balanced"? :)
    Problems A and B are so easy that there are ~10k submissions each.
    Problems C with < 2500 seems to be unusually hard.

    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Idk why C doesn't have more solves, its difficulty felt natural to me even though it took me a lot of time to solve.

      → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      C was i think 1700+

      → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Iterate from 0 to n — 1. Let's say you are at some index $$$i$$$, assume that you have already divided the suffix of numbers after $$$i$$$, if you decide to merge $$$i$$$ with the segment right of it, you will add $$$a - b$$$ to the difference between Alice and Bob(I will call this number sum), where $$$a$$$ is the number of 0 in the suffix, and $$$b$$$ is number of 1. Sort all $$$a - b$$$ and add them and decrease the number of segments while it is optimal. In the beginning divide the array into $$$n$$$ segments and then you reduce them.

    Implementation: 294433631

    → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you very much guys for the round.

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

did anyone do C using segment tree and binary search ?

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to Solve C ?

→ Reply
  • »
    »
    6 weeks ago, # ^ |
    ← Rev. 3   Vote: I like it +4 Vote: I do not like it
    1. Form an array consists of 1 and -1 from the input string
    2. Suppose there are $$$m$$$ groups, the $$$i^{th}$$$ group should be from $$$[l_i, l_{i+1})$$$, where $$$l_0 = 0, l_m = n$$$
    3. You could represent the score difference ($$$ps$$$ means prefix sum)
    Equations
    1. sort suffix sum descendingly, add to the sum one by one and see if it reaches $$$k$$$
    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can be much better if you explain why sort the suffix sum descend and sum them 1 by 1 will work.

      Anyway thanks for the clear hint, because the proof/observation why it works is very value-able.

      → Reply
      • »
        »
        »
        »
        6 weeks ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        As you can see in this image, the portion between blue segment and black segment is the first partition, between black and red is the second partition, between red and green is the third partition and the last green is the fourth partition. According the problem's solution, 1 * d1 + 2 * d2 + 3 * d3 + 4 * d4 >= k. where d1 is the difference between number of ones and zeroes in the first partition. Now, if you sum all of the portions highlighted in four colors, this will give us that left hand side of the equation, no matter in what order we take it. Hence, it's greedy to sort the differences in descending order and greedily pick from large to small.

        → Reply
»
6 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

My code
→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Explain the main idea?
    What is the logic of the main if-else in the solve function?

    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
      ← Rev. 4   Vote: I like it +3 Vote: I do not like it

      My logic is that I will take each color of the marble once. Then if number of the color >= number of Alice's turn, the ans will be number of the color + number of marble that appears only once. Else I will sort the number of each kind of marble ascending and just simulate the game, and see how many color can Alice conquer. (Alice will take each number of each kind of marble -1 until she cant for example 1 1 1 1 1 1 3 3 4 alice will take 1,3,4 then alice have 5 turn left and she will take 3,1). I know i explain kind of stupid ToT but hope you understand what I'm saying.

      → Reply
      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        consider marbles 1 2 3 3, if Alice pick 1 then Bob can pick 2 to prevent Alice to take each color once.

        → Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    First, it is too complicated for Div2B, and it is hard to see the logic. Second, for test below, your code gives 8, though 7 is the answer.

    Test Case
    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      oh tks so much bro

      → Reply
      • »
        »
        »
        »
        6 weeks ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Mfw when i realize "Alice wants to maximize her score at the end of the game. Bob wants to minimize it." actually means Bob wants to minimize Alice score not Bob wants to minimize his score after losing 100 rating ToT.

        → Reply
        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I also read B wrongly at first. I, for no reason (maybe because of urge of solving B fast), interpreted as one point for taking some character (same as in the problem), and second point for the one who takes last character. Then basically trying to understand what's wrong with output. Hopefully, it did not require much changes to correct from my approach.

          → Reply
»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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)

→ Reply
»
6 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Has the same question, felt like the number of solves would be a bit more "balanced" if n is bigger.

    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Looking back, it might be to allow people to simulate the removal of every marble, however I don't think that is appropriate for a D2B, I mean it is not hard to get to the $$$O(n)$$$ solution.

      → Reply
      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        i don't even know how one would simulate this, lol

        → Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    edu 2b frequently allows $$$O(n^2)$$$ while $$$O(n)$$$ solution exists. In the last edu 2b it also allows $$$O(n^2)$$$.

    → Reply
»
6 weeks ago, # |
← Rev. 3   Vote: I like it +15 Vote: I do not like it

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)

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 weeks ago, # |
  Vote: I like it +38 Vote: I do not like it
Problem C
→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I literally solved 1903C problem yesterday. but still wasn't able to solve today c problem.

    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      happened to me too. i have solved both of these problems in the past!

      → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If a CM couldn't solve it, I had no chance... I could only solve A and B. Is there a very specific technique that you have to know to solve C?

    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      well i tried everything! just couldn't crack it.

      → Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I m newbie but i solved C <...>

    → Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    C is peace of s***. Worst edu ever

    → Reply
»
6 weeks ago, # |
  Vote: I like it +28 Vote: I do not like it

Who put problem E at this position?

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    6 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Your WA case is:

    4 4
0011

    In this case you divide 0011 into 00|1|1, which gives a score of $$$3$$$ and your code thinks it's impossible to reach $$$4$$$. However, we can divide 0|0|1|1 to get a score of $$$4$$$.

    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah I got it now. I am nowhere near the solution and need to re-think this.

      → Reply
»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Exactly!! I always avoided EDU div 2, but this time I thought of participating and got a really bad rank.

    → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why it is TLE?

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

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    unordered map collisions, use map forever and always

    → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain logic for the problem C

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Replace $$$0$$$ as $$$-1$$$, and the result of some grouping, eg $$$[-1,1],[-1,1,1],[1,-1,1]$$$, is $$$\text{sum}[1,-1,1]+\text{sum}[-1,1,1,1,-1,1]$$$. So you can solve all suffix sums and add them greedily.

    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i thought of this but couldnt code would be helpful if i get code of this in c++

      → Reply
»
6 weeks ago, # |
← Rev. 8   Vote: I like it +46 Vote: I do not like it

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.

So Why?
→ Reply
  • »
    »
    6 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it +18 Vote: I do not like it
    • Problem E.
    • Step 1. Find the highest node r that is in the optimal solution — we use binary search for this part.
    • Step 2. Keep only the relevant nodes — do DFS from r with the restriction of moving to any vertex v such that v <= r — call this set G.
    • Step 3. Root the newly formed tree at node r. Let's call a vertex v good iff in the subtree of v do not exist two vertices p and q such that a[p] = a[q].
    • Step 4. We have a function sub(x) — number of vertices in the subtree of x — this function is dynamic.
    • Step 5. We have a function dup(x) — number of vertices p in the subtree of x for which there exists a node q in G such that a[p] = a[q] — this function is also dynamic.
    • Step 6. Go trough vertices in G from highest to lowest and try to remove them from the tree. It can be seen that a vertex x can be removed if it is a good vertex and sub(x) = dup(x). Note that after this step we need to remove the subtree of x.
    → Reply
»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Why is problem C tagged geometry?

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    high rating people trolling with tags once again; they're free to edit them regardless of what the problem actually is which can cause chaos if some person intentionally chooses the wrong tags

    → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why the suffix works in C?

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Does it matter if the starting score for the first group is 0 or 100?

    → Reply
  • »
    »
    6 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    The main key observation is to understand that the difference of Bob's score and Alice's score is just the summation of the suffix sums at each split;

    Why this works is really interesting:

    Basically, taking an example, if you have three groups:

    [ Group 1 elements ] [Group 2 Elements ] [ Group 3 elements]

    You could normally calculate the total difference between Bob and Alice's score as:

    (Difference in scores for group 1) * 0 + (difference in scores for group 2) * 1 + (difference in scores for group 3) * 2

    (Lets call the above equation (1))

    Now the key thing to understand here is that there is a pattern here; Group 3 is being summed 2 times, Group 2 is being summed 1 times, and Group 1 is being summed 0 times....

    So instead, if you just calculated the suffix sum for difference of scores at each position starting from the last element, and then calculated:

    (Sum of suffix scores at Group 1/2 split) + (Sum of suffix scores at Group2/3 split)

    You would automatically calculated the same thing as equation (1) above! This is because in this expression, the suffix sums for Group2/3 split would get counted twice (once because of the Group 2/3 split term, and once because of the Group 1/2 split term).

    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, that's seems too easy, just convert the multiplaction to summation.
      unfortunately i didn't get it :(

      → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you so much . Now i am able to understand the approach.

      → Reply
»
6 weeks ago, # |
  Vote: I like it -15 Vote: I do not like it

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;

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

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For your first code, if there is only 1 marble in the game, do you print 1 or 2?

    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      so if there is only one type of marble with frequency more 1 we should print 1. else 2

      Thank you for answering.

      → Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your code 1 can handle mp.size() == 1 in the else part but when you handle it in paritcular, you handle it wrong.

    ps. uni & 1 == 1 is actually uni & (1 == 1), but it doesn't matter in this case.

    → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Did anyone solve C using binary search?

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, you can to find ans on binary search. Checker: if you try to push level on number you can to recalc difference on Alice and Bob. Check my code.

    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please explain a little bit your logic? I am not able to understand it on the face of it. I know we binary search on number of groups and see if we can get a score atleast k with that many groups. But how to decide the group size in the check function?

      → Reply
»
6 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

What's the hack for C?

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Int overflow probably

    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
      ← Rev. 3   Vote: I like it +8 Vote: I do not like it

      Yes, when you have 2⋅10⁵ zeros, the sum gives negative overflow for int

      → Reply
      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        As a victim I can confirm. And I thought it was my best round ever. Now I have to wake up early tommorow to release the frustration

        → Reply
»
6 weeks ago, # |
  Vote: I like it -23 Vote: I do not like it

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.

→ Reply
»
6 weeks ago, # |
← Rev. 2   Vote: I like it +45 Vote: I do not like it

Bro, really?

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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;
}
→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    sorry,I know where I wrong. whether to choose to add a split is only relative to suffix 1's occurence > 0's occurence, which is not relative to Cnt1[i]-Cnt1[upS]>Cnt0[i]-Cnt0[upS] , so it should be fixed as Cnt1[i]>Cnt0[i] you can test your code with this datain to check this problem.

    1
5 6
01011

    It should out 5

    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ou, it's not 5, it actually 2

      010|11

      → Reply
»
6 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone share idea of question C ?

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    try do sth. from back?

    → Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try to approach the problem in the follow way:
    solve easy special cases of the problem such as
    all 0s
    all 1s
    0001111 and vice versa
    if you found the solution this way, please share how you did that, what did you discover

    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I know the mathematical relation for the problem which is d[0] * 0 + d[1] * 1 + d[2] * 2 + ... + d[m - 1] * (m - 1) >= k, where d[i] represents the difference between number of ones and zeroes in i-th partition. I saw people's solution, which involves taking all the partitions where cnt1 > cnt0, sorting them in descending order, and greedily summing them until the sum becomes greater than or equal to k. I don't know why it's working.

      → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

why unrated

→ Reply
»
6 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

.

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why I didn't recive any elo yet?

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 weeks ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    yapping while account sharing is wild work

    MikeMirzayanov awoo please look into this, this user had 2 different code styles in the same contest

    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for your statement and I respect every comment, even if I have to explain. There is a total of 3 styles of codes that I use throughout every competitive programming contest that I use, even including ICPC. Yes, sometimes with training sessions even my teacher asked me whether I cooperated with someone else's and I had to capture the screen for him of all my work. It seems that due to the fact that three of my teachers now have opposing coding styles, I am also affected. I felt that I could fix this in the future.

      I felt that the only advantage that I had was fast coding, as in every ICPC contest our team is always "first ranked of all teams with equal points". My knowledge is not world-class, but I surely wanted to reach there. So of course, every suggestions that make me change myself, I will be deeply appreciated. Thank you sir, and have a nice day.

      → Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    if you judge correctly you won't get overflow on both sides.

    To prevent overflow:

    • Positive side. Once the sum of suffix sums exceeds $$$k$$$, end the loop immediately, which everyone does. It can be shown that you won't exceed $$$2^{31}-1$$$ and left as an exercise.
    • Negative side. Add only positive suffix sums. If you keeps accumulating negative suffix sums, you'll get $$$-\frac{200000\times199999}{2}<-2^{31}$$$ and overflow given $$$00000000000\dots$$$. Many fail to handle this and are hacked.

    In fact I don't know how C can overflow until I see the comment. Maybe the authors also don't realize the case and thus fail to set a $$$00000000\dots$$$ in pretest.

    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you for sharing the idea. I just saw the 20 test cases that were added by hacks. The only idea that I used "long long" is that I felt that the suffix sums with their maximum value could be around 10^9 so I changed to long long before submitting only a few seconds.

      → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 weeks ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

(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";
}
→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
5 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

xD

→ Reply