scanhex's blog

By scanhex, history, 4 weeks ago, In English,
Tutorial is loading...

Author: isaf27

Tutorial is loading...

Author: 300iq

Statements and editorial: scanhex

Tutorial is loading...

Author: scanhex

Solution

Tutorial is loading...

Author: isaf27

Tutorial is loading...

Author: altruist

Tutorial is loading...

Author: altruist

Tutorial is loading...

Author: scanhex

Solution 1

Solution 2

 
 
 
 
  • Vote: I like it  
  • +24
  • Vote: I do not like it  

»
4 weeks ago, # |
  Vote: I like it -38 Vote: I do not like it

Thanks for fast editorial

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

in div2 E , i understand spanning tree , but what you mean by dfs spanning tree , what dfs means here ?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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).

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      gprano , but in a graph there can be multiple spanning trees , does dfs always gives us the spanning tree with largest depth ?

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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)

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            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 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

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 bound

1 39

2 469

3 2369

4 6734

5 10808

6 11598

7 7815

8 3462

9 895

10 110

11 4

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Calculations seem correct, but M goes without multiplying by m, so, we can also say that M<=11598

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why at Div2 D the pairs are powers of two?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 .

»
4 weeks ago, # |
  Vote: I like it +102 Vote: I do not like it

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?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +81 Vote: I do not like it

    I apologize that the editorial was not well-written.

    1. 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.
    2. X is a variable. We operate in polynomial ring. It contains polynomials, which have variables, only one in our case.
    3. 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.
    4. 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)
    5. 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.
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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 :)

      1. I knew the idea you mention, but apparently not well enough so it didn't click.
      2. You don't have 10th root, so you used magic and algebra to make one, got it.
      3. Nice.
      4. 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 :)

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        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.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 2   Vote: I like it +10 Vote: I do not like it

        (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 - a152 + (a3 - a153 + (a4 - a154. ω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.

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it -31 Vote: I do not like it

          is it a codeforces round or problems from international mathematics olympiadd , so complexx maths !

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
            Rev. 3   Vote: I like it 0 Vote: I do not like it

            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.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Please explain the approach of Game with string

      Thank you

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 T

    This will be the condition of matrix which cannot accommodate the tile.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks buddy for the help, by the way how you were able to conclude this bug in this approach

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          thanks for the help again :)

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Could you someone post a solution in Java of the problem D? Thank you.

»
4 weeks ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

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.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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).

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ...

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the approach of B. Game with string?