### voidmax's blog

By voidmax, history, 3 years ago, translation,

Thanks for participating in my contest!

It was my first round, I hope you enjoyed.

#### Editorial:

• +106

 » 3 years ago, # |   +60 I enjoy this contest very much. I hope I will see you as a problemsetter soon!
•  » » 2 years ago, # ^ |   0 bu cu
 » 3 years ago, # | ← Rev. 2 →   +28 D can also be solved with suffix arrays + BWT (see this reference: http://blog.avadis-ngs.com/2012/04/elegant-exact-string-match-using-bwt-2/ ).First you should know how to do it with suffix arrays, in that you can binary search for first and last entry so you can get all occurrences of a word in log(n) per word.You can speed this up with BWT to take O(|w|) time for a word w (so total is O(sum of lengths of words) rather than O((number of words) * log(n))). The basic idea is you can maintain an interval on the suffix array which contains a suffix of the pattern, and you reduce this interval's size in constant time every time you add another letter. You can see my implementation here: http://codeforces.com/contest/963/submission/37445232
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 We can do it using only suffix arrays too. No need for optimization using bwt.my submission: http://codeforces.com/contest/963/submission/37425722
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Didn't you have to iterate through all occurrences? Wouldn't that still be ? Or am I missing something?
 » 3 years ago, # |   0 I have another solution to problem D with suffix automation + dfs. This is my AC code: submission:37454639(http://codeforces.com/contest/963/submission/37454639)For string s, we build a suffix automaton(sam), and for each node in sam, we can also know its matching position in string s. For each query, we find the node x in sam which represent string m. By dfs the fail tree of sam, we can get a sequence of the positions of each node in the fail tree of node x. We sort this sequence and traversal it to get the answer.In the worst case, the complexity of this sulotion is O(N·sqrt(N)·log(N)).But when I solving this problem, I got a trouble. If I swap line 114 and line 115 in my AC code, I will receive a TLE, I don't know why, maybe the compiling optimize? Can anybody explain, thanks.
•  » » 3 years ago, # ^ |   0 maybe UB. try drmemory.
•  » » 3 years ago, # ^ |   +5 Maybe O(N·sqrt(N)·log(N)) is too large. In test 47, s[]="aaa..a", so the fail tree is a chain. If Pre-order traversal, order[l...r) is increasing before sort. So maybe the compiling optimize make it faser.
•  » » 2 years ago, # ^ |   0 You could use an O(n) linear sorting algorithm for an array whose elements are not very large.It could get rid of the "log" time complexity to construct a more fast solution.
 » 3 years ago, # | ← Rev. 2 →   0 My solution involved precalculating all of a & b. Then finding the sum takes O(n) time. This didn't pass, however I have solved n<10^9 problems with linear time before, is there a general rule as to what time is required? (I'm somewhat new to this)
•  » » 3 years ago, # ^ |   0 Z contains only k elements, so you can calculate in complexity O(k)
•  » » » 3 years ago, # ^ |   0 Sorry, I meant the full sum not Z(Its changed now)
 » 3 years ago, # |   0 can't understand "alternating sum " problem's solution . can anybody explain how it works. thanks.
•  » » 3 years ago, # ^ |   +6 and solve the last line using summation of geometric progression
•  » » » 3 years ago, # ^ |   0 in second line,second SUMMATION i think it will be=> S (in range from i=0 to i=k-1) = Si*a^(n-i-k)*b^(i+k)you wrote just Si*a^(n-i-k)*b^(i). if i mistake please help.
•  » » » » 3 years ago, # ^ |   0 my typo, sorry for that, it should be
•  » » » » 3 years ago, # ^ |   +3 We are basically taking advantage of the periodicity of s. So we first calculate the sum for the first k values.()can be seen as ()where (p) is ()Then can we multiply this sum by (n+1)/k i.e. number of this periodic strings to get the final result. Not quite. Why?Because for calculating sum each subsequent periodic substring The power that you raise p will be more. But by how much?- Yes it is k.
•  » » » » » 3 years ago, # ^ |   0 How to get these (b/a) values. You need to learn inverse modulo if you haven't learned already.
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   0 trueglory How can I prove that the power is k ?
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Why am i getting a runtime error in testcase 9?http://codeforces.com/contest/964/submission/38454719
•  » » » » 3 years ago, # ^ |   0 Because you are dividing by zero
•  » » » 23 months ago, # ^ |   0 Can you explain how you got the exponents in the last term in the second line? How you got a^(k-i-1)*b^(i+n-k+1). And also how you got the last term in the third line from that.
•  » » 3 years ago, # ^ |   0 the general thought is to use the peroidicity
 » 3 years ago, # | ← Rev. 2 →   0 Can someone please explain the reason behind why the solution in Destruction Tree Question work ? I am not able to understand the tutorial solution.
•  » » 3 years ago, # ^ | ← Rev. 6 →   +11 My solution is slightly different from the tutorial, but the thoughts are the same.It is obvious that the answer is yes' if and only if the tree have odd numbers of nodes. Otherwise it has even nodes, and n - 1 edges, which is odd. Each step we remove even edges, so odd - even - even - ... doesn't equal to 0, hence the edges cannot be removed completely.And then we use DFS to delete the nodes:For a node u, DFS(u) does: call DFS(v) on any subtree v that has a even size remove u call DFS(v) on any subtree v that has a odd size Why this method is right? Proof using mathematical induction:Base case: It is right when the tree has 1 or 3 nodes.Inductive step:Case 1: the (sub)tree has even nodes. For convenience we call it subtree u. Because it has even nodes, it must have a parent node (otherwise no solution). After removing u's even subtrees', there remain even nodes in the tree u(even - even = even). Leaving node u alone, there're odd nodes in the tree u. Since all the even subtrees of u was removed, the remaining subtrees have odd size. odd·odd = odd -> node u has odd numbers of odd-sized subtrees. (odd numbers of odd-sized subtrees) + parent -> the degree of u is even. So we can instantly remove u, and then recursively remove its odd-sized subtrees.Case 2: the (sub)tree has odd nodes. The proof is very similar with case 1, so omitted.As shown above, this strategy can remove all the nodes.Q.E.D.
•  » » » 3 years ago, # ^ |   0 Thank you!!
•  » » » 3 years ago, # ^ |   0 How can you remove u's even subtree?
•  » » » 3 years ago, # ^ |   0 Thank you. It is helpful for me.
•  » » » 3 years ago, # ^ |   0 Thanks a lot. :)
•  » » 3 years ago, # ^ |   0 I know a tree with even nodes can not be destructed, but how can you prove that there must exist a solution for an tree with odd nodes?
 » 3 years ago, # |   0 Cannot understand the solution of Cutting rectangle'... can anyone explain the tutorial for it in detail? Thanks in advance!
•  » » 3 years ago, # ^ | ← Rev. 6 →   +34 We'd like to combine the rectangles to a big one, and let's call a way to build the big rectangle A GOOD WAY. In a good way, we can move some small rectangles. For example:It has four types of rectangles and shows a good way. We can also get the same big rectangle in this way:It can be built by first constructing one part of them, then copy them several times. The Editorial states that every big rectangle contains the same part, like the picture above. More formally, we need to build one BASE PART, such that it contains all types of small rectangles, and the gcd of the numbers of all types in a part is 1. So we need to divide every ci with gcdi = 1 to nci (call it G), and check if base part can be built. If built, we will copy the base part G times to make a bigger rectangle, and the number of ways is the number of divisors of G (copy x times in one direction and y times another,x * y = G). Else, the answer is 0.The last is how to check the base part. We divide the rectangles into different groups based on their a, and discover that if a way is good, each line's ratio of number of b is the same. For example, when a = 2, [b = 1]: [b = 2]: [b = 4] = 3: 5: 7, and when a = 3, [b = 1]: [b = 2]: [b = 4] must be 3: 5: 7. Based on this we just need to compare some ratios and check if they are the same.
•  » » » 3 years ago, # ^ |   0 Thanks! a picture says more than thousands of words!
 » 3 years ago, # | ← Rev. 2 →   0 in problem c div2 i want to help how to calculate q when i saw one's solution i found him caculate it by this line long long q=poow(a,k*(MOD-2)%(MOD-1))*poow(b,k)%MOD;but i can't understand why it calculate in this way as from eq i know that q = (b/a)^k but i can't match this line of code with eq of q can any one help me?
•  » » 3 years ago, # ^ |   0 the code is a little weird(may contain typo) but i guess it's modulo inverse?i got it in this way: q = fastpow(a, k * (MOD-2) % (MOD-1)) * fastpow(b, k) % MOD; % (MOD-1)` since
•  » » » 3 years ago, # ^ |   0 i didn't know modulo inverse before so your code confusing me.as i can't understand why that's true and why i should do that could you help me to understand it by any source or detailed disscusion to that.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +3 q = fastow(b * fastpow(a, MOD-2) % MOD, k)
•  » » » » 3 years ago, # ^ |   0 that's more aceptable to me as i confused from why %Mod-1 not %MODall great thanks To you voidmax and panda_2134
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 i have another question in the same problem as i understand all above but i can't understand why i should multiply po(q-1,MD-2)%MD this term but in my answer as i understand from your equation above that the answer if q!=1 : cout<
•  » » » » 3 years ago, # ^ |   +8
 » 3 years ago, # |   0 So is that problem 963E a Markov chain?
 » 3 years ago, # |   -13 Can anyone please provide useful resources for aho-corasick as i am new to this topic ???
 » 3 years ago, # |   0 "Then we can replace all maximum numbers with twos and the rest we split into ones and weight will be the same."Sorry I'm very new. Can you please explain the solution to Div2 problem A again? I understand every number n > 1 has at least two ways to be partitioned in a strict ordering ([n] and [1,1,1....1]). But what about the numbers in between? Merge a pair of 1's into 2's? Then what do we do about the pairs of 2's? Thank you for your patience.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 "Then we can replace all maximum numbers with twos and the rest we split into ones and weight will be the same."So [4, 4, 2, 1] equivalent to [2, 2, 1, 1, 1, 1, 1, 1, 1]
•  » » 3 years ago, # ^ |   0 So we can use only ones and twos.
•  » » » 3 years ago, # ^ |   0 You replace 4's with 2's then where did the extra 1's come from? And what about odd numbers? What is base case?
 » 3 years ago, # | ← Rev. 2 →   0 Can anyone please explain why the Number of different lengths of mi is O(sqrt(M))? And How do we calculate the O(M*sqrt(M))? Many Thanks
•  » » 2 years ago, # ^ | ← Rev. 7 →   +8 Let M = m1 + m2 + ... + mk, then the number of distinct values of mi is O(sqrt(M)), because sum from integers from 1 to 2*sqrt(M) is equal to (2*sqrt(M) + 1)*sqrt(M) > M . Then, for every length Mi, we have O(M) occurrences in the text (note that this is only true because all query strings are different) and since we have O(sqrt(M)) different lengths, total complexity is O(M*sqrt(M)). Just leaving this comment here in case anyone has the same doubt as myself.
 » 3 years ago, # |   0 My approach in D was a bit different.I used a modified topological sort.I started with a queue and pushed a vertex with even degree in the queue and then just popped a vertex reduced the degree of it's adjacent vertices by one,checked if any of these vertices now have a even degree if so then push this vertex into the queue.I am not able to figure out what is wrong with my approach .Any help is much appreciated. Here is the link to my solution http://codeforces.com/contest/964/submission/37423833 . Thanking you in advance.
•  » » 3 years ago, # ^ |   0 5 0 1 1 2 3 Have a try.
•  » » » 3 years ago, # ^ |   0 My code is giving "NO" and I think no is the correct answer
•  » » » » 3 years ago, # ^ |   0 You can break node 2 first and then break node 3 and finally you got the answer 2 3 1 4 5
 » 3 years ago, # | ← Rev. 2 →   0 In Div 2D/Div 1B, problem tag contains dp. i do not understand how dp is used here. can someone pls explain.
•  » » 17 months ago, # ^ |   0 it's tree dp
•  » » 10 months ago, # ^ |   0 To late but ==>dp[i][0] = Is it possible to destroy i-th subtree if we havent deleted the (par,i) edge dp[i][1] = same as above but we have deleted the (par,i) edgeHow we update it ==> so we do a dfs from 1 assume that you're now in vertex start, lets call the neighbours of start that dp[u][0] == false && dp[u][1] == true group 1. and similar call the neighbours of start that dp[u][0] == true && dp[u][1] == false group 2, also call the neighbours of start that dp[u][0] == true && dp[u][1] == true group 3 ( if for some vertex both of them are false the answer is NO).So now it's obvious that you have to delete all the group 2 before deleting this vertex and similarly you have to delete all of the group 1 after deleting this vertex so now depends on your vertex degree and your DP state (0,1) you have to put some of the group 3 to make it correct ( you can put any vertex of group 3 after or before deletion of this vertex and it doesn't matter)
 » 2 years ago, # |   0 D can be solved simply by hashing lol
•  » » 6 months ago, # ^ |   0 How will you do it, wouldn't it lead to a complexity of O(N^2), because you will have to check every substring of length p where p is the length of M_i for a given query.
 » 3 months ago, # |   0 Testcase 9 in DIV2C/DIV1A is (a^k/b^k)%mod = 1 but a != b.Testcase 7 in DIV2D/DIV1B is "root of the tree is not 1" which means p1 is not zero
 » 3 months ago, # |   0 My solution for DIV2 D/DIV1 BDeleting a node will toggle the degree of it's neighbours (even becomes odd, odd becomes even)We find the deepest node that has even degree, delete the subtree of that node in a bfs manner( as all node should have odd degree, when we delete in bfs manner, they become even level by level).The reason why this is optimal is, we have to delete the deepest node and it's subtree in the above mentioned manner, because if we delete it's parent first then this becomes odd degree and the entire subtree becomes odd. So it is always optimal to delete the deepest even degree node and it's subtree, that will not change the answerSubmission : 91716266