Kilani's blog

Codeforces Round #699 (Div. 2) Editorial
By Kilani, history, 4 years ago, In English
Tutorial is loading...
code

Author: Salem_Alwarawreh

Tutorial is loading...
code

Author: Warawreh

Tutorial is loading...
code

Author: Kilani

Preperation: Warawreh

Tutorial is loading...
code

Author: Kilani

Tutorial is loading...
code

Author: Warawreh

Tutorial is loading...
code

Author: Kilani

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

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

Damn, really fast editorial. Thanks, the problems were great!

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

Problem C was not so good....

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

really quick

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

wow -__- fast editional

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

Boring implementation problems (first 4)

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

really fast,the editorial was ready while system testing

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

"DELETED"

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

https://ideone.com/ZpbCHH can someone tell me how is the above code wrong for problem C. I have done almost the same thing as tutorial , the only difference is that tutorial checks that we have enough painter to paint at the end and i check that in the beginning UPDATE : The mistake has been found and corrected

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

    I believe you don't check if the last painter has a color that doesn't appear in b (ie ans=-1) in which case you should say No and you say yes

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

      I have checked that , I have checked that whether Vis[c[m-1]]== false . Vis is true when the no. Appear in the array b.

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

Thanks for the contest!

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

D was lengthy :|. Got the idea but can't implement it.

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

B was brute force! C was hard implementation!! Let's see the editorial for D!!!

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

Thanks for quick editorial and wonderful problems, I got stuck on problem C but during the after-contest discussion with my classmates, I found that it was just hard implementation, while I was thinking of something like DP.

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

    As your senior,I have to point out that you've made A grammer mistake.

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

      As The Principal of your school, I have to point out that you've made a grammar mistake.

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

Can someone help me find the error in this solution. I have done exactly as the solution above states.

Link : https://mirror.codeforces.com/contest/1481/submission/106601553

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

    hack:

    3 2
1 2 3
3 2 3
1 3

    the ans can be

    Yes
1 1

    but your output is No

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

      Thankyou so much!

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

      It works for mine, but Im still getting WA

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

        Your code fails to pass this:

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

          thnxs for the testcase

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

          Hey VTifand, Can you tell a counter example for this code 107294260 for Problem C?

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

            Test this:

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

              Hey VTifand Can you please tell where I am going wrong in this solution? 109939615 because it passes all the above test cases that u mentioned in the comments.
              Thanks in advance...

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                4 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it 
                1
3 3
1 1 2
2 1 1
2 2 1
                → Reply
»
4 years ago, # |
  Vote: I like it -35 Vote: I do not like it

Problem C was worst in my veiw

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

    I think it was pretty good problem for Div2, because it does not require algorithm but the way you implement your idea into your code. So yeah, I personally enjoyed it

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

For Prob D, can someone clear my doubt. I had the same idea but was not able to prove one case.

Let's say there are no two nodes that have the same value on the edge. (If x and y are nodes then they will have value as a and b) and we have m as an even number,

I am not able to proof if we don't find two consecutive edges whose values are the same then the answer will always be NO. I was trying to figure out a case where it's possible.

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

    As mentioned in the editorial, for $$$n\geq 3$$$ it's actually always possible to find two consecutive edges that are equal. just consider 3 vertices $$$x$$$, $$$y$$$ and $$$z$$$. Then two of $$$xy$$$ $$$yz$$$ and $$$zx$$$ edges must be equal.

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

Video solution to problem D: https://youtu.be/U93sCV3I17Y

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

I have a different solution regarding problem D when m is even and there's no cycle with length 2 with the same character (i.e. $$$x \to y = y \to x$$$).

Observation: For every cycle with length 3, there will be always 2 adjacent edges with the same character

Proof: There are 3 edges in the cycle. We put $$$x \to y = a$$$ and $$$y \to z = b$$$. If we put $$$z \to x = a$$$, then $$$x \to y$$$ and $$$z \to x$$$ will have the same characters. Conversely, we can do the same for $$$z \to x = b$$$ and yielding similar result.

Therefore, it is enough to only consider the node permutation $$$1, 2, 3$$$. If $$$m \bmod 3 = 0$$$, then arrange it in such way so the string becomes "abaaba...". If $$$m \bmod 3 = 1$$$, then arrange it in such way so the string becomes "baabaab...". Lastly if $$$m \bmod 3 = 2$$$, then arrange it in such way so the string becomes "aabaabaa...".

The above strategy will work for $$$n \geq 3$$$, and it can be proven that it is impossible for $$$n = 2$$$.

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

    Your solution is more proven and understandable than the solution in editorial! Thank you!

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

Thanks for quick Editorial! I think Problem D is really ingenious!

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

Can someone tell me how is this code for problem C giving TLE on pretest 3. I think it's complexity is also O(N).

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

for problem C, here is my code(python[submission:106605351]), it is showing error on 4th input on test case 2 and, I am unable to look at that input? can someone help me out in my solution? https://mirror.codeforces.com/contest/1481/submission/106605351

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it 
    (Input#4, TestCase #2) 
24 24
19 19 19 17 24 7 12 15 11 23 3 11 1 20 10 23 24 1 23 18 23 17 3 7
19 11 19 17 24 7 12 15 11 13 3 11 1 20 10 23 24 1 23 18 23 1 12 7
22 15 3 20 22 11 18 9 10 21 11 2 13 12 10 12 16 11 16 16 12 16 11 1

    Answer:
YES
22 22 22 22 22 2 22 22 22 22 22 22 10 23 22 22 22 22 22 22 22 22 22 22
    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Thanks a lot,you saved my day,I literally had no idea why my case was failing. And as I debugged this case, boom it got "Accepted". And if you don't mind could you please let me know that how did you get to know about the test case. Once again thanks a lot for helping me a lot.

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

Can Problem B be done in less than O(n^2)?? using stacks ?? something like rain water trapping ? i wasn't able to code one !!

would appreciate some help, if possible code XD

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

    Consider the algorithm, because the height of each does not exceed 100, and when filling a part of the pit ($$$h_{i-1}\geq h_i<h_{i+1}$$$), it will gradually become a flat ground. Before it becomes flat, there can be no The height of the mountain is more than 100, because if there is a mountain of 100, the stone will either roll into a mountain in front of it or roll to a lower place behind it, and it is impossible to add it to this mountain.

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

    The solution from the tutorial is actually not O(n^2) but O(n^3). Consider the input:

    1
100 10000
1 1 1 ... 1 1 100

    We have to do (100 — 1) * (100 — 1) throwing simulations. Those are O(n). So that solution is O(n^3). (In this case we will need 490149 comparisons to be precise.)

    If you want a O(n) solution take a look at my solution. (although one needs to change the vector to doubly linked list to reach O(n) because i use erase alot.)

    106632891

    (It is not trivial that my solution is O(n) because I don't always increment my index. But every iteration either fills a pit or increases the index. You can't have to fill more than n pits in an array of size n (this can be shown using induction over n) so this is O(n).)

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

Problem D looks like a graph problem
Editorial — Well yes, but actually no!

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

Can anyone help me to know the case I missed here 106605508

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

    Nevermind it was an issue of colors being 1 ... n and I assumed it as 0 ... n-1. I want to die

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

      Aren't you the guy who writes beautiful explanations?

      Your code looks clean. Would be great to know about your thought process.

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

        You have to think that what is important ?.

        Important is in this case is that to paint every plank where a[i] != b[i].

        Second thing that is very important is that every painter is coloring some(exactly one) plank.

        Let's call the planks that need to painted some color other than a[i] as bad planks and rest (a[i] == b[i]) as good planks.

        We need all planks to be good at the end. Next thing is that Assume count is number of bad planks that wants color b[i]=k then we need atleast count painters that paint color k.

        If there are more than that and since every painter must paint (they are behaving like spoiled children) they can paint any good or bad plank of color k (if there exists such plank).

        Reasoning for this is to divide into three cases.

        Case 1 the extra painter is painting a good plank then he is just repainting it and it really doesn't do any harm.

        Case 2 the extra painter is painting a bad plank to its correct color but since he is extra that plank was going to be painted to its correct color at some moment , so either he is repainting or painting before its last painting.

        Degenerate Case is that there doesn't exist any plank that wants a color that m-th painter wants then in that case there is no answer. if there doesn't exist a plank that wants a color that (m-1)th or lesser index painter provides then he can color the unwanted color to the same plank the (m-th) last painter is going to paint at last.

        Assuming there exists an answer then you can be sure that last painter is going to paint or repaint some plank correctly. So any painter that comes at (m-1)th or lesser index can paint that exact plank since his paint will not remain in the end anyways.

        It must be clear by now that the last painters of some color k are to be processed first and other painters of color k are extra and they can paint any plank that b[i] = k (Case 2 or Case 1).

        Except degenerate case but that can be check by asking "Is there any painting done after this?". A flag variable can help you here.

        Iterating from mth painter to the first helps us a lot. For implementation details check my submission 106614841

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

Could anyone tell me what's the difference between the AC code and this 106549562

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

    For example, $$$px=0$$$ and $$$py=1$$$, the string is $$$\text{UUDD}$$$, your code is wrong.

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

      Code id edited .. the current id is my 1st submission

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

        An error occurred in the $$$x<=0,y>=0$$$ part

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

        It should be

        if (cnt['L'] >= -x && cnt['U'] >= y)

        But in the code

        if (cnt['L'] >= -x && cnt['U'] >= -y)
        → Reply
»
4 years ago, # |
  Vote: I like it +74 Vote: I do not like it

It's hard to understand E's solution! Why when $$$l[a[i]] \neq i$$$, I should move all elements except $$$a[i]$$$?

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

    There are 2 things to do when $$$l_{a_i} \ne i$$$ :

    • We can either move everything except books with color $$$a_i$$$ so they are next to each other.

    • Or move book $$$a_i$$$ so it can become next to the other books with color $$$a_i$$$.

    Both points are covered in case number 2 and 3.

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

      Can you share intuition behind this: (note that here we move all books even those after rai)

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

        If we keep all books of color $$$a_i$$$ unmoved and there are still books of color $$$a_i$$$ to the left of $$$i$$$ how will we make them adjacent, lets say we have this array $$$[1,2,2,1,1,3]$$$ and $$$i = 4$$$ and we don't want to move the last 2 books of color 1 how could we make all books of color 1 adjacent, simply we say that I will move all books of color 1 to my left then move all books between books of color 1 which is books between $$$i$$$ and $$$n$$$.

        So the sequence of moves are move the first book you will get $$$[2,2,1,1,3,1]$$$, then move book with color 3 to get $$$[2,2,1,1,1,3]$$$.

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

          Considering example and trying to dry run

          5

          1 2 2 1 3

          dp[i]: maximum number of books that can be left unmoved if looking at subproblem of books a[i], a[i+1]...a[n-1]

          dp[5] = 0 (base case)

          start with i=4 (0-indexed):

          dp[4] = 1 + dp[4+1] = 1 (scenario 1 from editorial)

          dp[3] = max(dp[4], cf) = max(1, 1) = 1 (scanario 2 and 3)

          now if dp[3] means the max number of books that can be kept unmoved when solving subproblem [i,n], shouldn't dp[3] be equal to 2. Since the suffix array is {1, 3} and both of them can be left unmoved in this subproblem

          Am I interpreting the meaning of dp[i] incorrectly?

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

            When calculating $$$dp_i$$$ we don't treat suffix $$$[i,n]$$$ alone (as a sperate new array) we still take into consider that there is still more books of color 1 that will be processed later.

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

              Could you explain in case 2, why do we even move the books after Rai? I'm a bit confused here.

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

            I think you got the idea. There are two ways to achieve the target.

            1. move book with color $$$a[i]$$$ to join the book behind.
            2. keep book with color $$$a[i]$$$ ummove and guarantee $$$a[i]$$$ is the first book on the shelf.

            To do the first way, we make $$$dp[i]=dp[i+1]$$$.

            To do the second way, we can do the process as Warawreh says : move all elements except color $$$a[i]$$$ and be ready for the elements $$$a[i]$$$ that is before $$$i$$$ to move to the right.

            But when $$$i==l_{a[i]}$$$, we have extra thing to do : just keep all $$$a[i]$$$ ummove and don't need to consider element before, since there are no $$$a[i]$$$s exist before. That is $$$dp[i]=f[a[i]]+dp[r[a[i]]+1]$$$.

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

              "move the book with color $$$a[i]$$$ to join the book behind" — can you elaborate a bit please? And how $$$dp[i] = dp[i+1]$$$ accomplishes that?

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

                The idea is to keep as many of books unmove as possible. That means all others books should be moved. It is obvious that we can arrange those moved book correctly to make the shelf beautiful.

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

      In case no. 3 when we are moving book $$$a_i$$$, shouldn't $$$dp_i = dp_{i+1}+1$$$ instead of $$$dp_{i+1}$$$ because we are moving $$$i^{th}$$$ book also. Moreover, I can't understand why in case 1, $$$dp_i = dp_{r_{a_i}+1}+f_{a_i}$$$. According to my understanding, it should be $$$dp_i = dp_{r_{a_i}+1}+(r_{a_i}-l_{a_i}+1-f_{a_i})$$$ as there are $$$(r_{a_i}-l_{a_i}+1-f_{a_i})$$$ books between first and last instance of book with color $$$a_i$$$. Kindly help me out with this.

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

        We are counting books that are "not" moved

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

        $$$dp_i$$$ which will find for each i the maximum number of books that we can leave unmoved in the suffix $$$[i,n]$$$.

        You are trying to find the minimum number of moved books, but I am trying to find the maximum #unmoved books.

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

        Sorry, got it, noob error ;(

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

    In my opinion, dp[i] means if books from 1 to i-1 must be moved, the maximum number of books we can leave unmoved in the suffix [i,n]. So if a book in [1,i-1] has the same color with book i, because it must be moved to the back, all the books except a[i] should be moved in order to make all books colored a[i] next to each other.

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

The only reason the solution to AB graph (problem D) needs to be O(n^2 + m) is because it takes that O(n^2) to read the input and O(m) to print the solution. Solving the actual problem can be done O(1). See https://mirror.codeforces.com/contest/1481/submission/106613756 (which sadly I only got right after the contest had ended).

The trick is that, however big the graph is, you only need look at the first three vertices. Either one of these has the same edge label in both directions, or you can find two consecutive edges in the triangle with the same values. You can then solve the problem using these three vertices as described in the editorial ignoring every other vertex and edge.

This also makes it clear that the only case with no solution is the two vertex case with different edges and an even m.

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

Can someone help me find the error in this solution. I have done exactly as the solution above states.

Link : https://mirror.codeforces.com/contest/1481/submission/106616688

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

    An error occurred in the (mp[1][2]==mp[2][3]&&mp[2][3]==mp[3][1]) part

    We should printf("YES\n") first.

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

Why my submission 106617241 is wrong? please provide me a counter case.

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

Does in Ques A if the changing position was allowed would the answer be different?

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

    as long as we can delete , changing positions won't make any difference .

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

What is case 57 of test 3 ?

My logic is same as editorial idk why failing ? code

EDIT: nvm Got it!

Btw if there's any way to see a complete test case please comment down!

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

    Failing on the same case, what is different about this case?

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

We don't need to find x,y,z in problem D because any three node will given us answer , so take first and second and third node and now in a loop 1->2->3->1 there will be atleast two continuous edges which are equal, this will make implementation easy , you can see my submission 106600375

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

hi there! great contest, although I am still struggling with problem C.

here is my submission: https://mirror.codeforces.com/contest/1481/submission/106619632

probably there is some obvious reason why it fails but cannot find it, cannot deduce that also from test cases, anyone could advise? cheers!

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

    Check with this input:

    1
2 2
1 2
1 1
2 1

    I believe your line last_index = colors_later.index(painters[-1]) is problematic. There is no guarantee that this index will be chosen by any painter, as shown by the input above.

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

Using the technique described in this blog, you can improve the time complexity of problem F by a factor of $$$w$$$, where $$$w$$$ is the word size of the machine (usually $$$32$$$ or $$$64$$$).

Instead of using the deque method to solve our 0-K knapsack, we instead decompose our items $$$(a_i, m_i)$$$ into $$$log_2(m_i)$$$ items and perform 0-1 knapsack on those.

Usually, this would add a factor of $$$O(log(n))$$$, but in this case it is provable that the time complexity still remains $$$O(n \sqrt{n})$$$.

The improvement comes from the fact that we can use bitsets for the calculation of the knapsack. Transitions are handled by simple OR functions, and tracing back can be handled by iterating over all new elements of the bitset. This speeds up the dp transitions by $$$O(w)$$$, allowing a complexity of $$$O(\frac{n \sqrt{n}}{w})$$$.

Submission: 106619988

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

Kilani The given code in this tutorial for 1481C — Fence Painting is giving wrong output for some cases.

For example:

INPUT:

1 2 2 3 5 8 9 8 8

OUTPUT(incorrect):

YES 1 1

Correct OUTPUT: NO

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

    That input is invalid. All colors are in the interval $$$[1, n]$$$.

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

Can someone tell me which case am I missing in problem C.106619774

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

106617485 what's the problem with the second test case

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

    $$$k <= 10^9$$$ you're making array of size $$$10^9$$$

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

The editorial for E completely fails to explain the core idea.

The idea is that you can choose any element that you move at the very beginning. Then it becomes obvious that you can add any permutation of the chosen elements to the end of the array of non-chosen elements. So, one necessary condition is that the array of non-chosen elements is beautiful. To understand the DP-transitions, note that the the ONLY case where two equal elements can be both inside the chosen and not chosen arrays is if it's at the END of the array of non chosen elements. So, if it's not the last element, the only way we can add it to the array of not chosen elements is to choose everything before it.

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

Thank you for the quick editorial! The problems are really great!

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

can anyone help me with my problem C? 106634920 or maybe some hack samples ? thanks :)

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

    https://mirror.codeforces.com/contest/1481/submission/106635785 here, i recoded it with "stack" instead of "vector", and I passed... What happened?

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

        whoops my fault... :| thank you so much! o7

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

          I am facing the same problem 109694896. What's wrong? The spoiler's missing

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

            I tried to stress-test your solution and got this test:

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

              Thanks! I immediately find out it should be rep(i,1,n+1)if(need[i].size()!=0)ok=false since the color is index from 1 to n, not 0 to n-1. This is inconsistency of the index. I am aware that I could have such bugs but unable to find a counterexample. Thank you so much.

              Exactly the same fault as hehepig. I should use for(int i=1; i<=n; i++) encounting such inconsistent index next time to avoid messing up myself.

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

        xD in need of help. What's the fault of that code

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

106561762 Can anyone spot the bug in my code why it is not accepted?

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

In problem div2-D, what if it says path must form a circle i.e. start and end point are the same and also you can't visit same vertex or edge twice?

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

Thanks for such a great contest and fast editorials! I love all the interesting problems especially F!

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

Problem D is exciting but problem E maybe too classic?

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

    And also thanks for the quick and good editotial!

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

    Hey, can you point me to some problems similar to E? I kind of understood the editorial but feeling shaky about how to arrive at the basic intuition

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

Could anyone help me find my mistake in this code of problem C?

It got WA on 2 but I can't see the exact test data.

Here's the code : 106592765

Thx a lot.

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

My solution for C is giving WA I've implemented it same as in editorial Please help me find what's wrong with my solution 106644778

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

    The loop which you were using for the greedy distribution of the painters is going till i=m-1, but you have already given the painter for the last one, thus the loop should go only till i=m-2. I changed that and got your solution accepted. 106646446

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

      But even if i goes to m-1(last painter) it will execute else condition only and assign ans[m-1]=ind which did not change the ans as it is already assigned to ind . Please explain if im missing something

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

        I explained C in my blog https://mirror.codeforces.com/blog/entry/87540. I hope you like it.

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

        No, it is not necessary that it will execute the else condition. It can execute the if condition too. Consider the case that s[C[m-1]].size() = 1, then it will execute the if condition and then when you are checking the size of the s[C[i]] (after that in which you are setting the 'flag' to zero), it would be empty and thus 'flag' won't be set to zero. But, in reality, you already have painted the last one earlier and thus, s[C[m-1]] shouldn't have been empty and flag should be set to zero. And this case occurs because a painter can paint only one fence and you have already chosen the fence for the C[m-1] when you are finding the value of 'ind'.

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

B will be more interesting when h[i]<=10^9.

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

Can anyone solve my problem: In problem E, when i is not equal to l[a[i]], we move all the books except for the color a_i, even if it is on the right side of R_a[i]. Why?

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

    The idea behind this is that for example if your original array is 1,2,1,1,1,2,2,2,2,3 you can't say that the numbers that will be unchanged from 3rd number(which is 1 ) to the last one since in this case you need to move the first one and there is no sequence to move the first one to be beside all the other ones (you can read rananjay23 's comment) so you want to have subsequence of numbers such that except for the last color in the subsequence all the colors occurrence (count) in the original array is the same as the subsequence so let's define dp[i] to be the length of the longest subsequence that satisfies that all colors count in the original array is the same as the subsequence except possibly for the last color in the subsequence so if i not equal to l[a[i]] and you considered only the number of colors in the range from i to r[a[i]] + dp[r[a[i]]+1] so in this case your dp[i] won't represent what we want it now will count for subsequences that have number of occurrence not equals to the original number of colors e.x. a=[1,2,2,1,1] so your dp[2]=3 (zero indexed) which is incorrect it should be 2 since you can't take the sequence 2,1,1 but your possible sequences so far are [2] the 2nd 2 or [1,1] the 2nd and 3rd 1 and the longest of them is [1,1] so dp[2]=2

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

Problem D can be solve using dfs + random(for even m). It's my code: https://pastebin.com/29jv66h3

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

I am getting WA in div2-D. Can someone help me find the error in this solution? Submission Link

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

https://mirror.codeforces.com/contest/1481/submission/106664046 can someone help me with my approach on C problem. its showing wa on test case 376 in test 2. the need map stores the index in which we need to repaint. the sb map stores a index of every element in b array. the count array is for checking we have enough painters of that color that we need. UPDATE : found the mistake

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

In problem E , I failed to understand through editorial completely , so i came up with following thought process while upsolving (might be same as editorial):

Note that answer is $$$n-sum$$$ , where $$$sum$$$ is largest subsequence of the array similar to $$$1,1,1,1,1,4,4,4,4,4,5,5,5,5$$$ . Important thing to note here is except the last color ($$$5$$$ here) , count of all other colors in subsequence must be equal to count in the original array.

For example if array was of the form : $$$1,1,2,1,1,3,1,4,4,4,4,4,5,5,5,5$$$ , then we cannot choose $$$1,1,1,1,4,4,4,4$$$ because $$$1$$$ is not the last element in subsequence and we haven't taken all of it's occurrences.

Once we have chosen the largest subsequence such that all similar colors in subsequence is consecutive and except last color in subsequence all other color count in subsequence is equal to that in original array , we can see that we can move all other colors greedily to the end of the subsequence .

For example if array was $$$1,1,2,1,1,3,1,4,4,4,7,4,4,5,5,5,5,2$$$ . Then we can choose $$$1,1,1,1,1,4,4,4,4,4,5,5,5,5,2$$$ as largest subsequence , then we can move the $$$2$$$( at 3rd position),$$$3$$$ (at 6th position) , $$$7$$$ (at 11th position) to the end of the subsequence and thus final arrangement will be $$$1,1,1,1,1,4,4,4,4,4,5,5,5,5,2,2,3,7$$$ .

For implementation while iterating we can keep track of largest such subsequence ending with $$$a[i]$$$ and also largest subseqeunce such that all colors in subsequence have count equal to that in original array (even the last color) .

Code is very short for this problem . submission

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

    I think I understood your idea, but could you help me figure out the implementation please? I didn't understand the submission you posted.

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

      you can try to see how code works line by line (i.e dry run) by taking samples in question and in my comment .

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

106663413 Can anyone please point out the error in this code for problem D?

Its been hours since I am trying to debug this code but its not getting an AC.

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

    I haven't solved this problem yet, but I think this input is a counter case:

    1
3 2
*ab
b*a
ab*

    Your code outputs 1 2 1 which I believe corresponds to a non-palindromic string 'ab'?

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

      Yes, I understood that what was the error in it, if (m/2) was odd so I was trying to print aabbaabbaa..... and so on and the last 2 letters would be 'aa' but through my code the last 2 letters were not coming out as 'aa' always, I just had to print d2+1 in place of d+1 at the last line, thanks for pointing out the error.

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

Why if M / 2 is even we cannot write out the vertices in the order x -> y -> z -> y -> x? (Task D).

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

Can someone please help me understand why my solution for problem B is WA? I'm placing boulders until there is no i that satisfies a[i]<a[i+1] in the array. I tried many test cases which I can do a dry run of but couldn't find where am I going wrong. My Submission

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

problem E was just amazing !!!

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

So for the problem E, why if i != l(ai) cant you just leave all ai unmoved and move only those between i and r(ai) same as if i = l(ai) and add dp(r(ai) + 1)?

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

If you can read Chinese，I'd like to recommend my blog

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

Can someone help with this: https://mirror.codeforces.com/contest/1481/submission/107022262

I did almost same explained in tutorial, but there is something wrong with my code, it doesn't pass all test cases, it stuck on test case 59 or 3rd set. It shows, that output string isn't a palindrome. Any help effort is appreciated.

Thank you!!

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

https://ideone.com/hOl1eG

Can anybody tell me the mistake in this solution for problem D. I am getting the following error in test case 3 wrong output format Expected integer, but "YES" found (test case 59)

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

Problem E — Can anyone tell me how to get the answer in 4 moves for the following input? 8 6 6 1 6 3 1 8 8 10, AC program outputs 4.

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

    1: move first 8 to end, 6 6 1 6 3 1 8 8 10 8

    2: move 10 to end, 6 6 1 6 3 1 8 8 8 10

    3: move first 1 to end, 6 6 6 3 1 8 8 8 10 1

    4: move the other 1 to end, 6 6 6 3 8 8 8 10 1 1

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

Kilani In problem F, when ans == mx + 2, why do you sort the vertex by its size as a subtree out of greed ? Can you explain it

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

For question C: Can somebody find error in my code. https://mirror.codeforces.com/contest/1481/submission/158748611

I am assigning last painter to a correct fence. Then I have made req, which stores for each color, which fence needs to be repainted(YES i have excluded the last painter one). Then for each painter if this color needs to be assigned then color that node otherwise color the fence which last painter will paint. If no fence needs to be repainted at last, then answer is YES

→ Reply
»
15 months ago, # |
  Vote: I like it +10 Vote: I do not like it

allah hayou ageed

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

https://mirror.codeforces.com/contest/1481/submission/288751901

NEED QUICCKKK HELPPP whats causing runtime rror here?
FENCE PAINTING PROBLEM--

→ Reply