Newtech66's blog

By Newtech66, 4 months 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

»
3 months 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.

  • »
    »
    3 months 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.

    • »
      »
      »
      3 months 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.

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

    Who tf asked?

  • »
    »
    3 months 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.

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

      How do you prove that this is sufficient?

      • »
        »
        »
        »
        3 months 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.

        • »
          »
          »
          »
          »
          3 months 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"?

          • »
            »
            »
            »
            »
            »
            3 months 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.

    • »
      »
      »
      3 months 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.

»
3 months 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.

»
3 months 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?

»
3 months 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

»
3 months 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 :)

»
3 months 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

»
3 months 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.

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

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

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

Problem A:

In the solution it is written, p = r/(b+1) and q = r mod (b+1). However, in the implementation for Python, it is written p = r%(b+1). This can be slightly misleading.

»
3 months 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.

  • »
    »
    3 months 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.
»
3 months 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).

»
3 months 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!

»
3 months 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.

»
3 months 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

  • »
    »
    3 months 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

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

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

  • »
    »
    3 months 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.

»
3 months 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!

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

    The whole cost of moving capital and the cost of conquering the cities can be counted separately. I think the part where representing them as

    $$$ a\cdot(x_j-x_i) \quad, \quad b\cdot((x_{i+1}-x_i)+(x_{i+2}-x_i)+\ldots+(x_j-x_i)) $$$

    is pretty clear. in $$$(x_{j_1}-x_0)+(x_{j_2}-x_{j_1})+\ldots+(x_{j_f}-x_{j_{f-1}})=x_{j_f}-x_0$$$ formula,the author is trying to calculate the cost made by moving capitals(we can get the cost by multiplying $$$a$$$ to this formula). The capitals are in positions $$$x_{j_1} ,x_{j_2} ,x_{j_3} ,\ldots, x_{j_{f-1}} ,x_{j_f}$$$ chronologically ,where $$$x_{j_f}$$$ is the final position of the capital.According to the formula, it can be abbreviated as $$$x_{j_f}-x_0$$$.It means the cost of moving capitals can only be determined by the final position of the capital.

    Then,let's see $$$b\cdot(p_j-p_i-(j-i)\cdot x_i)=b\cdot(p_j-p_i)-b\cdot(j-i)\cdot x_i$$$ part.this is the cost of conquering cities from current capital before moving the capital to the next position. let's observe $$$b\cdot(p_j-p_i)$$$ first, if capitals are still in positions $$$x_{j_1} ,x_{j_2} ,x_{j_3} ,..., x_{j_{f-1}} ,x_{j_f}$$$, the entire sum can be represented as $$$((p_{j_1}-p_0)+(p_{j_2}-p_{j_1})+\ldots+(p_{j_f}-p_{j_{f-1}})+(p_{n}-p_{j_{f}}))\cdot b=p_{n}\cdot b$$$

    Finally, there is $$$b\cdot(j-i)\cdot x_{i}$$$ part that we haven't discussed yet. The sum of this part is represented as $$$C$$$ in the tutorial. which can be represented as $$$((j_{1}-0)\cdot x_{0}+(j_{2}-j_{1})\cdot x_{j_1}+\ldots+(j_{f}-j_{f-1})\cdot x_{j_{f-1}}+(n-j_{f})\cdot x_{j_{f}})\cdot b$$$. if we want to maximize this, we can move our capital every time to the right after we conquer a new city,since the cost of moving the capital is only determined by the final position of the capital. In this case, we will be able to maximize $$$C$$$ by making all $$$j-i$$$ s equal to 1. Thus it becomes

    $$$ C=x_0\cdot 1+x_1\cdot 1+\ldots+x_{f-1}\cdot 1+\underbrace{x_f+\ldots+x_f}_{n-f\text{ }\mathrm{times}}=p_f+(n-f-1)\cdot x_f $$$

    Finally, all we have to do is to enumerate the possible final position of the capital.and find the minimum answer of it. (sorry for my bad English,please notice me it there is anything wrong or unclear with my idea)

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

    If the Math for this problem is hard to understand , you can pretty much implement the solution using concept of prefix array. Like you can put the capital at each and every index and compare and output the min cost, in theta(n) time****

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

Can Anybody give me the solution of Problem 'A' in C? Please

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    #include <stdio.h>
    
    void blind_eyes() {
    	int n, r, b;
    	scanf("%d %d %d", &n, &r, &b);
    	int _r = r/(b+1);
    	int x = r - _r * (b+1);
    	char s[101];int c = 0;
    	while(b--) {
    		 if(x > 0){for(int i = 0; i < _r + 1; i++)s[c++] = 'R'; r = r - _r - 1;}
    		 else {for(int i = 0; i < _r ; i++)s[c++] = 'R'; r = r - _r;}
    		 s[c++] = 'B';
    		 x--;
    	}
    	for(int i = 0; i < r; i++) s[c++] = 'R';
    	for(int i = 0; i < c; i++)printf("%c", s[i]);
    	printf("\n");
    }
    int main(){
    	
        int t;
        scanf("%d", &t);
        while(t--)
        	blind_eyes();
    	
     	return 0;
    }
    
»
3 months 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?

  • »
    »
    3 months 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
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

B and C were beautiful that I only came to know when contest got over, but thanks alot for problem A that took all the confidence and time.

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

    Don't talk bullshit Dumbass. A and B were meaningless. I don't know which f**head published these problems.

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

For problem D reverse sort sum, the explanation in the editorial for how to efficiently compute the value of some element of the C array is unclear to me. Can anyone explain what does it mean by maintain a left border, what is t[i] (I don't see a t[i] in the implementation, is it b[i] instead?), and how the formula v[i]=c[i]-(t[i]-i) is derived?

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

pretty good

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

Can someone help me figure out why my solution for A is run out of time? 154216123

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

    because you are f**king idiot!!!

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

      Please shut up,fucking stupid ass bitch,you just like the garbage

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

        even my dick could solve this problem. now you know who is garbage. dumbass.

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

          hhh,I don't think u have any dick , you look so funny.

»
2 months 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

»
6 weeks 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.

  • »
    »
    6 weeks 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.

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

can anyone please tell the DP approach of problem C