the_art_of_war's blog

XVI Open Cup named after E.V. Pankratiev. GP of China.
By the_art_of_war, history, 9 years ago, In Russian

Пытался найти блог про гран-при, не нашел и решил создать сам. Предлагаю обсудить задачи здесь. Очень интересно решение задач B,F,G.

На счет задачи о шестеренках (N)

Представим наши шестеренки как вершины графа, проводим ребра если шестеренки касаются друг друга. Дальше запускаем бфс или дфс разницы нет. И проходим по всем шестеренкам, если в какой-то не были запускаем дфс от нее. Теперь главная проблема была в том, что радиусы могут быть до 10^4, а разница в скоростях двух смежных шестеренок пропорционально отношению их радиусов. Из-за этого по-видимому шло переполнение. Для того чтобы этого избежать я хранил отношение скоростей шестеренок, ни как одно число,а в виде массива всех простых чисел от 1 до 10^4 включительно.

вот код

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve J?

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

    Solved by Egor Chunaev ch_egor with Simulated annealing (Global optimisation)

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

    I don't know normal solution, but this AC.

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

    Solution by mmaxio: Erdős-Ginzburg-Ziv theorem says that set of size 2*n-1 for sum n is enough to be sure that subset with good sum exists; therefore one of possible solutions is to compress numbers to be able to solve naive knapsack, and then decompress result to get answer in terms of original problem.

    If you need to get 2016 and you have 6666 numbers — you can group all odd numbers in pairs and all even numbers in pairs (if some number don't have a pair — throw it away); now you need to get even sum, and in all pairs sum is also even, so you can divide everything by 2 and start solving problem where you need to get 1008 and there are at least 3332 numbers.

    Repeat it again to get 504... 252... 126... 63 :)

    Now you need to get sum divisible by 63 with a set of ~200 numbers. EGZ theorem says it is always possible, so you can solve a straightforward knapsack, get some result and decompress it (because right now every your "number" means 32 numbers of original array).

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

      Or we can do bruteforce and solve for 3 (twice) and for 7.

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

    Explanation in Russian. For primes (2, 3, 7) you can just enumerate all possible subsequences or solve via knapsack.

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

How to solve H? I can't solve it better O(N^3)

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    The following passed in upsolving (idea by meshanya, he probably knows how to prove, I didn't entirely understand his proof during the contest).

    Suppose the tree is a chain. Then you can easily solve it in n2 with a standard idea (Knuth optimization). The idea is that when computing answer for a segment l, r, point of optimum is between points of optimum for l, r - 1 and l + 1, r. This still holds for tree, but the restriction doesn't give us quadratic time. To make it quadratic, one needs the following observation: suppose there's a node v with kids w1 and w2 with corresponding costs c1, c2, and c1 ≤ c2. Then for every segment (u, w2), point of optimum has an upper bound of point of optimum for (u, w1) (simply speaking — if we increase the last number, point of optimum cannot move to the left). This adds another restriction to restrictions from Knuth optimization, and makes running time quadratic (I don't entirely understand why).

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

      A long line of ones that breaks up in paths of length two with numbers 1, 109 (in that order) should break this, shouldn't it? You will run O(n) iterations of search for optimum point for all O(n2) paths that end in leaves anyway (because optimum point for all paths except paths to leaves is somewhere around middle of the long line).

      Something like this:

                   / 1 - 10^9
1 - 1 - 1 - 1 - 1 - 10^9
             \ 1 - 10^9
      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        Hm, on this test, the solution indeed seems to work longer than n2 :) So we can say it is well-deserved that we didn't get it during the contest. Though runtime is only ~3 seconds for the test, so even if it is cubic, it seems to be rather fast.

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

          How about slight improvement — first element of long path is 109 instead of 1? It should be even worse.

          UPD. Sorry for spamming, but it seems that I understood why it is not much worse and 106 as first element instead of 109 should work.

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

            Not much worse — around 3.2 seconds. Though this is my local workstation, I tried on Yandex.Contest servers, and it successfully times out.

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

      Could you show me ur code for this problem? I added ur last optimization, and it gets wa31 :(

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

    Try to solve the problem on array using Convex-Hull-Trick instead of Knuth optimization (store some functions in stack, each pair of those functions should have no more than one intersection). This approach can be done on tree if we will store all the values accurately.

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

I've found a paper with an algo which could be used to solve problem H in O(n2). Here it is. Though I didn't yet manage to read it at large.

The problem with Knuth optimization is that its time bound is amortized: although it runs in quadratic time we cannot just add one element to the array in worst-case O(n), counter-tests could be found above. However, there is a method similar to Knuth optimization with same time complexity but worst-case. It allows adding elements to the back of the array. It is described in the paper. Given this, problem H is trivial: just traverse the tree, adding elements and rolling back on the way.

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

I think last weeks Opencup problems were added in the gym. Would have been awesome if this was added in the gym too.

→ Reply