DS007's blog

Codeforces Round #695 (Div. 2) Editorial
By DS007, 4 years ago, In English

Many thanks to infinitepro, BledDest and alimq for helping me write the editorials.

Tutorial is loading...
Solution


Tutorial is loading...
Solution


Tutorial is loading...
Solution


Tutorial is loading...
Solution


Tutorial is loading...
Solution


UPD: Also, have a look at this comment for an explanation of the sample test case of C.

  • Vote: I like it
  • +114
  • Vote: I do not like it

Comments Comments (143)
| Write comment?
»
4 years ago, # |
  Vote: I like it +106 Vote: I do not like it

My sincere apologies for misjudging the difficulty of B. Most of the testers solved it hence I thought it was fine for a div2B. Hope you all enjoyed the other problems.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

    It was just unusual, I guess people (of course including me) fell for some short greedy type approaches. Problems were nice.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +37 Vote: I do not like it

    In hindsight it was fine. It gives the impression that it suffices to reduce the input to a sequence of -1, 0, 1, and work on that. At least I did that — and it felt really clever — until I got WA.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -234 Vote: I do not like it

    Fcuk off to you and your problem setting.

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

    I disagree. Although I didn't solve it and it ruined my contest, I think This is an excellent problem for Div 2 B. It requires a one simple observation and then can easily be solved by doing a case by case analysis.

    • it's trivial to calc the initial intimidation, init.

    • then, by the key fact that changing a_i affects at most 3 elements,

    our output = init — delta, where delta = 3, 2, 1, or 0.

    • If one carefully analyze the conditions under which delta = 3, then repeat for delta = 2 ..., one figures out the complete solution for sure.

    I like it. thank you.

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

      I applied the same concept. However, I have missed some case. Can you let me know some easy test case so that I can figure out my mistake? I am getting WA in test case 3 (23rd token)

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

        23rd Token : 23 16 9 4 14 9 4

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

          Can you let me know some easy test case or points that I missed so that I can figure out my mistake? I am getting WA in test case 3 in DIV2B(163rd token). Thank you.

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

            2 6 1 5 10 4 6 12 6 10 8 5 15 7 6

            answer — 1 1

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

          how did you find the 23rd case?

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

            add this:"if(count==23) {cout<<n<<' ';for(int i=0;i<n;++i) cout<<e[i]<<' ';} in your submitted code and you can get the 23th case in the WA report.See what your code output.

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

    its alright, This will help us improve even more.

    I have a doubt regarding the solution for the problem 2. What I did was that I found the max consecutive extremes(hill or valley) then from the total sum I subtracted the min(3,consecutive). So basically if there are 3 consecutive extremes then we can neutralize it and reduce it by 3. Similarly if there are 2 consecutive extremes then we can change the vaues and reduce the sum by 2. If there is atleast extreme then we can reduce it by at least 1. Please tell me what is wrong with this logic? Where have I gone wrong, so that I can improve in the next contest.

    Thank you

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

      I also did same during the contest but run your code on this test case 23 16 9 4 14 9 4. I think your code will give 0 but answer is 1.

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

    I found my mistake overnight it was just the index when I was checking how my change affected the integer on my left... Like instead of setting i>=3 (thus the integer on my left has an integer on its left) I said i>=2 and in 5 hours of debugging I could not see it.

    The problem for ranking up from Expert or Specialist to CM is not the concept of the problems. The problem is actually being able to write code with 0 bugs. Like I understand how to improve myself when it comes to the concept of problems (learn more algorithms and solve more problems) but I don't see how can I improve myself into not making mistakes while coding, I do believe solving more problems won't really help one stop making mistakes when implementing a solution.. The focus one has when implementing IMO comes from 3 importnat factors genetics, sleep and food. I will search for medication that can help one stay more focused like royal jelly and see if it makes any difference.

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

      Hi dude, I did not participate into the actual contest but tried div2 2 in practice and spend 2 hours trying to figure out why I got WA on Test case 3 and it was a simple index error, I was having a hill_or_valley(i) function and I was assumming that i is between 2 and n — 1, but that was not always the case.

      Totally agree that you can practice algorithms and logic, for example this div2 c idea has completely caught me off guard, but I also believe that you can practice not making mistakes. You can take for example WA submissions to div2 b and try to find the mistake in other people's code.

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

        Yes I do agree that you can partially improve your debugging skills but here is the thing: Even spending a minute in debugging is costing. I'd rather spend 5 more minutes writing the correct code rather than loosing a submission (which may cost 10 minutes penalty in some cases) and then have to debug that 1 extra minute. I bought coffee for tomorrow and we will both see if the experiment will fail or succeed.

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

    In problem div 2 C in 1ST LINE OF PROOF IN EDITORIAL::: DS007

    IT SHOULD BE CRITERIA 1 NOT 2 ...PLEASE CORRECT IT.

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

Please fix this => "Unable to parse markup [type=CF_MATHJAX]" in problem C and also I am not able to see the submissions.

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

The editorial will be translated to Russian tomorrow.

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

I can't view any of the author's submissions. It gives me the error: You are not allowed to view the requested page.

UPD: Fixed!

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +26 Vote: I do not like it

Hard, but nice quality contest! Learned the techinique of multiplying two dp values and adding them leading to the answer in D. Thanks :)

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

    Can u explain to me that part about multiplying dp[i][j] * dp[i][k-j] where 0=<j<=K for each i in order to get the number of occurrences for each i

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

      How does that tell us that a particular element at index i occurs in a path where it is not the beginning or the end of it

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

Really great explanation to C, probably one of the most beautiful problems in recent rounds. The graph modeling approach is amazing!

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

    ScrappyDoo Can you please explain the idea ?

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

      I'll suppose that the part about vertices and edges is clear. Suppose that we draw a rooted tree for the following example:

      2 3 4

1 2
3 4 5
6 7 8 9

      Notice that a-(b-c) is actually equal to a-b+c. This corresponds to the following graph example:

      a
|
c
|
b

      First we remove b, and change c for b-c, then we get the following tree:

      a
|
(b-c)

      Then we remove (b-c) and change a for a-(b-c) leading to:

      a-b+c

      This implies that we will be calculating our final answer as difference of sums of elements on even levels and sums on odd levels.

      Because nodes can connect only elements from different sets we observe that we can create a tree with at least 3 levels, which turns out to be just enough to get all the nodes in a tree. Here's an example of such tree using the previously mentioned sets:

               1
     /       \
    3         6
 / / \ \     / \
2  7  8 9   4   5

      What do we see? We can include just two elements from two different sets on our odd levels and all other elements on even levels. So if mn1 and mn2 are the two smallest values that don't belong to the same set (one belongs to 1. and other to 2., one belongs to 2. and other to 3., or one belongs to 1. and other to 3. set) the answer in this case is:

      sum of all elements - 2 * (mn1 + mn2)

      As we already counted mn1 and mn2 in total sum we have to remove them twice. There's another case where we'll store one complete set on the second level and two other sets on level 1 and level 3 (I'll leave it as an exercise for you). Again we take the minimum of those three cases and compare them to our answer.

      I hope this explanation was clear. TBH I'm not too good at doing these, so feel free to ask about any part of my solution.

      Here's a sample implementation I've done for you to understand completely:

      https://mirror.codeforces.com/contest/1467/submission/103829704

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

        ScrappyDoo Thank you for the wonderful explanation. This is indeed a beautiful problem :)

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

        Great explanation, but I think there is an error in the tree for a-b+c. The tree would be:

        a
        |
        b
        |
        c

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

          Yeah, I see I messed that part now. Thanks for the correction!

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
            ← Rev. 8   Vote: I like it 0 Vote: I do not like it

            Hi, I thought about it a lot but still can't figure out how to determine when to add the whole set. Could you please give an example of it?

            UPD: I think I figured it out.

            • 3 3 3
            • a b c
            • d e f
            • g h i

            Here we can do this,

            • lvl 0 -> a
            • lvl 1 -> d, g
            • lvl 2 -> b, c, h, i connected to d
            • lvl 2 -> e, f connected to g

            So, we subtract d and g. But we could have also done,

            • lvl 0 -> a
            • lvl 1 -> d, e
            • lvl 2 -> b, c connected to d
            • lvl 2 -> g, h, i connected to e
            • lvl 3 -> f connected to g

            Here we are able to construct the tree and delete all items from bag 2 (d, e, f).

            If removing the whole bag gives a better result than removing 2 items from different bags then we remove the whole bag. i.e. if (d + e + f) < (d + g) and so on.

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

              I think that you are overcomplicating the substraction of whole set, here's a simpler idea I've come up with.

              Put single element from first set on the first level (say a).

              Put all the elements from second set on the second level (d, e, f) and connect them with the only element from the first level.

              Lastly connect all the remaining elements with any of the elements from second level and put them on the third level.

              Here's one of approaches which solves your provided input:

              • First level: a
              • Second level: d e f, connected to a
              • Third level: b c g h i, connected to d

              We know that all the elements from last level belong to either first or third level so we can connect them with any of the elements that belong to second level (as they belong to the second set). The story is same for the first two levels.

              But yes, your approach also works as there are many ways to construct a tree here.

              And answer to your second comment — No problem, glad I could help!

              → Reply
»
4 years ago, # |
← Rev. 5   Vote: I like it +18 Vote: I do not like it

I have a different solution for problem E. I'll explain it here. Let me know if you have any questions.

Root the tree arbitrarily. Let's define $$$x[u]$$$ as the number of paths starting at node $$$u$$$ such that the value of the node at the other end of the path exists multiple times in the path. A node $$$u$$$ is distinctive iff $$$x[u] = 0$$$. Suppose you know $$$x[u]$$$ for some node. What paths could change the answer for a child $$$c$$$? There are two possible types:

  1. paths starting from $$$u$$$ that ends in $$$c$$$'s subtree s.t. they end with a node with the same value as $$$u$$$, and have exactly 2 nodes with the same value ($$$u$$$ and the ending node)
  2. paths starting from $$$c$$$ that end at a node that's not in $$$c$$$'s subtree s.t. it ends with a node with the same value as $$$c$$$

Using these facts, run a dfs starting from the root. You can pre-calculate the number of paths starting at each node of types one and two using a map. Using this, we can calculate $$$x[u]$$$ given $$$x[parent of u]$$$ (you add all paths of type 1 and subtract all paths of type 2). The answer is the number of nodes $$$u$$$ with $$$x[u] = 0$$$. Here's a link to my accepted submission: 103931989

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

    This fails on 4 1 2 1 1 1 2 2 3 3 4 (Test 104)

    It's because the '1,1' path in the subtree of 2 isn't accounted for by your two possible types.

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

      I've edited my code to account for those paths. The general idea is still the same. Lmk if you find another hack test.

      Edit: This submission was hacked too, I'll try to fix it again.

      Edit 2: I fixed it, it was a small mistake (I had to swap the order of two lines)

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

        Try printing out the pv values in your dfs2 method on this case: 12 1 3 3 1 1 1 1 1 1 1 3 1 1 2 2 10 1 3 3 4 7 9 3 5 5 7 7 8 1 11 11 12 3 6

        You should see that many of these values are greater than 11 (which shouldn't be possible because given some fixed vertex, there are at most 11 other nodes a path can end at).

        While your code technically gives the correct answer on this case (as it's trivially 0), for your type 2 paths, you only want to consider the number of paths starting from c which end at a node that's not in c's subtree and have exactly 2 nodes with the same value along the path (similar to the condition in type 1). Not accounting for this results in massive over-counting which accumulates in the pv values.

        I'm not sure how you'd actually efficiently compute this in one dfs.

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

          I realized that too, but it doesn't actually matter. The only cases in which I over counted don't actually matter, since everything in that subtree isn't distinctive anyway. On an unrelated note, the tests in this problem are apparently pretty weak considering my first solution was hacked on a really simple test case (but you can't really blame the authors for this since there are so many possible solutions).

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

    Thanks a lot

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

    Problem E is obviously a lot of ways to do it.

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

→ Reply
»
4 years ago, # |
← Rev. 5   Vote: I like it +9 Vote: I do not like it

Can anyone explain/provide test case of why the noob method of finding cases of decreasing 1,2,3 hills/valleys and writing if statements for it does not work in problem B .
My submission
cases like this also run fine
1
6
1 3 5 2 4 6
There's something else Im missing.
update : 2,22,23,14,18,18 is the case that breaks my code
thanks :)

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

    same doubt my submission

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

    1 3 5 2 4 6 You have (3 5 2) and (5 2 4) but you can't fix them both without producing extra one

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

    Here is a test case that fails the method you describe:

    23 16 9 4 14 9 4

    I think my method was the same as yours. Under our method, it seems that, since the first 4 is part of valley 9-4-14 and hill 4-14-9, that we can eliminate both of those hills/valleys by simply changing the 4. However, that is not possible, since eliminating the 4-14-9 hill requires 4 to be increased to at least 14, which will create a new hill (a 16-9-x hill).

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

      I think this corner case can be summarised as destruction of a hill compulsively creates a new valley or hill and vice versa.

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

      For these types of cases, my code runs fine. For the input you gave my output is 1. Any other test case?

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

        what is your answer for test case 1 3 1 3 5?

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

          the code works for this test case its output is 0. The test case that would fail is:

          2,22,23,14,18,18(Conditions for handling hv and vh pattern fail).

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

            thanks :)

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

              Can you tell me the intuition behind the condition. I couldn't figure it out.

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

                It's just observation/hit and trial ..also there is a better way to solve this (the tutorial one) without caring about the corner cases.

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

          0 . I guess its right

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

Can someone plz explain c in easy way ?

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

    Ignoring the proofs of my claims, first, you calculate the sum of all numbers in all the bags. Then from this, you subtract 2 * min(sum of the 2 smallest numbers such that they appear in different bags, minimal sum of all numbers in one bag).

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

      But what is reason behind this? Can u just give a brief ..bcz i am unable to get editorial

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

        I have put the best proof that we could come up with in the editorial. If you want to look at it from a different perspective, try to work out how the numbers would change after an operation, and how you can make the net effect of some number positive.

        Let's say that you choose bag 1 as the final bag. Then all numbers in bag 1 can be made positive. Now we try to make all elements in bag 1 positive by passing them through the minimum number in bag 2 and vice versa. However, if the net effect of this turns out to be negative, then we just flip the signs of all these numbers.

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

          DS007 are there any similar problems to Div2C? I am encountering this variety of problem for the first time.

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

        I found the explanation in the editorial not super intuitive (though it makes for a nicer proof).

        Less formal: Essentially, you pick one number to be your final number. Then you can add any number to it, buy passing it off twice. Now you have to empty two bags, so you cannot pass the last number in the bag and therefore you subtract the minimum (instead of adding it, therefore *2). Alternatively, you can also do what happens in the first example test case and subtract one complete bucket if that is cheaper than the smallest sum of two minima.

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

      My first idea to the problem was, that we subtract one big number from some small number, then subtract that negative difference from another big number to get a "bigger" number, than subtract that from some small number, to subtract that negative number again... and so on.

      And I still not get the prove why this is not the optimal strategy. Or is it, somehow?

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

        I went along the same lines and decided I need to create the largest possible negative numbers in two bags then finally add it to the positive numbers in the third bag. Got WA on 6. Will try some more and check if it takes me anywhere.

        UPD : This does work,just got an AC. First observation is we keep one bag aside and create two big negative numbers in each of the other two bags. If you can reach this stage the answer is the sum absolute values of all the numbers.

        The following is how to create these big negative numbers. Let's say the sum — minimum(note not just sum so asm + amin = sum of numbers in a) and minimum of the last two bags is asm,amin,bsm,bmin.

        Now we compare bmin with asm and bsm with amin. We are trying to keep as much of the sums as possible by subtracting against the smallest number in other bag. We take abs(bmin-asm) and abs(bsm-amin) as it is possible that the minimum turns out to be larger than the other bags sm. These two are our large negatives.

        There is one edge case to handle however if either of the bags happen to have just 1 element. We take abs(sum of a — sum of b) as our only negative.

        How to choose which two bags to do the operations on? Just try all 3 possibilities.

        Here is my solution https://mirror.codeforces.com/contest/1467/submission/103854808

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

        I think it's correct, tho you have not mentioned your entire approach but I think, I've done something similar, maybe if this helps. 103844818

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

    In my opinion, the easiest method to understand this problem is by analyzing the process. It's easy to see that each method of combining all the elements to obtain one single element can be reduced to some arithmetic expression.

    For example If I'm having three sets of form

    a1, a2 b1 c1, c2

    if I try to move c2, a1, a2 to the second set, and then everything to the third set the answer will be : c1 — (b1 — c2 — a1 — a2) = c1 — b1 + c2 + a1 + a2.

    From now on, if you do some kind of brute force where you try every possible way of combining the elements you will observe that there are two possible types of outputs :

    1) Two random elements from dfferent sets gets subtracted from the sum of the other elements. (or twice subtracted from the total sum).

    2) A whole initial set gets subtracted from the sum of the other elements (or twice subtracted from the sum).

    I know this is kind of a dumb way of observing the pattern but actually I do think it might help a lot of times.

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

      Hi, could you please explain how you determined the point 2 (1 whole initial set gets subtracted) ?

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

https://youtu.be/Q8mVSk9VBlc if anyone is stuck in C.

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

The solution code in problem C is incorrect. If you submit it to CF, it gives the verdict Runtime Error. To fix this, change the return type of the solveTestCase function to void.

→ Reply
»
4 years ago, # |
  Vote: I like it -58 Vote: I do not like it

what a land contest

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

Sorry but i'm confused with answer for problem D. I understand the building of dp but i dont understand the build of a[i][j] because when you take number of paths that end with i (dp[i][j]) why does it mean that the answer will be that multiplied with number of pats starting with i(because some of the paths in dp[i][j] may have a[i] several times so doesn't that change things?) Thanks in advance for the answer

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

    dp[i][j] = number of paths of length j that start or end at i.
    a[i][j] = number of paths of length k where i appears after exactly j moves.

    To achieve such a path, you must start from a path of length j that ends at i. From here, you have multiple choices to complete the path. For every path of length j that ends at i, you can complete it in dp[i][k-j] ways by starting at i and moving the remaining k-j moves. Hence a[i][j] = dp[i][j] * dp[i][k-j]

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

      Oh okay i get it now. Thanks for thr explanation :)

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

      I am not getting how the formula of cnt[i] is valid for the case when robot moves back and forth about a[i].can you pls explain giving examples.

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

        Yes, it's a very common confusion on such problems.

        When use "cnt[i]+=(dp[i][j]*dp[i][k-j])", it's possible that the robot walk on a[i] more than once in its first (j-1) steps or its last (k-j) steps? And the answer is: absolutely yes.

        But it doesn't matter, when we use "cnt[i]+=(dp[i][j]*dp[i][k-j])", it means the number of paths whose j-th step are on the a[i], and iterate for j we can get the sum of the ways. For example, if there is a path which stay at a[i] in its 1st step and 3rd-step, you may think this path contribute 2 for a[i](and it's correct), but in our method, this path contribute 1 while we calculate "cnt[i]+=dp[i][1]*dp[i][k-1]" and contribute another 1 while we calculate "cnt[i]+=dp[i][3]*dp[i][k-3]".

        To conclude, cnt[i] in this problem can be decomposed by paths(yours) or j-th step(editorail's). Both are correct but only the later one works for this problem.

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

WA on Pretest 3 of Div2B must be the biggest pandemic of 2021. Unfortunate :(

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

My solution for problem C failed on test case 17. Can anyone please suggest an easier case on which this solution is failing?

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

    1 2 3
    7
    8 9
    4 10 12

    Solution: 36
    (Ex: Subtract everything but 4 from 7 and then subtract this result from 4)
    Ans = 4 - (7 - (8 + 9 + 10 + 12) ) = 36

    Your code's output: 28

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

Oh, I just got it... What a brute force way for problem B, never thought like that before. I just thought to check every continuous 5 elements and check if they affect the answer by 0,1,2 or 3, and how to check is just divided them into many cases and the contest was in the evening and I just was confused by many cases by myself.

Nice problem bro.

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

Div2B was pretty similar to a problem from a recent contest.
I don't remember the exact problem or its code. But this is what we had to do.
We had to make a swap to minimize/ maximize the total number of minima/maxima/(minima+maxima).

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

I finished a DSU-on-tree solution for problem E during the contest. Here is the reviewed code with comments to explain the idea.

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

Problem C can be solved in another angle of thought.

Without loss of generality, lets assume that the final element will belong to bag A.
Now, think of the problem as ans = a1 + a2 + ...an + -b1 + b2 + ...bn + -c1 + c2 + ... cn
(Move all but 1 element in A to B. Move all but 1 in C to B. Move all but one in B to C. Now move all back to A. So all the elements except the ones unmoved in B and C will have a -(-) positive contribution to the sum.

There is one more possibility. Assume c1 was infinite, so a -c1 is not affordable. So we move all Cs to B and then to A, and ignore moving B twice.
Answer in this case will be Sum(A) + Sum(C) — Sum(B). Swap A, B, C and find the max case. 103801386

→ Reply

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

Finally became EXPERT !!!

→ Reply
»
4 years ago, # |
  Vote: I like it -21 Vote: I do not like it

I can't seem to figure out the problem in my code for Hills And Valleys Problem.

I first count all the hills and valleys. Then I check if any Hill-Valley-Hill or Valley-Hill-Valley combination occurred. If this is true, I decrement the counter by 3. If not true, then I search for Hill-valley or Valley-Hill pair, In this case, I decrement the counter by 2. Else final answer is Counter -1. 

    #define ll long long
    using namespace std;
    int main()
    {
        int t;
        cin >> t;
        while (t--)
        {
            vector<ll int> arr,vis;
            int n;
            cin >> n;
            for (int i = 0; i < n; i++)
            {
                ll int p;
                cin >> p;
                arr.push_back(p);
                vis.push_back(0);
            }
            ll int counter =0;
            for(int i=1;i<n-1;i++)
            {
                if(arr[i]>arr[i-1]&&arr[i]>arr[i+1])
                {
                    counter+=1;
                    vis[i]=1;
                }
                else if (arr[i]<arr[i-1]&&arr[i]<arr[i+1])
                {
                    counter+=1;
                    vis[i]=1;
                }
            }
            if(counter<1)
            {
                cout<<0<<endl;
                continue;
            }
            else
            {
                int flag =0;
                int final =0;
                for(int i=1;i<n-1;i++)
                {
                    if(vis[i+1]==1 && vis[i]==1&&vis[i-1]==1)
                    {
                        final =1;
                        break;
                    }
                    if(vis[i]==1 && vis[i+1]==1)
                    {
                        flag =1;
                    }
                }
                if(final)
                {
                    cout<<counter-3<<endl;
                }
                else if(flag)
                {
                    cout<<counter-2<<endl;
                }
                else {
                    cout<<counter -1<<endl;
                }
            }
            
        }
    }

It is giving me the wrong answer on the 3rd test case 21 token expected 1 found 0. Can someone tell me what am I doing wrong

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

Can anybody help me figure out why I am getting WA for tc3 in Problem C 103860085

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    It took a long time to figure out and in the end it turned out to be overflow of integer.
    Since each value can be 1e9 their sum can be near 1e14.
    Here
    10 10 10
    1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
    1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
    1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

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

Problem C. The solution looks interesting yet I find it very hard to understand it.

So we want to build a rooted tree ?
There is an additional node that is the root ? Any node is a leaf except the root ?
What is the definition of valid in : "the constructed rooted tree is valid" ?

It would be nice to have a simple example or some references : books, article, similar problems ...

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

https://mirror.codeforces.com/contest/1467/submission/103855499

Can anyone please tell me, what I did wrong here. It is giving this verdict on 3rd test case "wrong answer 8th numbers differ — expected: '0', found: '1'"

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

Nice editorial for Problem C

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

.

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

Can anyone tell me the 23rd case of test case 3?I am just curious to know what's wrong in my code!

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

    Maybe similar with this

    Input
    Answer
    your output
    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Legend how did u get it

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

        I just thought of some test case for which my code could get wa.

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

Nice and clean editorial solution code! for div 2 B. Thanks.

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

Actually your code of problem B shouldn't take AC, (int a[N]) and (int tmp = a[i]) tmp and a[i] should be long at least according to the constraints !!

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

REALLY GREAT CONTEST !! NOW, AFTER STRUGGLING WITH A , I HAVE SOLVE IT NICELY AND I AM BECOME PUPIL NOW.

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

Can anyone please explain problem E. And also some of the topics related to it, which might help in solving it.

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

Can anyone explain me the below line ? and what is the role of is[] array ??

ans = min(ans, s — is[i — 1] — is[i] — is[i + 1] + isHill(i — 1) + isValley(i — 1) + isHill(i) + isValley(i) + isHill(i + 1) + isValley(i + 1));

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

    is[i] denotes whether index i was a hill or a valley initially.

    In the line that you have mentioned, I remove the contribution of indices i-1,i,i+1 to the intimidation value of the unchanged sequence. Then I find whether these indices have now become hills or valleys and update it accordingly.

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

Can anyone explain for me that why in prob B the answer is equal to (count of hill and valley) — x with x = 0/1/2/3?

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

    because if you change $$$a_i$$$,only $$$a_{i-1},a_i,a_{i+1}$$$ can be effected,so x can not be greater than 3.And if there's no hills and valleys,x can not be less than 0.So x is a integer in [0,3].

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

Wow I don't know how do people solve problems like C. Greedy is certainly not one of my skills. Was it just a blind guess or do you actually find an intuitive way to "prove" your approaches?

I found problem D easier to approach, maybe a little bit harder to code but no so much. In fact I had to skip C during contest.

Nice problems!

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

    I was close to solving C on my own — just made a mistake wifh the case with the whole array (I thought it can only happen when whole array has length of 1). I come up with conclusion that we should look for the biggest negative number. By blindly guessing I've realized that we can always connect two elemnents from two groups with all the other elements (e. g. erase all elements besides three twice and than erase them again which ends up being addition, than add one element and erase two that are left), I've even sketched out the edges. The thing is that they weren't supposed to create a graph, I was just tracking what I've used so far. Lmao, turns out I was right.

    So I'd say I've guessed the graph modeling approach, bu t did so greedily, without any proof, but knew that it was impossible to erase only one element, shich would end up being the intended solution. I've talked to 5-6 people that have solved it — all of them did so without a proof...

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

VIDEO TUTORIAL FOR DIV 2 PROBLEM B WITH IN DETAIL EXPLANATION OF CREATIVE TESTCASES AND LINE BY LINE CODE HERE IS THE LINK : https://www.youtube.com/watch?v=I4oSzeygRzs HOPE YOU GUYS WILL ENJOY THE VIDEO !!!!

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

Observe that $$$dp_{i, j}$$$ is also equal to the number of good paths of length $$$j$$$ that start at cell $$$i$$$.

I didn't get this part from problem D, how is it the same?

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

    $$$dp_{i,j}$$$ is the number of good paths of length $$$j$$$ that end at cell $$$i$$$, then the reverse of those paths are paths of length $$$j$$$ that start at cell $$$i$$$

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

      Oh, that makes sense, I'm wondering how did I miss thinking about the reverse part.

      Thank you :)

      → Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it +7 Vote: I do not like it

Nice contest

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

can somebody easily explain C. Three Bags problem??

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

Can anyone explain this paragraph of editorial of Problem D?

Let ai,j denote the number of times cell i appears after exactly j moves in all valid paths of length k. Well ai,j=dpi,j∗dpi,k−j because we can split a path of length k into two paths of length j and length k−j, with the first path ending at cell i and the second path starting at cell i.

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

    For each i, we want to calculate how many times the cell i occur in all good paths, right ? this is the goal. Let f[i] denote that.

    Consider a good path of length k [x_0, x_1, x_2, ..., x_k].

    Do you see that f[i] is equal to the SUM of the following:

    • the number of times cell i occur in a good path in position 0, PLUS
    • the number of times cell i occur in a good path in position 1, PLUS

    '

    '

    • the number of times cell i occur in a good path in position k.

    So, the task now, for each j in [0, k], we need to calculate how many times a cell i occur in a good path in position j = " After j move" ? Let a[i][j] denote that.

    Let's now consider how we can calculate a[i][j] for specific i and j.

    Consider a good path of length k in which cell i appeared after j move, It will look like this

    [x_0, x_1, ....., cell i , ......x_k]

    Do you see that this path can be broken down into 2 paths:

    • a path of length j which ends with cell i

    • a path of length k — j which starts with cell i

    Let dp_en[i][j] denote number of paths of length j ending at cell i

    Let dp_st[i][j] denote number of paths of length j starting at cell i

    we know that any path of the first type can be joined with any path of type 2 to make a length-k path that contain cell i after j move. meaning a path that we should count it in when calculating a[i][j].

    Hopefully, It's clear now that

    a[i][j] = dp_en[i][j] * dp_st[i][k-j]. This is the key conclusion.

    now one extra unnecessary observation is that dp_en[i][j] = dp_st[i][j] for all i and j

    which means that

    a[i][j] = dp_en[i][j] * dp_en[i][k-j]

    The task now is to calculate dp_en[i][j], This is a simple dynamic programming task.

    Given dp_en[i][j] -> a[i][j] -> f[i] -> ans

    If any thing is not clear, please tell me

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

Problem D

I didn't understand solution. But I am now.

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

I highly doubt about Problem C solution: the summation of given data should overflow 32bit integer. Any thoughts?

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

Problem E honestly feels like it should be 2000/2100, here is an alternate brainless solution:

Observations:

  1. If there exists some value $$$x$$$, such that there are $$$\geq 3$$$ occurences of $$$x$$$ in the tree, and one occurence lies on the path between some two occurences of $$$x$$$, then there is no distinctive root.
  2. So firstly, just run a dfs, and check if this condition is satisfied by the tree, if yes the answer is $$$0$$$.
  3. If the condition is not satisfied, this means all the values (exclude values whose frequency is one) occur in one of the following manners:
  • Case 1: No occurence of $$$x$$$ is a parent of another occurence of $$$x$$$.
  • Case 2: Only one occurence of $$$x$$$ is a parent of another occurences of $$$x$$$, call this node $$$r$$$. $$$r$$$ must lie strictly above the LCA of all the other occurences of $$$x$$$. (Red nodes correspond to occurences of some particular x)

Let us call the region between red nodes (which contains distinctive roots wrt this value of x), a "good zone". Now, we can just do a dfs while maintaining the set of current good zones we are in. Any node $$$u$$$ which is in the good zone of all the values which have $$$>1$$$ occurences, will be a distinctive root.

Implementation: link

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

can you add this hack for E?

6
5 2 3 2 3 8
4 6
6 2
4 3
3 1
1 5

my wrong submission 288000968 which ACed. My code prints 1, but answer is 0.

→ Reply