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

Автор MikeMirzayanov, история, 8 лет назад, По-русски

Всем привет.

Контест закончен, а обсуждения пока нет. Я же с интересом жду разморозки результатов http://opentrains.snarknews.info/~ejudge/res/res10355

Как там в Новосибирске? Какие у участников впечатления от онсайта?

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

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

Why so strange restrictions on a^2+b^2 ?

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

    Restrictions for a and b allow to use integer coefficients when line formed by any two points from square where triangle can be located.

    Upper bound for a2 + b2 is redundant and should be set to maximum a2 + b2 value. Unfortunately it was set twice smaller and this mistake was found too late. Nevertheless it's easy to divide a, b and c by 2 and satisfy to restrictions without double precision loss.

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

      1) Why it is not PE? 2) Why did not increase restriction twice more during the contest?

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

А как 10-ю пихать?

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

    У нас зашло после отсечения "если до клетки в принципе не дойти, то нам пофиг есть там стена или нет". Так склеивается сильно больше состояний.

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

      Спасибо, до этого отсечения не додумались, с ним довольно просто запихнулось за 7.5.

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

    На самом деле ключевыми были две оптимизации. Первая — кешировать состояния, ведь на старте может быть много повторов для большинства тестов, второе — исключать из битовой маски уничтоженных стен те, которые уже не могут быть достигнуты из текущего состояния ни при каком возможном сценарии. В одном из авторских решений по таким состояниям делается обычный BFS. Переходы между состояниями рекомендуется делать за O(1), особенно это касается выстрелов. Для каждого положения танка и состояния (целых и разрушенных) клеток в той же строке и том же столбце можно заранее определить все возможные переходы. После чего доставать их, например, из хеш-таблицы за O(1). Можно воспользоваться и другими способами.

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится +10 Проголосовать: не нравится

Это я не умею писать или идея в 5 неверна? Переберем кол-во голосующих за нашего кандидата(х), после чего построим сеть, где через остальных проходит х-1 потока, через нашего кандидата и вершину прогула inf. После того как посчитаем поток, жадно переманиваем к нашему кандидату недостающих голосующих. Выбираем наилучший ответ. Wa9

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

    Идея правильная, я таким же способом сдал. Тоже было WA 9, там нужно было long long использовать.

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

    Мы перебирали x, через нашего в сток идет x, через остальных, кроме 'не прийти', идет x-1 в некую вершину Z, из 'не прийти' в Z идет инф, из Z в сток идет N-x. И ничего переманивать не нужно

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

    можно вместо жадности в конце, поставить x пропускной способности и -INF стоимости

»
8 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

How to solve 11?

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

    For each suffix compute the value (as a decimal number) mod P. Let ai be the value corresponding to the suffix starting at i.

    Then, for a fixed j, the value of the substring [i..j) only depends on ai. Now it's easy to get an O(nlogn) solution for each query.

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

      In fact you can get O(NT) solution (without logarithm) by using hash table.

      Just make sure you do O(N) insertions total instead of O(NT), otherwise you'll get TL unless you write a hand-optimized hash table.

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

Задача11 у дивизионов совпадала? Если да, то сдавали ли в первом дивизионе O(ntlogn)? Во втором дивизионе в этой задаче стоял ТЛ 1 секунда и даже вполне оптимальное решение, где logn это бинарный поиск по массиву не проходит.

UPD: У единственной сдавшей команды в div2 было +27, а стало +18. А так же был расширен ТЛ до 2-ух секунд.

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

    unordered_map + reserve заходит за 0.7.

    Наш исходник: https://gist.github.com/yarrr-ru/61da2acffff64b1a35117938fff83564

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

    На онсайте, кажется, был tl 3 секунды. (Но тут нужно не забывать, что открытый кубок и онсайт, насколько я понимаю, тестируется на разных серверах). Вроде бы (судя по таблице и со слов участников), у некоторых команд на онсайте тоже были проблемы со временем в этой задаче.

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

      Ну... TL в 1 секунду — это совсем не то, о чём шла речь в Новосибирске. Авторские решения работают от 0.5 до 1 сек, при таких порядках было решено выставить достаточно лояльный TL в 3 секунды. Однако, написав первое попавшееся решение на unordered_map, участники не только не хотели реструктуризировать само решение, но и не хотели отказываться от STL-евского unordered_map. Видимо, нынче самописные hash-таблицы уже не в моде.

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

      • »
        »
        »
        »
        8 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

        Действительно, был сбой при переносе на ejudge. После замены TL на 2 секунды (такой же, как на Яндекс.Контесте и соответствующий инструкциям по выставлению TL; сервера в дивизионах более-менее одинаковы с точки зрения TL, в то время как сервер на онсайте примерно на 40% медленнее) все попытки были пересужены и результаты не поменялись. После замены TL на 2.5 секунды с учётом пожеланий разработчика задачи Павла Хаустова у команды Mozyr CYF 1 задача прошла.

»
8 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

How to solve 5-th problem?

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

    I think 5th is MCMF problem. You can fix number of people who votes for no one, and maximum votes that other candidates get. Then build network with this variables and run MCMF. But not sure about whether it fits in time limit or not. I didn't have time to code it at contest because of 11th problem time limit in DIV2 :) I hope someone who solved it will write more detailed solution.

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

    I solved it with MCMF.

    Let a be the exact number of votes that we want our winning candidate to receive. Construct a flow graph with source/sink, a node for each person that is voting (N nodes), and a node for each voting option (K + 1 nodes). We need the following edges:

    • Source to the node corresponding to our candidate with capacity a and a very large negative cost.
    • Source to the other candidate that can be voted for with capacity a - 1 and zero cost.
    • Source to "not voting" with infinite capacity and zero cost.
    • Each voter to sink with capacity 1 and zero cost.
    • Each voter to the voting option with capacity 1 and cost equal to the cost of having that voter choice that voting option.

    It is clear that the minimum-cost flow here corresponds to the minimum cost required to have our candidate win with exactly a votes (the large negative cost from the source to our candidate forces any minimum-cost max flow to vote for our candidate a times). We can increment the cost of this flow by a·(negativecost) to get the exact cost, and look at the residual graph to reconstruct the solution. Finally, we can iterate a from 1 to N to get the optimal assignment.

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

      One thing worth noting is that the function "cost to win with exactly a votes" (depending on a) is convex. This can be proved by taking optimal flows for a = x and for a = z, then observing that their convex combination with appropriate coefficients would be a valid flow in the graph for a = y (where x < y < z).

      So you could optimize your solution by doing something like a ternary search over a.

»
8 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

А какие резы на онсайте? Может у кого есть скриншот или фото размороженные?

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

    Закрытие олимпиады завтра, вряд ли монитор онсайта разморозят до него.

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

      А, спасибо. Я думал в понедельник всем на учебу, поэтому закрывают в воскресенье :)

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

How to solve 10? It seems brute force is not too slow and only slight improvement is enough.

  • »
    »
    8 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +18 Проголосовать: не нравится

    1) Brute first K moves.

    2) After that you have state (X, Y, DestructedWalls). For optimizations purpose DestructedWalls can be 64 bit mask.

    3) Clean up bits in DestructedWalls mask, if you can't visit some walls anymore with (n - K) moves (to reduce different masks count).

    4) After that there are not so many different states. For each just brute remain (n - K) moves.

    K ~= 23 - 24 works for us in upsolving.

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

      In fact, there is no need to do any portion of brute force here.

      You can run DP with states: (turns passed, robot position, 64-bit mask of destroyed walls), always storing the states only for a single current value of "turns passed". In each state store also its multiplicity (i.e. how many ways are there to get it). After modelling each turn, merge all equal states.

      Now you have to add the "finish optimization". For each number of passed turns and robot position, precompute the set of cells you can theoretically move into regardless of whether any brick wall is destroyed or not. Then in the main DP you do bitwise AND between the mask of destroyed walls and mask of potentially visitable cells in future (i.e. you are forgetting about destroyed walls you can never bump into).

      With such a solution, there is no need to tweak a special parameter K, and no need to write recursive search.

»
8 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

How to solve C and D?

Also, I was wondering if there is any clever solution for F. I solved it using Hopcroft's DFA minimization algorithm.

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

    For F: take any remainder x modulo M. Now consider the chain of segments: [x, x], [b*x, b*(x+1)-1], [b*b*x, b*b*(x+1)-1], ... Find the first segment in this chain that contains 0 modulo M. The pair (k, (x*b**k) mod M) now uniquely defines state x, where k is the number of the segment (in other words, the size of the segment and its left boundary).

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +29 Проголосовать: не нравится

    C: we will only use "is intersection empty" questions. First, find bounding box using binary searches by X and Y. At least one of its corners is a vertex of the triangle, we can check by truncating a small 0.5*0.5 triangle from the corner. Now we've found a vertex and a 90 degree angle containing everything. Now use two binary searches by angle to find rays containing two sides from that vertex. Finally, use binary searches with half-planes parallel to one side to find the vertex on the other side.

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

    D: I find it really hard to explain, but the solution itself is really easy. First, the problem easily boils down to: you have N left ends, then N right ends of segments, connected somehow in pairs. Let's call two segments connected if they intersect, but not one lies inside another. Now we need to find connected components, check if each component is bipartite, and color with two colors if it is, all faster than N**2.

    It turns out that because all left ends come before all right ends, the structure is really simple. Let's look at the left end corresponding to the first right end. All left ends after it intersect it, and thus must have the opposite color. Thus, their right ends must go in reverse order (to avoid intersections between them). Now let's consider the rightmost right end of those. All remaining uncolored right ends to the left of it, again, must have the first color, and so on.

    Code for the coloring part:

            vector<double> sum_inside(2);
            vector<double> sum_outside(2);
            int bl = 0;
            int el = 0;
            int br = 0;
            int er = 1;
            double res = 0;
            while (true) {
                bool upd = false;
                int prev = -1;
                for (int ir = br; ir < er; ++ir) {
                    int cur = invr[ir];
                    if (color[cur] < 0) {
                        upd = true;
                        color[cur] = 0;
                        sum_inside[0] += inside[cur];
                        sum_outside[0] += outside[cur];
                        if (l[cur] < prev) {
                            out << -1 << endl;
                            return;
                        }
                        prev = l[cur];
                    }
                }
                br = er;
                el = max(el, prev + 1);
                prev = -1;
                for (int il = bl; il < el; ++il) {
                    int cur = invl[il];
                    if (color[cur] < 0) {
                        upd = true;
                        color[cur] = 1;
                        sum_inside[1] += inside[cur];
                        sum_outside[1] += outside[cur];
                        if (r[cur] < prev) {
                            out << -1 << endl;
                            return;
                        }
                        prev = r[cur];
                    }
                }
                bl = el;
                er = max(er, prev + 1);
                if (!upd) {
                    assert(bl == el);
                    assert(br == er);
                    assert(el == er);
                    res += min(sum_inside[0] + sum_outside[1], sum_inside[1] + sum_outside[0]);
                    if (er == n) {
                        break;
                    }
                    sum_inside[0] = sum_inside[1] = sum_outside[0] = sum_outside[1] = 0;
                    bl = el;
                    br = er;
                    ++er;
                }
            }
    
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится

      In fact, we did not find this a simple solution. We used a more technical approach.

      Renumber wires on the left to be [1..N] (and wires on the right accordingly). Then the indices of wires on the right form a permutation. It is easy to notice that we have to break this permutation into two increasing subsequences (one for inner wires, one for outer wires). For each element, we know the cost of including it into each subsequence.

      This problem can be trivially solved by DP with O(N2) states. In fact, you can use only O(N) states looking like (size of prefix processed, which subsequence contains last processed element). To achieve this, you have to add whole increasing blocks to alternating subsequences, one block on each step of DP.

      This DP takes O(N) memory, but O(N2) time. It can be optimized with RMQ structure to O(NlogN) time in a way similar to how classical "maximal increasing subsequence" is optimized with RMQ. In fact, it is also possible to optimize it to pure O(N) without any data structure by simply saving some minimums during long increasing runs. Of course, the details are rather nasty =)

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

        Right, the two increasing subsequences paradigm also allows to explain my solution a bit easier: let's look at 1. All numbers to the left of it must go to the other subsequence, and thus be in increasing order. Let the last of them (right before 1) be X. Now all remaining numbers less than X must go to the same sequence as 1, and be in increasing order, and so on.

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

У меня одного opencup таблицы результатов не открываются уже давно? В том числе прикрепленная Майком.

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

Результаты онсайта. Таблички 2 тура не было, так что пока так.

https://cloud.mail.ru/public/69Rv/JzWJJQK8e

https://cloud.mail.ru/public/MySS/LQpe8ALbS

»
8 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Размороженный рейтинг с онсайта здесь.

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

How one can solve 8?

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

    Yes, I would like to know about solving this problem too. I got TL 16 because of usual tree structure (bad idea when tree looks like a line — so queries would be executed O(N)), but what is right solution?

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

    What we need a data structure that allows to update numbers in a tree and to find the sum of numbers in a subtree. If we do a preorder traversal of the tree, then any subtree will correspond to a segment in that ordering. And a data structure that allows updating numbers and finding segment sums is a Fenwick tree.

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

      Thank you for your answer, I thought about segment tree, but could not understand how to enumerate vertices (build segment tree)... It is not difficult for me when we build segment tree according to the array 1..N, but when we have tree with randomly enumeration in that problem — I don't know about representing.