wuhudsm's blog

By wuhudsm, history, 4 months 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://codeforces.me/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
  • +92
  • Vote: I do not like it

»
4 months 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?

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

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

    • »
      »
      »
      4 months 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 :) ?

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Practice more and Think more:)

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          LeetCode should learn to set contests like the way CodeForces do. 0 solved by chatGPT :)

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone done C ...

Can you tell where 271597372 nd 271626656 is wrong ??

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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)
      • »
        »
        »
        »
        4 months 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 ??

        • »
          »
          »
          »
          »
          4 months 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.

»
4 months ago, # |
Rev. 5   Vote: I like it -14 Vote: I do not like it

okay, i accept defeat

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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.

»
4 months ago, # |
  Vote: I like it -27 Vote: I do not like it

Nice brain teasers. Now where are the problems?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    buddy, you got — ve contribution, 0 contests, has 1 problem solution, wtf? Brain teasers are the one for you (of course if you got one (brain)).

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for editorial! I really liked problem C :)

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same here, C was good one, but can you please simply explain to me why we cannot get the answer if we perform the operation on array only once and then using one for loop and maths we calculate the answer.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The main reason is that we can only directly calculate the answer when the MAD operation is performed on a sorted array, since performing it on unsorted arrays leads to things like this:

      Image (as is evident, it doesn't work out)

      The main reason for this is because when we perform the MAD operation on an unsorted array, the resulting array may not follow the "rules" of the calculations (mainly that each value appears at least twice), whereas it will definitely follow the rules with a sorted array:

      Image

      It intuitively makes sense why this is, since in order for a new value to appear in any MAD array, it must appear at least twice in the original array. Since the input array is sorted, a new value must only appear strictly after its first appearance in the original array. So, each number in the MAD array must appear twice, which requires that the input array be sorted. Only once we know that each value appears twice can we use the trick to calculate the answer.

      Hope this helps! :)

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For E solution 2, I think it should say

spoiler
»
4 months ago, # |
Rev. 4   Vote: I like it +45 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
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For D, I have a binary search solution: 271626468

»
4 months ago, # |
  Vote: I like it +12 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
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Isn't it right since $$$ d \times w \le n $$$ where d = depth, w = width, and your algorithm would be $$$O(min(d, w))$$$ which is less than $$$\sqrt n$$$?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    when you say using dfs to find the subtree of the current node with the fewest alive children you mean the subtree of a direct child right?

»
4 months 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.

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

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

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you so much. :facepalm:

  • »
    »
    4 months 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

  • »
    »
    4 months 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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I had the same doubt, and I think I did the same implementation as you, making the index >x and index < y all -1 and remaining other 1; Idk what was the issue until I saw this comment

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 months 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

  • »
    »
    4 months 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

»
4 months 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.

»
4 months 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?

  • »
    »
    4 months 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?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    justice for bob xD.

  • »
    »
    4 months 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

    • »
      »
      »
      4 months 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

      • »
        »
        »
        »
        4 months 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 :)

        • »
          »
          »
          »
          »
          4 months 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 :)

        • »
          »
          »
          »
          »
          4 months 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

  • »
    »
    4 months 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!!

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No bob can't win cause alice will pick 3 directly.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What about this approach for E:

Spoiler
»
4 months 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

  • »
    »
    4 months 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.

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it +84 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.

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it +11 Vote: I do not like it

    this code works in sqrt(n) queries in the worst case

    this case is 4901 nodes

    • adj[1]={2,3,...,71}

    • adj[i]={i-70,i+70} for all i in [72,4831]

    • adj[i]={i-70} for all in [4832,4901]

    and at each query you ask for a child between 2 and 71 and the response is 0 at the 70'th query you get the response

    you guess the correct answer in the some testcases in the 25-th test at 70 queries

»
4 months ago, # |
  Vote: I like it +14 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,

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    Lemma 1: if B <= size[x] <= n - B for some $$$B$$$ then querying $$$x$$$ removes at least $$$B$$$ candidates, where $$$n$$$ is the current number of candidates. To prove it formally, note that

    (size[0] - leaf[0]) - (size[x] - leaf[x]) =
      = (size[0] - size[x]) - (leaf[0] - leaf[x])
      <= size[0] - size[x]
      <= n - B
    

    Lemma 2: if size[x] < B or size[x] > n - B for all $$$x$$$ then there exists a node $$$p$$$ with size[p] > n - B and size[c] < B for every child $$$c$$$ of $$$p$$$. To prove it, note that the subtree size of the root is $$$n > n - B$$$ and the subtree size of any leaf is $$$1 < B$$$, so there must be a transition point in between.

    Lemma 3: if size[x] < B or size[x] > n - B for all $$$x$$$ then the tree has at least $$$\lceil\frac{n}{B}-1\rceil$$$ leaves. To prove it, consider node $$$p$$$ from lemma 2. It has at least $$$\frac{n-B}{B-1}$$$ children because its subtree size is large but all children have small subtree sizes so there must be quite a few of them. $$$\frac{n-B}{B-1} > \frac{n-B}{B} = \frac{n}{B} - 1$$$. All numbers are integers so we can take $$$\lceil \cdot \rceil$$$ of the last expression.

    Lemma 4: if there are at least $$$C$$$ leaves then querying one of them removes at least $$$C$$$ candidates. If the response is $$$1$$$ then we found the mole, and if the response is $$$0$$$ then all $$$C$$$ leaves are no longer valid candidates.

    Choosing $$$B = \sqrt{n}$$$ means that we remove roughly $$$\sqrt{n}$$$ nodes per query (where $$$n$$$ is the current number of candidates), and hence the greedy process results in $$$O(\sqrt{n})$$$ queries overall.

»
4 months 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

»
4 months ago, # |
Rev. 2   Vote: I like it +11 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.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Why the negative contribution? I'm genuinely curious. I'm gonna write them either way because it helps me get better at explaining things, an important life and interview skill, and also because it might help some people.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I genuinely thank u for sharing the way you think. I am suck at thinking constructive problems and your comment really helps me to build a certain way to think. Keep contributing! Don't let these downvotes upset u.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    In problem B, actually i came up with only [-1,-1,...,y,1,1,...,x,-1,-1,...] this and can't able to think further. Btw now understood completely thanks :)

»
4 months 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 ?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes, because the maximum suffix position of the array that you have given is 5

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, but this test case satisfies the condition for maximum subarray sum, doesn't it?

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks it was annoying me

»
4 months 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] >=.

»
4 months ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

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

Solution
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yay, I had the same solution =)

    But I added an additional condition: if you can't find the centroid — 'the node with the smallest subtree size that contains at least half of the remaining nodes of the current node's subtree and is not equal to the current node' — I chose the biggest child of the current node.

    current node — the last node that contained the answer in it's subtree.

»
4 months ago, # |
  Vote: I like it +33 Vote: I do not like it

E2 with $$$100$$$ queries

hint 1
hint 2(almost the solution)
answer
bonus 2
  • »
    »
    4 months ago, # ^ |
    Rev. 3   Vote: I like it +20 Vote: I do not like it

    i solved the problem in at most 70 queries (sqrt(n))

    if we denote by size[node] the number of possible location in the subtree of "node" and we denote by size_valid the number of possible locations if we ask about the node that minimizes abs(size[node]-size_valid/2)

    • if the response was 1 : so size_valid will be size[node] because the location will be in the subtree of node
    • if the response was 0 : so size_valid will be size_valid — the number of possible locations that hasn't any child that can be possible + 1 if the lca of all possible nodes isn't the root

    in the worst case childs of the lca of the possible nodes has the same size: size[node] in the worst case size[node] will be sqrt(size_valid) for sqrt(size_valid) nodes and size_valid after each query will decrease by at least 2*sqrt(size_valid)-1 (sqrt(size_valid) for the subtree of the choosen node and sqrt(size_valid)-1 for the nodes that hasn't any child that can be possible location else it will decrease by x+size_valid/x-1 with the same logic ) so if n can be solved in sqrt(n) than n-2*sqrt(n)+1 can be solved in sqrt(n-2*sqrt(n)+1)=sqrt(n)-1 so for n=5000 only 70 queries can be enough

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If you found, ask the same root until not found.

    How do you do this? If the answer to a query is $$$1$$$ then the mole doesn't move

    • »
      »
      »
      4 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      sorry, please consider subtree as strictly subtree

      UPD: I was wrong, fixed my solution is under the reply tree.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you explain in detail that how we can 'ask the same root until not found'? Thanks! My question is the mole doesn't just stop at the root you pick, so we have to use binary search for the real position.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      During asking the same node, if the result changes 1 to 0, the mole will be in the parer of the node, so answer there.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        But the mole doesn't move if the result is 1. So how can the result become 0 if we keep asking the same node?

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          Sorry, I answered as the inverted version(originally the outcome was inverted, but during testing the outcome is current style).
          If the answer is 0, cutting down the subtree is the same.(In this step, we can also cut all the leaves) If the answer is 1, now we have a tree atmost depth $$$100-i$$$, rooted by $$$v$$$.
          Now, ask sons in the order of decreasing the depth. If we receive 1, do the same thing. Note that, if we receive 0, all leaves are disappeared so we shouldn't care about small subtrees and we must look up atmost $$$O(\sqrt{n})$$$ sons.
          Finally, if we gets lost(no such subtree found), we can identify the path the mole is in(from $$$v$$$ to the parents), so do binary search.
          I think this fits in $$$100$$$ queries, but sorry if I'm wrong.

»
4 months ago, # |
  Vote: I like it +6 Vote: I do not like it

I'm still traumatized from A

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Could anyone explain why 271582281 fails on the 3rd test case?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am really confused. I have used the even and odd approaches. If the n is odd then it is clear that Alice will win.

example: 1 2 3 4 5 5 6 A B A B A B A

If n is even, then there would be 2 cases:

Case 1: The frequency of maximum numbers is odd. example: 1 2 3 5 5 5 A B A Hence, Alice will win.

Case 2: The frequency of the maximum number is even. example: 1 2 3 4 5 5 A B Hence, Alice will lose.

This is the approach I applied but I got the wrong answer. Could you guys please tell me, what is wrong with my approach?

  • »
    »
    4 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Your reasoning for case 1 is correct.

    Your reasoning is faulty in case 2.

    Take the test case:

    1 2 3 3 3 3

    You would say that Alice would lose because N is even and the frequency of the maximum element is even. However, if Alice chooses 2 in her first move she can win because then Bob goes first and they alternate picking 3s.

    Alice loses iff the frequency of all elements is even because as explained in the editorial Bob can mirror all her moves.

    In any other case Alice can force Bob into this situation if there is at least one odd frequency element by selecting the last odd element as her first move.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

orz round

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

C, D is brilliant!

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Got baited by A, thought that only the parity of frequency of maximum element mattered.

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone please explain why this code 271651820 for problem C giving wrong answer. I tried to do it with one operation and after this if mad value appears more than once , it will right shift in further operation otherwise if mad value appears only once, it will add once to the answer.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If a mad value appears only once, it will not only add once to the answer but also turn into its neighbor on the left during the consequent operations.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      hey, i'm facing the same problem as him, can you provide testcase for this mad value only once case please. I didn't understood.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have another solution for E1. my solution in chinese :)

»
4 months ago, # |
  Vote: I like it +19 Vote: I do not like it

In problem F, solution 1:

We notice that a local maximal polygon segment $$$[l,r]$$$ must satisfy $$$\min(a_l−1,a_r+1)\ge \mathbf{2}(a_l+...+a_r)$$$. (or $$$l=1,r=n$$$).

shouldn't it be:

...must satisfy $$$\min(a_l−1,a_r+1)\ge (a_l+...+a_r)$$$.

Is the extra "2" a typo?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Can you please explain this formula? How can we transform: a(l) + a(l + 1) + .. + a(r) > 2 * max(a[l..r]) (original condition to form a polygon I guess?) to that? Thanks

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am so confused about this, it that $$$\min(a_l-1,a_r+1)$$$ but not $$$\min(a_{l-1},a_{r+1})$$$? The author writes the latter. However, I still think both of them are confusing. I think $$$(a_l+\cdots +a_r)>2\max{a_l,\cdots,a_r}$$$ works.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The condition in the editorial is neccesary but not sufficient. However, since there are only $$$\log V$$$ "key points", it is quite enough for us to use.

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    I think so. The necessary and sufficient condition for judging whether $$${a_1,\ldots,a_n}$$$ is a "polygonal segment" is $$$\forall 1\le i\le n, a_i< \left( \sum_{j=1}^{n}a_j \right) -a_i$$$. We can obtain the necessary and sufficient condition for the "polygonal segment" $$$[l, r]$$$ to not be further expanded as $$$\left[\left(l=1\right) \vee \left(a_{l-1}\ge \sum_{i=l}^{r} a_i\right)\right] \wedge \left[\left(r=n\right) \vee \left(a_{r+1}\ge \sum_{i=l}^{r} a_i\right)\right]$$$.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem B, I don't understand why the first construction doesn't work. i.e. 1 in the common range, and -1 in the remaining positions.

The condition was simply that the prefix sum should be maximum at position x and not any position greater than x, and the suffix sum should be maximum at position y and not any position smaller than y. This construction satisfies it perfectly. What is the need for alternating -1 and 1?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ah nevermind, the sum might not ever become positive, in which case the condition isn't satisfied.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I need help in C, What am i missing 271697251

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

LeetCode should learn to set contests like the way CodeForces do. 0 solved by chatGPT :)

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

done

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain the funfact on c?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Maybe it's referring to doing the naive 'mad' simulation twice, and then just summing up once.

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

can someone please tell me why is this code giving tle for problem c? link

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

How to solve B if

  • The maximum prefix position of b is the largest index i that satisfies ...
  • The maximum suffix position of b is the smallest index i that satisfies ...
»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I think I've solved E in 100 queries,heres my submission:submission.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Amazing Fun Fact about Task3

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

Can anyone explain the solution 1 of F which store some information in one node in Segment Tree? I don't really understand what we have to store, and how we use it to get the answer.

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

    Hello! I just finished upsolving it, here's my code: 274583614. Search for prefix_t to skip the template.

    Let's call an element prefix peak if it is greater than a corresponding prefix sum. Define suffix peaks similarly. Pad the subarray with positive infinities on both ends, they are also peaks. Store a tuple (prefix length, sum, maximum, peak) for each peak. Let's call a vector of such tuples prefix info. Define suffix info similarly.

    You need a few operations:

    1. extend prefix info of the left segment with prefix info of the right segment to form prefix info of the combined segment;

    2. extend suffix info of the right segment with suffix info of the left segment to form suffix info of the combined segment (same as 1);

    3. combine suffix info of the left segment with prefix info of the right segment to update the answer.

    Operation 3 can be tricky to implement in linear time ($$$log^2$$$ overall) with two pointers, so I implemented it naively in quadratic time ($$$\log^3$$$ overall) to stress test but it passed comfortably in 3 seconds :| Disappointing preparation from the setter considering that most solutions are within a factor of 4 of my execution time whereas $$$\log = 40$$$.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem B:

Question says : It can be proven that such an array always exists under the given conditions. How do we prove that answer always exists ? Can someone help me understand this ? Thanks in Advance.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain the alternate solution for A using dp? Also, what does the author mean when he writes =∼? Thanks!

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    For dp[i], Alice is faced with the array a[1:i], where a is non-increasing.

    Transition

    Hope I didn't complicate it too much. And, =~ just means we are taking negation of RHS, and assigning it to the LHS.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone please answer this.... for Problem D, In shayan's video solution, dp[i][j], j={0,1,2,3} what is the j here ? , is it {00,01,10,11} where each boolean value tell us about the use of the 1st and 2nd 2x2 block in i_th row ?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I was a bit confused for C where i did one operation and did the same contribution idea (n-i)*a[i]. I am not sure why it is failing there but getting accepted if we do 2 operations. while one operation is sufficient for making the array increasing acquiring required elements.

can anyone help me to understand? Thank You

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    While the array may be increasing, some of the elements might only have a frequency of 1 which means they will be erased in subsequent operations. 2 operations ensures that the count of every element is >=2

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you give an example.. i tried hard for finding a case where this assumption fails

      • »
        »
        »
        »
        4 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Sure.

        [2,3,1,1,2,3]

        With 1 operation it is [0,0,0,1,2,3]

        with 2 operations it is [0,0,0,0,0,0].

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thank you mate. I got it now since after the second operation only it becomes a right shift for the next iterations until all becomes zero. I missed that and only considered one operation might be enough.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What do we mean by "left most row" is editorial of problem D. Rows run horizontally shouldn't they be top or bottom. Can anyone help i am confused.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "left most row" --> means absolutely left of any row (or from beginning of any row) example: if [a1,a2,.....an] representing a row , then a1 is leftmost, a2 is next leftmost,....

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For bonus in B, the array exists for y <= x case or not??

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

brainlet solution on problem D. 271773223 no dp, no extra variable. proof: AC

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

C > B > D gg contest the most stupid D problem of all contest

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain dp transition on dp solution for D? plz

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a few doubts in the solution 1 of the editorial for E. Firstly, why do we choose 50? It seems that we should be taking $$$\sqrt{n}$$$, so 70 should be ideal right? Is there something special about 50, because I saw another comment below which says that using a number slightly smaller than $$$\sqrt{n}$$$ is better and I didn't understand the reason behind that either.

Additionally, in the 3rd case, when there's no vertex with $$$maxdep_v - dep_v = 50$$$, then we only need at most 50 moves right, why does it say 100 moves then?

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    I figured taking Sqrt(n) is ideal for solving E2, because you'll need N / 70 + 70 + logN operations(though due to weird constants you still need to optimize binary search by cutting down to r = mid — 2), Then I believe it is optimal to choose K=50 as a constant only in E1 cuz choosing 70 exceeds allowed operations: N / 70 + 2*70 > 200

    As to the 3rd case, yeah you only up to 50 moves after optimization

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    When we drive away this mole once, we need to immediately check if it is still in the subtree v. So it is $$$50 \times 2$$$ moves.

»
4 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Can someone explain this part of sol2 for E?

Then the tree can be split into ≤70 chains.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    We query any leaf $$$70$$$ times, then delete all nodes $$$x$$$ such that $$$maxdep_v-dep_v+1<=70$$$. So if a chain is still alive after the deleting, there must be at least 70 deleted nodes underneath it.

»
4 months ago, # |
  Vote: I like it +6 Vote: I do not like it

An approach for bonus of E

Consider all the nodes that the mole can be one. These lie on a single path from leaf to the initial node of mole. If we can find this path then we can find the mole in O(log n) operations. To find this path consider the following: 1. We know that root node (node 1) lies on this path. 2. For each node that lies on this path exactly one of its children lies on the path.

Let numJumps be the number of operations where jury has returned 0, that is number of times mole has jumped up.

Now start tracing the path from root. Let's call the set of all children where maxDepth — depth >= numJumps candidates for our path extension. If candidates is empty, we are at end of our path. Otherwise while candidates has more than one node, remove the node with minimum maxDepth — depth value and query it. If judge return 1, we move to this node and proceed tracing our path recursively. If judge returns 0, we discard this node, increment numJumps and remove all nodes that have maxDepth — depth < numJumps.

At the end if we are left with exactly one node in candidates we move to this node.

To calculate the number of operations required, notice that first time we query at least 1 node is discarded, second time atleast 2, and so on.

If judge returns 0, then chain is discarded and size of numJumps increases meaning next chain to be discarded must have maxDepth — depth atleast 1 more that cur node's maxDepth — depth

If judge returns 1, notice that there must be atleast one more node with maxDepth — depth at least equal to this node's maxDepth — depth. Meaning at least half of nodes under consideration were discarded, considering single chains with no branching.

Thus nodes under consideration either reduce as 1, 2, 3, ... or half. Either way after k moves, atleast k * (k + 1) / 2 nodes will be removed from nodes under consideration. Meaning after atmost 71 moves we will have completed our path.

Binary search on path will take at most log n moves, that is around 13.

Thus we take atmost 71 + 13 = 84 moves.

Submission: Submission for the above approach

#include <bits/stdc++.h>
 
using namespace std;
 
//#pragma GCC optimize("Ofast,unroll-loops") 
//#pragma GCC target("avx,avx2,avx512,fma") 
 
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#ifdef LOCAL
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
 
#define ll long long
#define ld long double
 
#define PI 3.1415926535897932384626433832795l 

// -------------------------<rng>------------------------- 
// RANDOM NUMBER GENERATOR
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());  
#define SHUF(v) shuffle(all(v), RNG); 
// Use mt19937_64 for 64 bit random numbers.
 
vector<vector<int>> adj;
vector<int> depth;
vector<int> maxDepth;
vector<int> par;
vector<int> path;
int numOperations = 0;
int numJumps = 0;

int query(int x){
    ++x;
    cout << "? " << x << endl;
    int res;
    cin >> res;
    if(res == 0){
        ++numJumps;
    }
    ++numOperations;
    return res;
}

void answer(int x){
    ++x;
    cout << "! " << x << endl;
}


void dfs(int u, int p){
    for(int v: adj[u]){
        if(v != p){
            depth[v] = maxDepth[v] = depth[u] + 1;
            par[v] = u;
            dfs(v, u);
            maxDepth[u] = max(maxDepth[u], maxDepth[v]);
        }
    }
}

void tracePath(int u){
    path.push_back(u);
    stack<int> candidates;
    for(int v: adj[u]){
        if(v == par[u]){
            continue;
        }
        if(maxDepth[v] - depth[v] < numJumps){
            continue;
        }
        candidates.push(v);
    }

    while(!candidates.empty()){

        int v = candidates.top();
        candidates.pop();

        if(maxDepth[v] - depth[v] < numJumps){
            continue;
        }

        if(candidates.empty() || query(v)){
            tracePath(v);
            return;
        }
    }
}

bool cmp(int a, int b){
    return (maxDepth[a] - depth[a]) < (maxDepth[b] - depth[b]);
}

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

    adj = vector<vector<int>>(n);
    depth = vector<int>(n, 1);
    maxDepth = vector<int>(n, 1);
    par = vector<int>(n);
    path.clear();
    numJumps = 0;
    numOperations = 0;


    for(int i = 0; i < n - 1; ++i){
        int u, v;
        cin >> u >> v;
        --u, --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }


    dfs(0, -1);

    for(int u = 0; u < n; ++u){
        sort(adj[u].rbegin(), adj[u].rend(), cmp);
    }

    tracePath(0);

    int l = 0;
    int r = path.size() - 1;
    while(l < r){
        int mid = (l + r + 1) / 2;
        if(query(path[mid])){
            l = mid;
        }
        else{
            r = mid - 1;
            l = max(0, l - 1);
            r = max(0, r - 1);
        }
    }

    answer(path[l]);
    assert(numOperations <= 84);
}
 
int main() {
    int tc;
    cin >> tc;
    for(int t = 1; t <= tc; ++t){
        solve();
    }
    
    return 0;
}
»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

For solution 2 on F, I'm pretty sure you can store a max segtree for the last time each position was updated, and in the map store also store when the range was added. Then when you visit a range just check whether you need to recompute it in log N and then recompute if you have to. I think this doesn't increase the complexity because an interval tree is already n log^2 n to update...?

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

This solution of mine is getting WA for problem D. Can anyone point out the reason? 271964225

I'll explain my approach. I have followed greedy method. I have initialized the minimum no. of operations 'n' since it is always possible.

Now iteratively I am checking for each row the no. black cells, if it is >4 continue else if it's ==0 operation req decreases by one.

My approach is like we can decrease the operations req only when the count of black cells encountered is <=2 && !=0 if so, and the next row is <= 2 && != 0 decrease the operation req by one and move to i+2, if not then minimum of next 2rows should >2 && <= 4 and the next row(i+3 here) should >=2 && != 0 then we can decrease operation req by one as we can use only 1st option in these rows to make them all white and move to i+4.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Uneven problems

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I had a general question for interactive problems, I've seen a lot of problems mention whether the interactive is adaptive or not, I wanted to understand if this makes any difference to the solution. In this contest for example, for E1 and E2 it said that the interactor is not adaptive, but from what I understand, even if it was adaptive, that wouldn't have changed the solution in any way right? What's exactly the purpose of mentioning this then?

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone explain, please, why we cant solve problem C simply implementing the algorithm?

My observation was that number of 0's after each operation grows exponentially, so there will be no more log(n) iteration. Recalculating next iteration of the array will be O(n), times std::map operation to find the most frequent element is O(log(n)) times O(log(n)) total operation result in O(n*log^2(n)) opearions that should pass TL.

Also for some reason my implementation gives WA 272048767. Why so?

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone tell me why this code doesn't work for E1? https://codeforces.me/contest/1990/submission/273122031

I can't tell whether it is an implementation issue, or my algorithm is incorrect. Thanks (see find() function for the main logic)

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

someone tell me whats wrong with this solution for C?

273115595

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For the problem 1990B - Array Craft, I am setting all the elements in the segment $$$a[y,...,x]$$$ equal to $$$1$$$ and all the remaining elements as $$$-1$$$. In this way, the $$$presum_{y-1}$$$ is $$$negative$$$ as well as the $$$postsum_{x+1}$$$ is also $$$negative$$$. Therefore, the $$$\textbf{maximum presum}$$$ will be at the index $$$x$$$, because all the elements after it are $$$-1$$$, which will decrease the presum.

Similarly, the $$$\textbf{maximum postsum}$$$ will be at the index $$$y$$$.

wuhudsm What is wrong with this approach?

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem E, I just query the subtree that has the most possible nodes less than half of the amount every time. https://codeforces.me/contest/1990/submission/273813620

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My submission for problem C shows TLE for TC 15, I basically tried to simulate the process given in the problem statement using maps but am unable to come up with a mathematical equation in order to not run an unnecessary "while(mp.size()!=0)". Here's my submission to the problem : 274692750. Can someone please help me out? Tia

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone please explain , where my solution for c went wrong?. My_sollution

what I did was after first process if there are some consecutive numbers in array with same value of length greater than 1. they are going to exist in array till they get completely shifted out of the array.

so I added it's value to sum as length*(number of rounds this length will be sustained-1)*value + ((length)*(length+1)/2)*value (because after reaching end length will start to decrease by 1).

and for length ==1 I just added to sum only once because they will be removed after next process.

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

please explain solution one

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

for the submission bait: what if I take xor of all the elements when n is even and if result of XOR is not equal to 0 then my ans is "yes" else in all cases my answer will be "no". what is the issue in this approach (I am getting wrong ans on 3rd testcase) 278515326

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone make tell what does that prefix_sum till x should be >0, in B

»
46 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved E2 in q=log(n) (optimally) and O(n) time complexity. The idea is to find a node that divides the nodes of the tree in two. I cannot prove the worst number of queries is less than 160 though. Can someone hack it or explain its mechanisms in a mathematical/logical manner? Thank you very much!

Solution