Newtech66's blog

By Newtech66, 2 years ago, In English

Thank you everyone for your participation. Do vote under the Feedback section, and feel free to give your review of the problems in the comments.


1659A - Red Versus Blue

Idea: TimeWarp101
Editorial: TimeWarp101

Hints
Solution
Implementation (C++)
Implementation (Python)
Feedback

1659B - Bit Flipping

Idea: Newtech66
Editorial: Newtech66

Hints
Solution
Implementation (C++)
Implementation (Python)
Feedback

1659C - Line Empire

Idea: Newtech66
Editorial: Newtech66

Hints
Solution
Implementation (C++)
Feedback

1659D - Reverse Sort Sum

Idea: Newtech66
Editorial: Newtech66

Hints
Solution
Implementation (C++)
Feedback
Challenge

1659E - AND-MEX Walk

Idea: Newtech66
Editorial: TimeWarp101

Hints
Solution
Implementation (C++)
Feedback
Challenge

1659F - Tree and Permutation Game

Idea: Newtech66
Editorial: Newtech66

Bench0310 has written another proof for the solution to this problem here and here. Many thanks to him!

Hints
Solution
Implementation (C++)
Feedback
  • Vote: I like it
  • +74
  • Vote: I do not like it

| Write comment?
»
2 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Writing for the ones I solved:

  • I noticed many people complaining about A in the main thread. Although I wasn't affected by the judge server failing, I thought the observations needed for this problem were fairly straightforward, although maybe for some it could have been tricky to implement.
  • Problem B also had a very simple idea, but I found implementation for this problem to be quite hairy. Still a decent problem although a bit trollish for the second spot.
  • Problem C required a very straightforward greedy observation. I think this should have been swapped with the B problem.
  • Problem D is interesting. There exist other solutions than the one provided in the editorial. I'm not exactly sure how to describe it but the code is here.

I spent more time on problem B than problems A, C, D combined, although that's mostly my fault.

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

    I think the time you spend on each problem just depends on you, not on the problem's quality. I spent more time on A, than on B or C. Also, I do not get why you say B's implementation was hairy, I didn't have any problems implementing it and the idea was easy to get.

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

      I agree that the idea was very simple. For me personally, I overcomplicated the implementation and ended up falling in a lot of traps. I knew that it was mostly my fault, but I saw that others had similar experiences, so I thought it would be fairly reasonable to bring it up.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it -45 Vote: I do not like it

    Who tf asked?

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

    For the problem D, I have the same solution as you. It is pretty hard to explain, because it is a result of making several observations.

    The first thing I noticed is that the first number is the (0-indexed) position of the first zero in the original array; n means that there is no zero. That is because we either have a zero there (which will never be replaced) or a one (which will be replaced as soon as we encounter a zero). After thinking for a while, I was able to extend this logic to "if $$$A_i = 1$$$, then $$$C_i$$$ is the 0-indexed position of the i-th zero in $$$A$$$". That's because we will replace 1 with 0 as soon as we find the i-th zero, but no sooner since we first have to set the first (i-1) elements to 0. From this, we infer the first rule: if $$$A_i = 1$$$, then $$$A_{C_i} = 0$$$.

    Now what about the case when $$$A_i = 0$$$? Well, if there aren't any 1's before it in A, then (and only then) $$$C_i = 0$$$. Otherwise, it will become a 1 on the i-th step, because it will be the last sorted element. And after that, it will become a 0 again when we add the i-th zero. That means that $$$C_i = Z_i - i$$$, where $$$Z_i$$$ is the position of the i-th zero. Thus, if $$$A_i = 0$$$ and $$$C_i \neq 0$$$, then $$$Z_i = C_i + i => A_{C_i + i}$$$ = 0.

    One last thing we need to observe is that after we encounter the first non-zero $$$C_j$$$, we always know $$$A_i$$$ before processing it, because we know the position of the (i-1)-st zero and there is at least one 1 before this point.

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

      How do you prove that this is sufficient?

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

        Essentially, we learn the position of every zero in the array. On all the other positions there can only be ones. So there is only one solution, and we find it.

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

          How can you say that "at all other positions, there can only be ones"?

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

            Because there isn't a zero, and the only other option is one.

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

      Good explanation. Breaking it up into the core "observations" is a good way to put it.

»
2 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Thank you problem writers for problem B. I enjoyed solving it. Made me get my brain to work for the first time.

»
2 years ago, # |
  Vote: I like it +51 Vote: I do not like it

I remember seeing blogposts that said A’s are too ad-hocish and if you are new to CP and have no math competitions background you can’t really solve them. And some even suggested that first problems should be more about implementation than about math observations. But yesterday’s A was about pigeonhole principle and outputting such string. So basic math (you may even not know what pigeonhole principle is but you understand it intuitively) plus implementation. However people complained that A is too hard. So may I ask what the hell is going on?

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

Oh so that why I got WA on A, I'm suck at string problem as usual

And I got the exact idea for B quickly but I outsmarted myself lol

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

nice problems to training my weak brain.

And i've been struggled on B for more than 30min :)

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

For Problem D, We can also iterate from left to right in C and determine indexes of 0 in A.

Video Solution : Problem A-D

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

In the implementation of E, this line seems redundant: rep1(j, 29) if(one[j].is_joined(u, v)) return 1; Because rep(j, 30) if(zero[j].is_joined(u, v)) return 0; is easier to satisfy than the above.

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

So nice problems for div2.I love them,especially D and E.

»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Solution for the challenge of problem D:

First, we can check if the sum of values in $$$C$$$ is divisible by $$$n$$$, if not, then the array is invalid. Now, lets just solve the problem considering the array is valid, and later check if the resulting sequence produced by our algorithm can make the array $$$C$$$ or not. The goal is now to solve the reverse problem — we have the array $$$A$$$ and need to create the sums-array $$$C$$$ from it.

I'll assume one-based indexing from here on. Consider finding the sum of ones for an index $$$i$$$ in the array $$$A$$$.

First of all, we check its contribution in the first $$$i - 1$$$ iterations. Until then, $$$A[i]$$$ will remain unchanged, so, if $$$A[i] = 1$$$, then $$$C[i] = (i - 1)$$$, else $$$C[i] = 0$$$.

From iteration $$$i$$$ onwards, $$$A[i]$$$ will also get sorted along with the previous elements. The $$$i^{th}$$$ value in the sorted sequence can only be $$$0$$$ if there are atleast $$$i$$$ zeros in the sequence. So, we need to find the index $$$j$$$ such that $$$A[j]$$$ is the $$$i^{th}$$$ zero in the sequence. We can do this by storing all zero value indexes in a separate array.

From iteration $$$i$$$ and until before the $$$i^{th}$$$ zero has been found, the value of $$$A[i]$$$ will be one. If it is found at index $$$j$$$, then the contribution to $$$C[i]$$$ will be $$$(j - i)$$$. (If $$$i$$$ zeros do not exist in the sequence, then the contribution to $$$C[i]$$$ will be $$$(n + 1 - i)$$$.

So, for each element, $$$C[i] = (i - 1) + (j - i)$$$ if $$$A[i] = 1$$$, and $$$C[i] = (j - i)$$$ otherwise.

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

    It is actually possible to solve it without solving the reverse problem. The solution requires minimal additional casework. But good job.

    P.S.
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

If you prefer command line, checkout CF Doctor for more flexibility and faster feedback.

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.

If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).

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

Hi guys, I have some wonders and hope to seek for explanations! In problem D:

Submission 1: I use set and get AC -> complexity O(???) (I'm still confused about this)

Submission 2: I use deque and get TLE -> I expect the complexity would be O(NlogN) So I hope you guys will point out for me where did I do wrong.

Sorry for my bad clarifications! Thanks in advance!

I have known why my code got TLE! Thanks!

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

If any one can help me finding test case for problem D which fails my submission https://codeforces.com/contest/1659/submission/153997173 it will be really helpful it passes almost all smaller test cases it is failing on when n is huge, thanks in advance.(sorry for my bad english)

Edit: no need, found the bug.

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

Can someone help me figure out why my solution for A is WA'ing?

153898766

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

    Your code fails for the below test case: Input: 12 10 2 Output: RRRRBRRRRBRR Expected Output: RRRRBRRRBRRR According to your code 10 is begin split into 3 parts i.e., 4, 4, 2 whereas optimal division is 4, 3, 3 So we need to split the parts such that Max valued part — Min valued part is as small as possible!

    My solution for reference — 153908138

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

      Why does this matter, both have a maximum of 4?

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

    You can look at the testing details, the failed test isn't that long. Your solution uses too many R's in the beginning, which leads to a large cluster of B's in the end.

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can someone explain how to solve problem C, I having hard time following tutorial!

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

In solution of D, paragraph 5, every case after "Otherwise" word is very ambiguous. Can someone explain with correct grammar please?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • let cnt1 be the number of 1's in the array A
      Now consider the last element in array A
    • if it is 1 then it will stay 1 for all arrays B[i] (B[i][n] = 1) and because we have N of them then C[n] will be equal to n
    • if it is 0 and cnt1 = 0 then C[n] will be 0 because (B[i][n] = 0)
    • if it is 0 and cnt1 > 0 then for surethe last element for array B[n] (B[n] is the array generated by sorting the whole array) is 1 (B[n][n] = 1) and that means that the sum of all element B[i][n] is 1
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i think i solve C in another greedy way. here it is. code

the key is to see change location as saving money for further conquer. so every iteration i compare how much to change location(c2) and how much i can save(c1). if c1 < c2, that means worthless to change. otherwise, let's do change. though it get AC, i'm curious about this greedy correctness.

hope for some help

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

In problem B, why is it correct to add all remaining moves to the last element? What if the number of remaining moves is odd? I just cant figure out how to prove the remaining number be even.

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

    The remaining number can be odd and it may make the last element go from 1 to 0, but since we want lexicographically maximum, its better to have the earlier element maximum, and then use the remaining moves on last.

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

can anyone please tell the DP approach of problem C

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

Can someone please tell the approach to solve this question through dp. I am trying through dp but it is getting TLE in Test Case 5 .

my dp code is

ll dp[100002];

long long solve(int i ,int i2){

long long cost =0;

if(i>n)return cost;

if(dp[i2] != -1)return dp[i2];

cost+= b*(abs(arr[i]-arr[i2]));

cost += min( solve(i+1,i2) ,a*(abs(arr[i]-arr[i2])) + solve(i+1,i)  ) ;

return dp[i2] = cost;

}

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

Just storing how I solved C question. No matter what I have to visit all the kingdoms and say at each iteration my capital was xci then cost=conquer+ shifting_capitals (I am taking for n=5) and xc1=0(given initial capital) cost=b((x1-xc1)+(x2-xc2)+(x3-xc3)+(x4-xc4)+(x5-xc5))+a(xc2+(xc3-xc2)+(xc4-xc3)+(xc5-xc4)). cost=b((x1-xc1)+(x2-xc2)+(x3-xc3)+(x4-xc4)+(x5-xc5))+a(xc5) cost=b(x1+x2+x3+x4+x5+-b(xc1+xc2+xc3+xc4+xc5)+a(xc5) note that answer is depending only on the final position of the capital thus we will iterate over all x to check if it can be my final position of the capital and take the minimum answer out of it. remeber that if say xc2 is my final capital while checking make sure to write xc3=xc4=xc5=xc2 then only add.