### DomiKo's blog

By DomiKo, history, 4 years ago,

Grand Prix of North America is over...Let's discuss solutions. How to solve A and J?

• +33

 » 4 years ago, # |   +84 WTF? There was nothing in the schedule yesterday.
•  » » 4 years ago, # ^ | ← Rev. 3 →   +5 Interestingly enough, though the schedule wasn't updated, the left column on opencup.ru showed "GP of America" as of yesterday.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Last week I actually asked Snark about whether there would be Gp of America these weeks and he gave me a positive answer. Then I check the schedule multiple times but found nothing about Gp of America until I noticed Snark has made a comment under xiaowuc1 's blog about NAC2020 yesterday.
 » 4 years ago, # |   0 A:Calculate number of sequences $p_1, p_2, \ldots, p_m$, $p_i \le k$ such that $GCD(p_1, p_2, \ldots, p_m) = 1$ (or all elements are equal to $0$).We can calculate this with $dp$. $dp[k] = (2 \cdot k + 1) ^ m - (\sum_{i = 1}^{k}dp[\frac{k}{i}]$) — 1. At the end we have to add $1$ to result (case with all elements equal to $0$).It is $\mathcal{O}(k^2)$, but we don't have to calculate all states — if we calculate only states we need to know (with recurrence) we can achieve $\mathcal{O}(k \log k)$. It was enough to solve this problem.
•  » » 4 years ago, # ^ |   0 What is denoted by a single sequence $p$?
•  » » » 4 years ago, # ^ |   0 possible values that are returned on the measurement (in number of coins). You are interested only if gcd=1 because (2,2,2) is not distinguishable from (1, 1,1). Note that they are actually from -k to k
•  » » 4 years ago, # ^ |   0 I do understand why it's an upper bound for the answer. Can you show that it's also a lower bound?
•  » » » 4 years ago, # ^ |   +6 The set we built is equal to itself multiplied by -1, so the sum in every coordinate is zero, which is necessary and sufficient.
•  » » » 4 years ago, # ^ |   +10 In $i$-th weighting, for each sequence we can put $p_i$ coins on the left side of scale if $p_i > 0$ and $-p_i$ coins on the right side if $p_i < 0$.Now consider sequence of results for weightings as $a_1, a_2, \ldots, a_m$. For conveniece we can assume $a_i \ge 0$. Let's denote $x$ as a difference of weight between one false coin and one normal coin.If $a_1 = a_2 = \dots = a_m = 0$ then we know that only sequence $p_1 = p_2 = \ldots = p_m = 0$ satisfy requirements.Otherwise there exists $a_i > 0$. Let's assume we know that $a_i = t \cdot x$ for some integer $t$ between $1$ and $k$. Then we can uniquely determine answer. But because we picked only sequences with $GCD$ equal to $1$ then we can iterate over all possible $t$ and pick the smallest one for which all $\frac{a_i}{x}$ are integers — this is answer to our problem.
•  » » 4 years ago, # ^ |   +10 To make code a bit easier: Möbius function
 » 4 years ago, # |   +8 How to solve G?
•  » » 4 years ago, # ^ |   +8 Binary search, then iterate over classical problems in order of decreasing difficulty and try to chose max.possible creative one
•  » » 4 years ago, # ^ |   0 Binary search for answer. For fixed classical problems, a set of pairable problems form an interval over a difficulty. In such kind of graph, you can calculate the maximum matching with greedy.
 » 4 years ago, # |   0 How to solve D? We guessed the formula but don't know how to prove it. Formula$\prod_{i=1}^n (t - (a_i + a_{i+1} + \cdots + a_n) + (i = 1 ? 1 : n-i+2))$
 » 4 years ago, # | ← Rev. 2 →   +15 We can find the video solution here YouTube.btw, how did you guys prevent J from TLE? I basically used map and got TLE. Maybe I should compress it to longlong.
•  » » 4 years ago, # ^ |   0 On all test I could build with too many states answer is n. So just stop when any answer of n is reached.
•  » » 4 years ago, # ^ |   0 I built a trie over all the partitions of [n] (slightly pruned, I did not have an out-edge for the value $1$, hence the internal nodes also represented a partition) and assigned each node a value, this made for a fast partition-hash function. For transitions, I just generated new partitions with minimal optimization. Whole thing ran in 4 out of 8 sec.
•  » » » 4 years ago, # ^ |   0 Buiding a trie is a very smart move. I think in this case, we should try our best to prevent using STL stuffs.I also made my program quit when the answer reaches N and it got stuck in Test 24.
 » 4 years ago, # |   +17 All the solutions are here.