### triple__a's blog

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

Tutorial
Solution (C++)
Tutorial of div2 B-C #1

• +279

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