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

COCI 2012/2013 — контест №6
Автор eduardische, 12 лет назад, По-русски

Напоминаю, что сегодня (09.03.2013) в 18:00 по Москве состоится шестой (и последний регулярный) контест хорватской олимпиады по информатике. Залогиниться/зарегистрироваться можно тут. Продолжительность: 3 часа. Удачи!

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

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

I believe it is on 9 March :[ http://hsin.hr/coci]

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

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

Кто-то такое писал?

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

    Я писал такое. Только там длины периодов маленькие (до 10000), так что уравнения можно решать за O(длины периода). По сути то же самое, только кодить проще и не нужно никаких расширенных алгоритмов Эвклида.

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

      А почему период маленький? Мы ведь получаем до 5 выражений kx+b, и да, у каждого из них период до 10К, но их надо решить одновременно. А 2 (k * x + b) & (l * x + c) заменяются на одно lcm(k,l) * x + (место первой встречи), и тут уже период вырастает. Или я что-то недопонял?

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

        Да нет, период для одной бактерии маленький.

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

          Да, ну что я придумал и не успел написать — для каждой бактерии получаем до четырёх выражений, когда она будет в ловушке — const, если это в предпериоде или kx+b — если в цикле.

          Перебираем все 4^K вариантов. Если хоть одна константа — проверка элементарная, иначе — K выражений kx+b. k <= 10K у каждого да, но как их решить одновременно без расширенного Евклида, можно поподробнее, пожалуйста?

          Или решение вообще отличается?

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

            Решение точно такое же, просто без расширенного Евклида.

            Пусть у нас есть 2 арифметические прогрессии ax + b и cx + d, где b < a и d < c. Понятно, что если b - d не делится на gcd(a, c), то общих членов нет. Иначе проверим, принадлежит ли число b второй прогрессии. Если нет, то будем прибавлять к нему число a до тех пор, пока оно нам не подойдет. Ясно, что это произойдет за O(c) шагов. Теперь у нас есть прогрессия вида lcm(a, c) * x + y, где y мы только что нашли. Таким образом будем сливать по очереди первую и вторую прогрессии, потом ту что вышла с третьей и т.д.. В конце получим прогрессию Ax + B. Теперь осталось проверить, что число B не слишком маленькое (оно может не подойти к какой-то прогрессии). Если оно маленькое, то будем прибавлять A пока не станет нормальным.

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

              А, у одной только прогрессии будет большой период, у второй маленький всё ещё. ОК, понял, спасибо большое!

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

      Кстати, почему на первый сэмпл ответ 3? там же два шага?

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

        Там время — это количество шагов плюс 1.

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

May anyone suggest a suitable method to solve 4th problem ? I only came up with the following observation.


For a horizontal line y = c : 
the answer is the number of triangles that have at least one line segment (x1,y1)<-->(x2,y2) : y1 < y2 , 
c belongs to the interval ]y1..y2[
-  For a vertical line x = c : 
the answer is the number of triangles that have at least one line segment (x1,y2)<-->(x2,y2) : 
x1 < x2 , 
c belongs to the interval ]x1..x2[

I used 2 segment trees to handle the horizontal and vertical cases , but that scored 80 / 120 , due to exceeding the memory limit in the last 2 testcases. I think there are some tricks(coordinate compression , solving the horizontal cases then clearing the segment tree then solving the vertical cases) , but I'm not sure if they can help out.

And may anyone suggest how to approach 5-th problem ?

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

    If you have the range of [0..2^x-1] you can easily store a segment tree in one array of integers — for values. Every other needed information is easily computed on-the-go.

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

    You only need to do two sweep lines, one for the X queries, and another for the Y queries.

    In each sweep line, you need to keep a counter that tells you the number of active triangles.

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

    Regarding the 4th problem: First off, lets simplify the prob by assuming we deal with rectangles rather than triangles. Using that simplification we can make two arrays X and Y. where we are going to append X_min and X_max and Y_min and Y_max for each rectangle respectively. Secondly, we make two new arrays for X and Y: X' and Y' where on the i-th index we write the number of rectangles, edges of which are situated on the different sides of X[i].

    This is just an idea.

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

    The 5th problem can be solved with a simple O(N2) DP. The key observation is that any two adjacent elements in a good sequence differ by not more than 1. The reverse is also true: any sequence in which every two adjacent elements differ by not more than 1 and the first and the last elements are equal to 0 is good.

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

      I would also say that the correct relief of length N form a bijection with correct bracket sequence of length N-1, where in N-1 spaces we can put spaces as well. For example in 3rd sample case:

      ? ? ? 2 ? ?
 ( ( - ) )
 ( - ( ) )
 - ( ( ) )

      The numbers represent the level of bracket sequence at a given point.

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

      also we can improve this using combinatorics making the solution become O(N)

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

        Can u explain more about the O(N) solution? I can't solve it with O(N^2) neither because of memory limit...

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

          you use dinamic array as i think dn[N][N]

          you can use dinamic array like this dn[2][N]

          because f(n,k) = f(n+1,k)+f(n+1,k-1)+f(n+1,k+1)

          n is the position in the array and k is the what is the array[i]

          so you must only know N th and N+1 th rows .

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

Интересно, а какой максимально возможный ответ в 6-й задаче? В тестах жюри это 9298781157357368. А можно ли построить тест где ответ не влазит в long long?

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

    Понятно, что каждый период четный и не превосходит 104. Значит lcm пяти периодов не больше 1020 / 24, а это влазит в long long. И я сильно сомневаюсь, что период реально может быть 104.

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

      Точно, он же четный. Тогда ясно что влазит. Я не подумал об этом и хранил ответ в паре лонг лонгов.

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

Just published Results.

→ Ответить