How to solve B, H, K?
# | User | Rating |
---|---|---|
1 | jiangly | 3977 |
2 | tourist | 3815 |
3 | jqdai0815 | 3682 |
4 | ksun48 | 3614 |
5 | orzdevinwang | 3526 |
6 | ecnerwala | 3514 |
7 | Benq | 3483 |
8 | hos.lyric | 3381 |
9 | gamegame | 3374 |
10 | heuristica | 3358 |
# | User | Contrib. |
---|---|---|
1 | cry | 170 |
2 | -is-this-fft- | 162 |
3 | Um_nik | 161 |
4 | atcoder_official | 159 |
5 | djm03178 | 157 |
6 | Dominater069 | 156 |
7 | adamant | 154 |
8 | luogu_official | 152 |
8 | awoo | 152 |
10 | TheScrasse | 148 |
How to solve B, H, K?
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(√n) will time out xd
We passed by factorizing n in O(√n) and then backtracking over all divisors of n2.
D is just as you said. It doesn't time out.
We have a3+b3=(a+b)(a2−ab+b2) so (a+b) has to divide n2. Get divisors of n, then loop possible a+b that divide n2 and are at most 2⋅106. 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?
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...
Only loosely related, but can somebody explain to me how changing the type of the board in E from
vector<vector<bool>>
tovector<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 k0,k1,k2,…,kt.
Then, for every i=0,…,t−2, copy ki times, merge ki−1 times, then swap if ki>1 and roll. After the ith operation, you have i+1 strings corresponding to the first ∑j≤ikj 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=(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(P−2),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
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.
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