Qingyu's blog

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

| 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(n) will time out xd

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

    We passed by factorizing n in O(n) and then backtracking over all divisors of n2.

  • »
    »
    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 a3+b3=(a+b)(a2ab+b2) so (a+b) has to divide n2. Get divisors of n, then loop possible a+b that divide n2 and are at most 2106. 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.

    • »
      »
      »
      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?

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        code
  • »
    »
    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 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...

»
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?

»
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 n1 times and merge n times.

Otherwise, get lengths of continuous segments of the same letter, say these are k0,k1,k2,,kt.

Then, for every i=0,,t2, copy ki times, merge ki1 times, then swap if ki>1 and roll. After the ith operation, you have i+1 strings corresponding to the first jikj 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=t1 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 3n2 operations.

»
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=(C1,C2,,CK) be this cycle. Then what we want next is a set of K disjoint paths P1,P2,,PK, where Pi,1=Ci and union of these paths is precisely the set of cells on the first board. If we have such paths, the answer would be P1,second(rev(P1)),second(P2),rev(P2),P3,. 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 Pi: 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

  • »
    »
    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×4, 4×6, and 6×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.

  • »
    »
    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

»
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