Блог пользователя wuhudsm

Автор wuhudsm, история, 3 месяца назад, По-английски

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.net/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)
Разбор задач Codeforces Round 960 (Div. 2)
  • Проголосовать: нравится
  • +92
  • Проголосовать: не нравится

»
3 месяца назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    3 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

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

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 :) ?

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

anyone done C ...

Can you tell where 271597372 nd 271626656 is wrong ??

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 месяца назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      • you use map inside the loops so the complexity is even O(N^3logN) not O(N^3)
      • »
        »
        »
        »
        3 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 ??

»
3 месяца назад, # |
Rev. 5   Проголосовать: нравится -14 Проголосовать: не нравится

okay, i accept defeat

  • »
    »
    3 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
3 месяца назад, # |
  Проголосовать: нравится -27 Проголосовать: не нравится

Nice brain teasers. Now where are the problems?

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thanks for editorial! I really liked problem C :)

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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! :)

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For E solution 2, I think it should say

spoiler
»
3 месяца назад, # |
Rev. 4   Проголосовать: нравится +45 Проголосовать: не нравится

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

Solution
»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For D, I have a binary search solution: 271626468

»
3 месяца назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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

Спойлер
  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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$$$?

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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?

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    3 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
3 месяца назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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.

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    justice for bob xD.

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        3 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 :)

        • »
          »
          »
          »
          »
          3 месяца назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          3 месяца назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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!!

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What about this approach for E:

Spoiler
»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    3 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится +84 Проголосовать: не нравится

    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.

  • »
    »
    3 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

    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

»
3 месяца назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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,

  • »
    »
    3 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    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.

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

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.

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    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.

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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.

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    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 :)

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

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

Solution
  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
3 месяца назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

E2 with $$$100$$$ queries

hint 1
hint 2(almost the solution)
answer
bonus 2
  • »
    »
    3 месяца назад, # ^ |
    Rev. 3   Проголосовать: нравится +20 Проголосовать: не нравится

    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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      3 месяца назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      sorry, please consider subtree as strictly subtree

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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        3 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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?

        • »
          »
          »
          »
          »
          3 месяца назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          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.

»
3 месяца назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

I'm still traumatized from A

»
3 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    3 месяца назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

orz round

»
3 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

C, D is brilliant!

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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?

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

  • »
    »
    3 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    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]$$$.

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I need help in C, What am i missing 271697251

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

done

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can someone explain the funfact on c?

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 ...
»
3 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Amazing Fun Fact about Task3

»
3 месяца назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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$$$.

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 ?

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 месяца назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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].

        • »
          »
          »
          »
          »
          3 месяца назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    "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,....

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    3 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
3 месяца назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Can someone explain this part of sol2 for E?

Then the tree can be split into ≤70 chains.

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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.

»
3 месяца назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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;
}
»
3 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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...?

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Uneven problems

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can anyone tell me why this code doesn't work for E1? https://codeforces.net/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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

someone tell me whats wrong with this solution for C?

273115595

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

please explain solution one

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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