### scanhex's blog

By scanhex, history, 5 years 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

| Write comment?
 » 5 years ago, # |   -38 Thanks for fast editorial
 » 5 years ago, # | ← Rev. 2 →   0 in div2 E , i understand spanning tree , but what you mean by dfs spanning tree , what dfs means here ?
•  » » 5 years 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).
•  » » » 5 years ago, # ^ |   0 gprano , but in a graph there can be multiple spanning trees , does dfs always gives us the spanning tree with largest depth ?
•  » » » » 5 years 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)
•  » » » » » 5 years 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.
•  » » » » » » 5 years 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).
•  » » » » » » 4 years ago, # ^ |   0 Well simply ; its because the degree of each vertex is atleast 3 ( described in the problem statement )And a node when discovered in the dfs tree would be discovered by one of the edges. Now if degree is atleast 3 ; and 1 edge is wasted to discover the vertex ; where would the other 2 edges go ?They will be connected to some ancestor ( As this node is a leaf and does not have any descendants )And an edge from a node to ancestor — These are the back edges ( At least 2 ) !
 » 5 years 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
•  » » 5 years ago, # ^ |   0 Calculations seem correct, but M goes without multiplying by m, so, we can also say that M<=11598
 » 5 years ago, # |   0 Why at Div2 D the pairs are powers of two?
•  » » 4 years ago, # ^ |   0 If we use power of 2: For the pair [x, 2*x], if a > x and a <= 2*x, I can show you that x % a must be larger than x * 2 % a. Because a >= x and a <= 2*x, 2*x mod a <= 2*x - a < x. If we chose other number, we can hardly get this feature.
•  » » » 10 months ago, # ^ |   0 in fact, 2*x mod a = 2*x - a < x
 » 5 years 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?
•  » » 5 years 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.
•  » » » 5 years 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 :)
•  » » » » 5 years 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.
•  » » » » 5 years 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.
•  » » » » » 5 years 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.
•  » » » » » » 5 years 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.
•  » » » 5 years ago, # ^ |   0 Please explain the approach of Game with stringThank you
•  » » » 4 years ago, # ^ |   0 Can you finish the proof? I can get the point about irreducible, but even in that case there's still $2^{32} \times 2^{32} = 0$.
•  » » » » 4 years ago, # ^ |   0 Oh, I think I can answer your question. Forget about modulo for a moment and just think that we store real values. The solution will work, except precision issues as numbers will be large. Now, let's just calculate everything modulo 2^64 instead. We can always take any algorithm and do every operation modulo 2^64, result will remain correct (as long as we don't divide by zero).
 » 5 years 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
•  » » 5 years 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.
•  » » » 5 years ago, # ^ |   0 thanks buddy for the help, by the way how you were able to conclude this bug in this approach
•  » » » » 5 years 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
 » 5 years 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.
•  » » 5 years 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).
•  » » » 5 years 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.
•  » » » » 4 years ago, # ^ |   0 If y and x both are ancestors of some vertex 'v' ; then y,x and v all form a chain. Draw this on a paper ( In order y , x , v ( As he says dis(y,v) > dis(x,v) ) ; and you will see how !
 » 5 years 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 ...
•  » » 5 years 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?
 » 5 years 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?
•  » » 5 years 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
 » 5 years ago, # |   0 Can someone explain the approach of B. Game with string?
 » 5 years 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.