### triple__a's blog

By triple__a, history, 2 years ago,

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++)

• +279

 » 2 years ago, # |   +9 Auto comment: topic has been updated by triple__a (previous revision, new revision, compare).
 » 2 years ago, # |   +32 Video tutorial for DHere you can see how to prove the described solution, which is similar with the editorial's approach.
•  » » 2 years ago, # ^ |   0 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 years ago, # ^ |   +3 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
•  » » » » 23 months ago, # ^ |   0 But can you explain what is the correct approach to find maximum answer using DP because bob's approach is incorrect.
•  » » 2 years ago, # ^ |   +1 Clear and lucid explanation. Thanks.
•  » » 2 years ago, # ^ |   0 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 years ago, # ^ |   +7 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 years ago, # |   0 Thanks for such a fast editorial! Nice round!
 » 2 years ago, # |   +5 Fastest editorial in the west :3
 » 2 years ago, # | ← Rev. 2 →   +10 There is the tutorial of problem 1327A instead of 1332A UPD: now fixed
•  » » 2 years ago, # ^ |   +9 thanks for pointing it out. it is now fixed.
 » 2 years ago, # | ← Rev. 2 →   0 Why editorial for A is an editorial to another problem?EDIT: fixed now
 » 2 years ago, # |   0 Instead of tutorial for 1332A, its showing tutorial for 1327A, please fix
 » 2 years ago, # |   0 Auto comment: topic has been updated by triple__a (previous revision, new revision, compare).
 » 2 years ago, # | ← Rev. 3 →   -39 In problem D could some one tell what's the problem in that matrix?3k 2k 0k 3k k0 0 k
•  » » 2 years ago, # ^ |   +14 k = 3
•  » » » 2 years ago, # ^ |   -20 Thanks!
 » 2 years ago, # | ← Rev. 3 →   +33 Why so many people get "Wrong answer on test 57"(problem E)?
•  » » 2 years ago, # ^ |   +191 Because their code fails to produce correct output on test 57 of problem E?
•  » » 2 years ago, # ^ |   0 So do I. Hope somebody can tell me what happen.
•  » » 2 years ago, # ^ |   +29 I guess it is because Fermat's little theorem is not true if gcd(a, p) != 1
•  » » 2 years ago, # ^ |   +24 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 998244353the sad thing is that %(mod-1) wasn't even needed. I wish this test case was in pre-tests
•  » » » 2 years ago, # ^ |   +14 "the sad thing is that %(mod-1) wasn't even needed."Just realize it and feel sadder :(
•  » » 2 years ago, # ^ |   +24 I think I know what happened on it.This test is:998244352 2 1 998244353So, 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)%998244353AND, MY QUICKPOW() FUNCTION CONSIDERED THE VALUE OF 998244353^0 IS 1 !And this lead to the eventual WA.
 » 2 years ago, # |   0 People have used DSU/DFS in their solutions for problem C. Could someone explain how that works?
•  » » 2 years ago, # ^ |   +2 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 years ago, # ^ |   0 https://codeforces.com/contest/1332/submission/75023756I implement DSU but it fails. can you please check my code
•  » » » » 2 years ago, # ^ |   0 You can see my code.I have implemented using DSU. https://codeforces.com/contest/1332/submission/75040138
•  » » » » » 2 years ago, # ^ |   0 I got your idea but what is wrong in my code
•  » » » 7 months ago, # ^ |   0 I solved the question greedily and I wondered how the hell could I used DSU to solve this and your solution is really nice and insightful. Thank you very much.
•  » » 2 years ago, # ^ |   0 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 years ago, # |   +28 The round definitely made me think (and question my existence). Kudos to triple__a.
 » 2 years ago, # |   +13 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 years ago, # ^ |   +5 E too :(
 » 2 years ago, # | ← Rev. 2 →   0 nice 1;
 » 2 years ago, # |   +1 C is doable with dfs. It'll be an easier approach.
•  » » 2 years ago, # ^ |   0 Could u elaborate
•  » » » 2 years ago, # ^ |   0 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 years ago, # |   -6 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 years ago, # ^ |   0 well， the condition said that all inputs are great or equal to 4
•  » » 2 years ago, # ^ |   +6 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 years ago, # |   +10 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 years ago, # ^ | ← Rev. 3 →   +8 thanks for pointing it out,but i am not convenient to edit right now. i will fix it tmrupd: it is now fixed
 » 2 years ago, # | ← Rev. 3 →   +90 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 OThen we can use matrix and binary exponentiation to calculate the answer.74978938 •  » » 2 years ago, # ^ | +10 This is cool! BTW, I think this is a mistake, dp[i] should depend on dp[i — 1]. •  » » » 2 years ago, # ^ | 0 Thanks for your correction! :) •  » » » » 2 years ago, # ^ | 0 Hi, can you suggest apt. blog for matrix and binary exponentiation. Much appreciated! •  » » » » » 2 years ago, # ^ | 0 •  » » 2 years ago, # ^ | 0 haha(lol); :) Interesting code! •  » » 2 years ago, # ^ | ← Rev. 3 → 0 oh I see you're a man of culture as well74987963 •  » » 2 years ago, # ^ | ← Rev. 5 → 0 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. •  » » 2 years ago, # ^ | 0 Thank you! •  » » » 2 years ago, # ^ | 0 niu •  » » » » 2 years ago, # ^ | +5 Good English  » 2 years ago, # | 0 can somebody suggest me practise problems to improve my rating  » 2 years ago, # | 0 Is there solution for D if we say that values in matrices are a[i][j]<=1e5? •  » » 2 years ago, # ^ | ← Rev. 2 → +11 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 years ago, # ^ | +2 In the problem it is mentioned that all numbers can be in range [0, 300000] •  » » » » 2 years ago, # ^ | +21 Yes, but the question was about range [0, 100'000]  » 2 years ago, # | +24 triple__a Thanks for such a good round in these days!! No queueforces even after Contest and fast editorial!! Kudos  » 2 years ago, # | 0 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 years ago, # ^ | ← Rev. 2 → +1 here is an easy solution- https://codeforces.com/contest/1332/submission/74991949  » 2 years ago, # | +3 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 years ago, # ^ | +3 a and m need to be co-prime for this. Test 57 violates this. •  » » 2 years ago, # ^ | +17 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 years ago, # | +3 problem C first solution — wrong language (python code, linked as c++)  » 2 years ago, # | 0 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 years ago, # ^ | 0 is this valid input? bcoz i checked many code for this input and every code giveing m = 12. •  » » » 2 years ago, # ^ | 0 This input isn't valid, input must contain only composite numbers •  » » » 2 years ago, # ^ | 0 The input is not valid because it can only have composite numbers not prime.  » 2 years ago, # | ← Rev. 2 → 0 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 years ago, # ^ | 0 i b[i]-1 and b[i] will work if b[i] is the smallest index such that the answer is 3.  » 2 years ago, # | +14 How to write spj for D? •  » » 2 years ago, # ^ | +24 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 years ago, # ^ | +5 Good problem. This is the original version of D.As problem-setter said, use bfs to greedily check by bits. •  » » » 2 years ago, # ^ | ← Rev. 2 → 0 I got it, thanks. •  » » » 2 years ago, # ^ | ← Rev. 3 → 0 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 years ago, # ^ | 0 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 years ago, # ^ | ← Rev. 4 → +11 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 years ago, # ^ | 0 thanks •  » » » » » 8 months ago, # ^ | 0 Sorry for necroposting but can you please provide the code link for this approach of yours as I am unable to implement it. Thanks in advance!  » 2 years ago, # | -44 Bad problems and bad solutions. Nothing to learn. Just puzzle. It was like hit or miss.  » 2 years ago, # | 0 For E, can someone give more details about how to apply Newton expansion? I really cannot see a direct mapping :'(. •  » » 2 years ago, # ^ | +55 (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 years ago, # ^ |   0 can you please tell me how you guys write such mathematical expression in such a nice format and notation.
•  » » » » 2 years ago, # ^ |   +7
•  » » » » » 2 years ago, # ^ |   0 thanks
 » 2 years ago, # |   0 for 1332A can someone please explain why shouldnt we consider both height and width at the same timewhy taking only x axis in calculations. thank u!
•  » » 2 years ago, # ^ |   0 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 years ago, # ^ |   0 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 years ago, # ^ |   0 the answer is no if x-axis says no or y-axis says no
 » 2 years ago, # | ← Rev. 2 →   0 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 years ago, # ^ | ← Rev. 2 →   0 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 years ago, # ^ |   0 ok, I get it.edge induced subgraphs isn't connected graph .
 » 2 years ago, # |   +3
•  » » 2 years ago, # ^ |   0 why are you using 2*mod??
•  » » » 2 years ago, # ^ |   +1 To avoid the affect of mod if I divide ret by 2 later.
 » 2 years ago, # |   +7 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 years ago, # |   +3 hope everyone uploads the tutorials this fast as we r eager and curious about problems solutions!
 » 2 years ago, # |   +43 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 years ago, # | ← Rev. 2 →   0 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 7wudixiaoxingxingheclpI dont know where I am doing wrong. Please help.Link to code 75007323
•  » » 2 years ago, # ^ |   0 Dont answer the above query I have solved it.
 » 2 years ago, # |   0 Python solution for Problem C is incorrectly mentioned as C++, please correct it triple__a.
 » 2 years ago, # | ← Rev. 2 →   0 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 years ago, # |   0 So the verdict is "Yes" if and only if x1≤x−a+b≤x2 and (x1 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
 » 2 years ago, # |   -10 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 years ago, # ^ |   -10 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 years ago, # |   0 I used DSU for C. My submissionWe 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 years ago, # | ← Rev. 2 →   -7 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 years ago, # ^ |   0 I think this explains it Link to geeksforgeeks.org
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 This should help: https://www.youtube.com/watch?v=GU7DpgHINWQ
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 I did actually see that a few days back.
•  » » 21 month(s) ago, # ^ |   0 https://youtu.be/U66U1-umNbQhttps://youtu.be/V343UXw4P3YThis two videos will surely help you.
•  » » 21 month(s) ago, # ^ |   0 If no one, Pashka listened.
•  » » 13 months ago, # ^ |   0
 » 2 years ago, # |   0 Can someone pls explain C in ann easy way?
•  » » 2 years ago, # ^ |   +3 ProblemGiven 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
•  » » » 2 years ago, # ^ |   0 thank you so much it helps a lot @sh_maestro
•  » » » 2 years ago, # ^ |   0 How are we ensuring putting the most frequent character will make the String a palindrome?
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 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 years ago, # ^ |   0 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 ansThank you
•  » » » » » » 2 years ago, # ^ |   0 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.
•  » » » » » » » 2 years ago, # ^ |   0 Wonderful solution!! Thank you..
•  » » 2 years ago, # ^ |   0 Same logic as sh_maestro implemented as easily as possible.Here goes:
 » 2 years ago, # |   -18 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 years ago, # ^ |   +6 200000 / 64 = 3125
 » 2 years ago, # | ← Rev. 4 →   0 Can someone please tell me where my logic is wrong for problem F? https://ideone.com/zhB5clIt's failing for the sample test cases too.EDIT: Was able to solve it. https://codeforces.com/contest/1332/submission/75045994
 » 2 years ago, # |   0 Noob here so sorry if this is obviousIn 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 yThanks
•  » » 2 years ago, # ^ |   +4 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 years ago, # ^ |   0 Thank you!
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 can you explain that special case, please.How x1>x2 can be fixed with a+b=0?
 » 2 years ago, # |   +26 It's so sad that my E FSTed.. I can reach rk1 if it's not.. Again a quick power error!!
 » 2 years ago, # |   0 Could someone kindly explain 4th problem ? The editorial is not at all clear to me. Thanks in advance
 » 2 years ago, # |   +6 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 years ago, # |   0 First c++ code is python code in problem C
 » 2 years ago, # |   0 Why do we need to consider both cnt[i%k][j] and cnt[k-i%k-1][j] in Task C?
 » 2 years ago, # |   0 Can someone elaborate why we need *(MOD+1) in the solution1 of problem E? Thanks in advance.
•  » » 2 years ago, # ^ |   +26 $\frac{MOD + 1}{2}$ is the inverse of $2$ for any odd modulo.
•  » » » 2 years ago, # ^ |   +6 Oh did realize this, thanks!
•  » » » 2 years ago, # ^ |   0 Hi, I am wondering can this be generalised to (MOD + 1) / X where gcd(MOD, X) = 1 ?
•  » » » » 2 years ago, # ^ |   +1 It works only if $(MOD + 1)$ is divisible by $X$ — then $\dfrac{MOD + 1}{X} \cdot X \equiv 1 \pmod{MOD}$.
•  » » » » » 2 years ago, # ^ |   +8 Oh yes that makes obvious sense thanks :) !!
•  » » » 2 years ago, # ^ |   0 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 years ago, # ^ |   +3 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 years ago, # ^ |   0 So the only case that can't be matched is that all the cell is $k$ right?
•  » » » » » » 2 years ago, # ^ |   0 Yup
•  » » » » » » » 2 years ago, # ^ |   0 Finally understand it. Thank you so much!
 » 2 years ago, # |   +8 can anyone please explain how, dp is working in the f question how they ended up with these three equations??Thank you :)
 » 2 years ago, # |   0 can anyone explain proof why there can’t be more than 11 in B ? it’s little foggy in editorial
•  » » 2 years ago, # ^ |   0 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 years ago, # ^ |   +1 thank you
•  » » » 2 years ago, # ^ |   0 what should be the answer of this test case? 1 3 2 1 97
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 elements of $a$ are guaranteed to be composite numbers.
•  » » » » 2 years ago, # ^ |   0 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 years ago, # | ← Rev. 2 →   0 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 years ago, # ^ |   0 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 years ago, # ^ |   0 it means the sum of elements are odd, not that every elements are odd
•  » » » 2 years ago, # ^ |   0 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 years ago, # ^ |   +1 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 years ago, # ^ |   +3 You're right, it's for an even $k$, thank you.
 » 2 years ago, # |   0 In problem B I used following code , but it isn't working, Can anyone help me? CodeLink
 » 2 years ago, # | ← Rev. 2 →   0 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.
 » 2 years ago, # |   0 thanks for tutorial solutions in (PYTHON)
 » 2 years ago, # |   0 How solve C using dfs. I saw some code used dfs to solve. But no node comes in my brain...
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 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 years ago, # |   0 Auto comment: topic has been updated by triple__a (previous revision, new revision, compare).
 » 2 years ago, # |   +20 Can anyone explain how the dp formula in problem F works in detail? I don't understand it. Thanks a lot.
•  » » 2 years ago, # ^ | ← Rev. 3 →   +10 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:- The edge is included in your edge-induced subgraph:- dpv1 + dpv0 Explanation:- You just have to take all possibilities. 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 years ago, # ^ | ← Rev. 2 →   0 You mean dpv1 also counts the case that v is colored but isolated from all its children?
•  » » » » 2 years ago, # ^ |   0 Yes
•  » » » 2 years ago, # ^ |   0 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 years ago, # ^ |   0 Yes thats correct if by "we don't choose"- you mean they are not chosen as part of the independent set
•  » » » » » 2 years ago, # ^ |   0 Yes, I get it. Thank you a lot.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 !
•  » » » » 2 years ago, # ^ |   0 1 is subtracted to remove the no edge case.
•  » » » » » 2 years ago, # ^ |   0 got it, thanks
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 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 years ago, # ^ |   0 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 years ago, # ^ |   0 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 years ago, # ^ |   0 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 years ago, # ^ |   0 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 years ago, # | ← Rev. 3 →   0 Great contest and editorial
 » 2 years ago, # |   0 Great contest :))
 » 2 years ago, # |   +5 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 years ago, # ^ |   0 because you need to make the answer fit into range [L,R] instead of [L,n].
•  » » » 2 years ago, # ^ |   0 Since the code is doing precalculating, where does this $[L,R]$ come from?
•  » » » » 2 years ago, # ^ |   0 since you should do carefully when $R=c[L]$. (check the code for notation.)
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   0 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 years ago, # ^ | ← Rev. 2 →   0 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 years ago, # ^ |   0 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 years ago, # ^ |   0 Nvm, i was able to fix my solution to ac. i still don't get some parts of the editorial tho
•  » » » » » » » » 2 years ago, # ^ |   0 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 years ago, # |   0 Nice
 » 2 years ago, # |   0 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 years ago, # ^ | ← Rev. 3 →   0 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 years ago, # ^ |   +1 sorry, i will fix it!
•  » » 2 years ago, # ^ |   0 I have taken a little while to realize this, now it's nice that you have fixed it! It 's much clearer now! :)
 » 2 years ago, # |   -31 Worst contest ever
•  » » 2 years ago, # ^ |   +26 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 years ago, # ^ |   0 Then maybe my bad day, but somehow in any contest pikemike is involved i end up not even solving A. :(
•  » » » » 2 years ago, # ^ |   +11 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 years ago, # ^ |   -18 Practicing more won't help me solve dumb questions anyway.No matter how much i practice but thanks for advice.
 » 2 years ago, # |   +7 It's a very enjoyable round
 » 2 years ago, # |   +1 Can someone who got acc on D to tell me how they thought to get to that solution?
 » 2 years ago, # |   0 Can anybody explain problem B editorial?
 » 2 years ago, # |   +1 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 years ago, # ^ |   -9 I think backtracking is the only way to solve it correctly.
•  » » » 2 years ago, # ^ |   0 hmm, going through every possible path.
•  » » » » 2 years ago, # ^ |   0 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 years ago, # ^ |   0 check this floor
 » 2 years ago, # | ← Rev. 3 →   0 I know its trivial but,Can you please tell me the intuition behind Problem B?
•  » » 2 years ago, # ^ |   0 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 years ago, # |   0 In problem A, why I need the condition a+b=0?
•  » » 2 years ago, # ^ |   0 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 years ago, # ^ |   0 And why do we need x2>=x1 and y2>=y1....these conditions?
•  » » » » 2 years ago, # ^ |   0 Those are constraints given in the question.
•  » » » » » 2 years ago, # ^ |   0 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 years ago, # ^ |   0 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 years ago, # ^ |   0 Why are you just considering 1D case??
•  » » » » » » » » 2 years ago, # ^ |   0 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 years ago, # ^ |   0 Exactly. I misunderstood the question. Thank you very much ashwath for taking the trouble to make me understand the logic and the question.
 » 2 years ago, # | ← Rev. 2 →   0 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 years ago, # ^ |   0 i think you can try with (c-d)..
•  » » » 2 years ago, # ^ |   0 It works for c-d. That's why I am asking why it doesn't work for d-c.
•  » » » » 2 years ago, # ^ |   0 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 years ago, # ^ |   0 It makes sense now. Thanks.
 » 2 years ago, # |   0 Is B solvable using graph coloring where edge exist between two elements if their gcd is 1.
•  » » 2 years ago, # ^ |   +1 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 years ago, # | ← Rev. 2 →   +7 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 years ago, # ^ |   +3 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 years ago, # ^ |   0 Okay ..thank you:)
 » 2 years ago, # | ← Rev. 2 →   +18 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 years ago, # ^ |   +16 really appreciated! btw, best part xD(and 一键三连)
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Can you make tutorial available in English for F and G problems?
 » 2 years ago, # |   +1 Can anyone explain Problem D. Tutorial isn't enough.
 » 2 years ago, # | ← Rev. 3 →   +67 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 years ago, # |   +3 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 years ago, # |   0 Let me appreciate the fact, Problem E was really nice!!
 » 2 years ago, # |   +2
 » 2 years ago, # |   0 PYTHON USERS HELP OUTthe 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 answerdef 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) returnn=int(input()) ans=[] for i in range(n): solve(ans) for ele in ans: print(ele)
 » 2 years ago, # |   0 Please Explain C without DSU
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 I did it without DSU. I used a for loop to traverse all characters in position (i,k-i,k+i,2k-i,2k+i,3k-i...) Together and check for most frequent character then make all other characters that character. Do it for all i's from 1 to k/2 and summed up the answer along the way.75164924
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 Thankyou <3
•  » » 2 years ago, # ^ |   0
•  » » » 2 years ago, # ^ |   0 Thankyou <3
 » 2 years ago, # |   0 why we have done ans/2 in 1332-C ?
•  » » 2 years ago, # ^ |   0 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 years ago, # ^ |   0 thnks for the explanation.
 » 2 years ago, # |   0 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 years ago, # ^ |   0 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 years ago, # ^ |   0 "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 years ago, # ^ |   0 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 years ago, # |   0 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 years ago, # ^ |   0 check this floor
 » 2 years ago, # |   0 If anyone is interested in detailed explanation of Problem Dhttps://competitiveprogrammingdiscuss.blogspot.com/2020/04/codeforces-round-630-div-2-problem-d.html
 » 2 years ago, # |   0 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 years ago, # ^ | ← Rev. 2 →   0 I have written in detail:https://competitiveprogrammingdiscuss.blogspot.com/2020/04/codeforces-round-630-div-2-problem-c.html
•  » » » 2 years ago, # ^ |   0 thanks a lot
 » 2 years ago, # | ← Rev. 2 →   0 can some one explain the easy intuition solution of pikmike (problem E) ?
•  » » 2 years ago, # ^ |   0 You can just draw it out, like for these grids:1x2, l = 1, r = 2;1 11 2 2 1 2 21x2, l = 1, r = 31 11 2 1 32 1 2 2 2 33 1 3 2 3 3There'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 years ago, # | ← Rev. 3 →   -8 I didn't got why are we using (x2>x1||a+b==0)&&(y2>y1||c+d==0) condition??
 » 2 years ago, # |   0 As the C++ solution illustrates, an odd $k$ in problem C does not need to be treated separately, despite what the tutorial says.
•  » » 2 years ago, # ^ |   0 that depends on implementation. It's not a hard and fast rule.
•  » » » 2 years ago, # ^ |   0 No one said that it does not.
 » 2 years ago, # |   0 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 years ago, # |   +1 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 years ago, # ^ |   0 Think how the DP approach might give a nonoptimal result.
 » 2 years ago, # |   0 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 years ago, # | ← Rev. 2 →   0 Please anyone explain the C for the input below.Input:121 7wudixiaoxingxingheclp
 » 2 years ago, # |   0 triple__a I am wondering what is the checker code for problem D :)
 » 2 years ago, # |   0 For problem F, don't we need to consider stack overflow when using recursive dfs since n <= 3e5?
•  » » 20 months ago, # ^ |   0 Nah, I think I'd solved some 5e5 problem using recursive DFS and still OK.
 » 2 years ago, # |   0 Мне одному показалось что в легком наблюдательном решении что — то не так?
 » 2 years ago, # |   0 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 years ago, # |   0 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 years ago, # |   +1 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 years ago, # |   0 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
 » 2 years ago, # |   0 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.
 » 2 years ago, # | ← Rev. 3 →   0 Please anyone can tell me what is wrong in the sample test case of 1332B-Composite Coloring.Case23437 519 865 808 909 391 194 291 237 395 323 365 511 497 781 737 871 559 731 697 779 841 961Given Answer114 7 8 10 7 3 10 7 7 8 3 1 1 5 5 9 2 2 3 3 4 11 6The 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 answer101 2 2 3 2 1 3 2 2 4 1 4 5 5 6 6 7 7 8 8 1 9 10
 » 2 years ago, # |   0 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];
 » 2 years ago, # | ← Rev. 5 →   0 (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
 » 2 years ago, # |   0 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 96111 8 2 3 1 2 7 1 2 2 3 7 3 4 4 5 5 6 6 7 7 8 10 11There is not the number 9. Why it isn't working? Please help
•  » » 2 years ago, # ^ |   0 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.
•  » » » 2 years ago, # ^ |   0 I know there must be 9, but when a do a solution like in this blog, there isnt 9
•  » » » » 2 years ago, # ^ |   0 I solved the same way as in the editorial and got the correct answer. Maybe you should double check your code.
•  » » » » » 2 years ago, # ^ |   0 OK, I will do that, thanks
 » 23 months ago, # |   0 is there a problem in my code , i am getting tle on test 5 https://codeforces.com/contest/1332/submission/83755735
 » 22 months ago, # |   0 auto f=[&](int u){ for (int i=2;i<=u;++i){ if (u%i==0) return i; } }; Can anyone explain what type of function is this in the editorial of B?
 » 20 months ago, # |   0 triple__a I guess solution provided for 1332A contains some bugs. kindly verify it by checking against following test case1 2 3 0 0 0 0 0 0 1 0
 » 19 months ago, # |   0 in solution to prob C I am not able to understand this ---> "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"
 » 15 months ago, # |   0 why output "ans/2" in question C ? why not output just 'ans'.
 » 13 months ago, # |   0 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. 
 » 8 months ago, # |   0 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.
 » 6 months ago, # |   0 whu i get wrong answer in test 1 can someone help me??problem (B) https://ideone.com/uKkSIq