triple__a's blog

By triple__a, history, 2 months 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: pikmike

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

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

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

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

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

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

    Clear and lucid explanation. Thanks.

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

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

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

Thanks for such a fast editorial! Nice round!

»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Fastest editorial in the west :3

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

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

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

Instead of tutorial for 1332A, its showing tutorial for 1327A, please fix

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

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

In problem D could some one tell what's the problem in that matrix?

3k 2k 0

k 3k k

0 0 k

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

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

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

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

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

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

    • »
      »
      »
      2 months 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 :(

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

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

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

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

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

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

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

nice 1;

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

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

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

    Could u elaborate

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

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

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

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

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

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

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

can somebody suggest me practise problems to improve my rating

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

»
2 months ago, # |
  Vote: I like it +14 Vote: I do not like it

How to write spj for D?

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

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

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

      I got it, thanks.

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

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

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

»
2 months ago, # |
  Vote: I like it -44 Vote: I do not like it

Bad problems and bad solutions. Nothing to learn. Just puzzle. It was like hit or miss.

»
2 months 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 :'(.

  • »
    »
    2 months 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)$$$

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

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

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

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

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

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

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

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

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

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

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

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

Can anyone help me in correcting my approach for C?

My approach for C was to cnt all characters on indices i, i + k, i + 2k,...for all i's and then make a palindromic string of length k. Lets call k length string as p.

Now we have to make characters equal at index(0 based indexing) (i, k - i - 1), (i + 1, k - i - 2)...so we choose for every pos in p the max frequency occurring character at that pos and compare it with k - pos - 1 max occurring character, then we choose maximum from both and put it on pos and k - pos - 1. I am getting answer 17 for test case

21 7

wudixiaoxingxingheclp

I dont know where I am doing wrong. Please help.

Link to code 75007323

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

    Dont answer the above query I have solved it.

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

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

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

So the verdict is "Yes" if and only if x1≤x−a+b≤x2 and (x1<x2 or a+b=0).

the toturial is saying that ..but applying that getting WA,,, when we are considering both x and y axis the verdict is ac then...?

toturial> The key observation is x-axis and y-axis is independent in this task as the area is a rectangle. Therefore, we should only consider 1D case (x-axis, for example). The optimal path to choose alternates between right and left moves until only one type of move is possible. And sometimes there is no place to make even one move, which has to handled separately. So the verdict is "Yes" if and only if x1≤x−a+b≤x2 and (x1<x2 or a+b=0).

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

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

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

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

Can someone pls explain C in ann easy way?

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

      thank you so much it helps a lot @sh_maestro

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

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

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

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same logic as sh_maestro implemented as easily as possible.Here goes:

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

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

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

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

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

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

Could someone kindly explain 4th problem ? The editorial is not at all clear to me. Thanks in advance

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

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

First c++ code is python code in problem C

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

Why do we need to consider both cnt[i%k][j] and cnt[k-i%k-1][j] in Task C?

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

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

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

      Oh did realize this, thanks!

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

      • »
        »
        »
        »
        2 months 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}$$$.

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

          Oh yes that makes obvious sense thanks :) !!

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

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

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

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

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

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

      thank you

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

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

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

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

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

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

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

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

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

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

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

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

In problem B I used following code , but it isn't working, Can anyone help me? CodeLink

»
2 months ago, # |
  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 protests) wrong. Here's my submission 74980482. Can anyone tell me why my code was wrong? Thanks.

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

thanks for tutorial solutions in (PYTHON)

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

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

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

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

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

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

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

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

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

      !

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

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

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

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

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

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

Great contest and editorial

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

Great contest :))

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

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

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

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

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

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

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

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

              • »
                »
                »
                »
                »
                »
                »
                »
                2 months 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]$$$.

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

Nice

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

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

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

    sorry, i will fix it!

  • »
    »
    2 months 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! :)

»
2 months ago, # |
  Vote: I like it -31 Vote: I do not like it

Worst contest ever

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

    • »
      »
      »
      2 months 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. :(

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

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

          Practicing more won't help me solve dumb questions anyway.No matter how much i practice but thanks for advice.

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

It's a very enjoyable round

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

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

Can anybody explain problem B editorial?

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

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

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

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

      hmm, going through every possible path.

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

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

  • »
    »
    2 months 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}$$$.

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

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

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

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

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

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

        Those are constraints given in the question.

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

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

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

              Why are you just considering 1D case??

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

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

                  Exactly. I misunderstood the question. Thank you very much ashwath for taking the trouble to make me understand the logic and the question.

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

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

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

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

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

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

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

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

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

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

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

    really appreciated! btw,

    best part xD
  • »
    »
    2 months 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?

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

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

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

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

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

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

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

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

PYTHON USERS HELP OUT

the issue in the solution of problem C. I have made the first k letters a palindrome and then counted the changes to be made in every consecutive k letters to match it with the new string I made of k letter which is a palindrome as stated above. but , I am not getting the required answer

def solve(ans): n,k=[int(x) for x in input().split()] s=input() half_k=s[0:k//2] if k%2==0: small=s[0:k//2] new_string=small+small[::-1] else: small=s[0:k//2] new_string=small+s[(k-1)//2]+small[::-1] change=0 for i in range(k): if i>(k-i-1): break if s[i]!=s[k-i-1]: change+=1

for i in range(k,n,k):
    z=0
    print(i)
    for j in range(i,i+k):            
        if s[j]!=new_string[z]:
            change+=1
        z+=1

ans.append(change)
ans.append(final_string)

return

n=int(input()) ans=[] for i in range(n): solve(ans) for ele in ans: print(ele)

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

Please Explain C without DSU

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

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

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

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

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

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

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

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

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

i can't understand the editorial solution of 1332C problem. please , would anyone like to explain it ? i have tried many times. Thanks in Advance

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

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

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

I didn't got why are we using (x2>x1||a+b==0)&&(y2>y1||c+d==0) condition??

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

As the C++ solution illustrates, an odd $$$k$$$ in problem C does not need to be treated separately, despite what the tutorial says.

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

    that depends on implementation. It's not a hard and fast rule.

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

Please someone explain the meaning of " To minimize the required number of changes, you should make all the letters equal to the one which appears at these positions the most initially. Calculate that maximum number of appearances and sum up over all i." in tutorial of Div.2 C.

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

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

    Think how the DP approach might give a nonoptimal result.

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

In C, We are checking for the max used char in k+i and replacing them. Where are we ensuring that the final text will become a palindrome?

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

Please anyone explain the C for the input below.
Input:
1
21 7
wudixiaoxingxingheclp

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

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

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

Мне одному показалось что в легком наблюдательном решении что — то не так?

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

Hello everyone ! I first want to say that I'm just new to the site and really impressed of the quality of contents on it. It is the first Editorial I am reading so far and I am pleased to see the efforts you put on it and it really helps me to understand the logic of those problems, so congrats and thank you for that ! :)

I would like to specify the explanation under the problem 1332E - Height All the Same, on the Easy intuition solution: The case when k is even seems to me not clear enough and can be misleading. Indeed, saying that we can add a "fake" grid to get the correct answer is not the good reason (if I understand it correctly).

The real reason is that the remaining unpaired grid is VALID, which can be deduced by the last phrase : "You can easily see that only grid that consists of all numbers k has no pair", which is obviously valid as no operations has to be done to achieve the goal.

Thus, the formula would be clearer in my opinion if it was written like (total-1)/2 + 1 instead of (total+1)/2, as we have to remove the single grid from all the paired ones before dividing by 2 then add 1 because it happens that this remaining one is valid.

I hope my statement was clear enough, and please correct me if I am wrong.

Which you all the best (and stay at home :p)!

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

»
2 months 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}  
            };
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it
auto f=[&](int u){
    for (int i=2;i<=u;++i){
        if (u%i==0) return i;
    }
};

Can anyone pls explain me what the code snippet does or provide any link understand the coding

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

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

Please anyone can tell me what is wrong in the sample test case of 1332B-Composite Coloring.

Case

23

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

Given Answer

11

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

The above is the given test case and it's answer. I think the below data should be another answer but it is giving me wrong answer on this??

My answer

10

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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can some one tell me why we have to add both from u and v in problem C? I mean why this ret+=cnt[u][j]+cnt[v][j]; not this ret+=cnt[u][j] or ret+=cnt[v][j];

»
5 weeks ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

(Sorry, I got cleared) A doubt. For the solution of problem E using intuition, we consider a special case when k is even since k xor 1 > k. I am wondering that this should depend on the original values of L and R as well, for example, L = 3 and R = 4 ,so k = 1. If the original numbers were used(L to R), 4 xor 1 = 5. but since k is odd, we don't consider this case triple_a

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

  • »
    »
    7 days 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.

    • »
      »
      »
      7 days 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

      • »
        »
        »
        »
        7 days 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.