When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

triple__a's blog

By triple__a, history, 4 years ago, In English

Hope you enjoy those tasks!

1332A - Exercising Walk

Tutorial
Solution (python by pikmike)
Solution (C++)

1332B - Composite Coloring

Tutorial
Solution (python by pikmike)
Solution (C++)

1332C - K-Complete Word

Tutorial
Solution(python by pikmike)
Solution(C++)

1332D - Walk on Matrix

Tutorial
Solution(python by pikmike)

1332E - Height All the Same

Tutorial
Solution 1(python by pikmike)
Solution 2(python by pikmike)

1332F - Independent Set

Tutorial
Solution(C++)

1332G - No Monotone Triples

Contributor of idea of the solution: awoo

Tutorial
Solution (C++)
  • Vote: I like it
  • +279
  • Vote: I do not like it

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

Auto comment: topic has been updated by triple__a (previous revision, new revision, compare).

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

Video tutorial for D

Here you can see how to prove the described solution, which is similar with the editorial's approach.

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

    I saw your video tutorial but I am not able to understand the complete solution.

    I understood that we want to generate a matrix such that the answer by Bob's algo is 0, and optimal answer achievable is K.

    But other than that I am not able to understand anything.

    Like what is the actual fault in Bob algo and why his algo not able to achieve optimal answer. And how you are coming up with the matrix given in editorial.

    So can you help me?

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

      in order for a bit to be present in the final answer we must ensure that the bit is present in all the numbers from the path. Even though the dp can be correct at some step, greedily taking the best bitwise AND up to some (i, j) may prevent us from using subsequent bits which may have ended up in the answer

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

        But can you explain what is the correct approach to find maximum answer using DP because bob's approach is incorrect.

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

    Clear and lucid explanation. Thanks.

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

    Why is nobody talking about the fact that the question initialized dp0,1 as a1,1. Why was it done? What is it's implications? Is it just to make the dp work? Could it be dp1,0 as a1,1?

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

      it does not affect anything tbh. i wrote it because it is the shortest way to implement (tho the naive dp idea is incorrect as the statement suggests).

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

Thanks for such a fast editorial! Nice round!

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

Fastest editorial in the west :3

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

There is the tutorial of problem 1327A instead of 1332A
UPD: now fixed

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

Why editorial for A is an editorial to another problem?

EDIT: fixed now

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

Auto comment: topic has been updated by triple__a (previous revision, new revision, compare).

»
4 years ago, # |
Rev. 4   Vote: I like it -39 Vote: I do not like it

.

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

Why so many people get "Wrong answer on test 57"(problem E)?

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

    Because their code fails to produce correct output on test 57 of problem E?

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

    So do I. Hope somebody can tell me what happen.

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

    I guess it is because Fermat's little theorem is not true if gcd(a, p) != 1

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

    I figured out why many people(including me) got wa on test 57 in E)
    it was because of %(mod-1)

    x^y≡x^(y%(p-1))mod p
    but there is a condition that x needs to be coprime to p
    the following test case was a corner case- 998244352 2 1 998244353

    the sad thing is that %(mod-1) wasn't even needed. I wish this test case was in pre-tests

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

      "the sad thing is that %(mod-1) wasn't even needed."

      Just realize it and feel sadder :(

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

    I think I know what happened on it.

    This test is:

    998244352 2 1 998244353

    So, in my program, there is somewhere that are expected to calculate: (998244353^998244352)%998244353, the correct output for it should be 0. That's ok.

    However, if you use Euler Theorem there to calculate, then what you do is indeed calculating (998244353^(998244352%998244352))%998244353=(998244353^0)%998244353

    AND, MY QUICKPOW() FUNCTION CONSIDERED THE VALUE OF 998244353^0 IS 1 !

    And this lead to the eventual WA.

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

People have used DSU/DFS in their solutions for problem C. Could someone explain how that works?

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

    I approached C using DSU. For this, we needed to find out about what all indices should have the same char. Now, let's consider a string of length n and k=k. Condition 1: A/c to question indices i, i+k, i+2k.... should have the same char at their index. Hence, we will union(i,i+k) , union(i, i+2k) ..... Condition 2: String should be a palindrome. So, index (0,n-1) , (1,n-2) , (2,n-3)...should have the same char at these positions. Hence, we will also do a union of these indices. After these operations, our DSU will provide which all indices belong to the same connected component. Now, that we have the info about the connected components we can easily find the char which has occurred the most number of times in that component. The rest of the char needs to be replaced for that component and added to our overall sum.

    Sorry for my bad English.

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

    For dfs, if you are currently at position $$$i$$$, the position $$$i+k$$$ and $$$n-1-i$$$ should have the same character as position $$$i$$$. So you can do dfs an find which positions should have same characters and calculate the answer based on which character appears the most times on each group. Similar idea to DSU solution.

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

The round definitely made me think (and question my existence). Kudos to triple__a.

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

I am not satisfied with the pretests of C. My $$$O(n^2)$$$ solution passed them. It would have been trivial to fix it, so now I am feeling a bit bitter.

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

nice 1;

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

C is doable with dfs. It'll be an easier approach.

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

    Could u elaborate

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

      Yeah sure, In the graph connect the indexes which will have the same value. ie. (i) with (n+1−i) and (i) with (k+i) now each connected component of the graph will have same value in the final string. Optimal count of the characters to be deleted can be obtained using map. I am weak in calculating time complexity but according to my understanding it'll be O(N). Link to the AC soln

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

I want to know if the input is 1 12 6 3 5 7 11 13 17 19 23 29 31 37 The output is 12 1 2 3 4 5 6 7 8 9 10 11 12 but I think the first data could belong to the color 2 so we can use only 11 color

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

    well, the condition said that all inputs are great or equal to 4

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

    numbers must be composite

    A positive integer is called composite if it can be represented as a product of two positive integers, both greater than 1. For example, the following numbers are composite: 6, 4, 120, 27.
    The following numbers aren't: 1, 2, 3, 17, 97
    
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Tiny correction triple__a, You've written Solution(C++) but the code isn't C++ for problem C. Thanks for the fast editorial, and a great round

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

    thanks for pointing it out,but i am not convenient to edit right now. i will fix it tmr

    upd: it is now fixed

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

I would like to give an alternative solution for E using dp and matrices. From the editorial, we have a proof that the answer only depends on the number of ways choosing odd number of odd cells and that of choosing even number of odd cells.

Let $$$dp_{odd}[i]$$$ and $$$dp_{even}[i]$$$ be the number of ways choosing $$$i$$$ cells with odd number of odd cells and even number of odd cells respectively.

$$$dp_{odd}[i] = dp_{odd}[i-1] \cdot E + dp_{even}[i-1] \cdot O$$$

$$$dp_{even}[i] = dp_{even}[i-1] \cdot E + dp_{odd}[i-1] \cdot O$$$

Then we can use matrix and binary exponentiation to calculate the answer.

74978938

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

    This is cool! BTW, I think this is a mistake, dp[i] should depend on dp[i — 1].

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

    haha(lol); :) Interesting code!

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

    oh I see you're a man of culture as well

    74987963

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

    You can prove by induction that $$$dp_{even}[i] - dp_{odd}[i] = (-1)^i$$$ if $$$L, R$$$ are odd, $$$(-1)^{i+1}$$$ if $$$L, R$$$ are even, $$$0$$$ otherwise. Moreover, $$$dp_{even}[i] + dp_{odd}[i] = (R - L + 1)^i$$$. You can find $$$dp_{even}[i]$$$ and $$$dp_{odd}[i]$$$ by solving the resulting system of equations.

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

    Thank you!

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

Is there solution for D if we say that values in matrices are a[i][j]<=1e5?

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

    I think, if k == 65536 (2 ^ 16), there isn't any solution.

    Proof by contradiction: There is an optimal way with score not less than k (at least 65536). Then dp solution can find a way which score is at least 65536 too. The optimal way can't have score more than 2 * 65536 — 1 due to all numbers are at most 100'000. So difference between optimal way and dp way is less than k.

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

      In the problem it is mentioned that all numbers can be in range [0, 300000]

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

        Yes, but the question was about range [0, 100'000]

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

triple__a Thanks for such a good round in these days!! No queueforces even after Contest and fast editorial!! Kudos

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

I have done c using dsu it is efficient in this manner

but anyone did it using dp or is it not possible ? explain your solution if possible(any complexity)?

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

My solution of E failed on test 57. I removed b % phi(mod) in the power function and it passed. Can anyone tell why? (a ^ b) % m = (a ^ (b % phi(m) ) % m. Since m is prime, so phi(m) = m-1 Although it was not needed, I think this shouldn't fail.

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

    a and m need to be co-prime for this. Test 57 violates this.

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

    Case 57 is 998244352 2 1 998244353. (Let the modulo be $$$M = 998244353$$$)

    So $$$r - l + 1 = M$$$ and $$$n m = 2 (M - 1)$$$
    The answer should be $$$M^{2 (M-1)} \mod M = 0$$$.
    But if you use $$$b\mod \phi(M)$$$ as the exponent, you are computing $$$0^0$$$ and the code returns 1 instead.

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

problem C first solution — wrong language (python code, linked as c++)

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

1 13 6 10 15 7 11 13 17 19 23 29 31 37 41 for this input m = 11 but my code give m = 12 and still accepted.

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

    is this valid input? bcoz i checked many code for this input and every code giveing m = 12.

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

      This input isn't valid, input must contain only composite numbers

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

      The input is not valid because it can only have composite numbers not prime.

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

I think $$$k=3$$$ case is harder for problem F, I understand how to check if answer is 3 or 0, but how to reproduce the indices for $$$k=3$$$?

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

    i b[i]-1 and b[i] will work if b[i] is the smallest index such that the answer is 3.

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

How to write spj for D?

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

    for the optimal answer, it can be done by checking bits from the most significant one to the least and run a bfs or dfs

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

    Good problem. This is the original version of D.

    As problem-setter said, use bfs to greedily check by bits.

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

      I got it, thanks.

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

      I don't understand it. I think the bits are not independent. Can you please explain it further?

      upd:Oh I think I have understood it... I'm a fool.

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

      can you give me an idea of how to do it, like i understood that we will go bit by bit from the most significant to the least significant, but what value to keep and discard as we do the transition.

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

        Let's assume a[i][j] is your outputs, and cur[i][j] = (a[i][j] >> k) & 1 when you check the k-th bit.

        Set an array flag which is filled with 1 initially, and flag[i][j] == 1 means (i, j) is in legal routes when you finish checking the previous bit. Set an array tmp, which is used to check the current bit. Then, for each cell (from the upper left corner to the lower right corner), tmp[i][j] = (tmp[i - 1][j] | tmp[i][j - 1]) && cur[i][j] && flag[i][j], which means (i, j) is in legal routes iff (there should be at least 1 legal source) and (this cell is legal in the current bit) and (this cell is legal in the previous bit). At last, replace flag array with tmp array to check the next bit.

        This is what my code do. If you want, BFS also works.

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

For E, can someone give more details about how to apply Newton expansion? I really cannot see a direct mapping :'(.

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

    $$$(a+b)^n=\sum\limits_{i=0}^n\tbinom{n}{i}a^{n-i}b^i$$$

    $$$(a-b)^n=\sum\limits_{i=0}^n\tbinom{n}{i}a^{n-i}(-1)^ib^i$$$

    Then we have $$$(a+b)^n-(a-b)^n=\sum\limits_{i=0}^n\tbinom{n}{i}a^{n-i}(1-(-1)^i)b^i$$$

    If i is even, then $$$1-(-1)^i=0$$$,else $$$1-(-1)^i=2$$$

    So $$$(a+b)^n-(a-b)^n=\sum\limits_{i=1,3,5,...}^{i\leq n}2\tbinom{n}{i}a^{n-i}b^i$$$.

    In other words, $$$\sum\limits_{i=1,3,5,...}^{i\leq n}\tbinom{n}{i}a^{n-i}b^i=\frac{1}{2}((a+b)^n-(a-b)^n)$$$

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

for 1332A can someone please explain why shouldnt we consider both height and width at the same time

why taking only x axis in calculations. thank u!

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

    because once you give a valid walk something like UDUDLRLRUD. you may rearrange it so that UD is in the front and LR part in the back and it will be also valid

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

      what if there is a case where u dont cross the limit horizontally so it satisfies the condition in 1D but in vertical distance u go out of range!!

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

        the answer is no if x-axis says no or y-axis says no

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

I solved F in this way.dp[0][x] and dp[1][x] mean the results in x's subtree and x in edge induced subgraphs.than the subtree combine with the father and add to the father node so I get this:

dp[0][x]=dp[0][x]+dp[0][x]*(dp[0][ed[i].v]+dp[1][ed[i].v]);
    dp[1][x]=dp[1][x]+dp[1][x]*dp[0][ed[i].v];

initially, every node's dp[0][x]=1; dp[1][x]=1; for example,1-2,2-3,2-4, first 3 and 4 node are both (1,1), than in node 2, first I choose the 3 to mix 2 ,node 2 get (3,2) ,means now 2-3 this tree's ,with node 2 in edge induced subgraphs, results .than mix 4 to 2 ,get node 2 (9,4) as the question required, add all dp[0][x] and dp[1][x] to answer and remove the one node set , so ans-=2*n it shows right in two examples. what's wrong with me? could someone help me?

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

    I actually did the exact same thing (also I think you mean problem F, not E). I think it might be that this doesn't allow for combining groups of disjoint sets of the subgraph (this dp only allows the groups to be one connected component), but I'm not sure how to modify it to include this.

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

      ok, I get it.edge induced subgraphs isn't connected graph .

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

Writing several times within one explanation that it is easy and how easy it is does not makes it more understandable, or even easy.

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

hope everyone uploads the tutorials this fast as we r eager and curious about problems solutions!

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

How did my solution for problem G get TLE on test 109?

The pre-calculation costs only 202ms on test 109, and answering a query only needs constant time. So I don't think it could get TLE. However, the same code got accepted with 64-bit compiler (Submission). So strange.

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

Python solution for Problem C is incorrectly mentioned as C++, please correct it triple__a.

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

I was pretty sure that there is a formula solution for E, but during the contest I wasn't able to come up with a correct idea... So now you can check out my solution that uses matrix multiplication:74968680

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

Why verdict on task D test 2 is WA? Difference equal to 1...

1
Output
3 3
3 1 0
2 3 0
2 2 1
Answer
3 4
7 3 3 1
4 8 3 6
7 7 7 3
Comment
wrong answer difference is 0 - 0 = 0
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    At cell (3, 2) the algorithm will choose from 2&2 and 3&2 which are both equal to 2, and the optimal answer is 2 to begin with.

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

I used DSU for C. My submission

We can start by assigning each position of the string as a disjoint set.

Then we do a union on all those positions which have to be equal according the the Palindrome condition and the Period of size K condition.

After that I assigned characters to each disjoint set greedily. (ie for every disjoint set of positions, I assigned the character with maximum occurence in the particular disjoint set).

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

To begin, this post has nothing to do with the contest (i just need help with a topic is all)..

I want to learn "binary search the answer" and other details of the algorithm, I tried searching the internet and Codeforces blogs but couldn't find anything specific to the topic that I was looking for.. I think I understand discrete binary search (about monotonicity of the sequence for some predicate.. but I think that's standard and commonplace) but I need to master the details so that I can solve problems that aren't "apparent to involve anything with binary search yet does so beautifully". Can anyone help?

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

Can someone pls explain C in ann easy way?

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

    Problem

    Given a string s of length n and a "period" k, find the minimal number of changes such that the string becomes a palindrome AND every kth character is identical (i.e. s[i] = s[i+k] = s[i+2*k] = ..)

    For eg. if the string is "abba", and k=2, this is not a valid string because the 0th and 2nd chars are different, and so are the 1st and 3rd. So you'd need to change 2 characters to make this "aaaa" and so the answer would be 2.

    Solution

    • For any position in the string, i, every i+k'th character needs to be identical. Also since its a palindrome, the mirror character for each of these characters (i.e. mirrors of i, i+k, etc.) need to be identical as well
    • Now find the character that's used most frequently, and change the remaining characters to that
    • For eg., consider "abcbaa" and k = 3. In the first iteration (i.e. i=0), you'd find the maximum occurring characters among a[0] (the ith character), a[0+3] (the i+kth character), a[6-1-0] (mirror of the ith char), a[6-1-3] (mirror of the i+kth char) i.e. a[0], a[3], a[5], a[2] which are "a", "b", "a" and "c" respectively. Clearly "a" is most frequent, so change all remaining (4-2 = 2) characters to "a" making the overall string "abaaaa"
    • Repeat this for all i where i<k
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How are we ensuring putting the most frequent character will make the String a palindrome?

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

        For every character in position i, you're collecting all i+kth chars, and also finding the mirror positioned chars for each of them. Then you look for the most frequent amongst all of these and change all 4 to this character.

        So if the string is "abcaab" and k = 3:

        1) In your first pass (i.e., i=0) you will consider 4 characters: a b c a a b. Since a is the most frequent character, change all 4 to a b a a a a. It's still not a palindrome at this stage.

        2) In your next pass (i=1), you will consider the following: a b a a a a (this is your entire set of i, i+k palin_i, palin_i+k). Since "b" and "a" are equally frequent, you could use either one (say you choose "b") and your string becomes a b a a b a, which is now a palindrome.

        3) The next and final iteration (i=2) would consider the same four elements as the first iteration. All 4 are already the same and nothing else needs to be done.

        At the end of this, you have a string that meets the criteria, including being a palindrome.

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

          I saw your solution for this problem I must it's very easy to understand just one query why are we outputing ans/2 in the end instead of ans

          Thank you

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

            It's because each set of points is visited twice. So when the string is "abcaab", and k = 3, then at the first iteration (i=0) I visit 4 indices 0, 3 (0 + k), 5 (mirror of 0), 2 (mirror of 0 + k). On the second iteration (i=1), I visit 1 and 4 — twice (since 1 and 4 are the mirror positions of themselves). Then in the final iteration, I visit 4 indices — 2, 5, 3, 0 (the same as the first iteration). All for a total of 4 + 4 + 4 = 12 times.

            So n=6 and I've counted a total of 12, resulting in a factor of 2. I could avoid this division by 2 by not overcounting in the first place. For eg. I could stop iterating at k = n/2, and in the last index, make sure that if the mirror positions are the same as the indices, not to count them twice. This involves a couple of extra conditions, and sometimes its just easier to overcount and account for it at the end, so I chose that route instead.

»
4 years ago, # |
  Vote: I like it -18 Vote: I do not like it

In problem C, n is supposed to be divisible by k. However, for test 3, n=200000 and k=64. Isn't that wrong?

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

Can someone please tell me where my logic is wrong for problem F? https://ideone.com/zhB5cl

It's failing for the sample test cases too.

EDIT: Was able to solve it. https://codeforces.com/contest/1332/submission/75045994

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

Noob here so sorry if this is obvious

In question A, why don't we add an or condition for the y-axis also? (x2<=x-a+b<=x1 || y2<= y-c+d <= y1) I mean, what there's a case if x condition is satisfied but not y

Thanks

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

    You are correct, both the x and y-axis have to be considered. The author simply skipped the y-axis since he said at the beginning that it was the same for both.

    You have to check both x1 <= x+b-a <= x2 and y1 <= y+d-x <= y2, plus the special cases also mentioned in the tutorial.

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

It's so sad that my E FSTed.. I can reach rk1 if it's not.. Again a quick power error!!

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

I liked E among the first 5 problems of the round.

I couldn't get accept during the round but fixed the problem after the contest.

the approach of solving this problem was a bit cooler than the others !

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

First c++ code is python code in problem C

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

Can someone elaborate why we need *(MOD+1) in the solution1 of problem E? Thanks in advance.

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

    $$$\frac{MOD + 1}{2}$$$ is the inverse of $$$2$$$ for any odd modulo.

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

      Oh did realize this, thanks!

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

      Hi, I am wondering can this be generalised to (MOD + 1) / X where gcd(MOD, X) = 1 ?

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

        It works only if $$$(MOD + 1)$$$ is divisible by $$$X$$$ — then $$$\dfrac{MOD + 1}{X} \cdot X \equiv 1 \pmod{MOD}$$$.

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

          Oh yes that makes obvious sense thanks :) !!

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

      Sorry I still can't understand the case when $$$n*m$$$ is even and $$$k$$$ is even. You said that only one grid can't be paired but I can't figured out which one. My current understanding is that when $$$a_{0,0}=k$$$ we can't xor it with 1, but this will give us many unpaired grids. Or we need other method to pair those grids? Great thanks!

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

        Honestly, it doesn't matter that much what algorithm you choose to match them. I just found that second algorithm is the easiest to describe (odd $$$k$$$ case is only an easier example of it because every cell is modifiable).

        For the even $$$k$$$ I basically wanted to choose any cell which can be modified with $$$xor~1$$$. The point is that if we modify a valid grid with this algorithm, the corresponding invalid grid should also get modified to that exact valid grid (I mean that's why I called that "pair up"). So I chose "the first cell" (idk like smallest row and smallest column in that row) value of which is not $$$k$$$.

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

          So the only case that can't be matched is that all the cell is $$$k$$$ right?

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

can anyone please explain how, dp is working in the f question how they ended up with these three equations??

Thank you :)

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

can anyone explain proof why there can’t be more than 11 in B ? it’s little foggy in editorial

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

    First remember that any given $$$a$$$ is a composite number, that is it can be expressed as a product of $$$2$$$ integers both strictly greater than $$$1$$$.

    $$$ $$$

    Let $$$a$$$ be one such integer, $$$a \leq 1000$$$. Let $$$a = bc$$$ with $$$b,c > 1$$$. If both $$$b$$$ and $$$c$$$ are strictly greater than $$$\sqrt{1000}$$$ then $$$a > 1000$$$ which yields a contradiction.

    $$$ $$$

    Therefore at least one of them is smaller than $$$\sqrt{1000}$$$, and from now on let's consider that $$$b\leq\sqrt{1000}$$$. If $$$b$$$ is not prime, then there is one prime (smaller than $$$b$$$, therefore smaller than $$$\sqrt{1000}$$$) which divides $$$b$$$ and therefore divides $$$a$$$. If $$$b$$$ is prime, then $$$b$$$ is a prime number smaller than $$$\sqrt{1000}$$$ that divides $$$a$$$.

    $$$ $$$

    Now we know that for any given $$$a$$$, there is always a prime number smaller than $$$\sqrt{1000}$$$ which divides it. And it turns out there are only $$$11$$$ primes that meet this requirement !

    $$$ $$$

    So any given $$$a$$$ will be divisible by one of those $$$11$$$ primes. We can then greedily assign our colors with this in mind :)

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

      thank you

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

      what should be the answer of this test case? 1 3 2 1 97

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

        elements of $$$a$$$ are guaranteed to be composite numbers.

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

        As triple__a said, none of your numbers is valid. You should have read the first line of my message... $$$a$$$ can't be a prime or $$$1$$$ because it is composite.

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

In $$$E$$$, the omitted proof for matching grids with an even $$$k$$$ could be the following :

$$$ $$$

Take away all grids for which $$$a_{0,0} = k$$$ and do a regular matching. Then the set of all grids such that $$$a_{0, 0} = k$$$ remains unmatched. What we should do with it is applying the same trick but with an other $$$a_{i,j}$$$. The remaining unmatched grids will then be the ones for which $$$a_{0,0}=a_{i_,j}=k$$$. We may keep doing this until only the grid with $$$a_{i,j}=k$$$ for all $$$(i,j)$$$ remains. This is the only unmatched grid, and it is a valid one, hence the formula.

$$$ $$$

Thank you OP and every organizers for the contest ;)

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

    Hey in question E can you plz help me to understand the observation 5 in the editorial.As they said that if n*m is even and every cell is odd we are not able to reach our goal but why? Like if we take 1*4 and the cell values as 1 3 5 7 then if we increase cell height by 2 at some point of time we are able to make it all equal i know i am missing something but not able to find it.Can you plz help me..thankyou.

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

      it means the sum of elements are odd, not that every elements are odd

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

      Nezzar is right, they said that the sum of all cells is odd. Any operation we make doesn't change the parity of such a sum. If we were to complete the game, as there is an even number of cells, the sum of all of them would be even, which in our case won't ever happen !

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

    It's a small thing, but in editorial, k is defined as R — L(not R — L + 1), so your explanation is for not odd, but even k, isn't it?

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

      You're right, it's for an even $$$k$$$, thank you.

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

I have used the exact same method as stated in the editorial for Question B — Composite Coloring but I got one of the test cases (not pretests) wrong. Here's my submission 74980482. Can anyone tell me why my code was wrong? Thanks.

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

How solve C using dfs. I saw some code used dfs to solve. But no node comes in my brain...

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

    Basically for each i in range 1 <= i <= n — k , s[i] = s[n + 1 — i] , and s[i] = s[i + k]. Now you have to count how many letters should be the same in this cycle. The nodes are the indices. You can see my code, maybe you will understand.

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

Auto comment: topic has been updated by triple__a (previous revision, new revision, compare).

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

Can anyone explain how the dp formula in problem F works in detail? I don't understand it. Thanks a lot.

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

    Lets say a node has n children. Consider the child(v) along with the edge connecting the child as one group. The contribution for one group in the first formula is as follow:-

    1. The edge is included in your edge-induced subgraph:- dpv1 + dpv0 Explanation:- You just have to take all possibilities.

    2. The edge is not included in your edge-induced subgraph:- (dpv1-dpv) +dpv0 Explanation:- The term dpv is added because you need to remove the cases which would make v an isolated vertex.

    By summing up both the terms you would get 2dpv0 + 2dpv1 -dpv, and now you just need to multiply the contributions of all the children.

    I guess this will help you derive the other formulas. Let me know if you find any problems.

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

      You mean dpv1 also counts the case that v is colored but isolated from all its children?

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

      So dpu0 means we don't choose point u(no matter add edges or not), dpu1 means we must choose point u(no matter add edges or not), and dpu means for all sons of point u, we don't add the edge (u, v)? I don't know is it true to explain it in this way?

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

        Yes thats correct if by "we don't choose"- you mean they are not chosen as part of the independent set

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

      !

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

      How do we calculate dpu? It seems like it should be 2*(dpv1 +dpv0 — dpv) as it can come from cases when dpu is either coloured or uncoloured.

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

        dpu is only needed for dpu1.

        As my question below, it will be easier to understand dpu1 if it excludes dpu in the first place. When including dpu in dpu1, it actually includes case where u is isolated and colored. That's why when no edge between u and v and still need v in independent set, there must be some edge between v and its children. Thus it's needed to remove dpu from dpu1.

        But for dpu0, it doesn't care whether there is an edge between u and its child v or not.

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

      Thanks for the explanation.

      But why include dpv in dpv1 rather than exclude dpv from dpv1 directly? Isn't the latter approach more intuitive? And the editorial emphasized on no isolated colored vertex. I mean when looking at dpv1, it's perfectly valid count if dpv is already excluded.

      I know either way it's needed to deal with dpv. I just want to know the ideas here, or it's just happen to be this way.

      Thanks.

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

        No you need dpv to be in dpv1 because those cases will be used for the parent of v. It is fine for it to be isolated from bottom when it is connected to its parent by an edge.

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

          Thanks again for the reply.

          And I understand the part "It is fine for it to be isolated from bottom when it is connected to its parent by an edge."

          Actually I can do it with dpv being excluded from dpv1.(https://codeforces.com/contest/1332/submission/75576336). It's just equivalent transformation.

          I ask the question just because including dpv in dpv1 is kinda counter intuitive to me and different from what the editorial emphasized.

          Never mind now. Thanks again. Happy coding.

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

Great contest and editorial

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

Great contest :))

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

What's the meaning of

s1=lower_bound(st1+1,st1+p1+1,i,cmp1)-st1-1, s2=lower_bound(st2+1,st2+p2+1,i,cmp2)-st2-1;

in the code of problem G?

Why can't we use s1=p1,s2=p2; instead ?

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

    because you need to make the answer fit into range [L,R] instead of [L,n].

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

      Since the code is doing precalculating, where does this $$$[L,R]$$$ come from?

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

        since you should do carefully when $$$R=c[L]$$$. (check the code for notation.)

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

          Now I think you are coping with equal elements.

          s1:右边最后一个大于等于a[i]的位置+1 -> 右边第一个小于a[i]的位置

          s2:右边最后一个小于等于a[i]的位置+1 -> 右边第一个大于a[i]的位置

          So you will skip the equal elements to find "the closest to the right element greater than the top one" and "the closest to the right element smaller than the top one".

          BTW:The code is slightly different from the solution about details. Hope you could provide one that does what the solution says.

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

            the s1 and s2 is coping with the case where elements is the same as you mentioned. However, for range $$$L$$$ to $$$c[L]$$$, we cannot simply pick the element in the stack different from $$$a[i]$$$.

            Consider the following case:

            5 4 6 3 7 6
            

            in this case and $$$i=1$$$, you are supposed to pick 3 and 7 instead of the second top element of the stack which should be 4 and 6 if you follow the implementation the code presents. (the conception is mentioned in the $$$O(n^2)$$$ indeed)

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

              Can you explain more how to recover the min/max after we got the first and last index in a k=4 sequence? I am not understanding how to do this with just the stack.

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

                Nvm, i was able to fix my solution to ac. i still don't get some parts of the editorial tho

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

                to recover the index for $$$k=4$$$ case, my approach is pick the largest one in stacks so that it will not exceed $$$c[i]$$$. so the index should be i c[i] and those two if $$$b$$$ starts with $$$a[i]$$$.

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

Nice

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

I wonder if there is a typo in the formula of the combinatorics solution for task E. It should be $$$(E+O)^{nm}=\sum_{i=0}^{nm/2}E^{2i}O^{nm-2i}\binom{nm}{2i} + \sum_{i=1}^{nm/2}E^{2i-1}O^{nm-(2i-1)}\binom{nm}{2i-1}$$$ instead of $$$(E+O)^{nm}=\sum_{i=0}^{nm/2}E^{2i}O^{2i}\binom{nm}{2i} + \sum_{i=1}^{nm/2}E^{2i-1}O^{2i-1}\binom{nm}{2i-1}$$$ And similar for $$$(E-O)^{nm}$$$, could someone explain it?

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

    Yes, you are correct. This is just the binomial expansion, $$$ (x+y)^n = \sum\limits_{i=0}^{n}{ n \choose i } {x^i y^{n-i} } $$$

    Sorry, I got mixed up between your and editorials formula.

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

    sorry, i will fix it!

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

    I have taken a little while to realize this, now it's nice that you have fixed it! It 's much clearer now! :)

»
4 years ago, # |
  Vote: I like it -31 Vote: I do not like it

Worst contest ever

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

    Actually I think this contest is really good.

    The problems have very interesting ideas and appropriate difficulty.

    And the problem writer is also a very nice man.

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

      Then maybe my bad day, but somehow in any contest pikemike is involved i end up not even solving A. :(

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

        To solve problem A, maybe you shouldn't think the problem in a too complex way?

        practice more. Hope you good luck next time.

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

It's a very enjoyable round

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

Can someone who got acc on D to tell me how they thought to get to that solution?

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

Just a doubt for D though, what if we get a problem stating that find the maximum value you can get for going through (1,1) to (n,m), this dp in question is wrong for sure, then what is the correct dp or approach to solve this type of problem

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

    I think backtracking is the only way to solve it correctly.

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

      hmm, going through every possible path.

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

        It's correct that dp solution goes through all the possible paths so apparently should give the best result. But the problem is the absence of optimal substructure in the problem, as taking the maximum AND of left and up paths isn't optimal. Correct me if I am wrong because I was really curious as how can dp not give the correct result.

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

I know its trivial but,
Can you please tell me the intuition behind Problem B?

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

    Because $$$a_i\leq 1000$$$, while in other problems $$$a_i$$$ is always $$$\leq 10^9$$$. It's very strange. And that means maybe we can find the answer from the relationship between $$$1000$$$ and $$$11$$$. Then it may be easier to realize that there are only 11 primes smaller than $$$\sqrt{1000}$$$.

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

In problem A, why I need the condition a+b=0?

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

    It is given that x is in-between x1 and x2 and with the condition a+b=0 there is no need for movement in the x direction, so the verdict is a 'yes'.

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

      And why do we need x2>=x1 and y2>=y1....these conditions?

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

        Those are constraints given in the question.

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

          Then explain me how the following test case prints a no: 1 1 1 1 1 1 1 1 1 1 Because in this test the final position of cat is (1,1) which is the very same position her cat starts walking from and which satisfies the given constraints in the question i.e x>=x1 && x<=x2 && y>=y1 && y<=y2. Then why does it prints a no. Also my second question that if the cat is at the same position with Alice after moving a,b,c and d moves that means the cat is safe and not being lost then again, WHY should it print a NO??

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

            Let me explain why the cat goes in danger in the x axis. The cat is initially at x=1, and it is given that a=1 and b=1 so the cat now needs to move to x=0 or x=2 both of which are not 'safe' hence the answer is NO.

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

              Why are you just considering 1D case??

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

                That is sufficient to show that the answer is a no. I think you misunderstood the question, its not about checking weather the final position of the cat is safe instead the cat needs to be safe in the whole jurney. I suggest you to re-read the question.

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

In 1332A - Exercising Walk why can't we set y = y-(d-c). If I set x = x-(a-b) and y = y-(d-c), my output is wrong.

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

    i think you can try with (c-d)..

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

      It works for c-d. That's why I am asking why it doesn't work for d-c.

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

        d is for moving along positive y direction and c is for moving along negative y direction why would you subtract your current position(initial y) with d and add it with c,rather you are supposed to do the opposite(which is y+d-c=y-(c-d))..it's so obvious.

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

Is B solvable using graph coloring where edge exist between two elements if their gcd is 1.

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

    i don't know how you do the graph coloring. it really depends on your implementation. if you do it greedily, then the answer is no, and we have provided some tests against it in pretest 4.

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

I'm just curious in problem d ..since that dp algorithm fails...could there be a different dp approach which would actually lead to a correct solution triple__a ?

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

    tbh i don't know if there is one solving this task with pure dp. but the checker i provide is checking bits from the most significant to the least, and it can be done with dp. idk if that counts or not.

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

I think it's proper for a Chinese video solution(no it's just a recording) appearing under a Chinese contest editorial.

So, the link here : bilibili BV1at4y1m7V8.

Bullet screens and comments are welcomed.

If you like the video, please subscribe and leave a like (and 一键三连)!

If you don't like the video, leave your suggestions in the comment area below!

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

    really appreciated! btw,

    best part xD
  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Can you make tutorial available in English for F and G problems?

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

Can anyone explain Problem D. Tutorial isn't enough.

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

Another take on problem E:

Define polynomial multiplication like this: $$$x^{i} \times x^{j} = x^{(i + j) \mod 2}$$$. For example, $$$(1 + x)^{2} = 1 + 2x + x^{2}$$$ will be simply $$$2 + 2x$$$.

Let $$$p = $$$ number of even numbers in range $$$[L, R]$$$ and $$$q = $$$ number of odd numbers in range $$$[L, R]$$$. For even $$$nm$$$, the answer is the constant term of $$$(p + qx)^{nm}$$$, and for odd $$$nm$$$ the answer is sum of its both coefficients. Complexity will be $$$O(\log nm)$$$ with binary exponentiation. (Code)

This solution is also easy to generalize for different modulo classes and the polynomial multiplication be made faster with FFT if the modulo class is big.

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

In Problem E, It's mentioned that There is a general solution for this kind of problems.Can anyone provide any resource and more problems like that?

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

Let me appreciate the fact, Problem E was really nice!!

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

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

Please Explain C without DSU

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

why we have done ans/2 in 1332-C ?

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

    i have checked for all pairs (i,j) such that $$$i+j=k-1$$$. so something like (k-1,0) and (0,k-1) will be both counted.

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

I'm trying to understand the solution of 1332E - Height All the Same. In the proof of observation 2 it says that you connect 2 cells of the same parity via a route. Let's take a more simple problem say you have an empty grid and you have 2 * k marked cells in this grid. You want to connect these up into k pairs such that the routes connecting different pairs are not crossing(i.e. they don't have a common cell). I think the proof of observation 2 assumes this is always possible. I don't yet see it why this is true.

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

    I realized that R is only a bound in the beginning. I misunderstood the problem statement. Although the solution also stands when R is a bound in the end because when you have 2 * k marked cells on an n * m grid you can connect them such that no 2 routes cross each other. Just take a Hamiltonian path in the grid(not too hard to find one) and pair up the elements along this path. What this means is that you can change the parity of the even number of elements by raising their value by 1 and raising the value of the elements along the routes by 2. This obviously requires the routes not to go through cells which already have height R.

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

    "You want to connect these up into k pairs such that the routes connecting different pairs are not crossing(i.e. they don't have a common cell)"

    crossing is allowed.

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

      Yeah I figured that out in the meantime. I meant that if R is a bound in the beginning and the end as well and you have n * m % 2 == 1, L = 0 and R = 2 and an even number of 1s and an odd number of 0s you have to be able to connect them pairwise without crossing. This is possible, just line up the pairs on one of the Hamiltonian paths of the grid.

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

What will be the correct DP algorithm for the D problem I want tabulation method correct algorithm for finding the path for a given grid where the and of all the element on the grid is maximum as possible

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

can some one explain the easy intuition solution of pikmike (problem E) ?

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

    You can just draw it out, like for these grids:

    1x2, l = 1, r = 2;

    1 1

    1 2

    2 1

    2 2

    1x2, l = 1, r = 3

    1 1

    1 2

    1 3

    2 1

    2 2

    2 3

    3 1

    3 2

    3 3

    There's 4 grids for the first one and half of them are even, and there's 9 grids for the second one and (9+1)/2 of them are even. I assumed it would be like that for all grids.

    The intuitive part is that imagining all combinations of numbers, something like half of them will be even (we're looking for evens because there needs to be an even amount of odds, so sum has to be even).

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

Guys I found D solution so non-trivial and brilliant. How did you guys figured this out during the contest. What is the general thought process for approaching constructive algorithm based question.

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

    Think how the DP approach might give a nonoptimal result.

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

triple__a I am wondering what is the checker code for problem D :)

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

For problem F, don't we need to consider stack overflow when using recursive dfs since n <= 3e5?

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

    Nah, I think I'd solved some 5e5 problem using recursive DFS and still OK.

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

I don't have many ideas when I meet the constructive algorithm problems. Such as 630 div.2 D. I found that advanced CF players can solve those problems quickly. Can anyone give me some suggestions to improve my skill? Thanks a lot.

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

An alternative solution for D. Consider the example —

for k = 9 or 1001, consider the solution -
[11111 1111     0]
[10000 11111 1001]

The algorithm uses: 11111 -> 10000 -> 11111 -> 1001, answer = 0
Optimal answer: 11111 -> 1111 -> 11111 -> 1001, answer = k

int k; cin >> k;
int d = (int)log2(k) + 1;
vvi ans =   {   
                {(1 << (d + 1)) - 1,        (1 << d) - 1,           0}, 
                {1 << d,                    (1 << (d + 1)) - 1,     k}  
            };
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I used a quite different approach to solve the dp in problem F. Here instead of removing edges I just calculated the value of w(H) for any subgraph that may lie in the subtree of v. Then to calculate this assume dp[v][0] be the total value of sum(w(H)) for any subgraph that does not have any edge coming out of v, dp[v][1] be the value when there is at least one edge from the vertex v to at least one of its children but v is not counted in those independent subsets, and finally dp[v][2] be the value such that there is at least one edge to a child and also v is counted in the subsets. Then we obtain the following dp:

//for all to belong to the children of v;
dp[v][0]=Product(dp[to][0]+dp[to][1]+dp[to][2])
dp[v][1]=Product(3*dp[to][0]+2*dp[to][1]+2*dp[to][1])-dp[v][0]
dp[v][2]=Product(2*dp[to][0]+2*dp[to][1]+dp[to][2])-dp[v][0]

We can find it by assuming that if there are no edges from v then we can add any subgraph in a child to another subgraph in other children including a null graph. And by multiplying them we sort of add the independent sets together. Similarly, for the case where there is at least one edge from v to a child, we consider both cases for each child of whether to include it or not and subtract the cases when we don't include any one of them (inclusion-exclusion). The link to my submission: 76447494.

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

I don't understand one thing in solution of B. In the first test i have 10 different numbers, but also the number 11.

23 437 519 865 808 909 391 194 291 237 395 323 365 511 497 781 737 871 559 731 697 779 841 961

11 8 2 3 1 2 7 1 2 2 3 7 3 4 4 5 5 6 6 7 7 8 10 11

There is not the number 9. Why it isn't working? Please help

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

    According to the problem statement, "for each color from 1 to m there is at least one element of this color". So, your m is 11, but there must be an element with color 9 too.

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

      I know there must be 9, but when a do a solution like in this blog, there isnt 9

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

        I solved the same way as in the editorial and got the correct answer. Maybe you should double check your code.

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

is there a problem in my code , i am getting tle on test 5 https://codeforces.com/contest/1332/submission/83755735

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

triple__a I guess solution provided for 1332A contains some bugs. kindly verify it by checking against following test case

1 2 3 0 0 0 0 0 0 1 0

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

Hi awoo, can you explain this line for your solution for Div2D?

However, we should notice that we can only discard the suboptimal result if and only if anssuboptimal & ansoptimal = anssuboptimal rather than anssuboptimal < ansoptimal.
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how the question 1332C — K-Complete Word is from topics dsu and dfs, it didn't use any such algorithm but is listed in topic tags of dfs and dsu.