### voidmax's blog

By voidmax, history, 3 months ago, translation, ,

Thanks for participating in my contest!

It was my first round, I hope you enjoyed.

#### Editorial:

•
• +106
•

 » 3 months ago, # |   +60 I enjoy this contest very much. I hope I will see you as a problemsetter soon!
•  » » 2 weeks ago, # ^ |   0 bu cu
 » 3 months 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 months 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 months ago, # ^ | ← Rev. 2 →   0 Didn't you have to iterate through all occurrences? Wouldn't that still be ? Or am I missing something?
 » 3 months 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 months ago, # ^ |   0 maybe UB. try drmemory.
•  » » 3 months 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.
 » 3 months 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 months ago, # ^ |   0 Z contains only k elements, so you can calculate in complexity O(k)
•  » » » 3 months ago, # ^ |   0 Sorry, I meant the full sum not Z(Its changed now)
 » 3 months ago, # |   0 can't understand "alternating sum " problem's solution . can anybody explain how it works. thanks.
•  » » 3 months ago, # ^ |   +6 and solve the last line using summation of geometric progression
•  » » » 3 months 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 months ago, # ^ |   0 my typo, sorry for that, it should be
•  » » » » 3 months 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 months ago, # ^ |   0 How to get these (b/a) values. You need to learn inverse modulo if you haven't learned already.
•  » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 trueglory How can I prove that the power is k ?
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 Why am i getting a runtime error in testcase 9?http://codeforces.com/contest/964/submission/38454719
•  » » » » 2 months ago, # ^ |   0 Because you are dividing by zero
•  » » 3 months ago, # ^ |   0 the general thought is to use the peroidicity
 » 3 months 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 months 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 months ago, # ^ |   0 Thank you!!
•  » » » 3 months ago, # ^ |   0 How can you remove u's even subtree?
•  » » » 3 months ago, # ^ |   0 Thank you. It is helpful for me.
•  » » » 3 months ago, # ^ |   0 Thanks a lot. :)
•  » » 3 months 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 months ago, # |   0 Cannot understand the solution of Cutting rectangle'... can anyone explain the tutorial for it in detail? Thanks in advance!
•  » » 3 months 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 months ago, # ^ |   0 Thanks! a picture says more than thousands of words!
 » 3 months 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 months 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 months 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 months ago, # ^ | ← Rev. 2 →   +3 q = fastow(b * fastpow(a, MOD-2) % MOD, k)
•  » » » » 3 months 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 months 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 months ago, # ^ |   +8
 » 3 months ago, # |   0 So is that problem 963E a Markov chain?
 » 3 months ago, # |   -13 Can anyone please provide useful resources for aho-corasick as i am new to this topic ???
 » 3 months 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 months 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 months ago, # ^ |   0 So we can use only ones and twos.
•  » » » 3 months 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 months ago, # |   0 Can anyone please explain why the Number of different lengths of mi is O(sqrt(M))? And why do wd calculate the O(M*sqrt(M))? Many Thanks
 » 3 months 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 months ago, # ^ |   0 5 0 1 1 2 3 Have a try.
•  » » » 3 months ago, # ^ |   0 My code is giving "NO" and I think no is the correct answer
•  » » » » 3 months 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 months 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.