ChthollyNotaSeniorious's blog

By ChthollyNotaSeniorious, history, 23 months ago, In English

Thanks for your participation! I am so sorry for my careless review. We were preparing for this round for many months and made some problems which writers and testers are all like. We do want to give everyone a good time to enjoy the contest. But carelessness is deadly. In problem B, some test cases should have been made, but we missed them in not only the pretests but also the final tests. In fact, we had not noticed it until some suspicious hacks appeared. I and all co-authors sincerely regret our mistake and hope you can forgive us.

Besides, few people are cyberbullying authors, please do not do so. If you have a bad experience, you can downvote me because of our fault.

1774A - Добавьте плюсы и минусы
Idea: Cirno_9baka

Solution
Code

1774B - Покраска
Idea: Cirno_9baka

Solution
Code

1774C - Лед и пламень
Idea: Little09

Solution
Code

1774D - Одинаковое число единиц
Idea: mejiamejia and AquaMoon

Solution
Code

1774E - Две шахматные фигуры
Idea: Cirno_9baka

Solution
Code

1774F1 - Фокусник и свиньи (простая версия)
Idea: Little09

Solution
Code

1774F2 - Фокусник и свиньи (сложная версия)
Idea: Little09

Solution
Code

1774G - Покрытие отрезками
Idea: ChthollyNotaSeniorious and JianfengZhu

Hint 1
Hint 2
Solution
Code

1774H - Максимальная перестановка
Idea: Ecrade_

Solution
Code
| Write comment?
»
23 months ago, # |
  Vote: I like it +27 Vote: I do not like it

Auto comment: topic has been updated by ChthollyNotaSeniorious (previous revision, new revision, compare).

»
23 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Thanks for fast tutorial.

»
23 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Problem B was decent!!

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

Is it possible to solve Problem E if they don't have to return to the root?

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

    The implementation would be painful.

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

    We can see answer >= (answer of the original problem) — 2*(sum of max depth of target nodes of 2 pieces), but if there's no 2 deepest target nodes of each piece where their distance <=d, it's hard to find the minimum number of operations

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

    I didn't realize initially that they did have to return to the initial spot, so I solved it the other way. It was more complicated and I had to remove that complication to get the right answers.

    But the additional complication wasn't especially tough. Just required a lot of attention to small details.

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

DD_my_love solved one problem less than me still has a better rank by around 300. Don't know how many more candidates are like this. LMAO ded.

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

1774A - Add Plus Minus Sign

It can be solve in O(t * n). the solution sounds like this: Let's create a sum equal to the first element. Then we just subtract 1 if sum > 0, otherwise we add 1.

AC Code: 185664996

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

Alternative solution for E: We define dp[x] as minimum cost to visit all subtree nodes of x with both pieces and come back. We do DFS, maintaining two values — mn1[v] and mn2[v] — which signify the maximum depth of a vertex we has to be visited by the first piece or the second piece. Now let's do transitions from a vertex u which is a son of v to v: if there are both types of vertexes (which have to be visited by both pieces) we do dp[v] += (4 + dp[u]) (we have to come down, visit all vertices and then come back)

if there are no vertexes, we simply don't have to visit that subtree.

if there is one type (let's say type 1 — a vertex that has to be visited by the first piece), then we have to visit that subtree with the corresponding piece (dp[v] += (2 + dp[x]), and, if we have to come down with the other piece, we do dp[v] += 2 (and that is why we maintain both heights)

code: https://codeforces.net/contest/1774/submission/185696139

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

lol

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

ChthollyNotaSeniorious there is some problem with markup in the solution for D

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

Problem B was underrated, it was a much better problem to be at B

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

    I knew I had a problem with how I was approaching B so I looked at the other problems instead of trying to force it.

    Then I came back in 30 minutes and wrote a good easy solution. Sometimes it's important to recognize when you're on the wrong path, even when it seems to be working.

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

Thanks for the super fast editorial....

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

Is it just me or latex for D doesn't work?

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

is there any working score predictor for codeforces contest ?

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

Problem B had very weak pretests which lead to a lot of people getting hacked so some people flew up the ranks by hacking instead of solving more questions

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

dont know what is going with the solution of b in editorial if anyone interested in a single line solution do check this out https://codeforces.net/contest/1774/submission/185703602

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

    can u paste ur code here, I cant view it

    • »
      »
      »
      23 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it
      for _ in range(int(input())):
          n,m,k=map(int,input().split())
          arr=list(map(int,input().split()))
          if (max(arr)-1)*(k)+arr.count(max(arr))>n:
              print("NO")
          else:
              print("YES")
      
      • »
        »
        »
        »
        23 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        can you please explain why did we add arr.count(max(arr)) into the expression?

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

          like lets say we have multiple maximums than to fits those maximum we need count of maximum extra space .

          for example 1 2 7 7 than to fit these two 7s we need to use count of the maximum element

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

            Understood, thanks :)

»
23 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Can anyone view the solutions of other participants now? I aint able to view it

»
23 months ago, # |
  Vote: I like it +26 Vote: I do not like it

It was a good round and I liked it.

An occasional problem without strong pre-tests like B is a good thing because it offers opportunities to hackers. Those who made mistakes learn a valuable lesson about being more careful.

Pre-tests are not supposed to be a guarantee.

Problem E was very good.

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

The code for E is quite hard to understand compared to the written description which was crystal clear. It would be great if OP can use better variable naming in the future to help with readability.

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

A slightly different solution to F: 185721355

For every Create operation, we will find the number of pigs that survive. Let the index of the current Create operation be $$$i$$$. For now, we will assume that there was an Attack operation before $$$i$$$. We will create an array $$$s$$$: for $$$j >= 2$$$, $$$s_j$$$ will be the sum of Attack values between the $$$j-1$$$-th and $$$j$$$-th Remove to the right of $$$i$$$. $$$s_1$$$ will be the sum of Attack values between $$$i$$$ and the first remove to the right, and $$$s_0$$$ will be equal to the sum of Attack values before $$$i$$$ (so $$$s_0 > 0$$$). As we are only interested in the first $$$logX$$$ Repeats after $$$i$$$, we will only be interested in the first $$$t \leq O(logX)$$$ elements of this array. We will also denote $$$y$$$ to be the sum of Attack values after the last "interesting" Repeat.

The array $$$s$$$ and the value $$$y$$$ are enough to find the solution for pig $$$i$$$: among all its clones, the health of the one with the $$$k$$$-th largest HP ($$$0$$$-indexed) turns out to be $$$x_i - s_0*k - y - \sum_{1\leq j < t} s_j * (\lfloor \frac{k}{2^{j-1}} \rfloor + 1)$$$. I can't think of a simple proof for this, but it's easy to see if you write the "unwrapped" (as in, you actually copy the sequence in case of a Repeat) sequence of operations down. Anyway, this means we can do a binary search to find the smallest positive element.

In case of $$$s_0 = 0$$$ (if there was no Attack before $$$i$$$), we also need to count the number of Repeats before the next Attack, and multiply the answer accordingly.

This is technically $$$O(Nlog^2 X)$$$, but it passes F2 in just over a second and I haven't managed to hack it yet, so it's probably just optimized enough.

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

    I think your key formulation for "kth largest HP" aligns with the key observation in the tutorial. Essentially, because of the observation that the damage of clones is "greedy", we can always find the kth largest "subset sum" of clones (two ways to count this value: one is counting by clones, as the tutorial does; the other is counting by attacks, as in your formula). : )

    Thanks for providing another idea! The property of this problem is very intriguing.

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

Could anyone help me with Problem F1? I'm not sure why my solution doesn't work. Basically, I track all operations performed in an array of pairs ("ops"). I track the total decrease in the int "total" which I minimize with "SIZE" (a const int = 2e5+5) to avoid overflow.

If total == size when I encounter the third operation, I simply don't track the operation because all previous pigs will be killed, and all newly created pigs will be created in the same way as the first set was. If total < SIZE and total > 0, then I double all of the operations in "ops" and double total. If total == 0, I record that the count of all current pigs should be doubled.

I use prefix sums to calculate how many times each created pig will be doubled or have its health decreased.

Here is my submission: https://codeforces.net/contest/1774/submission/185734070

Thanks in advance.

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

Strange. We've made many hacks but there are only 18 testcases in the problem now.

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

Problems are good.

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

In problem E you can also just simulate all their moves:

My code
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

C was easy but I was panik by B and ended up solving only A :(

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

    dude can you explain problem C's idea

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

      Store max and min index of iTH game winner. If game iTH is "0", all player from 1 -> max[i-1] will win the game, otherwise is min[i-1] + 1 -> i. You can prove it yourself.

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

Can someone give better explanation for problem C. The intuition behind the solution and observation.

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

    I don't understand editorial. I'll just explain my solution.

    Sorry, I don't know how to explain it shorter
»
23 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Who can prove D's conclusion for me, why I don't feel so obvious?

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

    hello i did not get time to solve d in the contest but today i solved it without seeing the editorial, i'll tell you my implemetation. 1.)firsly we count the total number of ones in the (n*m) array, let's name it check, now we will like to distribute equal number of ones in all the n rows, now if check%n is not equal to 0, then we can not have our answer, otherwise we will like to distribute (check/n) number of ones to all the n rows, let's call this number req. 2.)now in all the n rows we will calculate the total number of ones present in it if it is greater than req, we will store the index of the row and the value in a map, and all the values less than req in another map and we will not touch the rows which have req no of ones, this can be done in (n*m) complexity which is allowed. 3.)now our task is to exchange ones between the rows which has smaller no of ones than required and with the ones which have larger number of ones required, note we already know about them in our two maps, both the index and the values, this can be done easily in ((n^2)*m) complexity by going row by row but sadly it is not allowed, here comes the tricky part:-> 4.)instead of going row by row we go column by column, each time we encounter a one in our column we will check if the row in which the one occurs is a row having larger number of ones than req using map, if yes we mark it and if we find a corresponding 0 for that one on the same column whose row has lesser number of ones than req, we exchange the value, vice versa goes for when we encounter a 0 and after the row having larger number of ones than required becomes equal to required we erase it from the map, vice versa for the row having lesser number of ones than required, this complexity for this process is order of n*m which is allowed, ignoring the logarithmic time complexities used for map. here is my submission: https://codeforces.net/contest/1774/submission/185759065

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

Hello everyone I am not able to understand the logic of question number d (same count one) from the tutorial. Can anyone explain the logic behind the d. I dont want to see the solution for d now because i want to try it first. Thank You...

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

    step1: find out all rows which have an excess of 1's and which have deficient 1's

    Swapping between ith, jth row in the kth column becomes valid only when a[i][k] != a[j][k] otherwise, after swapping, we will have the same matrix as before

    We need to minimize the operations.

    My claim :

    Given a row with excess 1's and another row with deficient of 1's, it is always possible to send one from the excess row to the deficient row. (i.e sum[excess_row] --; sum[deff_row] ++; )

    Proof :

    (By contradiction)

    Assume that you cannot do such swapping

    Let any excess row contain x1 ones
    Let any deficient row contain x2 ones

    => x1 > (sum/n) > x2

    If I cannot do such a swapping, it means that for every 1 in excess_row, the corresponding column in the deficient_row should also contain a 1.

    This implies
    => deficient row should contain at least x1 ones => x2 >= x1 But x1 > x2 This contradicts

    Our claim is correct

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

      thanks a lot for the proof. I had an intuition, but not being able to proof was really bugging me. Thanks again.

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

        you are the first person to reply to me , welcome pa

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

Any E solution in easy words?

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

    I'll try my hand at it.

    To make the problem a bit nicer to explain (imo), I'll label the $$$a_1,a_2, \dotsc ,a_{m_1}$$$ nodes as red and the $$$b_1,b_2, \dotsc ,b_{m_2}$$$ ones as green.

    We know that both nodes start at 1 and must return to 1, and so it's a good idea to root our tree at 1 as well. Let's consider an easier variant of the problem, where we only need to reach the red nodes.

    So first off, since the nodes must return to 1, we notice that every edge in the optimal paths is traversed twice (one to go, and one to return) for each of our pieces.

    If $$$d = n$$$, then we can simply keep the green piece back home at the root and let the red piece dance about. Let's suppose we know for each node whether it contains a red node in its subtree. Then it's clear that the minimum path that hits all red nodes AND returns to the root will traverse only the nodes that contain red nodes in its subtree. Crucially, it will traverse the edges twice and only twice (any more would be a waste).

    Okay, that's great, now let's see what happens if $$$d < n$$$. So, the green piece must follow the red piece within a certain distance like a leashed dog. Now, we want to move the green piece minimally. So what we can do is greedily move a green piece only if we need to. What do I mean by this?

    Let's assume we are at a root $$$r$$$ and both the red piece and green piece are here. Suppose $$$r$$$ has a child $$$c$$$ that has both green and red nodes in its subtree. We most definitely need to move both the green piece and red piece in that direction. (because we need to collect the green and red nodes). Thus, both red and green pieces traverse the edge from $$$r$$$ to its special child $$$c$$$, and we know that it must return back to the root (so it's gotta come back the way it came). Therefore, we can add $$$2$$$ for each piece, totaling to $$$4$$$ moves.

    Now, let's suppose $$$r$$$'s child $$$c$$$ only contains a red node in its subtree. Well, let's suppose we know the depth of the deepest red node in this subtree. If this depth $$$\text{maxDepth} \leqslant d+\text{depth}(r)$$$, then we clearly don't need to move the green piece. The red piece can do it all by itself. We can add $$$2$$$ for the red piece and recurse further into the subtree. Notice this also holds for the reverse case ($$$c$$$ only contains a green node in its subtree), aka WLOG.

    What if $$$\text{maxDepth} > d+\text{depth}(r)$$$? Well, we're gonna have to move the green piece in the direction of $$$c$$$, otherwise we violate the constraint. Note that this is very similar to the "+4" case where both red and green were contained in the subtree at $$$c$$$. So just like that, we add 4 and recurse further.

    We basically apply these two principles to every child and do a proper DFS through it. Now the question is, how do we calculate

    1. The max depth of a coloured node
    2. Whether a node contains a coloured node.

    You can do this in any number of ways but I find it easiest to just do a DFS beforehand to set everything up. Set up an int array maxRedDepth and when DFS'ing, if a node $$$v$$$ is red, then set maxRedDepth[v] = depth. Then take the $$$\max($$$maxRedDepth[c]$$$)$$$ of every child.

    185894910

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

      Detailed explanation. Thanks.

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

      when in your explanation, maxDepth > d + depth(r)? , are we assuming that the green piece and red piece are at the same place ?

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

        Yep.

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

          i am still not able to process it clearly, can you please simulate it over an example to help me understand clearly, like when +2 extra steps can help us when maxDepth > d + depth(r) can be greater than just one edge distance?

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

            Imagine that the tree is

            with $$$d = 2$$$, then it's clear that the red piece can't reach node 3 if the green piece doesn't move to 1.

            maxDepth of 1 will be 2, as the red node 3 is 2 levels down from node 1.

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

why in problem B we are doing (n-1)%k +1 instead of n%k. Any Particular reason???.

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

1774B - Coloring how to prove that number of $$$a_i$$$ which is equal to $$$\left\lceil \frac{n}{k} \right\rceil$$$ should be not bigger than remainder?

How to make sure construction works? Not for all segments there is $$$j$$$-th cell. Do we just skip segment if $$$j$$$-th cell doesn't exist?

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

    For a particular value of $$$k$$$, the number of segments $$$=$$$ $$$\lceil{\frac{n}{k}}\rceil$$$. Let's take $$$n = 12,$$$ $$$k=5$$$, then our segments will look like $$$[ __, __, __, __, __ ]$$$ $$$[ __, __, __, __, __ ]$$$ $$$[ __, __ ]$$$.

    Here $$$\lceil{\frac{n}{k}}\rceil = \lceil{\frac{12}{5}}\rceil = 3$$$

    Let $$$M[4] = [3, 3, 3, 2, 2, 2] = [a_1, a_2, a_3, a_4, a_5]$$$. Let's start filling the segment:

    After filling $$$a_1$$$:

    Segment $$$=$$$ $$$[ a_1, __, __, __, __ ]$$$ $$$[ a_1, __, __, __, __ ]$$$ $$$[ a_1, __ ]$$$

    $$$M[4] = [0, 3, 3, 2, 2, 2] = [a_1, a_2, a_3, a_4, a_5]$$$.

    After filling $$$a_2:$$$

    Segment $$$=$$$ $$$[ a_1, a_2, __, __, __ ]$$$ $$$[ a_1, a_2, __, __, __ ]$$$ $$$[ a_1, a_2 ]$$$

    $$$M[4] = [0, 0, 3, 2, 2, 2] = [a_1, a_2, a_3, a_4, a_5]$$$.

    Now you see that there is no way to fill $$$a_3$$$ such that the distance between any two $$$a_3$$$ is $$$k$$$.

    Hope this answers your question

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

      maybe it doesn't work just because very first arrangement of $$$a_1$$$ is already wrong, and if you put them in other way, it will somehow turn out. I don't need "see" explanations, I need rigorous one.

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

        How is the first arrangement of $$$a_1$$$ wrong? Since $$$a_1$$$ has the maximum frequency, it makes sense to handle it first and place it at the first position of the first segment since this position will definitely provide the distance of $$$k$$$ in the next subsequent segments.

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

          There is also: following possibilities

          [ a_1, __, __, __, __ ] [a_1,  __, __, __, __ ] [__,  a_1 ]
          [ a_1, __, __, __, __ ] [__,  a_1, __, __, __ ] [__,  a_1 ]
          [__,  a_1, __, __, __ ] [__,  a_1, __, __, __ ] [__,  a_1 ]
          

          Why you arguing about first one. May be for one of other it will work?

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

            First of all, notice that your second arrangement is wrong since you won't be able to place $$$a_2$$$.

            Hmmm, okay let me phrase it like this:

            Let $$$K'$$$ $$$=$$$ $$$(n \% k \equiv 0$$$ $$$?$$$ $$$k : n \% k)$$$ --> The size of the last segment.

            Let the suitable indexes in the $$$last$$$ segment be $$$[1, K']$$$

            The only way to place first $$$K'$$$ elements having value equal to $$$\lceil\frac{n}{k}\rceil$$$ in the $$$last$$$ segment is to place them in the suitable indexe of the $$$last$$$ segment. After you have placed them in the $$$last$$$ segment, one sure way to place them in the remaining segments without violating any condition is to place them cyclically at distance $$$k$$$. Now we have $$$\lceil\frac{n}{k}\rceil - 1$$$ segments remaining. If there is one more element having value equal to $$$\lceil\frac{n}{k}\rceil$$$, we won't be able to place that element without violating the condition. There are less segments and more values, then by the Pigeon-Hole principle, there will be two values in the same segment(box). The distance between these two same values will be less than $$$k$$$.

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

              Actually placing the first $$$K'$$$ elements having value equal to $$$\lceil\frac{n}{k}\rceil$$$ in the $$$last$$$ segment and then cyclically placing them in the next segments is the only way.

              Proof: Note that right now we are only dealing with those elements having value equal to $$$\lceil\frac{n}{k}\rceil$$$.

              Let's increase the distance between any two same elements (Let's call them $$$A$$$) in any consecutive segment by $$$x$$$. The new distance is $$$k+x$$$. Then the distance between the element $$$A$$$ in the next segment and the current segment decreases by $$$x$$$ making it $$$k-x$$$. To accommodate this change, the $$$A$$$ in the next segment will have to be moved by at least $$$x$$$. This creates a chain reaction that will reach the last segment. Since the size of the last segment is less than or equal to $$$k$$$, then $$$A$$$ in the last segment will have nowhere to move. So we can say that placing the element in the last segment decides the order in the next subsequent segments.

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

                This creates a chain reaction that will reach the last segment.

                Sometimes "chain" reaction would be resolvable, but you phase it like it will always fail: example:

                n = 11, m = 5, k = 3
                a = [3, 3, 2, 2, 1]
                [1, 2, 3, 4] [1, 2, 5, 3] [4, 2, 1]
                [1, 2, 3, 4] [1, 2, 5, 3] [4, *1, 2*]
                

                Please, stop claim you know proof when you don't. It obstruct comments section.

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

                  You wanted an explanation of the case when frequency of values equal to $$$\lceil\frac{n}{k}\rceil$$$ exceeds the remainder. I gave an explanation for that.

                  Why are you giving a rebuttal with an invalid test case?

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

                  Because I don't see why similar thing may not happen. If you're talking about case which is you claim is impossible, then starting from some arrangement and then extending distance is odd idea. Because if it's already impossible, why then we extend distance. If it's possible, then claim is wrong. If you consider some unfinished filling, with empty spots, then you just may consider my example with all colors > 2 not yet filled:

                  n = 11, m = 5, k = 3
                  a = [3, 3, ?, ?, ?]
                  [1, 2, _, _] [1, 2, _, _] [_, 2, 1]
                  [1, 2, _, _] [1, 2, _, _] [_, *1, 2*]
                  

                  Why I send this example, because this "chain" of reactions is perfectly fine, because one color just jumps to the front (but you claim it should only move farther, I'm extending distance between two cells of color 2)

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

              First of all, notice that your second arrangement is wrong since you won't be able to place $$$a_2$$$.

              Then why in your first reply to my question not just say "we can't place a1 in first places of all segments because we can't place $$$a_3$$$ then". It's not a proof if you tried all possibilities for some example and it didn't work.

              The only way to place first $$$K′$$$ elements having value equal to $$$\left\lceil\frac{n}{k}\right\rceil$$$ in the last segment is to place them in the suitable indexe of the last segment.

              Claim without reasoning. Many other statements also without reasoning.

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

    I came up with proof of first claim myself. Here it is.

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

Please add a test case with t=1; n=2; m=500000 in Problem D. the First array with all 1's and 2nd array with all 0's. I have seen many solutions with M^2 in solution getting accepted. Please look into it. 185717356

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

    In fact, you can hack it. However, I have hacked it.
    Thank you for providing the test.

»
23 months ago, # |
  Vote: I like it +20 Vote: I do not like it

My unproven solution to G:

We must start with an interval with $$$x=l$$$. Choosing an interval with the highest $$$y$$$ is irrelevant because whether you choose one with lower $$$y$$$ or not is pointless so the sum is $$$0$$$ so we can ignore it; that repeats until you get to the interval with lowest $$$y$$$, let's call that lowest $$$y$$$ $$$e_1$$$. Now the new intervals are the ones with $$$x$$$ in $$$[l+1,e_1]$$$; once again we find the interval with the lowest $$$y$$$ out of the ones which have $$$x$$$ in $$$[l+1,e_1]$$$, call that lowest $$$y$$$ $$$e_2$$$, continue the process with $$$[e_1+1,e_2]$$$, etc. until $$$e_i=r$$$ or we see that that's impossible, if it's impossible then the answer is 0, otherwise whether it's $$$1$$$ or $$$-1$$$ depends on the length of the path.

I precompute all the intervals which are possible to reach using this process and use binary lifting to answer queries. Code: 185786867.

The unproven part is the complexity; I don't know how many intervals are possible to reach using this process. It's not hard to see that the sum of lengths of intervals is $$$O(n^2)$$$, which means that there can be at most $$$O(n\sqrt{n})$$$ of them. Is there a better upper bound on the amount of reachable intervals?

  • »
    »
    23 months ago, # ^ |
      Vote: I like it -18 Vote: I do not like it

    The solution for G is a bit strange.

    If there exist two segments (l1,r1),(l2,r2) such that l1≤l2≤r2≤r1 and we choose (l1,r1), number of >ways of choosing (l2,r2) at the same time will be equal to that of not choosing. Hence if we >choose (l1,r1), the signed number of ways will be 0. So we can delete (l1,r1).

    This is not true. For eg. if the segments are $$$[1,3],[4,6],[2,5],[3,4]$$$ and $$$[l,r]$$$ is $$$[1,6]$$$, then the answer is equal to $$$1$$$ (not zero) and also $$$[2,5]$$$ contains the segment $$$[3,4]$$$.

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

      Why did you reply to my comment? Your reply is completely irrelevant to my comment.

      I recommend reading the part of the editorial that you quoted more carefully. It just says that the solution will stay the same if we delete $$$[2,5]$$$, not that the solution is 0 due to its existence.

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

Totally blown away by the knapsack trick in F2 of the array where $$$2a_{i-1} \lt a_{i}$$$. Is it a well-known trick among high rated contestants, or is it something ad-hoc for this problem?

Tagging the author of the Problem Little09

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

    In my opinion, some high rated contestants might have seen it in other problems. However, when I made this problem, I was unfamiliar with the trick. But I think it is not difficult to solve it after observing $$$a_i>\sum_{j=1}^{i-1}a_j$$$.

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

https://codeforces.net/contest/1774/submission/185708026 Can anyone help me, why is my submission wrong?

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

Can anyone tell what's wrong in my approach for Problem-E, 189112092 its failing at test 20...

My approach: I am first calculating minimum number of steps separately for the two chess pieces. For each piece, for a particular node, if there exists a node in its subtrees (or the node itself) which is supposed to be travelled(is in the piece's sequence), then increase the number of steps by 2 as we will have to reach the root node of that subtree atleast once. This path of nodes is marked(coloured) separately for both nodes. At the end, subtract 2 from steps as the piece was already there on the root of the whole tree.

Then I am calculating the extra steps separately for each piece that they will have to travel. For each piece, at a particular node which has to be traversed atleast once, if the other piece's marked path's distance becomes more than 'd' (given in ques), then increase number of steps by 2, as we will have to pull down the other piece atleast one node down.

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

map<int, vector<int>> adj; vector<int>red(2e5 + 1, 0), blue(2e5 + 1, 0), occ(2e5 + 1, 0); map<pair<int,int>, int > edges; int ans = 0; //solve function return max depth of the found vertices... int solve(int v, int p,vector<int>&m) { bool b = 0; if(m[v]) b = 1; for(auto it : adj[v]) { if(it == p) continue; int k = solve(it, v, m); if(k) { edges[{it, v}] += 2; edges[{v, it}] += 2; ans += 2; } b |= k; } return b; } int func(int v, int p, int d) { int maxi = -1; if(occ[v]) maxi = 0; for(auto it : adj[v]) { if(it == p) continue; int k = func(it, v, d); if(k < 0) continue; else { if(k > d && edges[{it, v}] < 4) { edges[{it, v}] += 2; edges[{v, it}] += 2; ans += 2; } } maxi = max(maxi, k); } if(maxi == -1) return -1; return maxi + 1; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, d; cin >> n >> d; for(int i = 1; i < n; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } int sz; cin >> sz; for(int i = 0; i < sz; i++) { int k; cin >> k; red[k]++; occ[k]++; } int a = solve(1, -1,red); cin >> sz; for(int i = 0; i < sz; i++) { int k; cin >> k; blue[k]++; occ[k]++; } a = solve(1, -1,blue); a = func(1, -1, d); cout << ans << endl; }

Easy Solution for Problem E with Neat code

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

In problem C, lets consider x = 3 in the first test case

string = 0 0 1

array = 1 2 3 4

It is already mentioned in the notes section that player 2, 3 and 4 can win this round, but what about player 1?

condition for 1 to win: 4 beats 2 (ground 1), 3 beats 4 (ground 0) and 1 beats 3 (ground 0)

Is this not right?