### Stefan2417's blog

By Stefan2417, history, 3 weeks ago, translation,

We hope you enjoyed the problems.

Problem 1977A - Little Nikita was created by Stefan2417 and prepared by alexchist.

Problem 1977B - Binary Colouring was created by alexchist and prepared by Stefan2417.

Problem 1977C - Nikita and LCM was created and prepared by Stefan2417.

Problem 1977D - XORificator was created and prepared by alexchist.

Problem 1977E - Tensor was created and prepared by Stefan2417.

1977A - Little Nikita

Tutorial
Author's code
Feedback

1977B - Binary Colouring

Tutorial
Author's code
Feedback

1977C - Nikita and LCM

Hint
Tutorial
Author's code
Feedback

1977D - XORificator

Hint
Tutorial
Author's code
Feedback

1977E - Tensor

Tutorial
Author's code
Feedback
• +98

 » 3 weeks ago, # |   -49 better late than never. thank you for the editorial
 » 3 weeks ago, # |   +37 Ooooh so you have a temporary third chain in E. I love it, it's close to what I was trying and makes it so elegant. Also thank you for the proof of existence using Dilworth.The contest was of huge quality, one of my favorite codeforces. Thank you setters. orz
 » 3 weeks ago, # | ← Rev. 2 →   0 for the 2nd question; can anyone help me debug why/where is my logic wrong? its different than author's. https://mirror.codeforces.com/contest/1977/submission/262928317
•  » » 3 weeks ago, # ^ |   0 It says "wrong answer coefficients do not sum to x (test case 3)" (failed on 1359) in the second test.
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   0 https://mirror.codeforces.com/contest/1977/submission/262935920Here are the minor changes I've made. if(j){ // v.insert(v.begin()+start,0); // don't insert a new element, cuz it affects the final accumulation v[start] = -1; v[i]=1; i--; // i = start + 1; is incorrect } 
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 oh yess, thank you for the correction, i get it now.
 » 3 weeks ago, # |   0 Thanks for the editorial!
 » 3 weeks ago, # |   +5 Does anyone know any similar problems to C,Want to improve on concepts of LCM, GCD and divisors.
•  » » 3 weeks ago, # ^ |   0 Learn it from math/number theory books, not codeforces problems.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Please can you suggest some good books?
•  » » 3 weeks ago, # ^ |   +3 this post my help bro https://mirror.codeforces.com/blog/entry/118882
•  » » » 3 weeks ago, # ^ |   0 thanks
•  » » 2 weeks ago, # ^ |   0
 » 3 weeks ago, # | ← Rev. 2 →   0 Yo for C can someone explain me this part?"Then we iterate over the divisors of the maximum and greedily check for the presence of a subsequence with such an LCM."It's not immediately clear why this will yield the max sequence broEdit: nvm I acc get it now it's clear from the tutorial, I'm so stupid bro
•  » » 3 weeks ago, # ^ |   0 not easy to understand immediately, you are clever bro
•  » » » 3 weeks ago, # ^ |   0 thanks bro I needed that ego boost lmfao
 » 3 weeks ago, # |   0 Thank you so much Stefan! I quite enjoyed figuring out the solve to question C, even if I only figured it out after the contest... Question B was satisfying as well.
•  » » 3 weeks ago, # ^ |   +7 Radewoosh, This proves not only Indians say "question" instead of "problem".
 » 3 weeks ago, # |   0 what does this mean in C problem tutorial?? "Then we iterate over the divisors of the maximum and greedily check for the presence of a subsequence with such an LCM."
•  » » 3 weeks ago, # ^ |   +1 Basically since all elements in a divide max(a), then any combination of elements in a will have an LCM that divides max(a) too. And for an LCM to belong to a sequence, it must be divisible by all elements in that sequence must match the actual LCM of that sequence Using those facts our search space is now the divisors of max(a) where we just need to check for those two facts and greedily get the maximum subsequence.
•  » » » 3 weeks ago, # ^ |   0 crazzy bro,, great explaination. just one thing why this check is necessary in calc func? if (LCM != d) cnt = 0; as it will always be equal, right?
•  » » » » 3 weeks ago, # ^ |   +1 not always, take this for example:3 2 10 20 60 1here the overall LCM is 60 so we search over its divisors. If we choose 4, then only 1 and 2 divide it, but their LCM is 2 (which is acc in a), not 4. We're searching for a subsequence that has exactly that divisor as its LCM for this iteration so 4 is not even valid to consider.
•  » » » » » 3 weeks ago, # ^ |   0 yup got it
•  » » » 3 weeks ago, # ^ |   0 Very well explained. This should be a part of the editorial! Thanks bruh
 » 3 weeks ago, # | ← Rev. 2 →   +1 Can someone explain the solution of Problem D. Only thing I am seeing is Xor and Random numbers. Totally Confused right now!!PS: Understood the solution. But why are we keeping 2 random numbers of each index?
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 To reduce the probability of collision. It's for the same reason that you use two modulos in hashing sometimes.
•  » » » 3 weeks ago, # ^ |   0 Oh! Okay. Thanks!
•  » » 3 weeks ago, # ^ |   0 Will you please explain it for us?
•  » » » 3 weeks ago, # ^ |   0 Suppose we want the 1st column to contain exactly one 1. Then there are n options in which we can have that 1. Let's say we make the only one 1 at the first row itself. Then the set (of each row) of XORificator used will be unique. Similarly, it will be unique for each of the (i, j) if we decide that in the jth column the only 1 will be at ith row. So, now we will calculate all the unique set of XORificator, for which we have used hashing. Now, if the cnt[hash] is x that means x columns will contain only one 1 with the following set of XORificator. So, you can just choose the one with the most cnt and that will be your answer.
•  » » » » 3 weeks ago, # ^ |   0 Yep! Got the feel. Thanks.
•  » » » » 3 weeks ago, # ^ |   0 But we still have a non-zero probability of getting a wrong answer , right?
•  » » » » » 3 weeks ago, # ^ | ← Rev. 3 →   0 No, it's actually 0, the only reason it might cause a wrong answer is when the hash values collide, where as seen in the editorial you can just store 2 values for the hashes, making the hash collision probability wayyy less(around 0 for the problem constraints), but a single hash suffices Why is the probability zero: Well, the lower bound of the answer is 1, cause you can just select a single column and invert every 1 except one. Now imagine You selected the column $i$ as the column with the single inverted 1, and the row $j$ as the 1 bit, since there is only a single way to make that cell $(i, j)$ to be one and none other $(i, k)$, the operations you chose are unique, so just save the resulting table best answer, and since there is no other way to fix $(i, j)$, if it was to fix $(i, j)$ this would be the best result, just take the maximum for every $(i, j)$
•  » » » » » » 3 weeks ago, # ^ |   0 Short answer: the only reason the probability for WA is 0 is just that for a fixed (i, j) there is only a single way to do it
•  » » » » » » 3 weeks ago, # ^ |   0 It is not zero, but a very small probability (negligible for the purposes of passing tests).
•  » » » » » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 which probability isn't zero? hash collision or the idea itself? (regarding of the hash function) Like there is a chance that not fixing anything will be the best answer? in that case there is at least 1 column is special(since we know that the answer >= 1), where its answer is calculated during the selection of that column and row
•  » » » » » » » » 3 weeks ago, # ^ |   0 You can't say that the probability is exactly zero unless you can make sure that there is absolutely not a single case where a hash collision that leads to wrong answer occurs, which is why we say it's a 'non-zero probability' because it is indeed not exactly zero, but negligible.
•  » » » » » » » » » 3 weeks ago, # ^ |   0 By zero I meant the prob of wrong answer not considering hash collisions, but yes, taking that into part even if u have 10000 different hash values for a single element there is always a way for the to collide even when n = 2, (and in my original comment I said unless hashes collide)
•  » » » » » » » » » 3 weeks ago, # ^ | ← Rev. 3 →   +3 It seemed quite obvious to me that the original question was asking about whether hash collision can occur or not (because otherwise they wouldn't say terms like non-zero probability), so starting with saying directly "no, it's actually 0" to that question looked like you had some clear evidence that it can always avoid hash collision (or even if that occurs you still won't get wrong answer) somehow.
•  » » » » » » » » » 3 weeks ago, # ^ |   0 Ohh, I thought the question was asking if there is a chance the idea itself not being correct and giving wrong answer
•  » » » » » » » » » 3 weeks ago, # ^ |   0 yes , i was referring to the hash collisions. Can't we generate test cases for which there is high chances of collisions(considering the hash functions used)? Thanks
 » 3 weeks ago, # |   +4 For B I did some uninteresting wack shit. Someone explain Jiangly or Tourist's solution for B please? They did something like % 4 = 1 then 1, % 4 = 3 then -1 and % 2 = 0 means 0.
 » 3 weeks ago, # |   0 In problem B, why is [-1 0 -1 -1 0 1] not a valid answer for x = 19? -1 + 0 + -4 + -8 + 0 + 32 = 19, so why am I getting wrong answer? Judge says "wrong answer. wrong coefficient format.", what am I doing wrong?
•  » » 3 weeks ago, # ^ |   0 Atleast 1 number for every pair of adjacent elements should be 0
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 @SriRam523 How did you understand this point from the problem?
•  » » » » 2 weeks ago, # ^ |   0 In the constraints of the problem (at the top), it reads, "There does not exist an index $0≤i≤n−2$ such that both $a_i≠0$ and $a_i+1≠0$."
 » 3 weeks ago, # |   0 Could someone explain the hashing in D. I could come up with the idea of trying to fix a $i, j$ cell to be 1, but couldn't deal with the efficient XOR operations. What will we actually hash right here?
•  » » 3 weeks ago, # ^ |   +17 You want to count which configuration on the rows appearead most often : if a given configuration appeared n times, it means that there will be n special columns if you use it.So if you name a configuration "000110" for example (meaning flip rows 4 and 5 only), you want to hash this string to keep track of how many times it appeared. The issue is that you want this hash in O(1) time. Luckily, if, for each column, you try to make bit 1 special, then bit 2 special, etc... you will notice that the string representation of your configurations does not move much (only 1 or 2 characters change each time). So you want a hash that you can easily change in O(1) using this property instead of re-hashing in O(n).For this, you can use author's trick to prevent collision, or use a more classic technique of "rolling hash" which worked for me for example.
 » 3 weeks ago, # |   0 I am unable to understand why I am getting WA in problem C.submission
•  » » 3 weeks ago, # ^ |   0 A possible reason：when you calculate the LCM of all elements, it will go beyond i64. So try to stop getting LCM as it becomes larger than the max element. (Cool painting btw)
•  » » » 3 weeks ago, # ^ |   0 Thanks for pointing it out. Got AC. Thanks for the painting as well :}
 » 3 weeks ago, # |   0 For D I got the idea, but why if I use an unordered_map to keep track of how many time had a configuration appeared I will get a ME
•  » » 3 weeks ago, # ^ |   0 (At first, I wanted to use 01trie to maintain the times a configuration appeared but I think it would get a ME too.
 » 3 weeks ago, # | ← Rev. 2 →   +24 Problem D can have also have deterministic solution rather than probabilistic one. we can write the solution for two different cases (m > n and m <= n). for m > n number of rows are less than 550, for a cell in the grid to be 1 the set of rows to be flipped can be encoded into a string (len < 550), complexity: n * n * m (n < 550). these strings can be stored in a map with their count and max count string is answer. unordered map can be used for speed up. for m <= n we can solve this using dp, where two columns differing at two or zero places are used for transitions, we check every pair of columns for transitions, answer can easily be constructed for a cell having max dp value, complexity: n * m * m (m < 550), max iterations ~ 1.65 * 10 ^ 8, safely under the time limit:262840232
•  » » 5 days ago, # ^ |   0 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } hey i was also using the same approach but didnt separate the case of m>n and my sol tled.Nice to see i was half right for the dp.Thanks
 » 3 weeks ago, # |   0 Can someone please explain the time complexity of Question C?
 » 3 weeks ago, # |   0 Has anyone tried solving problem C with the Hasse graph (an edge $u \rightarrow v$ means $v | u$ )? It's easy to construct it in $O(n^2)$ but I can't find a way to maximize the set (I tried DP on graph). Eventually I did to the Brute force solution.
 » 3 weeks ago, # | ← Rev. 3 →   0 i'm struggling with problem C.here is my approach.[solve for N]if N <= 1: return 0if LCM(A[1] ~ A[N]) overflow A[N]: return Nif LCM(A[1] ~ A[N — 1]) == A[N]: find maximum length subsequence its LCM is not A[N] <- brute forceif LCM(A[1] ~ A[N — 1]) < A[N]: [solve for N — 1]https://mirror.codeforces.com/contest/1977/submission/263102096what is wrong with my code
 » 3 weeks ago, # |   0 In the authors code for D did he just ignore the possibility of collisions? If yes then is this normal in competitive programming to ignore collisions if chances are too low?
•  » » 3 weeks ago, # ^ |   0 Yep, if there's not a huge chance of collision then you can mostly ignore it
 » 3 weeks ago, # |   0 Honestly, don't know how I didn't realize that the LCM on C could be bounded that easily, I guess we have good and bad days
 » 3 weeks ago, # |   0 Can the problem C be solved by Dynamic Programming ?
•  » » 3 weeks ago, # ^ |   0 you can solve it with recursive and memoization but you need to use unordered map
•  » » 3 weeks ago, # ^ |   0 262785009Check out this soln
•  » » » 3 weeks ago, # ^ |   0 Thanks !!!
•  » » » 3 weeks ago, # ^ |   0 Can you please explain the logic behind this part of your solution:- I am not able to understand it. if (mp[LCM]) { // It is a factor ans = max(ans, 1 + func(p, LCM, a, n)); ans = max(ans, func(p, val, a, n)); } else { ans = max(ans, max(mp[a[p]] * 1ll, mp[a[p]] * 1ll + func(p + (mp[a[p]] - 1), LCM, a, n))); ans = max(ans, func(p, val, a, n)); } 
•  » » » » 3 weeks ago, # ^ |   0 if partif our current lcm which is val,if we take lcm(val,a[p]) ll LCM = lcm(val, a[p]); if after taking lcm our result LCM comes an element which is already present int mp[] that means it's the factor in that case we hope that in future we can form a sequence that doens't exit in mp other wise base condition return a large negative value =-1e17else partnow we get out LCM which isn't present in mp[] that means we can form sequnce till that and also we can also increase our sequnce further but we have to store temporary ans that's why this max(mp[a[p]] * 1ll, mp[a[p]] * 1ll + func(p + (mp[a[p]] — 1), LCM, a, n))) first part in max return ans till that if we don't able to increase our length and 2nd part return the max if we can increase our lengthnow why i use m[p] instead of 1 bcif we have element like 5 7 7 7 7we can just take 5 7 7 7 as whole rather than5 75 7 75 7 7 7hope u understand
•  » » » » » 3 weeks ago, # ^ |   0 Yeah, Thanks
 » 3 weeks ago, # |   0 Has anyone tried divide and conquer in B? There are 5726623061 sequences of {-1, 0, 1} lenght 32 with at least one zero among every 2 adjacent elements. We can bruteforce first 16 elements of the sequence, and use precalced values for other half.
 » 3 weeks ago, # |   0 I have another approach for C :sort the array and check for the longest prefix such that lcm of that prefix is not the last element of the corresponding prefix.is this wrong?
 » 3 weeks ago, # | ← Rev. 2 →   +8 Stefan2417, problem E editorial is incorrect.Let $n = 3$ and only one edge $1 \leftarrow 2$. According to the text solution $1$ will be white and $2$ will be black (or vice versa). Then the red stack is empty, but no vertexes are reachable from the 3rd. You said such a situation is impossible, but here it is.
•  » » 3 weeks ago, # ^ |   0 The editorial is incorrect, but the code handles this case correctly. In particular, the part if (ask(i, st.back())) { st.push_back(i); } else { st2.push_back(i); } does not match with the editorial; the editorial says that the vertex should be put into the empty stack by default, but the code puts it into the first stack, if the last vertex in the first stack is reachable from the current vertex, and into the second stack only if the aforementioned condition is not true.
 » 3 weeks ago, # | ← Rev. 2 →   0 In editorial C, What d(C) means?
•  » » 3 weeks ago, # ^ |   0 divisors of max element
 » 3 weeks ago, # |   0 In editorial C, why is O(N * d(C)) sufficient? Is'nt N <= 10**3 and C <= 10**9, thus O(d(C)) <= square root of C which is 10**4?Would'nt O(N * d(C)) be 10**7 than?
•  » » 3 weeks ago, # ^ |   0 A number up to $10^9$ can have at most $1344$ divisors. Check https://mirror.codeforces.com/blog/entry/14463.
 » 3 weeks ago, # | ← Rev. 2 →   0 [user:Stefan2417]Stefan2417 In Problem C this solution should not pass but it passes.Please anyone try to hack it. https://mirror.codeforces.com/contest/1977/submission/263672671
 » 3 weeks ago, # |   0 I don't get C — Nikita and LCM. I understand that if the lcm of the whole array is equal to the max element in the array, then all elements divide the max. What I take from this is that the max element should not be in our solution subsequence.What does "iterate over the divisors of the maximum" mean?
•  » » 2 weeks ago, # ^ |   0 It means that If all the elements in array A are divisible by max(A), LCM of any subset of A will be divisor of max(A). ProofLet $a_i = p_1^{x_1} * p_2^{x_2} * p_3^{x_3}...$, where $p_i$ is the i'th prime number and $x_i\,€\,Z$ such that $x_i \ge 0.$ So LCM of this array is $p_1^{max(x_1)} * p_2^{max(x_2)} * p_3^{max(x_3)}...$ If number $a_i$ is extracted from this list, no primes $p_1 ... p_n$ were added to the new LCM, we can just decrease $max(x_i)$'s with this way, so new LCM will remain as a divisor of max(A). (Apologies for first time using latex.)
•  » » » 2 weeks ago, # ^ |   0 Do you mean if all the elements in array A divide max(A)?
•  » » » » 2 weeks ago, # ^ | ← Rev. 2 →   0 Yes, If they didn't the answer would be simply length of array A which is N.
 » 2 weeks ago, # |   0 For problem "B" how can it be a WRONG_ANSWER.Can anyone help? https://mirror.codeforces.com/contest/1977/submission/264399208Input 7 1 14 24 15 27 11 19 Participant's output 1 1 5 0 -1 0 0 1 6 0 0 0 -1 0 1 5 -1 0 0 0 1 6 -1 0 -1 0 0 1 5 -1 0 -1 0 1 6 -1 0 -1 -1 0 1