### Sereja's blog

By Sereja, 9 years ago,

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

• +12

 » 9 years ago, # | ← Rev. 2 →   0 [Deleted]
•  » » 9 years ago, # ^ | ← Rev. 6 →   +6 [Deleted]Sorry, because of my browser's error.
 » 9 years ago, # |   0 In solve D(div2), why we divided by 2^(number of such i = 1..n,that Ai=Bi)? I don't understand, please proof.
•  » » 9 years ago, # ^ |   +6 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.
 » 9 years ago, # |   -8 "brtueforce"? I think you mean "bruteforce"
•  » » 9 years ago, # ^ |   0 I think there are a lot of small mistakes. Anyway (as we like to read the tutorial as soon as possible) it's acceptably
 » 9 years ago, # |   +27 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!
•  » » 9 years ago, # ^ |   -24 Nobody cares
•  » » » 9 years ago, # ^ |   +6 It was little mistake, sorry.
 » 9 years ago, # |   +17 I expected more detailed tutorial ...
•  » » 9 years ago, # ^ |   -22 Your expectation failed. Yours Cap
 » 9 years ago, # |   +6 the problem E(div 2), I want to know why it will operate at most M times?
•  » » 9 years ago, # ^ | ← Rev. 2 →   +4 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.
•  » » » 9 years ago, # ^ |   +3 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.
•  » » » » 9 years ago, # ^ |   0 thanks to byijie and Bobgy.
•  » » » » » 9 years ago, # ^ |   0 no problem
•  » » » » » 9 years ago, # ^ |   0 What is meant by "bad edge"?
•  » » » » 9 years ago, # ^ |   0 What is meant by "bad edge"?
•  » » » » » 9 years ago, # ^ |   +1 an edge that is connecting two vertex in the same set.
 » 9 years ago, # | ← Rev. 3 →   +7 C(div. 1). "Then we will find some vertex that is incorrect." what does it mean? What do you mean by saying "incorrect"?
•  » » 9 years ago, # ^ |   0 Vertex (horse) is incorrect, if it has more than one enemy in other party.
 » 9 years ago, # | ← Rev. 2 →   0 How can we solve problem "Dima and Horses" by 2-SAT method? Thanks Actually, I don't know method 2-SAT.
•  » » 9 years ago, # ^ |   0 I don't sure that this problem can be solved by 2-SAT.
•  » » » 9 years ago, # ^ |   0 But in Problem Tags of "Dima and Horses" (in Div 2), there is "2-sat". Can anyone help me? thanks
 » 9 years ago, # |   0 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.
 » 9 years ago, # |   +3 Никак не пойму, как все-таки в D делать переход за O(1)?
•  » » 9 years ago, # ^ |   +3 а вы поняли по каким правилам dp строится ?у меня идея подобная была, я трактовал m1 и m2 {0,1} — можно ли след-ий столбец расширить вниз/вверх соотв-но. здесь тоже так?
•  » » » 9 years ago, # ^ |   +3 Я мало что понял из разбора, но моем в моем "решении" за O(N^5) все так. И для перехода из состояния у меня нужно значение динамики в этом состоянии добавить к нескольким прямоугольникам на следующем "слое". Вот как-то надо сделать это быстро. Видимо загадочное "precalculations of sums on some rectangels" — это как раз то что нужно.
•  » » » » 9 years ago, # ^ |   +8 Лучше сделать переход дп не вперед, а назад, тогда перед переходами делаешь прекальк частичных сумм для текущего слоя, чтобы потом можно взять сумму любой подматрицы.
•  » » » » » 9 years ago, # ^ |   0 Точно, спасибо.
•  » » » 9 years ago, # ^ | ← Rev. 3 →   0 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. Thena[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).
•  » » » » 8 years ago, # ^ |   0 what's the meaning of m1 and m2?
•  » » » » » 8 years ago, # ^ |   0 the most left and right coordinates of the figure
•  » » » » » » 8 years ago, # ^ |   0 thanks,then how should I initialize the array a's state?I think I am not good at dynamic programming.
 » 9 years ago, # | ← Rev. 2 →   +4 Так когда будет разбор на русском, я заждалься
•  » » 9 years ago, # ^ |   +27 Ждать нечего — на английском разбор напоминает конспект разбора от Burunduk1 на каком-то чемпионате матмеха
 » 9 years ago, # |   0 Can Problem Setter post the solution of problem "Dima and Game"? Thank you so much.
•  » » 9 years ago, # ^ |   0 ya, I'm waiting for it too.
•  » » 9 years ago, # ^ |   0 I will post it little bit later, sorry for so long delay.
 » 8 years ago, # |   0 the tutorial is too simple,I want more details.
 » 7 years ago, # |   0 In the problem "Dima and Horses",why does this problem always can be worked out,i means never have the answer with -1.
•  » » 7 years ago, # ^ |   0 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.
 » 6 years ago, # | ← Rev. 2 →   0 273E — Dima and Game . please give this problem tutorial . Sereja
 » 5 years ago, # |   0 It's very good
 » 4 years ago, # |   0 For 272A, why it is error when my program print 1 as the out of the first example input? It is embarrassing.
 » 3 years ago, # |   0 please anybody help me in Dema And Staircase problem 167 div 2
 » 2 years ago, # |   0 Problem A, which is supposed to have multiple answers is only accepting single/ specific answers.
 » 17 months ago, # |   0 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