voidmax's blog

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

Thanks for participating in my contest!

It was my first round, I hope you enjoyed.

Editorial:

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Vote: I like it  
  • +106
  • Vote: I do not like it  

»
3 months ago, # |
  Vote: I like it +60 Vote: I do not like it

I enjoy this contest very much. I hope I will see you as a problemsetter soon!

»
3 months ago, # |
Rev. 2   Vote: I like it +28 Vote: I do not like it

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

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

    maybe UB. try drmemory.

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

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

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

    Z contains only k elements, so you can calculate in complexity O(k)

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

can't understand "alternating sum " problem's solution . can anybody explain how it works. thanks.

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

    and solve the last line using summation of geometric progression

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

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

        my typo, sorry for that, it should be

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

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

          How to get these (b/a) values. You need to learn inverse modulo if you haven't learned already.

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

          trueglory How can I prove that the power is k ?

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

      Why am i getting a runtime error in testcase 9?

      http://codeforces.com/contest/964/submission/38454719

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Because you are dividing by zero

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

    the general thought is to use the peroidicity

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

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   Vote: I like it +11 Vote: I do not like it

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

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

Cannot understand the solution of `Cutting rectangle'... can anyone explain the tutorial for it in detail?

Thanks in advance!

  • »
    »
    3 months ago, # ^ |
    Rev. 6   Vote: I like it +34 Vote: I do not like it

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

      Thanks! a picture says more than thousands of words!

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

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

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

      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   Vote: I like it +3 Vote: I do not like it

      q = fastow(b * fastpow(a, MOD-2) % MOD, k)

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

        that's more aceptable to me as i confused from why %Mod-1 not %MOD

        all great thanks To you voidmax and panda_2134

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

      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<<ans*(po(q,(n+1)/k)-1)%MD; but i found answer: cout<<ans*po(q-1,MD-2)%MD*(po(q,(n+1)/k)-1)%MD; can you help me?!

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

So is that problem 963E a Markov chain?

»
3 months ago, # |
  Vote: I like it -13 Vote: I do not like it

Can anyone please provide useful resources for aho-corasick as i am new to this topic ???

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

"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   Vote: I like it 0 Vote: I do not like it

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

    So we can use only ones and twos.

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

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

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

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

    5 0 1 1 2 3 Have a try.

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

      My code is giving "NO" and I think no is the correct answer

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

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

In Div 2D/Div 1B, problem tag contains dp. i do not understand how dp is used here. can someone pls explain.