Блог пользователя yarrr

GP of America
Автор yarrr, 11 лет назад, По-русски

Можно ли обсуждать задачи? (а то тишина что-то)

Если да, расскажите пожалуйста как решаются задачи B, E, F.

  • Проголосовать: нравится
  • +32
  • Проголосовать: не нравится

»
11 лет назад, # |
← Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

А правда ли, что тернарник в D решение неправильно и умные люди писали выпуклые оболочки + расстояние между ними?

А как G за полином ещё решать?

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Правильно ведь: с одной стороны у нас выпуклая поверхность, с другой вогнутая. То есть выпуклая и вогнутая функции. Тернарный поиск работает по разности этих функций. А разность выпуклой и вогнутой функции то же самое, что сумма двух выпуклых функций, что есть выпуклая функция.

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      Спасибо. Получается я хоть одну задачу нормально написал.

      → Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Можно заменить тернарник на бинарник — ты ведь знаешь производную функции.

    → Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Расскажите как решались A и I.

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

Классные у ребят тесты.

По G на контесте зашел полный перебор банальным DFS'ом, в котором есть какое-то несложное отсечение по ответу и еще одно отсечение по "пропал путь с 1 в 2".

А я после контеста составил тест, на котором это решение не успело отработать даже за 45 минут. Это 1 тест, даже не мультитест. И мое АС-решение можно оценить как (n+m)*(2^n). Ну или там 2^(n-2), а не 2^n, в нашем случае это все равно немного страшно отправлять в 5 секунд.

→ Ответить
  • »
    »
    11 лет назад, # ^ |
    ← Rev. 4   Проголосовать: нравится +31 Проголосовать: не нравится

    У меня в G зашло такое: Перебираем кратчайшие пути и считаем, что крадем из всех деревень. Как дошли до вершины 2 -- зафиксировали этот путь. Теперь запускаем Дейкстру: если в оригинальном графе было ребро (u, v), то делаем у него вес gold[v] в случае если вершина v попадает в зафиксированный путь, иначе 0. Ну и для зафиксированного пути ответ -- разница между суммой gold[i] по деревням из пути и веса кратчайшего пути.

    Сложность должна быть примерно такой: O(n2·max(2n / 2, 3n / 3, 4n / 4, 5n / 5, 6n / 6, ...))

    → Ответить
»
11 лет назад, # |
← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится
  • A: Select a node, keep toggling until all of the nodes becomes same color. :)
  • C: DP with state (pos in string, knight1, knight2)
  • D: Exactly as gen said, Ternary Search on time.
  • G: Pure Backtrack. One of our team mates observation was like: if you arrange 36 nodes in 6 x 6 fashion and add edges between adjacent rows, from S to all top row, bottom row to T, then we have only 6^6 ways for going from S to T. which is quite low. We are not sure if this is the worst graph (here to simplify we took 38 nodes) [but there 2^6 also, for 18*2 it makes 2^36 may be]
  • H: loop over all gcd, run a loop over number to see if there is any segment where gcd is that number. its easy.
  • I: I am not sure how many team mate did it, my idea is, you can in O(nlogn) list all divisors for all numbers from 1 to 2e6. Now we know: a + ... + b = (b — a + 1)(a + b) / 2. So see if for each of the divisors of given n, you can find out such a and b.
  • J: DP in two stage. One inter-group another intra-group. Both almost same bitmask DP

Unsolved:

  • B: no idea
  • E: I coded DP but later found I overlooked a special permutation, giving WA
  • F: For each number you need to keep track of the number (previous and next) which is not co-prime to it. Say we get a-b pair (a, b are index) if a-b distance is > k ignore. Otherwise, from (k — (b-a)) ~ a add 1 to segment tree and so on. If you just check for 0's in Segtree you will find answer. Not sure if it is correct.
→ Ответить
  • »
    »
    11 лет назад, # ^ |
    ← Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

    I don't understand how you solve H. Could you be more specific?

    I solved it using divide and conquer with bitset and a little heuristic.

    But how to solve it in 4 mintes???

    In I:

    k=number of consecutive numbers

    a=starting number

    x=the number we want to get

    x = a*k + k*(k-1)/2

    Then i just thought

    for a to 10e6:

    for k to (while possible):

    would pass XD

    and it passed XD

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

      assume gcd = g,

      last = 0
for i = 0 to n - 1:
  if num[i] % g == 0:
    if last == 0:
      last = num[i] / g
    else
      last = gcd(last, num[i] / g)
    
    if last == 1:
      "g can be gcd"
  else
    last = 0
      → Ответить
  • »
    »
    11 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    For G you can write a dp to calculate the worst case graph for number of shortest paths. The problem is to create a sequence of positive integers which sum to 34 where the product is maximized.

    Here is the code in python:

    N = 34
dp = (N+1) * [(0,)]
dp[0] = (1,)
for j in range(1,N+1):
   for i in range(j):
      dp[j] = max(dp[j], (dp[i][0]*(j-i),)+dp[i][1:]+(j-i,))
print dp[N]

    The answer: (236196, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3)

    or

    236196 = 4 * (3 ^ 10)

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      yap, but at the same time, i think to choose/not to choose gold is a factor, but in this complete type graph that factor is 1, since you can always come back. So making a worst graph is a bit difficult, right?

      → Ответить
      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        This is the worst case graph for maximizing the number of shortest paths. This would be the worst case runtime for a brute force all shortest paths solution that used Dijkstra's Algorithm to pay back the necessary nodes.

        There are many graphs you can make that require payback but they reduce the number of shortest paths in the process. So yes, depending on the solution, constructing a worst case graph is hard. :)

        A solution that brute forces all shortest paths but then brute forces all gold usage on all shortest paths should TLE. I don't think the data is strong enough to break that solution. :(

        → Ответить
»
11 лет назад, # |
← Rev. 3   Проголосовать: нравится +29 Проголосовать: не нравится

F

Отрезок плохой, если в нем есть два взаимно непростых числа. Будем хранить количество "свидетелей плохости" для каждого отрезка в RMQ (говорю RMQ, а не дерево отрезков, чтобы избежать тавтологии). Тогда количество хороших отрезков — это количество нулей в RMQ.

Теперь что такое "свидетели плохости". Будем для каждого простого хранить список позиций, в которых стоят числа, делящиеся на него. Два последовательных числа l, r в этом списке — свидетели плохости для отрезков, начинающихся в позициях r-k+1, ..., l.

Теперь решение: когда на вход приходит число, посмотрим на каждый его простой делитель (их не более шести), для простого делителя посмотрим на правого и левого соседа в списке позиций и сделаем три прибавления-вычитания единицы в RMQ. Аналогично нужно обработать простые делители числа, которое раньше стояло на этой позиции.

Сумму в конце можно считать линейным проходом по массиву. Не забудьте про long long!

P.S. Не понимаю, зачем там 40 секунд TL. Сначала это сильно сбило с толку.

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

A relatively complex, but non-hacky solution.

1) divide the nodes into levels according to BFS order from node #1; you can merge all levels starting from the one containing node #2 for convenience.

2) process levels in ascending order and apply the following dp:

dp(i, P) — maximum money we can get on the (shortest) path to i such that the current level of nodes has partitioning P.

Partitioning of nodes of a particular level means node arrangement into sets, where all nodes of a set are connected internally and disconnected from nodes in others sets. Two nodes are connected if there exists a path between them in a graph induced by nodes on current and all previous levels minus the nodes we have stolen gold from. Also, mark one or zero sets as special if the nodes in this set are also connected to node #1.

knowing dp(i, P), try all edges from i to j on the next level of nodes, and try both stealing and not stealing the money from i, and update dp(j, P) accordingly.

3) base case: dp(1, {{1}}) = 0

4)result: max of dp(2, P) over all P's, where node #2 is in the special set.

→ Ответить
»
11 лет назад, # |
← Rev. 2   Проголосовать: нравится +19 Проголосовать: не нравится

B можно сдать следующим образом. Для начала поймем, что если у нас есть две точки на окружности и мы хотим пройти кратчайшим путем, то правильный вариант — это ходить вдоль дуги окружности отрезками длины t и, возможно, последний отрезок будет короче чем t.

Теперь, пусть отрезок между стартовой и конечной точкой пересекает окружность. Будем искать оптимальный ответ в следующем виде: выбираем две точки на окружности, соединяем отрезком первую точку и стартовую, вторую точку и конечную, а выбранные две точки соединяем как кратчайший путь отрезками длины t вдоль дуги. Осталось понять, как оптимально выбрать две точки на окружности — для этого запустим два вложенных тернарных поиска. Первый тернарный поиск будет выбирать точку, которую мы соединим со стартовой, при этом границы в тернарном поиске — это точки, где касательные от стартовой точки касаются с окружностью. Второй тернарный поиск аналогичным образом выбирает точку, которую соединим с конечной.

Если же отрезок между стартовой и конечной точкой не пересекает окружность, то ответ это просто длина этого отрезка.

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Вроде бы если выбрана первая точка, то вторая ищется без тернарника -- это просто первая точка из которой можно пройти к финишу насквозь оставшийся кусок окружности (это и будет та маленькая хорда, которая меньше t)

    → Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hi! I already have an opencup account. I have tried "Sector admin tools -> Ejudge console"(under google translate XD), but didn't find recently contest. Could you tell me where to submit this contest's problem after the contest?

→ Ответить