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

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

382A - Ксюша и чашечные весы

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

382B - Разрушители чисел

В этой задаче нужно было понять, что из себя представляет хитрая операция Артура. На самом деле, если перед выполнением всех действий сделать присвоение b = w - b - 1 (то есть как бы перевернуть ситуацию), то операция аналогична присвоению b = (b + x) % w. Причем если происходит переполнение через w, то дополнительно происходит присвоение a = a - 1.

Таким образом, если выполнить k таких операций, то переменные изменятся так: b = (b + k·x) % w, a = a - (b + k·x) / w, c = c - k. Зная это, легко решить задачу бинарным поиском по ответу.

382C - Арифметическая прогрессия

В этой задаче нужно было разобрать несколько несложных случаев:

1) если n = 1, то ответ: -1, потому что любые два числа будут являться арифметической прогрессией;
2) если массив состоит целиком из одного числа, то ответ: эта единственная константа;
3) если вам уже дана арифметическая прогрессия, то ответ это 2 числа: minVal - d, maxVal + d, где minVal — минимум, maxVal — максимум, d — разность прогрессии.
Однако, если n = 2, то в этом случае ответ бывает 3 числа (как, например, в последнем тестовом примере, когда разность (a[1] - a[0]) четна);

4) иначе, возможно, в прогрессии пропущено ровно одно число и его можно аккуратно найти двигаясь по исходному массиву (предварительно его удобнее отcортировать). Разность прогрессии можно вычислить, как d = min(a[i + 1] - a[i]) (если n > 2);
5) во всех иных случаях ответ 0;

382D - Ксюша и пешки

В этой задаче из всех клеток кроме # один переход. Поэтому граф на клетках является почти фунцкиональным графом. Если в этом графе есть цикл, то очевидно ответ -1, потому что этот цикл имеет длину не менее 2 и мы можем разместить на нем две наши пешки.

Иначе в графе нет циклов. Найдем в нем самый длинный путь, пусть его длина len. Тогда если мы расположим две наши пешки в первую и вторую клетку пути, то ответ на задачу уже будет len - 1.

Однако, иногда можно получить ответ len, если в этом графе есть два непересекающихся по вершинам пути (вершины, не являющиеся #). Непересекающиеся они будут потому, что если вдруг они пересеклись в какой-то клетке, то дальше они будут совпадать (а по условию задачи такие ходы совершать нельзя).

Остается проверить есть ли в этом графе два непересекающихся по вершинам (не #) пути длины len. Это можно сделать как угодно. Например, посчитать для каждого истока v величину d[v] длины пути из него. После серией поисков в глубину из всех истоков с максимальным d[v] = len проверить найдутся для два непересекающихся пути. (если очередной поиск в глубину не находит поюзанной вершины, значит этот путь новый).

382E - Ксения и комбинаторика

Чтобы решить задачу, нужно было посчитать количество деревьев с заданными свойствами. Сделать это можно с помощью динамического программирования. Основная идея динамического программирования в том, что размер максимального паросочетания в дереве ищется простой линейной динамикой dp[v][used] (v —- вершина, used —- уже использована она в паросочетании или нет), поэтому для подсчета количества деревьев достаточно включить в состояние динамики два значения dp[v][0] и dp[v][1].

Другими словами, нужно написать динамику z[n][dp0][dp1], значение которой — это количество подвешенных деревьев, состоящих из n вершин, в корне которых динамика dp[root][0] = dp0, а dp[root][1] = dp1. Если просто написать такую динамику она будет получить TL по времени. Из этого положения можно выйти двумя способами. Либо посчитать все значения динамики прекалком, немного оптимизировав код, либо ассимптотически оптимизировать динамику.

Авторское решение использует второй подход. Для того, чтобы оптимизировать динамику достаточно заметить, что значение dp0 отличается от значения dp1 не больше чем на 1. То есть либо dp0 = dp1, либо dp0 = dp1 + 1. Тогда динамика превращается в динамику r[n][dp0][add], которая работает сильно быстрее. Другая важная оптимизация состоит в том, что возможных троек (n, dp0, add), для которых значение r[n][dp0][add] ненулевое очень мало (около 250). Это значит, что достижимых состояний динамики не много, поэтому если написать ее "лениво" с отсечениями, программа будет работать в несколько раз быстрее.

Комментарии, которые описывают решения (некоторые отличаются):

http://codeforces.net/blog/entry/10423#comment-158177
http://codeforces.net/blog/entry/10423#comment-158182

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

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

when input 2 3 3 the answer is 1 3 why it's true? the answer 3 3 3 3 also correct i think

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

    The statement implies that all numbers should be distinct.

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

    No, you're asked to find the number you can put on one card, regardless their position, so 1 3 is correct since you can place it anywhere within the sequence.

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

Very fast tutorial, thanks!

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

This was my first contest and I'm unrated. How long does it take for the ratings to show up ?

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

for problem C, i feel that the the case where (a[0] + a[1]) / 2 also had to be included in the answer could have been omitted from the pretests (or atleast from the examples), as a good number of participants may not have seen that.

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

5716844

I solved Problem B in a quite different way.

(I'm not sure if it's absolutely correct,and sorry for my poor English)

if b ≥ x, perform the assignment b = b - x

if b < x, then perform two consecutive assignments a = a - 1; b = w - (x - b)

Let's define the b ≥ x one as operation A,and the other operation B

You may notice that a and c seems works as counters,and (c-a)gets smaller after operation A,(c-a) won't change after operation B

Define the times doing operation B as k

So the time Alexander gets ahead of Arthur is c-a+k

Also,you can easily find that the time Alexander gets ahead of Arthur can be also described as ceil((b+kw)/x)

So,now we have a formula

(b+kw)/x=(c-a)+k

we can get:

k=((c-a)*x-b)/(w-x)

and now we can get the answer by calculating ceil(c-a+k)

However,the (c-a)*x can be very large,bigger than INT_MAX.So,we should use long long.(That's why I made two Wrong Answer submissions)

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

    I can't get neither this nor author's solution for B :(

    "the time Alexander gets ahead of Arthur can be also described as ceil((b+kw)/x)"

    Why is it so?

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

      Well another approach is using dfs and finding cycles.

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

      Sorry for the trouble I caused.I forgot to explain that,and I may have made a mistake.

      operation B says,if b < x, then perform two consecutive assignments a = a - 1; b = w - (x - b)

      It's a little tricky

      b=w-(x-b)=b+w-x

      Which means,In operation B,we also did minus x.And we only add w for k times

      So no matter which operation we did, b always -x.

      If we don't -x during each operation B,b will be (b+kw) after k operation B.

      And (total times minus x)*x is supposed to be smaller or equal to (b+kw).

      (After a second thought, I think we don't need a ceil() here)

      So (total times minus x)<=(b+kw)/x

      So (c-a)+k<=(b+kw)/x

      So k>=((c-a)*x-b)/(w-x)

      Since We want to find the minimum time ,k=((c-a)*x-b)/(w-x)

      What should we do if k is't a integer?We can't do a half of operation B

      k=ceil(((c-a)*x-b)/(w-x))

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

      hi, look here http://codeforces.net/blog/entry/10423 for the explanation of clp012345 is a good one.

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

    i first use binary search , but WA twice . then in the last five minutes i try nearly the same algorithm with you then AC. lucky! k=((c-a)*x-b)/(w-x)

    for(int i=k-10000;;k++) { when i find a i,break. }

    i find that my bsearch is wrong just because the right need to be larger than 2000000000000LL a simple mistake takes me nearly all the time……

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

    我猜这个你能看懂

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

Из разбора задачи D: " После серией поисков в глубину из всех истоков с максимальным d[v] = len проверить найдутся для два непересекающихся пути. (если очередной поиск в глубину не находит поюзанной вершины, значит этот путь новый)." Как доказать, что это работать будет быстро?

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

    Я понял. Тут имелось ввиду, что мы просматриваем пути с макс. длиной не попарно, а просто по одному и красим путь с false в true. Если 2 пути пересекаются, "то дальше они будут совпадать". =)

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

my solution for B is completely different from author`s

notice that 0 <= b < w <= 1000, this means that we had a cycle on b, so find it and compute its length and delta -- count of decreasing c (without a). now we can say how many times we should pass this cycle and then pass one more time for end. It works O(w)

5725480

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

Let me state another solution for problem B. The key observation is that both b=b-x and b=b-x+w are equivalent modulo w, and number b is always going to lie in [0, w-1]. So each operation means taking (b-x) instead of b (modulo w). So if we look at the reminders mod w, the sequence becomes b, b-x, b-2x, ..., b-kx, ... Now it's clear, that there is going to be a period P (we can find it via simulation in O(w) initially or notice that it's just the minimal p : b-px=b(mod w), or px=0(mod w), or p = w / gcd(w, p).). Also we should calculate the decrease of a variable "a" in this period — call it S.

Now, we can calculate the decrease of a variable a in X steps the following way: If X <= P, then it's just a simulation in O(P). Otherwise, it's just S*(X/P) + simulation of (X % P). Clearly, it works in O(P) which is also O(w).

All that left is a binary search: obviously, c always increases, while a increases just sometimes. So once c<=a is satisfied, it's gonna stay like that all the time afterwards.

Hopefully it's clear :)

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

    px = 0 (mod w), then p = w/gcd(w,x), not p = w/gcd(w,p). Anyway, thank for your clear explanation!

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

may someone explain solution for D?, thx

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

    The problem can be formulated in terms of directed graphs: each cell is a vertex, it has outdegree 0 if it's '#' (let's call those vertices endpoints) and outdegree 1 otherwise, with the only outgoing edge pointing to the cell that a pawn moves to from it.

    If there's a cycle in this graph, the answer is -1.

    Otherwise, the path from every cell must end in an endpoint; notice that the graph is, in fact, a forest of trees rooted at endpoints. For every such tree, you can count (BFS, DFS, whatever you wish) its depth in its tree, which is equal to the number of moves, and the last vertex on the path from it before the root.

    Now, you can only put pawns in vertices which either have different depths or "last" vertices, or they'd meet on a non-end vertex; think why it works. For different depths, it's simple: just find the largest (a) and second largest (b) depth overall. If you want to choose 2 vertices with the same depths, both must be equal to a or it won't be better than a + b; that means you can choose a vertex v with depth a, iterate over all vertices with depth a and iff you find one with "last" different from last(v), then there's a better solution 2a. Just check all those possibilities.

    The time for this is O(NM).

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

Thanks for fast editorial.. But what about 382D and 382E?

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

Although I pass the problem b,I can't understand your explaination. I use the pigeonhole principle and have a way to solve it in o(2*x). Could you explain that how to get these formulas in details? Thank you very much.

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

    Could you please explain how have you used pigeonhole principle in problem B?? Thank you

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

      First,you should find the if the datas is enough big,the value of b will repeat.So it's easy to see that the value of b will repeat at most of x times. For example,if you use a array[x] to record the value of b when it appear,it must have one of the array[x] to equal 2 and that means b repeats. So we just need to use the value to devide the remain of a,and then caculate at most x times to get the answer.

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

Can someone please help me understand why this submission of mine for problem A gives WA at test 5.

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

Problem D i Got MLE in test 35

please help,though my array is arr[2000][2000] it shows MLE solution

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

For problem C: I have a test case for which my solution which got accepted will fail and I have no idea how many other solutions will fail

test case

my code : 88891597

expected 0 , output 1 => 5

HolkinPV I think this test case should be added. maybe only my solution fails.

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

Alternative approach for Problem C: Let, l=last term of A.P a= First term of A.P d=Common difference Then, n( Required number of terms) = (l-a)/d+1 and Sum of all terms = [n*(l+a)]/2

Using difference of sum of actual array and desired sum(computed using parameters l,a and d) gives us the left element(which must be included to make all elements of array follow the Arithmetic Sequence for given a,l and d. Ambiguous cases need not be worried out, all such cases can be judged as they don't follow the mathematical equations mentioned. https://codeforces.net/contest/382/submission/104538828