DomiKo's blog

XX Open Cup: GP of North America
By DomiKo, history, 5 years ago, In English

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

  • Vote: I like it
  • +33
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +84 Vote: I do not like it

WTF? There was nothing in the schedule yesterday.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it

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

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      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.

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    To make code a bit easier: Möbius function

    → Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve G?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D? We guessed the formula but don't know how to prove it.

Formula
→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
5 years ago, # |
  Vote: I like it +17 Vote: I do not like it

All the solutions are here.

→ Reply