Vladithur's blog

By Vladithur, history, 4 months ago, In English

Hope you liked the problems! We apologize for the (very?) weak tests in H.

Editorials for problems will be added over time (and hints), for now, please take a look at the available hints and model solutions.

Easter eggs

1987A - Upload More RAM

Hints
Tutorial
Solution
Feedback

1987B - K-Sort

Hints
Tutorial
Solution
Feedback

1987C - Basil's Garden

Hints
Tutorial
Solution
Feedback

1987D - World is Mine

Hints
Tutorial
Solution
Feedback

1987E - Wonderful Tree!

Hints
Tutorial
Solution
Feedback

1987F1 - Interesting Problem (Easy Version) and 1987F2 - Interesting Problem (Hard Version)

Hints
Tutorial
Solution (F2)
Feedback (F1)
Feedback (F2)

1987G1 - Spinning Round (Easy Version)

Hints
Tutorial (by errorgorn)
Solution
Feedback

1987G2 - Spinning Round (Hard Version)

Hints
Tutorial
Solution
Feedback

1987H - Fumo Temple

Please try solving the problem with a deterministic solution :)

Hints
Tutorial
Solution
Feedback
  • Vote: I like it
  • +195
  • Vote: I do not like it

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

Tutorials are broken

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

    If an editorial isn't showing properly, it should be because there currently isn't one.

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

      Oh alright, thanks for the great contest btw :)

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

Can someone please explain why greedy won't work for D? My solution: https://codeforces.me/contest/1987/submission/268165706

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

    This is the exact greedy solution I did.But not able to figure out why it fails.

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

      Did you remember monotonicity? I messed up b/c of it.

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

    Sorting by freq won't work here as someone with higher freq that has a lower tastiness would be eaten by alice which could be prevented by bob by eating that first

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

    Check for this frequency array F = {4, 4, 4, 3, 5, 5, 2}

    Correct answer is 5

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

      Sort: 2 3 4 4 4 5 5

      Alice: 2

      Bob: 3

      Alice: 4

      Bob: 5

      Alice: 5

      Bob: rest two 4's

      So Alice will get total 3 cakes. This is what i was trying greedily but it didn't worked, can you tell me what i am doing wrong here?

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

        Given array F is Frequency array, not the array containing tastiness values of the cakes. F[i] contains number of cake with tastiness value i.

        Check this comment

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

          Let the array you mentioned is tastiness array, then is my approach correct?

          Or let tastiness = {4,3,2,5,6,8,3,4} then after sorting:

          2 3 3 4 4 5 6 8

          A/c to my approach:

          Alice: 2 Bob: 5 Alice: 3 Bob: 6 Alice: 4 Bob: 8

          Now Alice can't choose any so total she will choose 3 cakes.

          Is this a correct approach, Bob will choose the cake whose frequency is as minimum as possible and greater than Alice's last chosen cake.

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

            This approach wouldn't work always.

            Check for this = {1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 5 5 5 5 5 6 6 6 6 6 7 7}

            According to your approach, Bob will start with 7 but optimal is start with 4 and complete it then take 7.

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

              Got it, thanks!

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

              My approach is as follows:

              Alice 1 Bob 4 Alice 2 Bob 4 Alice 3 Bob 4 Alice 5 Bob 7 Alice 6 Bob 7 But I get wrong answer on test 2. 268201241 Can you help, please?

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

    Please simulate the last test case to know why greedy won't work.

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

Problem G1 coincides with QOJ 3797 Wireless Communication Network.

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

    Seems like G1 unfortunately does :( The subtask was added later to help balance the problemset and we weren't aware of such a coincidence.

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

Problem D. World is Mine ***** 2 pointer approach -> sorting the array -> (i)one pointer of alice is on left -> (j)bob's pointer is on right . HashSet -> cakes have been eaten by the alice -> i encounters a cake at a[i] -> if the a[i] is already present in the set -> not present -> cake is added in set -> j encounters a cake at a[j] . didn't work can anyone pls tell me why.

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

I have a $$$O\left(n \log n\right)$$$ solution for D. https://codeforces.me/contest/1987/submission/268177088

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

    can you please explain?

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

      ok! Obviously, we need to iterate through all the elements in smallest-to-largest order to simulate Alice's choices, and I'm using a std::map to keep track of how many of each number there are for subsequent calculations. First, I'll try to have Bob try to stop Alice from selecting the current element every time, and for convenience we'll write the number of times the current number occurs as $$$c$$$. This requires that Bob has been unable to stop Alice at least $$$c$$$ times before, so we'll maintain a variable ("hv" in the code) representing the number of times Bob has been unable to stop Alice. But the above is clearly wrong. We need to reverse the operation. Specifically, if we are now certain that we cannot stop Alice, we replace this operation with the previous successful stopping operation, the most consumed one, if that is preferable. In the code, I use a std::multiset to keep track of successful blocking operations.

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

      I wrote a version with comments, which should be easier to understand https://codeforces.me/contest/1987/submission/268356662 I understand this as there might be a tastiness appears later, that costs less "skip points" than the skip before, so you record all the skip happen in the previous, and keeps finding for better solution which costs less rounds for b that happens later

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

nice problem h guys, really appreciate your testing

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

    yes, it seems that they just generated 300+ random tests and thought "hmmm, maybe on some test the square will get a time limit")))

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

    268226747

    It seems like this solution uses no more than $$$50$$$ queries on the current data. Can anyone construct a counter-test?

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

      Sure.

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

        Cool. Do you have any estimate of how many queries are used for the test you constructed (as a function of $$$N$$$)?

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

          I guess $$$\mathcal{O}(\sqrt{N})$$$? The idea is to have a square of $$$1$$$s in the corner (and also the hidden cell there). So almost wherever you ask, you see something around $$$x+y+(\sqrt{N})^2$$$, so it only tells you that the hidden cell is not in this area (so you discard around $$$N$$$ cells, but we can show better). What gives you more information is asking about a rectangle that won't contain all $$$1$$$s. My initial idea was that if we get an answer larger than $$$N$$$, then we discard the area around the queried cell (hopefully discarding around $$$N$$$ cells), and if we get an answer smaller than $$$N$$$, then we restrict ourselves to a square (hopefully decreasing the number of cells geometrically). But yeah, it seems that it's even better. Also Idk what about $$$M$$$ much larger than $$$N$$$, probably you can show something too. I was mostly worried about TL and spent most of the time thinking how to optimize it, but it just passed, so...

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

            Oh, actually (on a square grid) response greater than $$$N$$$ tells you that you can discard around $$$N \log (N)$$$ cells (a shape enclosed by hyperbolas).

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

E can be solved in $$$O(N\log N)$$$ time by replacing the vectors in my solution 268156681 with mergeable priority queues.

(or even $$$O(N)$$$ if we compress equal keys in the priority queue and merge the priority queues in time proportional to the smaller subtree depth)

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

    I think my submission for E works in O(NlogN) using small-to-large merging technique. 268419277

    Let diff[node] be difference between a[node] and (summation of a[child]). Each subtree maintains a set of nodes ordered by depth such that diff[node] < 0. On DFS, if diff[currentNode] > 0, take first node in the set, update result and diff[firstNode]. To combine the sets of each child to parent, small-to-large merging is used.

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

      Actually I think it is $$$O(n \log^2 n)$$$. One is for dsu on tree and the other is for std::set.

      By using mergeable priority queues, the problem could be solved in $$$O(n \log n)$$$.

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

        dsu is not used. For each node in DFS, either first element in set gets erased or diff[currentNode] becomes zero. As the number of elements in the set for a subtree is atmost n, this takes O(nlogn) time. Merging subtree for all nodes takes O(nlogn) time separately. I think this analysis is similar to amortized time complexity analysis.

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

          I'm sorry for not understanding what you said and I believe it's still $$$O(n \log^2 n)$$$. We can assume that the tree is already a wonderful tree, so we don't need to make any modifications to it. So according to your code, small-to-large merging is $$$O(\log n)$$$, and inserting them into the set is $$$O(\log n)$$$. What's more, we won't delete or modify the elements. So I think it's $$$O(n \log^2 n)$$$. I may not have understood your code and words. If there are any issues, please point them out.

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

    I thought this idea was really neat, so I decided to write my own implementation of it with some comments to make it accessible. Thanks for sharing! 271969422 O(n) per test case

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

Personally, I like this round very much, not because I get positive delta, but because the problems are really cool. D & E are easy problems but they require you to seek for the solution (that is, I don't get the solution as soon as I read the problem statement). I think that reminds me how to set problems like this.

UPD: It seems that the straight greedy solution to E works well. However I was writing minkowski sum, which seems of more correctness to me.

The model solution for F seems fascinating (thus I'm looking forward to seeing the editorial soon) because my solution works in the same time complexity but is much more complex than yours (as a result, I've made many, many mistakes in some of the details). And I got WA on 3 on G1 during contest time. For now, I've understood why my solution to G1 is wrong through several small hacks. Sorry for being so weak, but I will try to spend more time solving G2 and H.

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

I wonder whether using min cost max flow was expected to pass in E (268173238)

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

D can also be solved NlogN by using priority queues

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

Waooo...

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

Can anyone please help me understand why my idea for problem D is not working?

Here is what I am trying to do.

Alice always takes smallest number. Bob takes any number bigger than what alice took which also has the smallest frequency and alice won't be able to reach it.

code: https://codeforces.me/contest/1987/submission/268190399

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

    Bob sometimes may want to eat a less tasty cake with a higher frequency over a cake that has lower frequency but high tastiness.

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

      Could you give example?

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

        Let there be cakes with tastiness 1, 2, 2, 3, 3, 4, 4, 4, 5 Bob will want to eat the cakes with tastiness 3 first.

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

          Thank you so much.

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

      But how does Bob decide which particular cake to eat?

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

E. Tell me if my approach is correct or not. First, you calculate sum of values of direct children, just below, for every node, lets call it sum[i] for node i. Next we do a dfs traversal. For leaf nodes we do not have to do anything. Then for others nodes, if val[i]>sum[i], then we need to perform some operations. We need to add exactly val[i]-sum[i] to one of the child node, but in doing so you are changing the value of child node, which can result in val[child]>sum[child], and if this happens, you just need to add val[i]-sum[i] again to the child's children node, and so on.

If I am going in the right direction, do tell me. If not, please point out the mistake.

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

    "We need to add exactly val[i]-sum[i] to one of the child node": this is wrong
    Example tree:


    4
    1 1
    2 2
    In this example you add 1 to each node in the second row, total cost 2. If you add 2 to a node, the cost will be 3
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      268472191

      can you please help me why am i getting WA, my approach- first calculated the min distance from the node to a leaf node in height vector and in diff vector stored the value a[node]-(sum of a[child])

      then for each node , if diff>0 this means that child nodes needs operations to be done,so i check if there is any child node such that its value can be increased without further nodes being affected then for the remaining difference i just multiply the distance stored in height vector Please point out the mistake

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

I am curious on why a Greedy solution of removing the highest pair for problem F doesn't work. Couldn't find the counterexample during the contest. Example: https://codeforces.me/contest/1987/submission/268216353

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

    1

    8

    1 1 3 4 1 2 2 1 taking the last pair gives 3 but there is optimal order to erase the whole sequence

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

Why iterating over the maximum possible cake Bob could remove and choosing the others greedely yields an incorrect answer? serious question

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

dp-forces

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

Could somebody explain me, how to solve D using DP, please?

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

    I have used 2D DP. First state is for distinct positions and 2nd state is for Bob's time to eat all cakes of a specific tastiness. Bob will try to eat cakes in ascending order of their tastiness. He should eat all the cakes of a type so that Alice can't eat that type of cake. Bob will have 2 options.

    1. Either he will eat all copies of a cake if he has enough time before Alice reaches to that type.
    2. He can skip the cake and will move to the next one.

    You can see my code for better understanding: https://codeforces.me/contest/1987/submission/268196842

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

    Firstly, it could be seen that the optimal strategy for Alice is to eat cakes in ascending orders of tastiness from the smallest to largest one. So if Bob wants to minimize her overall number of cakes, he must try to eat up all cakes of some particular tastiness in order to avoid Alice eats that type of cakes (I used the term type here instead of tastiness from now on for convenience). So let's get the frequency of each type of cakes and sort those in ascending order of tastiness. Let $$$dp_{i,j}$$$ be the minimum number of cakes that Bob will eat if we consider the first $$$i$$$ types and Bob has been eaten $$$j$$$ types of cake. The transition is pretty simple, but we need to ensure that the number of cakes that Bob eats needs to be smaller or equal to Alice does at any time of the transition. The answer will be the total number of types minus the maximum number types that Bob could eat which can be checked by the valid transitions we made.

    Submission: 268186295

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

    Have a look at my explanation in another thread.

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

The problem were very interesting thank you

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

C was also doable regardless of direction.

The formula for the time taken, assuming the $$$i$$$th column is the bottleneck is: $$$h_i + i$$$ (proof is simple)

So we just try out all $$$i$$$ and get the one that gives the max $$$h_i + i$$$, that would be the real bottleneck.

https://codeforces.me/contest/1987/submission/268234160

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

    Can you please help me prove it.

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

      I should first clarify what I mean by bottleneck. Check out this example for initial heights 1 2 3 5 4:

         #
         ## 
        ### 
       ####
      ##### 
      12354
      

      The fourth flower is the "bottleneck" because it is taller than all the flowers behind it hence nothing from behind will stop it from going down every second (this is only the initial idea, we later explain how index, aka width, comes into play).

      Hence, the fourth flower reaches height 1 after 4 seconds.

      Notice how the previous flower heights will be dragged down along with the fourth column (we ignore after 4):

      1235-
      1234-
      1233-
      1232-
      1221-
      1210-
      1100-
      1000-
      0000-
      

      There's this pattern where when $$$h[4]$$$ ($$$1$$$ indexed) is first $$$0$$$, then $$$h[3]$$$ is $$$1$$$, and so on...

      Hence after $$$h[4]$$$ is $$$0$$$ it will take $$$(4 - 1)$$$ seconds for the rest to become $$$0$$$.

      When we're $$$0$$$ indexed, the index of the fourth flower is $$$3$$$ anyway. Hence the $$$h_i + i$$$ formula.

      Also in case you're wondering, it doesn't matter if the sequence behind is monotonically increasing (the explanation is a bit long but think of the other extreme where it's actually monotonically decreasing before the bottleneck).

      Now it's perfectly possible something after the fourth column was the real bottleneck, especially since using this formula we got $$$h_i + i$$$, so there's an aspect of width to it too, not just height, hence why we take the max over the whole array.

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

Can anyone please explain to me why the second loop is used in problem D in the tutorial?

Here's the code: --->

int n = a.size();
vector<int> dp(n + 1, inf);
dp[0] = 0;

for (int i = 1; i <= n; i++) {
    vector<int> ndp = dp;

    for (int k = 1; k <= n; k++) {
        int nv = dp[k - 1] + a[i - 1];

        if (nv <= i - k) {
            ndp[k] = min(ndp[k], nv);
        }
    }

    dp = ndp;
}

It would be very helpful if someone could explain it. Thanks in advance! ^-^

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

Is the example array in problem F’s tutorial wrong? The array is [1,2,5,4,5,7,1,8] ,how can we remove a[7] and a[8] when a[7] != 7?

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

Can someone please review my profile and guide me ? I have tried different problems of different ranges(900-1300 more frequently ), but still I am unable to think of even the easiest problems for eg I was unable to think in correct direction for C (which was probably of the range 1100-1200) and took a lot of time for B and came up with a difficult and unnecessary approach compared to other solutions for problem B. Can someone please guide me on how can I improve from my current situation? it would me a lot of help for me Thankyou

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

    I do not personally think C was that easy though it had around 8k submissions, B was easy once you see whats actually happening, i would suggest you to solve codeforces ladders on your own as well as give virtual contest regularly, it would definitely help you grow!

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

      Thankyou Sir, and can you tell me more about Code Forces ladders ?

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

        Google them they are a set of 100 questions for each difficulty ranging from A to F.

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

In problem C, Ive seen that most have used dp to solve it. Ive spent the past 5 hours to prove that the approach is correct.

I could only prove the following 1987C - Сад Бейзила 1. if A[i] > dp[i+1]+1 => dp[i] = A[i]

I was not able to prove the other parts. And Im also wondering how the guys had gotten the idea and were also able to prove this confidently in a decently less quantity of time.

Could someone please help me...

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

    We let dp[i] be the seconds for arr[i] to reach 0. As you have proven, if arr[i] > dp[i+1] or i = n, then dp[i] = arr[i].

    So now let's assume arr[i] <= dp[i+1]. We need to prove that this means dp[i] = dp[i+1] + 1.

    First off, it's easy to see that dp[i+1] + 1 is a lower bound for dp[i]. In order for arr[i] to reach 0, arr[i+1] needs to have reached 0 too, and two consecutive elements of arr can never both decrease and reach the same value at the same second.

    Therefore dp[i] >= dp[i+1] + 1.

    Now let's establish that dp[i+1] + 1 is an upperbound for dp[i]. Suppose that it is not, and that dp[i] = dp[i+1] + c, for a constant c > 1. Then, after dp[i+1] seconds, arr[i+1] = 0 and arr[i] = c. That implies that arr[i] and arr[i+1] never got equalized, therefore arr[i] > arr[i+1] should hold. But if arr[i] can keep getting decreased while never getting equalized with arr[i+1], then dp[i] = arr[i] -> dp[i] <= dp[i+1] -> dp[i] < dp[i+1] + 1, and that violates the lowerbound.

    Therefore the upperbound is dp[i+1] + 1.

    Lowerbound is equal to upperbound, therefore if arr[i] <= dp[i+1], dp[i] = dp[i+1] + 1.

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

In the problem F I just traversed from the back and whenever I find the element satisfying the condition just delete it and next element and then again traverse from the back again. doing this until we can. Most of the test cases are passing. Can someone please help. My solution 268194520

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

so? everybody can provide solution pieces and make it a full solution?

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

Can someone please review my profile and guide me ? Thank you :-)

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

The sample input in problem F is kind of weak so that even I mistakenly typed a <= as a >=, it would pass the sample.

I consistently received Wa On Pretest 2 until I realized what a stupid mistake I had made.

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

    me too bruh btw the sample is too weak I think, since any kinda algorithm can pass so I got a lot WAs on pretest 2 or 3.

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

Upsolved G1 with dp:

Since we know that the paths leading up to the root don't collide, we can keep track of 3 dps for each section, where segment i represents all numbers from l_i+1 to r_i-1. We can keep track of longest single path up to p_i, longest sum of lengths of two paths such that the root of the left path has higher p vale, and same thing but with the right path. Then, we can calculate answer by going through all the root positions.

Submission: https://codeforces.me/contest/1987/submission/268250482

Update: it also worked for G2 with some (annoying) changes!

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

Too much DP.

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

How can C be solved if height can also be 0? Like test 9 0 9 0 and answer 9. I was wondering that the whole time and then realized the constrains :(

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

    it can be seen that ranges separated by 0 do not affect each others

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

I spent 30 more minutes just to realize $$$O(n^3)$$$ can pass F2 lmao...

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

not my best performance but atleast i got the references

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

Cheating has increased so much . At this point solutions should be leaked intentionally which fails on main test and passes the pretests . This would be good way to catch cheaters which changes the code using AI to avoid plag checks .

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

OMG, a CrossCode reference! That game was amazing, not nearly well enough known considering how good it is.

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

I'm very much curious to learn that for problem D, is there any other approach than dp?

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

For those who were not able to understand the DP solution of D. 268157606

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

good blog

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

.

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

Can anyone explain me the dp in problem D how is it working and I am not able to see dp logic generally in problems how can I become better at it ?

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

someone please explain why my code for problem E is giving wrong answer on testcase 2 below is my submission https://codeforces.me/contest/1987/submission/268323462

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

Solution of problem D with priority_queue:

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

Can someone please help me to understand whats wrong in my B solution?

code: https://codeforces.me/contest/1987/submission/268337048

1 -> put all differences in a ascending order heap

2 -> for each peek, i know i can pick a maximum k equals to heap size, and i can pick it peek times

3 -> sum coins and sum shifts from previous peek to next elements

4 -> Ex:

4 8 16

I know i can choose K = 3, 4 times I'll spend (3 * 4 ) + 4 coins = 16 coins Shift 4 for all next -> 4 12 continue

Whats wrong, pls? X-X Fails here: wrong answer 11th numbers differ — expected: '2020469122', found: '1207241465'

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

I came up with a solution to G1 during the contest, but it failed on pretest #3. The idea is to build the cartesian tree first, than enumerate the root of the diameter, which seperates it into two parts.

When dealing with root u, first consider if the two parts come from different subtrees, which can be done by calculating the maximum depth in the subtree. It can be proven that going up from v to u on the cartesian tree is the longest way in all possible trees according to the constraints.

Second, consider if the two parts come from the same subtree (for example, the left one). First we set v to the left son of u and keep going to its right son, and pull out the chain (the points on the chain are the only points whose $$$r_v$$$ is u). The diameter we are considering is made by fliping one choice from $$$l_v$$$ to $$$r_v$$$. By enumerating the point that is flipped, we can find the longest route. Since one point will be enumerated only twice, the complexity is $$$O(n)$$$.

(Maybe it is hard to understand and you may have to check the code)

I wonder whether the algorithm itself is right and how to hack it.

Submission

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

Can someone recommend similar problem to D but easier, like 1400, 1500

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

Thank you for the amazing contest

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

Problem F is so beautiful, I love it. Also how did I miss the Celeste reference in problem H lol

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

void solve() {
ll n ;
cin>>n ;
vll v(n);
for(int i=0;i<n;i++){ int x ; cin>> x; v[x-1]++; } vll a; for(int i=0;i<n;i++){ if(v[i]!=0) a.pb(v[i]); }

int m=a.size();


  vector<vector<ll>> dp(m+1,vector<ll>(m+1,-1));

  dp[0][0]=0;

  for(int i=1;i<m;i++){

    for(int j=i;j>0;j--){

        dp[i][j]=dp[i-1][j-1];


        if(j>=a[i]){
            dp[i][j]=max(dp[i-1][j-a[i]]+1,dp[i-1][j-1]);
        }


  }

}

// for(int i=0;i<m;i++){ // for(int j=0;j<m;j++) // cout<<dp[i][j]<<" "; // cout<<endl ; // }

ll ans=0;
  for(int i=0;i<m;i++)
    ans=max(ans,dp[m-1][i]);
 cout<<m-ans<<endl ;

}

can anyone correct this code for D. I cant able to figure it out.

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

More tasks like D??Thanks

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

Can someone tell me why my code is not working? I am getting a runtime error in test case 9 https://codeforces.me/contest/1987/submission/268383994

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

Solution for G1 (440ms & 132MB):

Define

$$$f(\text{int l},\,\text{int r},\,\text{bool lemax},\,\text{bool remax}) = (\text{maximum diameter},\,\text{maximum depth},\,\text{maximum sum of depths of two vertices where one is connected to lemax and one to remax})$$$ if we only consider indices $$$[l,\,r]$$$ and the possible two extra vertices. If $$$\text{lemax} = \text{true}$$$ we also have a vertex to the left that we can connect to, similarly for $$$\texttt{remax}$$$, there's a vertex to the right if it's true. Also note that there's no restriction for the vertices to form a connected graph, because only the maximum must be connected to itself, for all the rest we can reconnect it if we had connected it to itself previously, thus being unconnected wouldn't be a better solution for any of our outputs.

One can easily calculate $$$f(l,\,r,\,\text{lemax},\,\text{remax})$$$ from $$$f(l,\,m-1,\,\text{lemax},\,1)$$$ and $$$f(m+1,\,r,\,1,\,\text{remax})$$$ where m is the index of the maximum element in $$$[l,\,r]$$$. I won't bore you with explanations and different cases that may occur, you can read more in my G1 submission.

Solution for G2 (420ms and 132MB):

Do the same but instead of maximum depth, we output two maximum depths, one for vertices connected to the left and one to the right. Again, the detailed explanations are nothing crazy, but here's my G2 submission.

Overall I loved E and F and liked the rest. They'll be good problems for practicing as well. Thanks very much. Also, this might interest you Vladithur

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

    In G2 the different cases that may occur will handle forced edges.

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

    wanted to point out another similiar dp like recurrence approach.

    For G1, my initial idea was to categorize shapes into 3 broad classes : path (self explanatory), hill (2 paths from opposite sides merging at the highest element), skewed_hills (2 paths from same side merging at highest element)

    You naturally get left and right skewed hills. This is nearly enough for writing the dp recurrences for G1, except you notice that sometimes a technically invalid skewed_hill can later on be made valid. (for example consider a case like 5 2 1 3 4)

    I had to maintain 2 extra variables called skew_right_bad and skew_left_bad respectively. You can check my code for exact details of the recurrences https://codeforces.me/contest/1987/submission/268296892

    A similiar approach can be made to work for G2 but it is much cleaner to categorize things by actual properties instead of their shapes.

    I needed the following properties :

    one_path[dir] = largest path which can be extended in direction dir

    two_path[dir1][dir2][max] = largest set of 2 paths where the first path can be extended in direction dir1, second path in direction dir2, and the maximum element is path numbered max.

    Submission : https://codeforces.me/contest/1987/submission/268339806

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

Epic

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

For problem E I traverse each node and return a list of information in each node
https://codeforces.me/contest/1987/submission/268349130

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

Really enjoyed solving problem E! It took me a long time to come up with the idea but eventually I figured out I could treat each node as either a "source" or a "sink". Then we must send the difference between parents and their children down to sink nodes, in BFS order to minimize cost. Then it becomes clear that the cost to use a sink node is dist * difference, and we can use the sink node until it is equal to the sum of its children, or infinitely if it is a root.

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

Can someone explain the formal proof to the claim in Hint 3 of problem E?

it is not less optimal to apply the operation on (v1,w2) and (v2,w1).

or why the bottom up approach works in the small-to-large solution?

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

So how soon can we see the tutorial of problem G & H

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

To the problem F, can anyone tell me Why is the dp transition written that way? for this sentence: op =max(dp[l+1][m−1],dp[m+1][r]−(m−l+1)/2) I have some difficulties in understanding the content after the transition of dp

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

    I think it's typo in editorial. Read the solution code

    in the code:

    $$$op = max((l + 1 - a[l]) / 2, dp[m + 1][r] - (m - l + 1) / 2);$$$

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

Can somebody tell me whats wrong with this solution ? 268517922

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

F problem is really nice! Thanks for the round.

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

Could someone please explain the dp transitions for F1 if the dp state is dp[l][r][k] -> max operations on interval [l,r] if exactly k operations are performed to the left of l? I was thinking we could iterate m from l+1 to r such that we try to pair a_l and a_m, given that a_l == l — k and dp[l+1][m-1][k] == (m-1) — (l+1) + 1. If a_l != l-k, then dp[l][r][k] = dp[l+1][r][k]. If a_l == l-k and dp[l+1][m-1][k] == (m-1) — (l+1) + 1, then dp[l][r][k] = max(dp[l][r][k], 1 + ((m-1)-(l+1)+1)/2 + dp[m+1][r][k1], where I am not sure what the optimal k1 is because we can perform the operations on [l,m] and [m+1,r], in different orders. Thus I think that I would have to iterate over the possible values of k1, which would lead to an O(n^5) solution. TLDR: What are the dp transitions dp[l][r][k] for F1?[problem:F1]

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

Can anyone explain the O(n) solution for problem E "Wonderful Tree"? I don't get it. Please help.

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

can someone explain to me why you have to iterate from n to 1 in problem D? Thanks

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

5

581485311 581485311 581485311 147717016 581485311

can somebody explain why the answer for this testcase for problem C is 581485315 and not 581485313

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

.

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

What's the intuition for problem F? Even if I understand the editorial, I can't seem to grasp how one would come up with this...

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

for problem F, why it is wrong that, i always chioce to delete the last legal position?this greedy idea seems like right.

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

In case those who are not able to understand the dp of the tutorial of problem D. after getting the freq array of the elements of the main array you just need to maximise the number of indices that Bob can take and then subtract it from the freq array size. Below is the simple understandable recursion + memoization code —

const int MAXN = 5001;
vector<vector<int>> dp;

int helper(vector<int>& v, int ind, int steps){
    if(ind >= v.size()){
        return 0;
    }
    if(dp[ind][steps] != -1){
        return dp[ind][steps];
    }
    int curr = 0;
    if(steps >= v[ind]){
        curr = 1 + helper(v, ind+1, steps-v[ind]);
    }
    curr = max(curr, helper(v, ind+1, steps+1));
    return dp[ind][steps] = curr;
}

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n);
    map<int, int> mp;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        mp[a[i]]++;
    }
    dp.assign(mp.size(), vector<int>(MAXN, -1));
    vector<int> v;
    for(auto x : mp){
        v.push_back(x.second);
    }
    int ans = helper(v, 0, 0);
    cout << v.size() - ans << "\n";
}

Thanks.

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

[problem:C] I think the approach to solving problem C is little difficult for me to figure out. I thought about it for a very long time!!!

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

lefist heap solution for E in O(nlogn) complexity:268358732

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

Anyone can please help with 1987E - Прекрасное дерево! 269388889?

For every node I try to go into its child, and its subchild and so on, I keep its height from the source node and the potential (val[node] — val[childs]) [Similar to Shayan's Editorial]. I then greedily increase the value if its potential is positive or it is a leaf node.

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

Can anyone debug my solution for F1 please?

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

Why did nothing happen to the cheater of the EPIC Institute of Technology Round Summer 2024 (Div. 1 + Div. 2) contest and their rating? MikeMirzayanov & Vladithur

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

A key thing to do in E is to work the tree from bottom to root level by level I missed that when I read the tutorial so in case some one else missed it too

this test case will help you understand why

9

10 2 7 5 1 1 1 3 2

1 1 3 3 2 4 4 5

if you start from the root (1) and try to fix it using node (5) instead of (6) you will end up with answer equal to 6 instead of 5 because (3) now have to go two nodes down to fix itself instead of one to (5)

draw it and it will become clear

I got WA on test 9 because of this

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

    Thanks for this. Would you happen to know why a dfs that solves for the children of a node before solving for a node doesn't work? Intuitively, it seems like the same sorta thing as iterating from n to 1, but it still gets WA on test 9.

    edit: nvm, they are the same. I just messed up the implementation.

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

I need some help.

My approach for problem F: instead of a $$$dp[l][r][k]$$$ (range $$$l$$$ to $$$r$$$ with exactly $$$k$$$ elements removed before $$$l$$$), I tried $$$dp[i][j][k]$$$ ( $$$i$$$ current position, $$$j$$$ elements removed and $$$k$$$ unmatched positions to delete) . Basically, I use the claim: let $$$jumps:=i-a[i]$$$, if $$$jumps <= j$$$ and $$$jumps\mod 2==0$$$ and jumps are non-ngative we can like open a bracket since we can perform the previuos operations in such order to do this valid operation".

submission: https://codeforces.me/contest/1987/submission/270545863

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

Why is it true for Problem E that we must iterate from bottom up of the tree. Is there a proof or some sort of intuition as to why this is true to produce the optimal answer?

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

The “Tutorial” of problem D may have an error.

The answer to the problem is $$$m − y$$$, where $$$y$$$ is the largest value where $$$dp[m][y] \le +\infty$$$.

According to the code of “Solution”, this sentence may need to be corrected to:

The answer to the problem is $$$m − y$$$, where $$$y$$$ is the largest value where $$$dp[m][y] \color {red} < +\infty$$$.

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

Good one

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

Great contest overall

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

Why we must iterate from n to 1 in E??

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

https://codeforces.me/contest/1987/submission/272550792 dude this solution for E must not work because I don't clear vector $$$order$$$ after multitest :skull:

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

Can someone please explain why my solution for F1 is wrong? My code: https://codeforces.me/contest/1987/submission/268271924

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

The solution for problem E mentioned in the Editorial gives wrong answer for this testcase :
1
7
1 5 0 1 1 6 1
6 6 7 7 1 1

My solution (which got AC) returns the output =1 and the authors solution output is 0 .
Is it that such type of inputs are invalid ? Vladithur

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

Never have I seen a tutorial as convoluted with errors as D.

Getting to Σci <= ip — p is easy, but the way they have worded it is atrocious. "In ci1+…+cip turns, Alice will zero out exactly that many values. Additionally, Bob would have zeroed out p−1 values before index ip" This frankly needs to be better worded, I can't make heads and tails of it.

"If s≤ik−k"

What is ik here? Randomly defining your own variables mid equation and not explaining must be fun.

Wasted 30 min of my life just trying to UNDERSTAND the tutorial.

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

Guessed the answer for C as $$$ans = \max_{i=\overline{0,n-1}}(h_i + i)$$$ (in 0-indexed notation), which is the same as in tutorial if you expand all $$$t_i$$$-s by definition and bring all $$$\max$$$-s outside.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

G1/G2 can be solved by doing a cursed dp with 7 states on the cartesian tree of the array: 288649201 (I wrote definitions of states in comments).

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

My Binary search solution for C :

290649146