Qingyu's blog

XXI Open Cup GP of Ural
By Qingyu, history, 4 years ago, In English

How to solve B, H, K?

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

Comments Comments (13)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

Are we still in 20th century so that all tasks got ML=64MB? That caused me some problems in E and J :/

How to solve D? I got some ideas, but my local tests showed that even the simplest loop finding divisors of $$$n$$$ in $$$O(\sqrt{n})$$$ will time out xd

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

    We passed by factorizing $$$n$$$ in $$$\mathcal O\left (\sqrt n\right)$$$ and then backtracking over all divisors of $$$n^2$$$.

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

    D is just as you said. It doesn't time out.

    We have $$$a^3 + b^3 = (a + b)(a^2 - ab + b^2)$$$ so $$$(a + b)$$$ has to divide $$$n^2$$$. Get divisors of $$$n$$$, then loop possible $$$a + b$$$ that divide $$$n^2$$$ and are at most $$$2 \cdot 10^6$$$. With fixed $$$a + b$$$ you have a formula for $$$a$$$ and $$$b$$$. The formula involves taking a square root but binary search was fast enough for that.

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

      Well, that's almost exactly what I did... Could you share your code?

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

    Hehehe, I changed finding divisors of n from loop from 1 to $$$\sqrt{n}$$$ to dividing $$$n$$$ by primes I find on the fly and it passed :|... Tbh that kinda makes sense, because that part becomes much faster for highly composite numbers, while the second part is fast for not highly composite numbers, but it still sucks...

    → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Only loosely related, but can somebody explain to me how changing the type of the board in E from vector<vector<bool>> to vector<vector<int16_t>> could have changed my MLE to OK?

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

B: If the string starts with a 'a', start with a swap. Now, assume the string starts with a 'b'.

If the string is all 'b', just copy $$$n-1$$$ times and merge $$$n$$$ times.

Otherwise, get lengths of continuous segments of the same letter, say these are $$$k_0, k_1, k_2, \dots, k_t$$$.

Then, for every $$$i = 0, \dots, t - 2$$$, copy $$$k_i$$$ times, merge $$$k_i - 1$$$ times, then swap if $$$k_i > 1$$$ and roll. After the $$$i$$$th operation, you have $$$i+1$$$ strings corresponding to the first $$$\sum_{j \leq i} k_j$$$ symbols at the start, and then a b or b a depending on the parity of i at the end.

For the last two $$$i$$$ you do one copy less. For $$$i = t-1$$$ you swap instead of swap and roll, and for $$$i = t$$$ you neither swap nor roll. Then in the end, merge until only one string is left.

This does around $$$3n - 2$$$ operations.

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

Is there an elegant solution to K? I don't have one so I'll leave my ugly approach instead.

Let's find a large cycle on the first board, and let $$$C=(C_1,C_2,\cdots,C_K)$$$ be this cycle. Then what we want next is a set of $$$K$$$ disjoint paths $$$P_1,P_2,\cdots,P_K$$$, where $$$P_{i,1}=C_i$$$ and union of these paths is precisely the set of cells on the first board. If we have such paths, the answer would be $$$P_1,second(rev(P_1)),second(P_2),rev(P-2),P_3,\cdots$$$. Here, $$$rev(P)$$$ means a reversed path and $$$second(P)$$$ means a path on the second board using the same positions.

How to get $$$C$$$: I repeated a certain pattern on the anti diagonal, which results in a cycle of length $$$O(N)$$$.

How to get $$$P_i$$$: I just run a DFS. When I choose the next vertex, I picked one with the minimum degree. Ties are broken randomly.

This algorithm sometimes succeeds, and sometimes fails because of randomness. Therefore I run several times to get a solution. In the worst case the running time didn't fit in the TL, so I pre-calculated for all $$$N$$$ a good seed which result in a solution.

My code

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

    Our solution was pretty straightforward and easy to prove. It's similar to the proof for the existence of a normal knight's tour.

    First, divide the square into blocks of size $$$4 \times 4$$$, $$$4 \times 6$$$, and $$$6 \times 6$$$ (possibly missing a corner). Then, we'll first compute a Hamiltonian cycle for each shape of block, and then try to join them together. The simplest way to join the cycles of 2 neighboring blocks is to find 2 portal edges which are a knight's move apart, and then swap them to 2 knight's move edges instead. To facilitate this, we picked a solution for each block size with many portal edges. That's actually pretty simple: we just ordered portal edges first and ran a recursive backtracking search; the results have more than enough portal edges for this construction.

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

    so I pre-calculated for all N a good seed which result in a solution maroonrk orz

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

How to solve the problem I? I tried but failed qwq

→ Reply