cgy4ever's blog

By cgy4ever, 9 years ago, In English

Hello, I'm the writer of SRM 651.

It turns out this round is unrated due to some system failure. Sorry about the inconvenience it caused. I hope Topcoder can improve their infrastructure soon so that can be as good as codeforces.

I will post the problem statement, reference solution and a short editorial here.

Welcome to discuss the tasks, as well as to give feedback about them!

Problem Statement: http://www.speedyshare.com/2kRaC/task.rar

Reference solution:

Div1-Easy: http://ideone.com/a9siv1

Div1-Medium: http://ideone.com/sbEZSH

Div1-Hard: http://ideone.com/9JXoSL

Div1-Easy: RobotOnMoon

Look at this example:

....
.S.#
....

There will be infinite long perfect safe sequence, why? because we have "RRR...". That means if there is one '#' at any of the 4 direction of 'S', then the answer will be -1..

Then look at this example:

#.##
.S..
#.##
#.##

since there is only 1 cell to the left of 'S', there can be at most 1 'L' in any perfect safe sequence, otherwise if all characters other than 'L' are missing, it will lead the robot to die. So we can have a maximal bound of length of any perfect safe sequence: we have at most 1 'L', at most 2 'R', at most 1 'U' and at most 2 'D'. And we could find "LRRUDD" is perfectly safe: we have only 1 'L' so it is impossible to move outside the board from the left edge, etc.

So if the answer is not -1, then it must be n+m-2.

Div1-Medium: FoxConnection3

The key is notice that there can be few "shapes" of the result connected foxes. In fact if n = 6 there can be at most 216 of them: http://oeis.org/A001168

And then we should figure out which fox goes to which position in the final shape. There will be 6! ways.

Then we need to decide the position of our final shape.

After decide the position, we will calculate how many steps do we need to get it. It is simply the sum of length of shortest paths from s[i] to t[i] where s[i] is the start position of fox[i] and t[i] is the end position of fox[i], because we can ignore "there cannot be two foxes in the same cell at the same time." by this way:

Suppose we want to move O to x in this situation:

.O..o...o.x.

There are 2 foxes block our way, but we can do this:

.o..o...o.x. -> .o..o.....o. -> .o......o.o. -> ....o...o.o.

The if we write down the equation, it will be something like abs(offsetX — u[0]) + ... + abs(offsetX — u[n-1]) + abs(offsetY — v[0]) + ... + abs(offsetY — v[n-1]). We can find we should set offsetX = middle number of u[] and offsetY = middle number of v[].

Div1-Hard: FoxAndSouvenir

It will be quite easy to get a solution run in O(n^4) for each query, a classic DP:

dp[i] = how may ways to get exactly i dollar.

initially we have dp[i] = {1, 0, 0, ...}

For each souvenir of price p, we update new_dp[i] = dp[i] + (i-p>=0 ? dp[i-p] : 0).

So how to improve this? One observation is that this kind of dp can be write into convolutions:

for example, new_dp[i] = dp[i] x {1, 0, 0, ..., 1, 0, .., 0}.

Then one possible improvement is FFT with 2D segment tree, but it will need O(n^4 (logn)^4) which is too slow.

Another observation is that, we shouldn't do lots of FFT to merge segments again and again, for example, the answer will be {1, 0, .. , 1, 0, ..} x {1, 0, .. , 1, 0, ..} x {1, 0, .. , 1, 0, ..} ... We should first transform all of them into frequence domain, do the pointwise product of all of them. then transform back the result into time domain.

The last observation is it: we can transform {1, 0, .. , 1, 0, ..} into frequence domain in O(n) by bruteforce instead of O(n logn) by FFT, because we only have 2 non-zero values. And we just need one point value in time domain, so we can get it by brutefoce in O(n) instead of paying O(n logn) to reconver all elements in time domain.

So the solution looks like: preprocoss s[i][j][k] — the pointwise product of index k in frequence domain of the subrectangle [0, 0] — [i, j]. Then for one query we can find the frequence domain value of index k by calculate s[xMax][yMax][k] * s[xMin-1][yMax][k]^(-1) * s[xMax][yMin-1][k]^(-1) * s[xMin-1][yMin-1][k].

We should do the DFT over GF(1000000009). And we can avoid 0s in s[i][j][k] by use a length of an odd number. There are lots of divisors of 1000000008, we can choose 3507, the smallest odd divisor that is no less than 2500.

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

| Write comment?
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Forgive me for my very noobish question but my initial thoughts about Div1 Medium was to ternary search on X-coordinate separately and Y-coordinate separately and get the answer.

Why does this not work?

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think this could work. :)

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
      • »
        »
        »
        »
        9 years ago, # ^ |
        Rev. 2   Vote: I like it +8 Vote: I do not like it

        Oh, sorry, it can't work because we have a[i]=a[i+1] for some i, so we can't use ternary search. The a[] may look like {..,9,8,7,6,5,4,4,4,4,4,4,5,6,7,8,9,...}.

        For example you can't find the '1' in '000000001000000000000' by ternary search (if so that would be too crazy, right?).

        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh yeah, crap.

          P.S: you mean to say "you can't find the '1'...." right?

          Thanks a lot for the help. :)

        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I believe there's a difference between 9,8,7,6,5,4,4,4,4,4,4,5,6,7,8,9 and 000000001000000000000. Since in our case only minimum can occur multiple times it seems everything will work. My code using this idea passes my tests, I only doubt if it runs fast enough.

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

        I believe that the ternary search on X and Y is correct, but your solution doesn't seem to account for the hexaminoes portion at all. That is, it has the foxes all converge on the same square, instead of forming a connected hexamino. For example, in the test where all the foxes are in a line (already connected), the answer is 0, but you give 9, which is what would be expected if the foxes all had to touch the same square (then the distance is 2+1+0+1+2+3 = 9).

        UPD: Ah, as CGY said, the ternary search might be wrong as well. But I believe the main issue is the hexaminoes thing (I tried a complicated sort of grid search, and was able to pass all of the provided tests, except my hexamino search TLE'd because I was doing it in a stupid way).

        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes, this is one more detail I totally screwed up. Thanks :)

        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Ternary search has been shown to be wrong by CGY but I feel that the bitonic nature of the problem should be possible to use somehow. :(

          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
            Rev. 2   Vote: I like it +5 Vote: I do not like it

            No problem!

            The way I searched was to cut the grid into 64 squares, test the center of each square, and recurse on the best square (making the grid half as large, i.e. 4 by 4 squares, in order to give me a little room for error). This seemed to work on all of the problem statement's test cases (I was able to get the correct answers on my machine, and the grid search was always very fast, but my hexamino portion TLE'd as I mentioned).

            EDIT: Oh, I forgot to mention: once this grid search returned a cell, I would try to place the hexamino anywhere in a 20x20 grid surrounding the cell, to account for small amounts of error.

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

            Oh, in fact you can, because we only have a[i]=a[i+1] when we get maximal values.

            You should write something like:

            while(R-L>1)
            {
            	M1 = (L*2+R)/3;
            	M2 = (L+R*2)/3;
            	if(f(M1) > f(M2))
            		R = M2;
            	else
            		L = M1;
            }
            
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you also upload tests? It's not clear when practice rooms will be up.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is hard to do that.

    We don't have an "export to text" function in the system.

    You can test your solution by run random data and compare result with the reference solution. (For Div1-Hard, if you pass the last sample and don't get TLE for maximal data then it has high probability to be correct, and for Div1-Med, random tests should work.)

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

      Hmm, is sample #5 for 1100 right? It looks like this:

      int n = 1;
      int m = 1;
      int[] price = new int[] { 0 };
      int[] xMin = new int[] { 0 };
      int[] xMax = new int[] { 0 };
      int[] yMin = new int[] { 0 };
      int[] yMax = new int[] { 0 };
      int[] require = new int[] { 1 };
      
      int[] expected = new int[] { 1 };
      

      but I think that actually answer is 0.

      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I checked my samples, require is {0} in them. Do you really see {1}?

        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yep, sorry, it was either a plugin bug or me editing this test case when I was debugging.

»
9 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Does the idea of problems design of Div.1 hard come from New Year Shopping?

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    No, in fact I get that idea when I find the tree DP in 512D - Лиса и путешествие could be optimized to O(n^2) by DFT. (of course we didn't use that version in Round #290, the implementation is much more harder than today's Hard)

    rng_58 told me we can use the same algoritm in New Year Shopping to solve 1D version of today's Div1 Hard in O(n^2 logn). But that solution couldn't work for 2D.

»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Could you do a DIV 2 tutorial ?

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

    Div2-Easy: http://ideone.com/V1lc7O

    First we find the position of 'S', then simulate it step by step.

    Div2-Medium: http://ideone.com/uFdGNl

    DP[i][j] := can we get a total of i dollar by buying j item?

    Div2-Hard: http://ideone.com/TLoazT

    First search all shapes (fixed polyominoes) of size k. Then try to place them on the board by try all offsets of x and y.

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you please add some more details to the explanation of Div-2 Hard? More specifically, how to generate all the polyominoes of size 8 ? Through backtracking?

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why do zeroes disappear when we use odd length?

  • »
    »
    9 years ago, # ^ |
    Rev. 3   Vote: I like it +8 Vote: I do not like it

    DFT({1,0,0,...,1,0,0,...}) = {1+r^(0*t), 1+r^(1*t), 1+r^(2*t), ...} where r^N = 1 mod 10^9+9, and t is the index of 1.

    If N is even then we have r^(N/2) = -1 mod 10^9+9 that means we may get a zero at somewhere.

    But if N is odd then there is no e such that r^e = -1.

    You can also deal with zeros like this: we calculate both the product of non-zero values, and the number of zeros in rectangles from (0,0). By this way we can still calculate products of any subrectangle.

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

      Thanks, this is such a wonderful problem, I would never imagine DFT can be useful without FFT.

»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I really like the theory behind the hard problem, though I'm not too familiar with number theory so I'm not sure how you would choose the constants.

Can someone elaborate on the number theory aspects of this problem? (i.e. looking over the code, it seems we chose "13" and "3507", and I would like to know the reasoning behind that). Thanks in advance.

»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

On Div1 Medium: "Then we need to decide the position of our final shape."

Can anyone give me a hint on this step?

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Tried to upsolve SRM 651 Div1-hard. Get following result for test 6 for solution in c++. http://paste.ubuntu.com/10550162/

Then copied bad test to test-code of kawigi.Edit, and no problem was found. My code with tests: http://paste.ubuntu.com/10550152/

Could you please explain what is the problem? Is there another bug in my code or bug in topcoder checker? It seems strange that in verdict there was no RE and that I did not return any vector as answer in this case.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I've got the same. And I think that the problems is on server side.