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

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

1 | tourist | 3843 |

2 | jiangly | 3705 |

3 | Benq | 3628 |

4 | orzdevinwang | 3571 |

5 | Geothermal | 3569 |

5 | cnnfls_csy | 3569 |

7 | jqdai0815 | 3530 |

8 | ecnerwala | 3499 |

9 | gyh20 | 3447 |

10 | Rebelz | 3409 |

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

1 | maomao90 | 171 |

2 | adamant | 163 |

2 | awoo | 163 |

4 | TheScrasse | 157 |

5 | nor | 153 |

6 | maroonrk | 152 |

6 | -is-this-fft- | 152 |

8 | Petr | 145 |

9 | orz | 144 |

9 | pajenegod | 144 |

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

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/17/2024 19:04:43 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

WTF? There was nothing in the schedule yesterday.

Interestingly enough, though the schedule wasn't updated, the left column on opencup.ru showed "GP of America" as of yesterday.

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.

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.

What is denoted by a single sequence $$$p$$$?

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

I do understand why it's an upper bound for the answer. Can you show that it's also a lower bound?

The set we built is equal to itself multiplied by -1, so the sum in every coordinate is zero, which is necessary and sufficient.

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.

To make code a bit easier: Möbius function

How to solve G?

Binary search, then iterate over classical problems in order of decreasing difficulty and try to chose max.possible creative one

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.

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))$$$

We can find the video solution here YouTube.

btw, how did you guys prevent J from TLE? I basically used map<vector,int> and got TLE. Maybe I should compress it to longlong.

On all test I could build with too many states answer is n. So just stop when any answer of n is reached.

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.

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.

All the solutions are here.