Tima's blog

Grand Prix of Saratov
By Tima, history, 9 years ago, In English

Let's discuss problems. How to solve F?

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

Comments Comments (7)
| Write comment?
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Off topic: Edit your title and add "2016" to it.

Solution for F: Use extended euclidean algorithm to find solution for a1x1 + a2x2 + a3x3... = A, where x1,x2,x3 are unknowns.

What does this tell us? If x1 is positive, it means we have to fill container a1 x1 times. If x1 is negative, we have to empty a1 container x1 times.

Ultimately that should matter only. Once you know which one to fill and which one to empty, rest is simulation.

I will give an example using two containers of capacity 5 and 3. Let them be A and B. Suppose we want to make 1. Then:

5*2 + 3*-3 = 1. Therefore, we have to fill first container two times and empty second container 3 times. How do we do that?

Fill first container. Now, we have to fill it again. But it's already full, so transfer 3 units from A to B. We still have 2 units left in A. But B is already full, so we can't transfer. Then again, we have to empty B 3 times. So let us empty it once now. Then transfer 2 units to B again. Keep repeating until desired result is achieved.

Basically, those that need to be filled will get their water from outside and are not allowed to throw their water outside. Those that will empty their container will throw their water and are not allowed to get their water from outside.

We didn't get time to code it. Can somebody who got AC verify the idea?

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

    We got AC using this approach. You should note that you can't calculate x1,x2,... simply using extended gcd algorithm because they would grow exponentially. However you can exchange xi, xj for xi'=(xi — aj), xj'=(xj + ai), so a1x1'+a2x2'+... still equals A, and using operations of this type after each run of extended gcd you can ensure |xi| <= max aj <= 2 * 10^4. Another solution is to run bfs on graph with 4 * 10^4 vertices with edges v -> v + ai, v -> v — ai and find a path from 0 to A.

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

Published in the Gym: 2015-2016 Petrozavodsk Winter Training Camp, Saratov SU Contest.

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

Так как F то решать? А то мы видимо одна команда с 8 без нее :) И даже идей особо кроме какого то паленого перебора не было :)

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

    Мы сдали вот что, доказывать не умеем.

    Скажем, что в каждый момент нас интересует только одно ведро и уровень воды в нём. Остальные вёдра либо пустые, либо полные, не важно. Состояние -- [vessel_id, amount]. Переходов три или четыре, типа "нальём из другого ведра, пока не перельётся", "выльем в другое ведро, пока оно не заполнится" и т.д. (деталей не знаю). Дальше по этим состояниям запускаем поиск в ширину.

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

    Известный алгоритм:

    Пусть у нас есть два ведра a, b, тогда можно получить любое значение в большем ведре, кратное gcd(a, b).

    Алгоритм: наливаем в маленькое, переливаем в большое, если оно наполнилось, то выливаем. мы будем получать значения a, 2a % b, 3a % b, etc

    Наша задача: Отсечем тупые случаи(не кратно gcd, больше максимума).

    Отделим ведро-максимум M от остальных a_1,..a_k Будем аналогичным алгоритмом наливать в a_k переливать в M, пока в нем не станет x % g == a % g, где g= gcd(M, a_1, a_2 ..., a_{k-1}), после этого повторим с оставшимися ведрами. В конце получим x % g == a % g , g = M, что и нужно.

    Минимизировать не просили, операций получается если грубо оценивать как раз порядка 2e4 * 10 * (3-4)

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

how to solve K?

→ Reply