Sereja's blog

Codeforces Round #167 tutorial
By Sereja, 12 years ago, In English

272A - Dima and Friends

We will bruteforce number of fingers that will be show Dima, then if total sum of fingers = 1 modulo (n+1), Dima will clean the room. So we should increase answer if the remaining part after division by (n+1) is not 1.

272B - Dima and Sequence
First of all — f(i) is number of ones in binary presentation of number. We will repair all numbers to functions of them. Now we have to find number of pairs of equal numbers. Lets Q[i] — number of numbers with i bits, the answer will be sum of values Q[i]*(Q[i]-1)/2 for all i.

273A - Dima and Staircase
Lets L will be the answer after last block, last block was (w1, h1), next block is (w2, h2). Next answer will be max(L+h1, A[w2]), where A — given array. At the beggining we can suppose that L = 0, w1 = 0, h1 = 0.

273B - Dima and Two Sequences
Not hard to understand that answer will be (number of numbers with first coordinate = 1)! * (number of numbers with first coordinate = 2)! * ... * (number of numbers with first coordinate = 10^9)!/(2^(number of such i = 1..n, that Ai=Bi)). The only problem was to divide number with non prime modulo, it can be easely done if we will count number of prime mulpiplies=2 in all factorials. Then we can simply substract number that we need and multiply answer for some power of 2.

273C - Dima and Horses
Not hard to understand that we have undirected graph. Lets color all vetexes in one color. Then we will find some vertex that is incorrect. We will change color of this vertex, and repeat our search, while it is possible. After every move number of bad edges will be decrease by 1 or 2, so our cycle will end in not more then M operations. So solutions always exists and we need to change some vertex not more then M times, so we will take queue of bad vertexes and simply make all operations of changes.

273D - Dima and Figure
Good picture is connected figure that saticfy next condition: most left coordinates in every row of figure vere we have some cells will be almost-ternary, we have the same situation with right side, but here we have another sign. So it is not hard to write dp[i][j1][j2][m1][m2] numbr of figures printed of field size i*m, where last row contain all cells from j1 to j2, the most left coordinate will be m1, the most right coordinate will be m2. But it is not enough. We have to rewrite it in way that m1 will mean — was there some rows j and j+1 that most left coordinate if row j is bigger then most left coordinate in j+1. So now it is not hard to write solution with coplexity O(n*m*m*m*m). But we should optimize transfer to O(1), is can be done using precalculations of sums on some rectangels.

273E - Dima and Game
will be added soon.

  • Vote: I like it
  • +12
  • Vote: I do not like it

Comments Comments (43)
| Write comment?
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

[Deleted]

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 6   Vote: I like it +6 Vote: I do not like it

    [Deleted]

    Sorry, because of my browser's error.

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In solve D(div2), why we divided by 2^(number of such i = 1..n,that Ai=Bi)? I don't understand, please proof.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Consider the influence of the position of pair(Ai,i) and pair(Bi,i). In one sequence,if we change the position of (Ai,i) and (Bi,i),that will not form a new sequence. But when we solve the problem, what we are calculating is that all different positions for all pairs with same x-coordinate. And that contains the different positions of Ai and Bi. So we divide the answer with 2, because (Ai,i) and (Bi,i) will lead to 2 different answer, but in the problem they should be considered to be 1. For all different Ai==Bi, we divide the answer with 2^k where k is the number of pairs with Ai==Bi.

    → Reply
»
12 years ago, # |
  Vote: I like it +27 Vote: I do not like it

It seems there is a mistake in posting tutorial. English version of tutorial is TopCoder SRM announcement and the post itself is for 8 days ago!

→ Reply
»
12 years ago, # |
  Vote: I like it +17 Vote: I do not like it

I expected more detailed tutorial ...

→ Reply
»
12 years ago, # |
  Vote: I like it +6 Vote: I do not like it

the problem E(div 2), I want to know why it will operate at most M times?

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    I think DFS can explain it more easily.This solution is like magnetic repulsion.consider that there are two sets marked S1 and S2(at first S2 is empty),we pick one element from S1 that has more than one enemy in S1,then put it in S2,so bad edge will decrease,but in S2 maybe increase some bad edges and cause some bad elements,so we pick out these bad elements and put them into S1,and repeat this way. If there is a answer then each time the bad edges are decrease,and we can find a stable state.But i don't know how to prove that there must exist one answer.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      As you said, each time bad edges will decrease. If at some point, you cannot find a vertex to fix, then the solution is found. If not, you can always find a vertex to fix and the number of bad edges will decrease. The total number of bad edges is finite, therefore the process cannot go infinitely, cause each time the number of bad edges decrease by 1 or 2 or 3,(This is ensured by each horse having at most 3 enemies, so if a horse have more than 1 enemies, it will have 1 or 0 enemies in the other party) and the total number of bad edges cannot go below zero. Therefore the process will end and a solution will come.

      → Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it +7 Vote: I do not like it

C(div. 1). "Then we will find some vertex that is incorrect." what does it mean? What do you mean by saying "incorrect"?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Vertex (horse) is incorrect, if it has more than one enemy in other party.

    → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

How can we solve problem "Dima and Horses" by 2-SAT method? Thanks Actually, I don't know method 2-SAT.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't sure that this problem can be solved by 2-SAT.

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Isn't Problem D for Division 1 is supposed to solved in O(M*N*N) time? Don't need to keep track of m1 and m2, just keep that whether m1 < j1 or not and whether m2 > j2 or not, that is whether it has reached its leftmost cell and its rightmost cell.

→ Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Никак не пойму, как все-таки в D делать переход за O(1)?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    а вы поняли по каким правилам dp строится ?

    у меня идея подобная была, я трактовал m1 и m2 {0,1} — можно ли след-ий столбец расширить вниз/вверх соотв-но. здесь тоже так?

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Я мало что понял из разбора, но моем в моем "решении" за O(N^5) все так. И для перехода из состояния у меня нужно значение динамики в этом состоянии добавить к нескольким прямоугольникам на следующем "слое". Вот как-то надо сделать это быстро. Видимо загадочное "precalculations of sums on some rectangels" — это как раз то что нужно.

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Точно, спасибо.

          → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      create an array a[M][2][2][N+1][N+1]. a[i][k1][k2][j1][j2] stands for number of figures with last row i and last row has cells from j1 to j2 and k1 is 0 if j1 <= m1 else 1 and k2 is 0 if j2 >= m2 else 1. Then

      a[i][0][0][j1][j2] = a[i][0][0][j1+1][j2]+a[i][0][0][j1][j2-1]-a[i][0][0][j1+1][j2-1]+a[i-1][0][0][j1][j2].

      a[i][0][1][j1][j2] = a[i][0][1][j1+1][j2]+a[i][0][1][j1][j2+1]-a[i][0][1][j1+1][j2+1]+a[i-1][0][1][j1][j2]+a[i-1][0][0][j1][j2+1].

      a[i][1][0][j1][j2] is similar with a[i][0][1][j1][j2].

      a[i][1][1][j1][j2] = a[i][1][1][j1-1][j2]+a[i][1][1][j1][j2+1]-a[i][1][1][j1-1][j2+1]+a[i-1][1][1][j1][j2]+a[i-1][0][0][j1-1][j2+1]+a[i-1][0][1][j1-1][j2]+a[i-1][1][0][j1][j2+1].

      Note that if you use bottom up dp and do it in correct order you can actually omit the i and only use dp array of a[2][2][N+1][N+1]. So time complexity O(M*N*N) and memory space O(N*N).

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        what's the meaning of m1 and m2?

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          the most left and right coordinates of the figure

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            thanks,then how should I initialize the array a's state?I think I am not good at dynamic programming.

            → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

Так когда будет разбор на русском, я заждалься

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

    Ждать нечего — на английском разбор напоминает конспект разбора от Burunduk1 на каком-то чемпионате матмеха

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can Problem Setter post the solution of problem "Dima and Game"? Thank you so much.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    ya, I'm waiting for it too.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I will post it little bit later, sorry for so long delay.

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

the tutorial is too simple,I want more details.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In the problem "Dima and Horses",why does this problem always can be worked out,i means never have the answer with -1.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If there is at least one unsatisfied vertex, then it can be moved to another group and the overall number of conflicts is decreased(otherwise we are done). Problem is obviously solved when the number of conflicts is zero. Since we can decrease the number of conflicts whenever the problem is not yet solved, then we simply do it. One day the process will finish because the initial number of conflicts is finite.

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

273E — Dima and Game . please give this problem tutorial . Sereja

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For 273A/272C (Div 2 C), the general case when blocks can fall from any position (not just 0) can be solved using lazy propagation of segment tree (for range max update and range max query) in $$$O(m\cdot \log n)$$$. See my submission 81852819

→ Reply
»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

11 years have passed, and there is still no tutorial for problem 273E ...

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

11 years have passed, and there is still no tutorial for problem 273E ...

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

273E — Dima and Game

will be added soon.

→ Reply