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.
[Deleted]
[Deleted]
Sorry, because of my browser's error.
In solve D(div2), why we divided by 2^(number of such i = 1..n,that Ai=Bi)? I don't understand, please proof.
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.
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!
Nobody cares
It was little mistake, sorry.
I expected more detailed tutorial ...
the problem E(div 2), I want to know why it will operate at most M times?
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.
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.
thanks to byijie and Bobgy.
no problem
What is meant by "bad edge"?
What is meant by "bad edge"?
an edge that is connecting two vertex in the same set.
C(div. 1). "Then we will find some vertex that is incorrect." what does it mean? What do you mean by saying "incorrect"?
Vertex (horse) is incorrect, if it has more than one enemy in other party.
How can we solve problem "Dima and Horses" by 2-SAT method? Thanks Actually, I don't know method 2-SAT.
I don't sure that this problem can be solved by 2-SAT.
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.
Никак не пойму, как все-таки в D делать переход за O(1)?
а вы поняли по каким правилам dp строится ?
у меня идея подобная была, я трактовал m1 и m2 {0,1} — можно ли след-ий столбец расширить вниз/вверх соотв-но. здесь тоже так?
Я мало что понял из разбора, но моем в моем "решении" за O(N^5) все так. И для перехода из состояния у меня нужно значение динамики в этом состоянии добавить к нескольким прямоугольникам на следующем "слое". Вот как-то надо сделать это быстро. Видимо загадочное "precalculations of sums on some rectangels" — это как раз то что нужно.
Лучше сделать переход дп не вперед, а назад, тогда перед переходами делаешь прекальк частичных сумм для текущего слоя, чтобы потом можно взять сумму любой подматрицы.
Точно, спасибо.
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).
what's the meaning of m1 and m2?
the most left and right coordinates of the figure
thanks,then how should I initialize the array a's state?I think I am not good at dynamic programming.
Так когда будет разбор на русском, я заждалься
Ждать нечего — на английском разбор напоминает конспект разбора от Burunduk1 на каком-то чемпионате матмеха
Can Problem Setter post the solution of problem "Dima and Game"? Thank you so much.
ya, I'm waiting for it too.
I will post it little bit later, sorry for so long delay.
the tutorial is too simple,I want more details.
In the problem "Dima and Horses",why does this problem always can be worked out,i means never have the answer with -1.
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.
273E — Dima and Game . please give this problem tutorial . Sereja
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
11 years have passed, and there is still no tutorial for problem 273E ...
11 years have passed, and there is still no tutorial for problem 273E ...
273E — Dima and Game
will be added soon.