How to solve B, H, K?

# | User | Rating |
---|---|---|

1 | Radewoosh | 3707 |

2 | Benq | 3691 |

3 | tourist | 3669 |

4 | ecnerwala | 3565 |

5 | Um_nik | 3533 |

6 | ksun48 | 3489 |

7 | maroonrk | 3457 |

7 | jiangly | 3457 |

9 | Petr | 3370 |

10 | scott_wu | 3350 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 208 |

2 | awoo | 187 |

3 | rng_58 | 184 |

4 | Errichto | 182 |

5 | SecondThread | 178 |

6 | Radewoosh | 177 |

7 | -is-this-fft- | 176 |

7 | maroonrk | 176 |

9 | Um_nik | 173 |

10 | antontrygubO_o | 170 |

How to solve B, H, K?

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/14/2021 20:29:07 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

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

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.

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

codeHehehe, 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...

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?https://stackoverflow.com/questions/15809157/why-is-the-size-of-stdvectorbool-16-byte

https://stackoverflow.com/questions/31523118/memory-allocation-of-c-vectorbool

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.

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

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.

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

maroonrk orzHow to solve the problem I? I tried but failed qwq