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

Автор Sereja, 12 лет назад, По-русски

214A - Система уравнений

В данной задаче решение — просто перебрать возможные пары чисел и проверить их на правильность. Делать это можно было любым способом.

214B - Домашнее задание

Число делится на 2,3,5 только в том случае, если сумма цифр кратна 3, а последняя цифра 0, то есть если в наборе нету нулей, то ответ -1. Дальнейшее решение — разбор случаев.
Возьмем все цифры в невозрастающем порядке, если сумма цифр кратна 3, то это и есть ответ. Если остаток от деления вышел 1, то нужно убрать 1 цифру у которой остаток от деления на 3 равен 1. Если такой не нашли то нужно убрать 2 цифры с остатком 2. Аналогично рассматривается случай когда изначальный остаток равен 2. Так-же нужно рассмотреть случай когда остались только нули, в этом случае нужно вывести только 1 ноль.

213A - Игра

Решение — жадность. Пусть у нас компьютеры стоят по кругу, и ходами "вперед" назовем перемещения (1->2, 2->3, 3->1), а перемещением "назад" (1->3,3->2,2->1).

Заметим что ходить "назад" не выгодно, так как можно 2 раза походить "вперед", что в сумме равноценно. Будем перебирать стартовую вершину. Дальше будем ходить по кругу до тех пор, пока не "откроем" все уровни. В авторском решении для каждого уровня поддерживается количество уровней, которые нужны для него. После того как мы находим очередной 0 в этом списке, мы просто уменьшаем такую величину для всех уровней, которые от него непосредственно зависят. Сложность решения O(n^3).

213B - Числа

Решение — динамика. Перебираем длину числа, которое будем строить. Далее будем пользоваться динамикой f(len,i) — сколько чисел диной len можно составить из цифр i..9.
Пересчет:
- f(len,0) = sum(f(len-i,1)*C(len-1,i), i=a[0]..len);
- f(len,j) = sum(f(len-i,j+1)*C(len,i), i=a[j]..len), 0<j<9;
- f(len,9) = 1, если len>=a[9], 0 если len<a[9].
C(n,k) — количество способов выбрать k элементов из n.

213C - Эстафета

Решение — динамика.
Заметим, что мы можем просто провести два пути их клетки (1,1) в клетку (n,n).
Заметим, что после каждого шага клетки будут оставаться на одной диагонали. Будем решать задачу динамикой f(d,i1,i2), d — номер диагонали, i1 — 1я координата 1го маршрута, i2 — 1я координата 2го маршрута. Понятно что вторую координату мы можем определить однозначно. Переходы — очевидны, делаем 4 возможных перехода, если маршруты пересеклись, то добавляем величину клеточки один раз, иначе добавляем величины посещенных клеток. Так как данная динамика не влазит по памяти, то ее нужно делать двумерной, просто перенося значения из прошлой диагонали в новую.
Еще нужно не забыть про то, что ответ может выйти отрицательным.

213D - Звезды

Предоставлю разбор как небольшую презентацию картинками:
https://get.google.com/albumarchive/pwa/115317317397602031319/Solutions131

Реализация.
Единственную сложность могло составить определение координат, все координаты можно найти из правильного пятиугольника. Все что о нем нужно описано тут.

213E - Две перестановки

Первый шаг: заменить перестановки на обратные, то есть из перестановки A мы делаем перестановку B, такую что B[A[i]] = i. Если посмотреть на то, что получилось, то выходит такая задача: сколько подотрезков второй перестановки равны первой, в случае если мы "сожмем координаты", то есть числам сопоставим их номер в отсортированном виде. Эту задачу предполагалась решать хэшами, но брать их нужно было не только по основанию 2^64, а и еще по нескольким простым модулям, тайм лимит специально стоял 3 секунды.
Теперь, собственно, как ее решать: Для каждой позиции i — сопоставим коєфициент step[i], где step[i] = 1000003^i. Теперь Рассмотрим такую функцию: F(A) = num[1]*step[1] + num[2]*step[2] + num[3]*step[3] + ... + num[n]*step[n], где num[i] — порядковый номер элемента A[i] в отсортированном списке. Понято что эта функция однозначно задает множество, от нее и будем считать хэш.
Как пересчитывать при переходе не следующий элемент.
Заметим что когда мы убираем какой-то элемент, то все элементы которые больше его уменьшают значение num на единицу. Ровно как и после добавления они его увеличивают. То есть заведем Дерево отрезков/Фенвика для хранения таких величин как сумма степеней на отрезке и количество элементов на отрезку, что-бы за O(log(n)) находить величину num для числа и после каждого добавления/удаления будем пересчитывать хэш, тоже за O(log(n)). Так-же нужно будем умножать хэш на от первой перестановки на 1000003 после каждого смещения на 1 элемент вправо, так как коэффициенты step уже не будут идти от единицы.

Все замечания просьба писать в комментарии.

Через некоторое время постараюсь сделать формулы более красивыми.

Разбор задач Codeforces Round 131 (Div. 1)
Разбор задач Codeforces Round 131 (Div. 2)
  • Проголосовать: нравится
  • +40
  • Проголосовать: не нравится

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

D можно сильно проще: берем пятиугольник из семпла, сдвигаем его параллельно одной из диагоналей на одну, две и т.д. диагонали. Проводим длинную линию. дальше легко

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

    Да, я уже это понял. Изначально не подумал о таком решении.

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

    Еще можно было расположить на окружности но это не проще(

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

      А тогда ответ вообще будет для n = 100, если ставить по окружности и без разворотов?

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

        Я сдал в дорешивание. Да там с запасом хватает. На контесте я написал чтобы нижние основания были на окружности, но это конечно неправильно нужно чтобы диагонали были на окружности и ок.

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

    У меня так же, как у тебя. Гораздо проще.

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

А почему в задаче Е нужно было брать не только по модулю 2^64? У меня в дорешивании прошло. Здесь же вообще непонятно, как строить контрпример сразу под все нечетные основания.

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

    Для гарантии. Я понимаю что не понятно как перестановку завалить, именно по этому я дал эту задачу.

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

      Вот генератор, валит все зашедшие на контесте решения, кроме моего. Правильный ответ (вроде) 21.

      Респект Zlobober за идею, конечно.

      import java.io.InputStream;
      import java.io.OutputStream;
      import java.io.PrintWriter;
      
      /**
       * Built using CHelper plug-in
       * Actual solution is at the top
       */
      public class Main {
      	public static void main(String[] args) {
      		InputStream inputStream = System.in;
      		OutputStream outputStream = System.out;
      		PrintWriter out = new PrintWriter(outputStream);
      		BadGen solver = new BadGen();
      		solver.solve(out);
      		out.close();
      	}
      }
      
      class BadGen {
      	public void solve(PrintWriter out) {
              int n = 1 << 12;
              int m = 1 << 17;
              out.println(n + " " + m);
              int[] pn = buildBadPerm(n);
              for (int i = 0; i < n; ++i) {
                  if (i > 0) out.print(" ");
                  out.print(pn[i] + 1);
              }
              out.println();
              int[] pm = buildBadPerm(m);
              for (int i = 0; i < m; ++i) {
                  if (i > 0) out.print(" ");
                  out.print(pm[i] + 1);
              }
              out.println();
          }
      
          private int[] buildBadPerm(int n) {
              int[] invs = new int[]{0};
              while (invs.length < n) {
                  int[] ninvs = new int[2 * invs.length];
                  for (int i = 0; i < invs.length; ++i) {
                      ninvs[i] = invs[i];
                      ninvs[i + invs.length] = 1 - invs[i];
                  }
                  invs = ninvs;
              }
              int[] perm = new int[n];
              for (int i = 0; i * 2 < n; ++i) {
                  if (invs[i * 2] == 0) {
                      perm[i * 2] = i * 2;
                      perm[i * 2 + 1] = i * 2 + 1;
                  } else {
                      perm[i * 2] = i * 2 + 1;
                      perm[i * 2 + 1] = i * 2;
                  }
              }
              return perm;
          }
      }
      
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +20 Проголосовать: не нравится

        Авторские ради предостережения были написаны по трем модулям, они тоже 21 выводят.

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

В div1 C динамика отлично влазит по памяти (по крайней мере в С++).

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

А можно пожалуйста 213-B Числа подробнее объяснить? В частности что означает функция sum() и вот эту строку - f(len,9) = 1, если len>=a[9], 0 если len<a[9].

Спасибо.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    if(len >= a[9])
        f(len, 9) = 1
    else
        f(len, 9) = 0
    
  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    функция sum() — прибавление f(len, i); f(len,9) = {0, 1}, потому что либо можно получить число состоящей только из 9, например f(2, 9) = 1, это значить что можно получить число 99, либо нельзя получить это число так как len < a[9], т.е не соответствует условиям задачи.

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

Подскажите пожалуйста как посмотреть полностью тест 16 из задачи B. Или какой хотя бы там смысл.

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

Sereja , thanks for writing the editorial. Can you explain solution to 213C(Relay) more detailed? Using the English version translated by Google, I was confused.

It would be better if you submit your reference solutions with proper comments.

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

I would be appreciated if someone explains the idea behind Petr's solution to 213C, especially what the state best[][] means and how the transferring works, note that it's 2d(two dimensional) instead of 3d used by most contestants which reduced a lot of memory.

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

    Most contestants use best[step][x1][x2], but you only need to know best[step-1][][] when you are calculating best[step][][], which means you don't need to store best[x] (x < step-1). So you can compress best[MAXSTEP][][] to best[2][][], or like Petr use best[][] best1[][].

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

in 213B f(len,i) is equal to the quantity of numbers we can build using digits i..9 of length len.but why do we multiple in formulas for example f(len-i,1)*C(len,i),should not it be f(len-i,j+1)*C(len,i),please tell me where's my mistake,thanks in advance

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

Мне кажется, что в задаче D div2, во второй формуле должно быть: f(len,j)=sum(f(len-i,j+1)*C(len,i), i=a[j]..len), 0<j<9;

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

It would be nice to see a visualisation of some interesting solutions for stars (div1 D).

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

    I think it's difficult for me and I cannot understand it yet...= =

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

    This is another easy solution for problem D:

    Assume that the distance between 2 vertices (1-5) is len. After pre-computing the positions of 4 vertices 1 2 3 4, positions of others vertices can be calculated easily by adding k * len to the x coordinate of the first 4 stars (for example, if we know (x3, y3), then (x7, y7) = (x3 + len, y3))

    To draw the stars, for example, with n = 2, we can do like this: 1 5 9 7 6 8 5 3 2 4 1.

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

In the example of problem E,why "1 3 5 2 4 1"is correct but "1 4 2 5 3 1"is wrong? I just output them in an opposite way.

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

I think the time complexicity for 213A is O(3*N^2)(N^2), not O(N^3)

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

    Well, O(N^2) is a subset of O(N^3) :), but you're right, the time complexity of the algorithm described by Sereja is O(N^2).

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

      It will work O(n^2) only if we will find all zeros(when there is not any edge to the vertex) quickly. Of course it is easy. But my solution works O(N^3) at worst case.
      It is A problem, so I think that it is normal, when such solution can passed system tests.

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

        Are you sure that it's O(N^3)? When we go around 3 computers, we'll always find at least one zero, so we'll perform O(N) loops. Since you maintain a degree array (and I'm very sure that you also use a boolean array of visited vertices), it's possible to find a zero in O(N). And for each zero you decrease O(N) items in the degrees array. The result is O(N) * (O(N) + O(N)) = O(N^2). What have I missed?

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

Насколько я понял, в разборе к задаче 213B, тут: - f(len,j) = sum( f(len-i,1)*C(len,i), i=a[j]..len ), 0<j<9; опечатка.

Вместо, f(len-i,1) нужно использовать f(len-i,j+1) . По крайней мере, у меня так ( кстати, еще есть пару опечаток ) прошло.

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

In problem 213E,I have a question. when you use hash,why do you choose 1000003,and it is likely that F(A) you define exceeds long long? What should you do to avoid the problem.

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

    1). I use 1000003, becouse it's bigger then 200000 and prime. 2). I use long long's overflow (it's the same as get number modulo 2^64), but I also use hashes by some other modulos.

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

      Does it possible that the hash crashes,that is to say,two different permutations have the same number modulo 2^64 ? But I notice that most people don't consider it.

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

        Yes, it can be.

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

          So I get an AC, But how should we improve it?

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

            We can calculate hashes by modulos 1000000007 and 1000000009 instead of 2^64.

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

              Can you assure that it doesn't crash if you use 1000000007 and 1000000009 as modulos. Also we can't store the permutations who crash.

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

                We can't assume that. Hashes give big probability, but not 100%.

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

                  Ok,Thank you,I get an AC using 1000000007 as the modulo a moment ago,

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

Подскажите, пожалуйста по задаче C — эстафета. Работает ли такой алгоритм: с помощью простого ДП находим max путь из точки (1;1) в точку (n;n), затем с помощью поиска в глубину проходим по max маршруту обнуляя клетки, которые посетили. Потом простой динамикой ищем max маршрут из (n;n) в (1;1). И суммируем результаты маршрутов. Простая динамика: pole[i][j]+=max(pole[i-1][j],pole[i][j-1]); pole2[i][j]+=max(pole2[i+1][j],pole2[i][j+1]). pole2 — это матрица после прохода по 1-ому маршруту ( после обнуления ). Результатом я считаю pole[n][n]+pole2[1][1] Если алгоритм невереный, то почему? Ecли алгоритм работает, то где у меня ошибка 2087919?

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

    Видимо, контрпримером против такого алгоритма может быть

    3
    99 99 98
    98 99 99
    11 98 99
    

    Первоначально оптимальный путь — идущий всю дорогу по значениям 99. Но потом второй персонаж вынужден идти через 98, 11, 98. Тогда как можно сформировать 1-й путь как вправо, вправо, вниз, вниз, а 2-й как влево, вверх, влево, вверх, и так сумма будет больше.

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

In div2 B-Hometask, after ensuring there is a 0 in the list, I tried to find the maximum digits I can keep which will give me a sum % 3 == 0 using Knapsack DP. Here is my code Code. I got WA on test case 13. All I want to know, did I get WA due to stack overflow? Or is it not possible to find which digits to keep using Knapsack dp? Also, if stack overflow occurs in codeforces, do we get WA or run-time error?

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

I can't understand  So it means: (a-b)(a+b-1)=n-m if n==m, a=b is a true answer that consists of infinite pairs. What is wrong with my insight? (problem A)

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

    not every solution of (a - b)(a + b - 1) = n - m is the solution of this system. Futhermore, the number of solutions of the system is finite, because if a > n or b > n then a2 + b > n

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

Can someone please explain in detail(in English) the editorial for div1 B?

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

Начал в архиве решать эту задачу и по сокращенным фамилиям героев понял, кто автор :)

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

comment deleted

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

Can someone give a proper explanation for 213C Relay Race . What does the author mean by "There are 2 paths from (1,1) to (n,n)" and also "after each move our cells will be located on the same diagonal."

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

    Consider Rubik also starts from (1,1) and moves to (n,n) . (this will not change answer ) .

    The diagonals refer these --.

    Clearly at each step both will be on same diagonal

    Knowing the diagonal number , and x-coordinate , you can get y = d-x + 1.

    So , we store only diagonal number and x-coordinates for both rubik and furik

    33898588