### Qingyu's blog

By Qingyu, history, 3 years ago,

How to solve B, H, K?

• +59

| Write comment?
 » 3 years ago, # | ← Rev. 2 →   +18 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
•  » » 3 years ago, # ^ |   +39 We passed by factorizing $n$ in $\mathcal O\left (\sqrt n\right)$ and then backtracking over all divisors of $n^2$.
•  » » 3 years ago, # ^ |   0 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.
•  » » » 3 years ago, # ^ |   0 Well, that's almost exactly what I did... Could you share your code?
•  » » » » 3 years ago, # ^ |   0 code#include using namespace std; using ll = long long; const int H = 1e6; pair res; void recSolve(ll s, ll n, int i, const vector>& factors) { if (s >= 2*H) return; if (i == factors.size()) { ll sub = s*s*s - n*n; if (sub <= 0 || sub % (3*s) != 0) return; ll p = sub / (3*s); ll low = 0; ll high = s; while(low != high) { ll mid = (low + high) >> 1; if (mid*mid < s*s - 4*p) low = mid + 1; else high = mid; } ll a = s - low; ll b = s + low; if ((a <= 0) || (a & 1) || (b & 1)) return; a /= 2; b /= 2; if (a*a*a + b*b*b == n*n) res = {a, b}; } else { for (int j = 0; j <= factors[i].second; ++j) { recSolve(s, n, i+1, factors); s *= factors[i].first; } } } void solve(ll n) { res = {-1, -1}; ll tmp = n; vector> factors; for (ll x = 2; x*x <= tmp; ++x) { if (n % x == 0) { factors.emplace_back(x, 0); while(tmp % x == 0) { ++factors.back().second; tmp /= x; } factors.back().second *= 2; } } if (tmp > 1) factors.emplace_back(tmp, 2); recSolve(1, n, 0, factors); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int t; cin >> t; for (int ti = 0; ti < t; ++ti) { ll n; cin >> n; solve(n); if (res.first == -1) cout << "impossible\n"; else cout << res.first << ' ' << res.second << '\n'; } } 
•  » » 3 years ago, # ^ |   0 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...
 » 3 years ago, # | ← Rev. 3 →   0 Only loosely related, but can somebody explain to me how changing the type of the board in E from vector> to vector> could have changed my MLE to OK?
•  » » 3 years ago, # ^ | ← Rev. 3 →   +10
 » 3 years ago, # |   +20 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.
 » 3 years ago, # |   +20 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
•  » » 3 years ago, # ^ |   +13 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.
•  » » 3 years ago, # ^ |   +16 so I pre-calculated for all N a good seed which result in a solution maroonrk orz
 » 3 years ago, # |   +13 How to solve the problem I? I tried but failed qwq