rng_58's blog

GP of Ural
By rng_58, history, 5 years ago, In English

How to solve BCF (preferably in a proved way)?

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

»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

D: Is segmented ternary search the correct solution? I am getting WA10,so not sure if it's because my code is wrong or the approach is wrong

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

C: I permuted over the order of kings going to a new column. Other than that, I just made a valid move (either move current king in the order to a new column or just make other valid moves not clicking king)

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

    We got WA but passed with some additional random strategy. Not sure whether our first solution has some bugs.

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

    abistrigova used backtracking with memoization and restriction on iterations.

    → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

In B I bruteforced 3 of the strings which have fewest question marks, then in the last string if we know either first or last symbol, we can find the other one, the same for the second and second to last symbol and so on. It works in $$$2^{26}n$$$, but passes in 1 second.

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

    If we don't know the two ends?

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

      Bruteforce one of them.

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

    Brute force from both borders to middle, with checking s for which all is known works in $$$O(2^{3n/4})$$$, because one ? in first two lines can be found because of modulo 4 equation, and one in last two lines can be found.

    In fact, you don't need to find them, this only proves, that for each s, at least 1/4 of branches will be thrown away imidiatly.

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

    The same proved complexity but probably faster in practice (and works in 5 ms): Do a recursive brute in this order: first and last column first, then going inside, and checking that currently everything is ok.

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

I have solved F with the following solution:

Bruteforce width of the first column(there are only O(1e6) interesting widths). Then, measure the width of the second column with ternary search by the answer.

Not sure, if it is correct or not.

→ Reply
»
5 years ago, # |
  Vote: I like it +42 Vote: I do not like it

Why 64Mb in F?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

At first I've tried to solve B with MITM. But ML 64 MB was fighting against me. In the end I've solved it with local optimization.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve J?

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

    You can find with DP in $$$O(n \cdot 2^n)$$$ that the answer is a linear recurrence of order $$$8$$$. So you can solve it with Berlekamp-Massey.

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

    Let $$$f[S]$$$ be the possibility that you start from $$$0$$$ to state $$$S$$$, where $$$S$$$ is a $$$n$$$-bit integer. The state means you are now at $$$0$$$ and a position $$$k$$$ is visited if and only if $$$S_k=1$$$.

    For each state $$$S$$$, find the first and last $$$11$$$, and set all the bits between them to $$$1$$$.

    i.e.

    0010101011000110000110101 -> 0010101011111111111110101

    It is not hard to prove that the number of states is now acceptable.

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

    Solution from my team: run random simulation multiple times, print arithmetic mean of number of moves in all simulations.

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

      Don't you need $$$10^{18}$$$ simulations to get the required precision ($$$10^{-9}$$$)?

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

        No, only about 10^11 simulations are required. So we had like non-polynomial which passed around 30 tests, and the rest 20 tests we passed with such a precalculation. One test proceeds in about 1 minute on my PC.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          When we repeat simulations $$$10^{11}$$$ times and take the average, the standard deviation of the result is multiplied by $$$1 / sqrt(10^{11})$$$. So it's very strange that this is accurate enough.

          My output for $$$n = 50$$$ is 3.845878128958. What's yours?

          → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

I'm doubtful about the validity of test 8 of problem D. I checked if the given polygon was convex, and it failed. Could anybody responsible for the problem take an inspection?

→ Reply