Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

wuhudsm's blog

Codeforces Round 960 (Div. 2) Editorial
By wuhudsm, history, 26 hours ago, In English

Thank you for participation and we hope you enjoy this round :)

Additionally, we sincerely invite you to join the unofficial round of TheForces Community tomorrow. Compete alongside many high-rated participants and earn your own rating in a our own rating system(TheForces Rating System)!

For more details, pls read https://mirror.codeforces.com/blog/entry/131733.

A — Submission Bait

hint1
hint2
solution 1
solution 2
code(solution 1)

B — Array Craft

hint1
hint2
solution
Bonus
code

C — Mad MAD Sum

hint1
hint2
hint3
solution
code
fun fact

D Grid Puzzle

hint1
hint2
hint3
solution
code(greedy)
code(DP)

E Catch the Mole

hint1
hint2
hint3
hint4
solution1
solution2
bonus
code(hard version)

F Polygonal Segments

solution1
solution2
code(solution 1)
code(solution 2)
  • Vote: I like it
  • +24
  • Vote: I do not like it

»
4 hours ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

first

Can someone please tell me what the bait was for A? Was it that people thought the $$$\ge$$$ was $$$>$$$ so the answer is always yes?

Nvm, I think I got it. Did people only count the frequency of the max number?

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

    I bit the bait.Got a WA just in first few minutes......(Yes,Only counting the largest number)

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

    same here, at first only considered frequency of max number (;

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

      oh wow! This was my first contest ever and I felt stupid after just ensuring that the max appears odd times. Same thing happened with B. Got the initial idea but couldn't combine the prefix and suffix sum construction. Is it down to just lack of practice? Any resources for me to start on :) ?

      → Reply
»
4 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone done C ...

Can you tell where 271597372 nd 271626656 is wrong ??

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

    N<=2e5, your solution repeats at most N times the code in while-loop and you make 1 for-loop inside while-loop and another for-loop inside the first for-loop, so the time complexity is O(N^3) which is obviously too slow.

    → Reply
    • »
      »
      »
      3 hours ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it
      • you use map inside the loops so the complexity is even O(N^3logN) not O(N^3)
      → Reply
      • »
        »
        »
        »
        3 hours ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        but in the second one its giving wrong answer not even TLE or I would have think of some other logic . also in second one I think the TC is good no ?? Can you tell me where the logic is wrong in second one ??

        → Reply
        • »
          »
          »
          »
          »
          3 hours ago, # ^ |
            Vote: I like it 0 Vote: I do not like it 
          for(int  i=1;i<n;i++){
    if(v[i]==v[i-1]){
        curr=v[i];
    }
    mpp[i]=curr;
}

          The same numbers don't have to be next to each other and this one has time complexity O(N^2) so it would get TLE anyway.

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

deleted

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

    In the case that the sum becomes <= -1 at point x or y. Then the first time the sum is equal to the maximum will be at 1 or n instead of x or y. That's why you need to alternate between -1 and 1.

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

      yeah got it, i had the intuition and had implemented it in one of my soln but my way of implementation was just unnecessarily complex and i am dumb so got it WA. anw bad day it was. thank you for your explanation.

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

Nice brain teasers. Now where are the problems?

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

Thanks for editorial! I really liked problem C :)

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

For E solution 2, I think it should say

spoiler
→ Reply
»
3 hours ago, # |
← Rev. 4   Vote: I like it +16 Vote: I do not like it

Here is another solution for E (actually, I think there are a lot of ways to solve it):

Solution
→ Reply
»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

For D, I have a binary search solution: 271626468

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

I had a different approach to E which I don't have proof for, but it managed to pass tests with $$$\le 160$$$ queries.

Spoiler
→ Reply
»
3 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

For Problem B, Can anyone please help me understand why my construction is wrong for the case 5 2 1

my construction : 1 1 -1 -1 -1. Prefix max is at 2 and suffix max is at 1.

Thank you.

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

    Suffix sum is max at 5 and 1 both so it will consider 5

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

      Thank you so much. :facepalm:

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

    the suffix max is -1

    and it occurs at indices 1, 5

    y should be the greatest index that satisfies $$$a_i+\ldots +a_n=\max_{j=1}^{n}(a_j+\ldots+a_n)$$$

    but the index 5 is the greatest here, that is why your solution is wrong

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

    Suffix is max at 1 and 5 also, and since we need to return maximum such index, so index 5 will be considered not 1.

    Hope you Understands

    → Reply
»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me why is this wrong for B? 271591444

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

    For 5 2 1 you print 1 1 -1 -1 -1 Suffix max should be at 1 but here it's at 5

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

    consider this test case (from the above comment)

    n = 5, x = 2, y = 1

    your code outputs: 1 1 -1 -1 -1

    and this is wrong because the maximum suffix occurs on indices 1 and 5, while it should be occurs only in the index 1

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

I find it interesting that a theforces organizer was 2nd place in div2. What are the odds some of the problems were proposed or seen for some theforces rounds? Not accusing anyone though. Just an observation.

→ Reply
»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

In question A, how is it possible that the maximum number does not get condisered ?

Foe Example if the numbers were 1 2 2 2 3 3. Then, Alice won cause there are 3 2s. But what if Alice chose 2 and then Bob chose 3. In the operations mentioned, we can choose a[i]>= what the opponent chose.

Why is that Bob only chooses equal to Alicw?

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

    Alice chose 2 then Bob chose 3 Then again Alice chose 3 See?

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

    justice for bob xD.

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

    if every number occurs even number of times then, any number Alice will choose, Bob can mimic it and choose it again

    if there is a number that appears odd number of times, then Alice can choose it, forcing Bob to choose a number that occurs even number of times, now Alice can mimic Bob choices and win

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

      Yeah but why should Bob even mimic. I mean its not even mentioned anywhere that Bob plays optimally. There DOES exist a winning strategy for Alice

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

        well, there does not exist a winning strategy for Alice, if she cannot win using this strategy somehow.

        let's say that bob won't play optimally, but he still can mimic Alice choices, right ?

        while there is a chance to Bob to win in Alice's winning strategy, then it won't be considered as a winning strategy

        I don't know why would Bob not to play optimally btw :)

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

          Yeah I mean fair enough to assume that, but a special case IS a possible one too :)

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

          exactly. this thought kept me from trying what actually the question wanted. maybe i'm thinking too much

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

    just another case 1 2 2 2 3.

    bob could have won in this but alice will win lmao!!

    I'm not trying to oppose anyone, just a curious doubt!!

    → Reply
»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

What about this approach for E:

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

I solved E by deleting a half of tree each query, so there is $$$O(\log(n))$$$ queries.

In each query find a subtree with closest size to a half of the current tree. From current root, go to subtree with maximum size while the current subtree size is greater than a half. Query this subtree.

Response 1. Set this subtree as a current tree.

Response 0. Delete this subtree and all leaves from the current tree. Then add a parent of the root to the tree. This can be done in $$$O(n)$$$, so total complexity is $$$O(n\log(n))$$$.

CODE

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

    Yes I realized this ended up being my solution, but in my head I thought of the subtree you find as the centroid. I wonder what kind of bound they potentially could have set for the number of queries.

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

    I think the problem is unsolvable in less than $$$O(\sqrt{n})$$$ queries. Consider the tree with the root having $$$\sqrt{n}$$$ chains of length $$$\sqrt{n} + 1$$$ attached to it. You have to at least know in which chain the mole is in, so you have to query each chain at least once, since the mole won't get to the root in $$$\sqrt{n}$$$ queries.

    → Reply
»
2 hours ago, # |
  Vote: I like it +2 Vote: I do not like it

My solution 271646773 for E passes tests in $$$\le 100$$$ queries but I don't know why. I would appreciate it if anyone could prove some upper bound on the number of queries or provide a counter-example.

The idea is to greedily choose a node that results in the minimum number of candidates in the worst case. Specifically, querying $$$x$$$ results in size[x] candidates if the answer is $$$1$$$ and (size[0] - leaf[0]) - (size[x] - leaf[x]) candidates if the answer is $$$0$$$. Here size[x] is the number of candidates in the subtree of $$$x$$$ and leaf[x] is the number of leaf candidates in the subtree of $$$x$$$.

It's easy to compute these numbers for all $$$x$$$ with a simple dfs, after which I pick $$$x$$$ with the minimum value of max(size[x], (size[0] - leaf[0]) - (size[x] - leaf[x])). Finally, I repeat this process until only one candidate is remaining,

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

Can anyone explain me how to solve B plzz :(, i might have lost my mind after today's contest

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

Personal Editorial that focuses mostly on intuition

A:Basically, Alice can always pick the largest element a_i such that count[a_i]%2==1. No matter what Bob picks, Alice still wins. If that element doesn't exist Alice loses. This was a pretty hard Div 2 A in my opinion.

B: I started by thinking that we want to limit the maximum sum or in other words we don't want the prefix sum to get any larger after X or the suffix sum to get any larger before Y. The obvious construction is [-1,-1,...,y,1,1,...,x,-1,-1,...] The problem is that it might be the case that the prefix sum of -1 (the first element) is the larger than the first x elements (the same might be true for the suffix sum). To avoid that, we notice that we can alternate between -1 and 1 at the ends. The construction is as follows: [...,-1,1,-1,Y,1,1,...,1,1,X,-1,1,-1,...] This solves both problems.

C: We try testing the operation on the array to see what happens. The two key observations are that the first operation makes the array increasing, and the second operation shifts the array to the right by 1. The solution then becomes pretty much just math. We use the operation once, and then we use math to calculate the answer.

D: I didn't have time to write the AC code during the contest, but the approach is actually very simple — too simple in my opinion for a Div 2 D. The key observation is realizing that if a[i] is large the only operation that makes sense is to fill the whole row. If it takes more than two operations to fill a row with white with 2x2 squares, we might as well just fill both the ith and the ith+1 row with white. We also notice that there are two cases where using 2x2 squares are beneficial.

Case 1: a[i] <=2 and a[i+1]<=2 Case 2: a[i]<=2 and there is an even number of 3 <= a_x[i] <=4 followed by an a_y[i] <=2. In both cases our answer goes up by one.

→ Reply
»
52 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

For B problem if test is 5 2 1
is [ 1 1 -1 -1 -1] consider to be wrong answer ?

→ Reply
»
50 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

For F solution2, I think the pseudocode should have 2a[mxp] <= instead of 2a[mxp] >=.

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

I am here to provide yet another solution to E that I cannot prove the query ammount.

Solution
→ Reply