### scanhex's blog

By scanhex, history, 9 months ago, ,

Author: isaf27

Author: 300iq

Statements and editorial: scanhex

Author: scanhex

Solution

Author: isaf27

Author: altruist

Author: altruist

Author: scanhex

Solution 1

Solution 2

• +24

 » 9 months ago, # |   -38 Thanks for fast editorial
 » 9 months ago, # | ← Rev. 2 →   0 in div2 E , i understand spanning tree , but what you mean by dfs spanning tree , what dfs means here ?
•  » » 9 months ago, # ^ |   0 It's the spanning tree you run through when you do a Depth First Search (DFS) on your graph (the root is the vertex you start with, etc).
•  » » » 9 months ago, # ^ |   0 gprano , but in a graph there can be multiple spanning trees , does dfs always gives us the spanning tree with largest depth ?
•  » » » » 9 months ago, # ^ |   0 You won't necessarily get the spanning tree with largest depth, but the argument works for any tree you'll get that way. (it's possible that sometimes both CYCLES and PATH solutions exist but the argument guarantees that if your dfs tree has depth < n/k then the CYCLE solution works)
•  » » » » » 9 months ago, # ^ |   0 I really don't understand why a leaf has at least 2 back edges (edges which connected with one of ancestors). I mean why they are sure to be connected with ancestors. It's possible that they are in other brunches, right? Sorry for interrupting.
•  » » » » » » 9 months ago, # ^ |   +1 Don't be sorry :-)If the graph is undirected, the edges of a leaf in the DFS tree can only be ancestors : - if an edge were to a previously visited branch, because edges are bidirectionnal then the DFS would have visited our leaf in that previous branch too. - if an edge is to a not-yet-visited branch, then the DFS would visit it from our leaf (which wouldn't be a leaf anymore).
 » 9 months ago, # |   +13 Good editorial but I don't understand here about DIV1 D, why M<=12000? I mean is it the final number that has counted m times for every vector? My answer for the number of vectors (upper bound) is here:m upper bound1 392 4693 23694 67345 108086 115987 78158 34629 89510 11011 4
•  » » 9 months ago, # ^ |   0 Calculations seem correct, but M goes without multiplying by m, so, we can also say that M<=11598
 » 9 months ago, # |   0 Why at Div2 D the pairs are powers of two?
•  » » 9 months ago, # ^ |   0 bcoz we want to find first x for which x % a > 2x%a , after that we can stop and claim that a will lie in the range of (x , 2x] . in simple words , a*1 =a and a*2 = 2a so we have to check within the limits of [x,2x] for each pair .
 » 9 months ago, # |   +102 I'm sorry, but the editorial for E is terrible. Anyone care to rewrite the editorial for E so that it is understandable also to people that do not already know the solution?I have a solution based on FFT/NTT, but it is obviously too slow.In particular: it is pretty clear that you should apply something like Hadamard transform No, it isn't clear. Why and how? How does the transformation matrix look like and how do you compute it fast enough? How do you use it afterwards? The main idea is that you should calculate all values in a polynomial ring modulo x10−1 ... What is x and how do I incorporate it into the transform? ... then we simply divide the answer by 25 with integer division, it can be easily shown that the result will be correct. If it can be easily shown, please show it. It is worth noting that after inverse transform you should eliminate monomes larger than x4 by ... How does it help to get rid of these? Also, you probably mean larger or equal to x4, right? After that only the coefficient with x0 remains. You just said that you eliminate monomes larger than x4. What happens to x1 through x3. Do they disappear? Why?
•  » » 9 months ago, # ^ |   +81 I apologize that the editorial was not well-written. Consider a problem: given a set of numbers, for each i find the number of pairs with XOR equal to i. It can be easily solved, but there is also trivial solution with Hadamard transform(actually xor-convolution). Let's apply xor-convolution (Link, 15-th paragraph), then square each element of the array and apply inverse convolution, voila, here the answer is. I thought this convolution was well-known. Our problem looks similar, the idea is just to do 5-dimensional FFT(a dimension for each digit). In FFT we just substitute polynomial's coefficients with its values at roots of one, so let's do it. X is a variable. We operate in polynomial ring. It contains polynomials, which have variables, only one in our case. OK, let's prove it. Suppose the answer to the problem is x, so we know (x*2^5) mod 2^64 (let's call it y) and want to obtain x mod 2^58. x*2^4 mod 2^64 is either y/2 (here all divisions will be integer) or y/2+2^63. Obviously, this numbers are equal modulo 2^63, so (x*2^4 mod 2^63)=(x*2^5 mod 2^64)/2. Similarly (x*2^3 mod 2^62)=(x*2^4 mod 2^63)/2 and so on. x^4-x^3+x^2-x^1+x^0=0 => x^5-x^4+x^3-x^2+x^1=0, x^6-x^5+x^4-x^3+x^2=0, ... Let's apply it to eliminate x^9, then x^8, ..., then x^4 (yes, in the end we will have only four coefficients x^0,x^1,x^2,x^3, my bad) Well, I didn't want to make the editorial complicated, so I've omitted this. They will disappear as it was said. It is pretty intuitive(for us at least, because basically it is just FFT over another ring), but for formal proof we need some algebra. x^4-x^3+x^2-x^1+1 is a cyclotomic polynomial, so by definition it is irreducible (and corresponding ideal is prime). So, quotient ring modulo this ideal is integral domain. I will finish the proof later, maybe, but you get the point.
•  » » » 9 months ago, # ^ |   +1 Thanks for the reply and clarification! I still don't understand it, but I not understand it less than before. I mean I understand the solution, but I don't understand how I should come up with it :) I knew the idea you mention, but apparently not well enough so it didn't click. You don't have 10th root, so you used magic and algebra to make one, got it. Nice. That was clear to me. The question I had here you answered in 5. :) In Solution 1, you use a ring modulo x5 + 1 instead of x10 - 1, presumably just to make the solution 4 times faster. Failing to notice that, along with the fact that  - x4 was the inverse of x, was the main source of confusion. Also, the function smfft doesn't do FFT, but "only" DFT :)
•  » » » » 9 months ago, # ^ |   +10 Yeah, sorry for that, I didn't think I will publish author solution. To come up with this idea, you might think: "Everything we need is a ring with 10-th root of one. We know one similar ring, complex numbers (i is the 4-th root of one). So let's just make our own ring, where x is the 10-th root. Then each number in this ring has a form of a_0*x^0+a_1*x_1+...+a_9*x^9". It is actually polynomial ring, but it doesn't matter. Then you somehow (I did it after writing the solution) realise that you get the answer quite not as you was expecting and you should eliminate large powers of x (for example x^7=-x^2). You come up with identity x^4-x^3+x^2-x^1+x^0=0 and actually solve the problem.
•  » » » » 9 months ago, # ^ | ← Rev. 2 →   +10 (The followings are mostly equivalent to scanhex's explanation in some sense. I just want to share how I came up with the solution. Some details, such as why DFT is used, how to divide 10 in the final step, are skipped since they are exactly the same as scanhex's explanation.)I used the ring modulo x5 - 1. It is more natural to me. Actually, no polynomial rings appeared in my mind before I attempted to proof my solution after getting AC.According to Wikipedia, we need a principal root of unity in which has the exact same role with in . We can easily see that  - 1 is a principal root of unity. In order to convert this root from order 2 to order 10, I extended the ring to include ω5 and thus  - ω5 becomes a valid candidate. Then the ring is now extended to to preserve the closure of addition and multiplication. For implementation, we only need to store those a0, a1, ..., a4. In fact, 1 + ω5 + ... + ω54 = 0 (which is also required by the definition of principal root of unity). It is sufficient to store 4 of those coefficients but this increases the complexity of the DFT so I simply stored all of the 5 coefficients.Originally, I thought the final answer is a0 in each corresponding entry after the inverse DFT, which is incorrect. In the debugging process, I found that a1 = a2 = a3 = a4 after the inverse DFT. Then I used a0 - a1 as the final answer and got AC.The last step is correct since 1 + ω5 + ... + ω54 = 0 implies a0 + a1ω5 + ... + a4ω54 = (a0 - a1) + (a2 - a1)ω52 + (a3 - a1)ω53 + (a4 - a1)ω54. ω5 is a root of the polynomial , which is irreducible over . The degree of the polynomial is 4 so the above representation with 4 coefficients is unique. Then implies a2 - a1 = a3 - a1 = a4 - a1 = 0.As a side note, the first idea in my mind is changing the input numbers to base 19 without changing the digits, i.e. . Then we can use 1D FFT with fast exponentiation and handle the modular operation on each digit ourselves between each FFT. However, the constant factor, 1.95 is too large and the modular base 258 is not friendly.
•  » » » » » 9 months ago, # ^ |   -31 is it a codeforces round or problems from international mathematics olympiadd , so complexx maths !
•  » » » » » 9 months ago, # ^ |   +8 Thanks for adding your view!I had the exact same idea with base 19, but not only you get the 1.95 factor for the base, you also get two factors (one for NTT and second for binary exponentiation). And on top of that you need CRT with four moduli.
•  » » » » » » 9 months ago, # ^ | ← Rev. 3 →   0 I feel that all the explanations about killing x5 in the last step are mysterious and vague. So I am trying to describe my own.The (extended) ring we actually used is . It's clear that is the 10-th primitive root. As R is a subring of , we can do the intermediate computation in R' to save a time factor of 5. My biggest confusion is why the ring does not work. It turns out that to be used in the DFT as the primitive root, should hold along with x10 = 1.
•  » » » 9 months ago, # ^ |   0 Please explain the approach of Game with stringThank you
 » 9 months ago, # |   0 can someone help me with my solution of problem c , i am getting "wrong output format Unexpected end of file — int32 expected" on test case 14 , here is the solution to my link https://codeforces.com/contest/1104/submission/48794438
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 See, this is the same approach I applied which works for small length strings. Basically , you cannot guarantee of a solution using this approach and this is the reason for Wrong Answer. In your matrix after few insertions there will be a state which cannot accommodate horizontal tile.1 T F T F T T T F F T F T F T F TThis will be the condition of matrix which cannot accommodate the tile.
•  » » » 9 months ago, # ^ |   0 thanks buddy for the help, by the way how you were able to conclude this bug in this approach
•  » » » » 9 months ago, # ^ | ← Rev. 2 →   0 Length of string in 14 Test Case is 999. So just add a Constraint to your code to see if it print answer of every index and if not then print the boolean array. Remember not to print required answer in case if length of string is 999 Cheers :P
•  » » » » » 9 months ago, # ^ |   0 thanks for the help again :)
 » 9 months ago, # |   0 Could you someone post a solution in Java of the problem D? Thank you.
•  » » 9 months ago, # ^ |   0 Never mind. How come I cannot delete my own comments?
•  » » » 9 months ago, # ^ |   0 HAHAHA
 » 9 months ago, # | ← Rev. 2 →   +10 Few doubts in problem DIV2 E — 1) Obviously, we have three cycles here: path from x to v with corresponding back edge, the same cycle from y to v. Why it will be always the same cycle from y to v and not a different cycle? 2) Lengths of these cycles are d(v,x)+1, d(v,y)+1 and d(x,y)+2, where d(a,b) — distance between vertices a and b. It's clear that one of these numbers is not divisible by three. Why one of them will not be divisible by 3? Still I am having these doubts, anyone please help.
•  » » 9 months ago, # ^ |   0 Suppose d(v,x) + 1 and d(v,y) + 1 are divisible by 3 and d(v,y) > d(v,x). d(x,y) = d(v,y) — d(v,x) = (d(v,y) + 1) — (d(v,x) + 1) is divisible by 3 too. Hence, d(x,y) + 2 is not divisible by 3."Why it will be always the same cycle from y to v and not a different cycle". It differs, but has the same form (path with the back edge).
•  » » » 9 months ago, # ^ |   0 I am not sure how you got this formula — d(x,y) = d(v,y) — d(v,x) Please tell if I am making some basic mistake.
 » 9 months ago, # |   0 Why we have taken power of 2 in problem D (game with modulo) ,I mean how that would click to someone ,Is there any mathematical reasoning behind it? Please help me ...
•  » » 9 months ago, # ^ |   0 It seems that binary search could be useful in this problem.Lets assume that x=a and y=2a and the number must lie between x+1-y.If that's the case then number can easily be found using bin search.So we have to find out such x,y.That's why we took power of 2.First we checked 1 and 2.If 1 or 2 is not the ans then the answer is elsewhere .U know we are doing binary search.So why not use power of 2?
 » 9 months ago, # |   0 In problem D, O(M⋅2^m⋅m+m^2⋅4^m) is accepted,but how can we solve it in O(M⋅2^m⋅m+m^2⋅3^m) according to the editorial? Is it a typo or my mistake?
•  » » 9 months ago, # ^ |   +2 No, it's not. Maybe you have small mistake in complexity estimate, most of solutions have a component with iterating over all submask for an each particular mask which works in O(m2·3m). For example: Code
 » 9 months ago, # |   0 Can someone explain the approach of B. Game with string?
 » 4 months ago, # |   0 scanhex or any other person Can u please explain me the concept behind solving the game of string question more elaborately I am a noobie/amateur so thats why am having a bit of trouble understanding the solution given above in the tutorial
 » 3 months ago, # |   0 With reference to the editorial for problem B:It can be shown that the answer does not depend on the order of deletions.Can this fact be elaborated on?I tried a few cases but I'm unable to build an intuition for this. For ex., consider the string abcbbccbb. There are several places that you can start performing operations from, but no matter where you start, you will always end up with only 3 operations. I can't manage to prove this though. Any help would be very appreciated.