### ch_egor's blog

By ch_egor, 11 months ago, translation,

Thanks for the participation!

1248A - Integer Points was authored by voidmax and prepared by gritukan.

1248B - Grow The Tree was authored by voidmax, _kun_ and prepared by wrg0ababd.

1239A - Ivan the Fool and the Probability Theory was authored and prepared by voidmax.

1239B - The World Is Just a Programming Task (Hard Version) was authored by V--gLaSsH0ldEr593--V and prepared by DebNatkh.

1239C - Queue in the Train was authored by _meshanya_ and prepared by Sehnsucht.

1239D - Catowice City was authored by platypus179 and prepared by Nebuchadnezzar.

1239E - Turtle was authored by voidmax and prepared by _kun_.

1239F - Swiper, no swiping! was authored and prepared by voidmax.

• +52

 » 11 months ago, # |   +38 can someone prove that answer for div2c is 2(Fn+Fm−1)?
•  » » 11 months ago, # ^ |   +77 This was my logic during the contest. Consider each of the cells as a point and we connect cell A and B with an edge if they're adjacent, and they have the same color. Note that no edges can share their endpoints ( otherwise, a cell should share its color with two or more neighboring cells ).Also note that if a cell at coordinate (x, y) is connected with (x, y + 1), then (x + N, y) and (x + N, y + 1) are also connected for all valid integer N ( This can easily be seen by assuming each of their color ). The same holds for the case where (x, y) is connected with (x + 1, y).Now we see that there are no cases where there are both horizontal and vertical edges. So our answer is (The number of shapes where there are no horizontal edges) + (The number of shapes where there are no vertical edges) — (The number of shapes where there are no edges).Now the number of shapes where there are no horizontal edges are completely determined by the state of the first column by our previous observation. And this number is eactly the N-th fibonacci number times two (The number of the positionings of the edges are F_n, and you can alternate color for each cases).The second term is M-th fibonacci number times two similarly.The last term is obviously 2.Therefore, the answer is (F_n + F_m — 1) * 2
•  » » » 11 months ago, # ^ |   0 got it, thanks
•  » » » 11 months ago, # ^ |   +6 As per the editorial "this problem equal to the same problem about strip. Answer for the strip is 2Fn." Can any one say which problem is he talking about?can anyonne give the link of this problem
•  » » » » 11 months ago, # ^ | ← Rev. 2 →   +55 This is a pretty well-known problem."What is the number of sequences of 1 and 2 such that they sum up to an non-negative integer N?"The answer is N-th fibonacci number F_N and it's easy to show it inductively.First, when N = 0, there is one empty sequence so the answer is 1 which is equal to F_0. Similarly, when N = 1, there is one sequence with exactly one 1 so the answer is 1 = F_1.Now suppose N >= 2 and suppose you have proved that the answer is F_k for all k < N. Then, when you consider a sequence summing up to N, the last element is either 1 or 2. Since there are F_(N-1) of them of the first type and F_(N-2) of the second type, the answer for N is F_(N-1) + F_(N-2) = F_N.And sorry I don't know any link to this kind of problem.
•  » » » » » 4 months ago, # ^ |   +6 Thanks,bro for such a beautiful explanation!
•  » » » » 11 months ago, # ^ |   +6
•  » » » 11 months ago, # ^ |   0 Thank you so much got it!
•  » » » 5 months ago, # ^ |   0 The no. of shapes where there are no horizontal edges will be Fn:Proof: let cnt[n] will be the answer for n vertices. Assuming we know the answer for k < n; Then,Adding a new vertex at the end of the given set of n-1 vertices, there are only 2 new ways for this new vertex — either connect to n-1th vertex or not connect at all. cnt[n] = 0, initialized.Case 1: make en edge with (n — 1)th vertex, then cnt[n] += cnt[n-2], since for no. of ways with (n — 2) vertices, we can add in all of those ways 1 edge from n-1 to n, without any overlap/shared edge gauranteed (since (n — 1)th and (n-2)th are not connected in counting ans for n-2 vertices only).Case 2: make no edge for nth vertex with (n-1)th vertex, then cnt[n] += cnt[n-1]. Since, for all the positions/arrangements of edges with (n-1) vertices, we can add the answer for nth vertex, again ensuring no adjacenet edges since we are not connecing nth and (n-1)th vertex.Thus cnt[n] = cnt[n-1] + cnt[n-2]. Hence cnt[n] = Fn.
•  » » 11 months ago, # ^ |   +11 Some observations: if you repeat some color horizontally, you cannot repeat any color vertically, and vice versat if you repeat some color horizontally, the colors of all cells in the whole 4-columns slice is defined uniquely Let's count the number of "horizontal colorings".Define $d_{k}$ the number of horizontal colorings of the first $k$ rows (no matter how many columns there is).There are two options to fill $k$-th row: Fill each cell with the opposite color of the upper cell: $a_{ij} = \bar{a}_{i-1 j}$ Fill each cell with the same color of the upper cell: $a_{ij} = a_{i-1 j}$ In addition, you cannot apply the $2^{nd}$ option more then twice in a row. It's easy to see that other "mixed" variants break the rules.Let's assume that the first row is filled in some correct way. Therefore, the number of horizontal colorings $d_{k} = d_{k-1} + d_{k-2} = f_{k}$ The same formulae stands for vertical colorings.The only coloring that presents in both of vertical and horizontal colorings is pure chess coloring. And you need to multiply the result by 2 because you defined the first row in some fixed way and colors can be the opposite.
•  » » » 11 months ago, # ^ |   0 thanks
•  » » » 11 months ago, # ^ | ← Rev. 2 →   0 you made the question worthy.
•  » » » 11 months ago, # ^ |   0 If color is repeated horizontally, then the whole 3-columns slice would be filled right? so if you repeat white we can fix 3 columns wwb , the fourth column can be b or white. May I know how it is 4 columns?
•  » » » » 11 months ago, # ^ | ← Rev. 2 →   0 If you have ...ww... then you must place the black both before and after the repeat: ..bwwb..
•  » » 9 months ago, # ^ |   0 Here's a late reply but maybe people who will see this editorial in the future will find it helpful.Consider that you have a valid coloring for the first row, you will notice that the coloring of this row enforces the coloring of the entire grid. Similarly for the first column. We have (-1) since the case where white and black alternates in each row and in each column is counted twice (with F(n) and with F(m)). **** Answer = T(n,m) = 2 * (F(n) + F(m) — 1)Where F(x) is the number of ways we can fill a (1 by x) grid using blocks of size 1x1 and blocks of size 1x2. If x >= 2, we can choose to put a 1x1 block at the beginning (we're left with F(n-1) choices) or put a 1x2 block at the beginning (we're left with F(n-2) choices) -> F(n) = F(n-1) + F(n-2) -> Fibonacci!! (Note: Equivalent to the problem where you're asked to the find the number of ways to climb n stairs if you can at each step go to the next level or to the one next to the next level).We multiply the factor (F(n) + F(m) — 1) by 2 since flipping black and white will keep the grid coloring valid.
•  » » » 4 months ago, # ^ |   0 I did not understand that why the coloring of first row would enforce coloring of entire grid. Let's assume rows=2 and cols=4. Let us color the first row as 1 0 1 0. Here,1=BLACK , 2=WHITE. So , we can color the second row as either 1 0 1 0 or 0 0 1 0. In both the cases the condition is satisfied . Can anyone of you please help me out??
•  » » » » 4 months ago, # ^ |   0 Let me clear it out. Consider 2 rows and 4 columns. First we consider those cases where we have only horizontal adjacent colors. So if we have 1 0 1 0 in the first row(1 = Black and 2 = White), then we'll only take the case of 0 1 0 1 because if we consider 1 0 1 0 in the second row, then it is the case of having vertical adjacent colors which will be counted again where we count the number of ways of filling 2X1 Grid.
•  » » » » » 4 months ago, # ^ |   0 Got it.Thank you so much!!
 » 11 months ago, # |   +3 Can any one Explain div2 C problem more clearly.
 » 11 months ago, # | ← Rev. 3 →   +22 Div2 C I thought of it this way during the contest but Mahotsukai 's approach is more better and straight forward. Hint1Think about the number of ways the first row can be formed. Hint2Try assigning colors to the second row for all the ways in which two same colors are adjacent (atleast once) in the first row Hint3For all the ways in which two same colors are adjacent (atleast once) in the first row there is only one valid way of assigning colors in the second row.There are only two ways in which no two same colors are adjacent and that is if the colors alternate. So F[m] indicates the total number of ways in which we can assign colors to the first row.As in (F[m]-2) ways two same colors are adjacent (atleast once) the coloring of the grid becomes fixed as soon as we color the first row. For the remaining two ways we know that the remaining rows only depend on first element of each row so answer for those two ways is equal to the number of ways we can color the first column which is F[n].
•  » » 11 months ago, # ^ |   +7 Great explanation.
•  » » 11 months ago, # ^ |   0 How to find F[m] or F[n] i.e total no of ways in which we can assign colors to the first row.
•  » » » 11 months ago, # ^ |   0 F[m] represents the mth fibonacci no.We get the result from the strip problem explained by Mahotsukai above
•  » » 11 months ago, # ^ |   0 detailed analysis
 » 11 months ago, # |   +4 $O(n)$ solution to Div2B: Since the range is only $10^4$, use element counting to sort or find the median?
•  » » 11 months ago, # ^ |   0 Can you please elucidate a bit?
•  » » » 11 months ago, # ^ | ← Rev. 2 →   +4 Look up "counting sort". Basically: Make a $cnt$ array with maximum index $\geq \max(a)$ Iterate through array $a$, incrementing $cnt[a_i]$ each time You can now sort $a$ by iterating through the counts in $cnt$, or directly find the sums of the two sets desired.
 » 11 months ago, # |   +23 Here is my approach for D. All indices from 1 to $n$ have to appear in our solution. This might sound obvious but it's probably the most important observation. SpoilerIf we pick a set of indices for residents, we must pick the complement set for cats. Try to convert the bipartite graph of residents and cats to a graph of only residents. Cats are useless. (I'm a dog person) SpoilerIgnore all the edges connecting same indices. Build a directed graph with the remaining edges. If we pick a resident, who else must we pick? SpoilerFind all SCCs for our graph. If there is only one, it means we have to pick all residents thus there is no answer. Otherwise, just pick one SCC without outgoing edge.
•  » » 11 months ago, # ^ | ← Rev. 3 →   -8 Why do we need to pick SCCs?
•  » » » 11 months ago, # ^ |   +3 If you pick a node $x$, you'll have to pick all the nodes that can be visited from $x$. Our goal is to pick a set of nodes such that starting from any node in this set, we can't visit a node that is not in this set. Think about the easy case where the graph has no cycle, we can simply pick a node without outgoing edge. If the graph has cycles, we can compress it into a new one without cycle by finding SCCs.
•  » » » » 11 months ago, # ^ |   0 Ohh ok thanks!
 » 11 months ago, # | ← Rev. 2 →   0 Can someone tell me why I keep getting Runtime Errors on test 10 of 1239A? I thought I fixed REs by changing the recursion limit but maybe not. Test 10 is (1, 100000). import sys sys.setrecursionlimit(999999999) def f(n): if n == 1: return 1 elif n == 2: return 2 else: return f(n-1) + f(n-2) a, b = tuple(map(int, input().split())) print(((f(a)+f(b)-1)*2)%(10**9+7)) 
•  » » 11 months ago, # ^ |   0 your recursive tree goes exponentially, and that probably causes memory overflow
•  » » 11 months ago, # ^ |   +3 Time complexity of recursive Fibonacci is exponential.
•  » » 11 months ago, # ^ | ← Rev. 3 →   0 I demand you to stop RIGHT THERE NO STOP You're calculating nth fibonacci number explicitly NO STOPMOD IT EVERY TIME YOU CALCULATE PLEASEAlso you did not use memoization try this M = 10 ** 9 + 7 # MODULO array = [0] * 100010 # Extra because im bad array[0] = 1 array[1] = 1 # array[2] = 2 def f(n): if array[n] == 0: array[n] = (f(n — 1) + f(n — 2)) % M return array[n] # To initialize, don't use sys.setrecursionlimit(99999). It's bad. for i in range(1, 100010): f(i) # Calculates the value but doesn't do anything with it # Now you can do # a, b = tuple(map(int, input().split())) a, b = map(int, input().split()) # No need tuple, python is smart :) print (( (f(a)+f(b)-1)*2 ) % M) 
•  » » » 10 months ago, # ^ |   +1 Thank you so much for helping me! Now I can solve recursion problems without getting TLEs or REs :)
•  » » » » 10 months ago, # ^ |   0 No problem lol seems like my ranting explanation didn't get any upvotes :P
•  » » » » » 10 months ago, # ^ |   +1 I think it would've got more than a dozen upvotes if the ranting part didn't exist lol
 » 11 months ago, # |   0 In D1 ,How can we arrive at that formula for cyclic Shifts?
 » 11 months ago, # |   +1 Why in D1 the answer is minimum prefix balaneces count.
•  » » 11 months ago, # ^ |   0 We reduce $cnt$ if we see "(" and increase $cnt$ if we see ")".Let's calculate it on example: "))()(())(("Cnt: [-1, -2, -1, -2, -1, 0, -1, -2, -1, 0]The minimum of all $cnt$ (-2 here) is when we close all levels of brackets. Then we increase it again (opening new levels) and closing them, checking if we again closed all levels (when $cnt$ = minimum).Also we should check if last $cnt = 0$ (it means that we find opposite brackets for starting).Hope you understand it better)
•  » » » 11 months ago, # ^ | ← Rev. 2 →   0 You are supposed to swap reduce(decrease is better) and increase in the first line of your reply.
•  » » » 11 months ago, # ^ |   0 Can you please explain the polyline part?
 » 11 months ago, # |   0 Is there any resource where I can learn about brackets and their corresponding properties?
 » 11 months ago, # |   +30 the worst editorial ever
•  » » 11 months ago, # ^ |   +8 It is written on higher level than most of div2 participiants could understand.C editorial should be extended as for me.
 » 11 months ago, # |   0 liked the second problem
 » 11 months ago, # |   +27 Another way to thing about div1D:From each house we need to choose either the cat or the resident. Let $x_i$ be a logical variable equal true if we take resident from $i$-th and false if we take the cat. Each pair of resident and cat knowing each other is one 2-SAT constraint on those variables. This 2-SAT has clearly two solutions: all variables set to true and all set to false, but we are interested in finding another solution. A pretty standard problem is: given 2-SAT check if it has a unique solution, and if not: find two different solutions. The way to do it is: first find any solution (in case of this problem we don't need to run 2-SAT, we can just set all variables to true/false). Now run through all components set to false, check if a component: has no edges to components set to false, and no edges to component containing negations of variables from current component then flip it and its negation and terminate algorithm.This is almost what we need to do in this problem, but we have two solutions and want to find a third one. We can do a simple trick: check two cases: either x_1 is true or not. If we add constraint that x_1 is true in case 1, or false in case 2 and in each case check if the 2-SAT has more than one solution.
•  » » 11 months ago, # ^ |   0 Awesome! Didn't know about the problem you refer to, It turns that giving problems for contests is very useful sometimes.
•  » » » 11 months ago, # ^ |   0 Didn't know about the problem you refer to The theory of SAT and specifically 2-SAT problems is well-known. It's not "the problem" any more than BFS.This isn't some kind of special case of 2-SAT. It's direct textbook 2-SAT, you don't even need to know that for each condition/edge "if x then y", you need a condition "if !y then !x" in the graph too, since they correspond to different endpoints of an edge, so the symmetry is clear. The only thing you need to know is that it behaves "nicely" when you compress SCCs — either there's no solution or any greedy assignment works.
 » 11 months ago, # | ← Rev. 2 →   +3 div2-Queue in the TrainWhy is my method wrong?wa in fourth test point //Sort by time in ascending order sort(a,a+n,cmp); //now means now's time ll now=0,i=0; //que is a heap sort by person's position while(i
 » 11 months ago, # |   0 Can someone explain the meaning of line This problem is same problem about strip...
•  » » 11 months ago, # ^ |   0 Let's fill the first row in some correct way. Then, the way you fill all the other rows is forced (this is the key observation for the problem). So, to get the answer to the problem you actually just need to find the number of ways to fill the first row (the first "strip").There are some technicalities. Let's assume that the top left cell is always white. We will need to multiply the eventual answer by 2 to account for symmetry (when the top left cell is black).Let $f(k)$ be the number of ways to fill a "strip" of length $k$.1) We fill the first row. The number of ways for this is $f(n)$. All other rows depend on the first row.2) We fill the first column. The number of ways for this is $f(m)$. All other columns depend on the first column.3) Notice that both in 1) and 2) we count the "chess board" case, where the color of every cell is different to all its neighbors'. This is why we subtract 1, because we want to count each board state exactly once.We now have a total of $f(n) + f(m) - 1$ ways. We multiply by 2 to account for the case where the top left cell is black (and thus flip the colors of all cells). So the answer is $2*(f(n) + f(m) - 1)$.The only thing left to do is to find out how to calculate $f(i)$ for some $i$. I think this is literally one of the simplest ways to use dynamic programming.$f(0) = 1$$f(1) = 1$$f(i) = f(i-2) + f(i-1)$ for $i \geq 2$
•  » » » 11 months ago, # ^ |   0 Brilliant explanation.
•  » » » » 11 months ago, # ^ |   0 Amazing explanation. But the number of ways for filling the first row should be f(m) since the length of strip is m , not n.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 the thing i was confused about is that how do you make sure that f(n) and f(m) don't coincide on the first cell (1,1)? for example, if you fill the first row, then that cuts off like half of the options for the first column (because (1,1) is now forced white or black). and i understand parity comes into play so multiply by 2, but still, won't it still cut off half of the options despite parity?
•  » » » 4 months ago, # ^ |   0 now i'm clear thanks for this Explanation
 » 11 months ago, # |   0 "So now we need to split our set into two of equal size, so that the maximum sum is smallest possible."This statement is misleading, the first time I read it I thought you might mean that the optimal solution is to split the 2n items into to groups, each consisting n items, one of which is the first line and the other is the second line of the answer.However, this is untrue. Consider the test case 4 0 3 4 4 4 4 3 2 This is the optimal solution while the way to split these into two set of equal sum would lead to 4 0 4 4 4 4 3 3 2 Which answer is 14, larger than 13 in the former case.Please look into it ch_egor
•  » » 11 months ago, # ^ |   0 You should split 2n-2 items. Two smallest will be start and finish.
•  » » » 11 months ago, # ^ |   0 Yeah, you are right. It's just the solution said nothing about that.I figured it out myself today though, you could see my submissions.
 » 11 months ago, # |   0 How to solve Div2B in O(n)
•  » » 11 months ago, # ^ |   0 It's overkill because you can just sort the elements in $O(n log n)$. But since $a_i \leq 10000$ you can use counting sort and solve it in $O(n + maxa)$.
 » 11 months ago, # | ← Rev. 2 →   +13 The editorial for E is wrong! So now we need to split our set into two of equal size, so that the maximum sum is smallest possible. No, because our path doesn't have $N$ elements. It has $N+1$, the top left and bottom right element are always included, and there are just $N-1$ differences $x_{i+1}-y_i$, which is obvious from the shifted first index! Alternatively, we want two sets with equal size $N+1$, but they're not disjoint!We can do knapsack DP e.g. if the states contain the difference (cost of our path) — (cost of the rest) without the top left and bottom right element, and if their values are (cost of our path) — (cost of the rest). However, we can do better and add bitsets.The problem with bitsets is that we need the values of states to be 0/1, so it's not straightforward. Let's sort all the elements in decreasing order. The top left and bottom right elements can be the smallest two of elements chosen for our path, since that maximises the chance of our path being taken. That means we'll have some state where we've chosen $N-1$ elements for our path out of the first $i$, their sum is $s$, then we want to choose the $i+1$-th element for our path too, and the last element we'd want to choose is $j > i+1$. Our path has sum $a_j + a_{i+1} + s$, the other path has sum $\sum a - s$ and we want their difference to be non-negative: $2s \ge \sum a - a_j - a_{i+1}$. Obviously, we need just the smallest such $s$.Now we can do knapsack DP with bitsets; the states are obviously ($i$, $s$, number of elements that summed up to $s$) and their values are just if it's possible to reach them. For each $i \ge N-1$, we then try all $j$, try to find the smallest $s$ that satisfies the above condition and if it gives the best answer so far, construct a solution. The time complexity is the same, except with a much better constant.
 » 11 months ago, # |   0 Can someone please explain Div 2 D(Hard)? I could not understand the polyline thing in the editorial. It would be really helpful if someone could elucidate it a bit with an example.
•  » » 11 months ago, # ^ |   0
•  » » » 11 months ago, # ^ |   0 What cases are we talking about in editorial? What are the indices of the brackets that we are switching in the editorial, in 4th and 5th para?
 » 11 months ago, # |   0 For div1F，what if a way between nodes-1 on nodes-2 have more than one edge between one node-1 and nodes-2?
•  » » 11 months ago, # ^ |   0 I realized bfs can solve my problem
 » 10 months ago, # |   0 64369202 Sorry, I want to know how this should be changed. What it shows is----Runtime error on test 4
 » 8 months ago, # |   0 For 1239D, if B' = Intersect(Q, R), how come to prove "some l in L lies in B'"?
 » 5 months ago, # |   0 Can someone tell if my understanding of Div2C/Div1A is correct?If there exist two adjecent cells with same color then one of two cases can happen: 1. Adjacent cells with same color are vertically adjacent. 2. Adjacent cells with same color are horizontally adjacent. Both cases cannot happen for the same board — if there is a strip such that case 1 holds true for it, then the rest of the board can either follow chessboard coloring, or case 1 coloring — but not case 2 coloring. Likewise for a strip colored according to case 2.No. of ways for case 1 is $F_n$, and for case 2 is $F_m$. Since only one of these two cases can happen for a particular board, total ways = $F_n + F_m$.But the 1 case where full board is colored according to chessboard coloring in counted in both $F_n$ and $F_m$, so we subtract it from either one, to get $F_n + F_m - 1$.For each of the $F_n + F_m - 1$, we can flip colors across entire board, so final answer = $2(F_n + F_m - 1)$.Is this correct?
 » 5 months ago, # |   0 In div2D1, It's written/hinted in the tutorial that O(n^3) works but system testing giving TLE for such solution like I have implemented herePersonally, I also believe that n^3 (125000000) is too large and should get TLE but then why is it written in editorial as such?Thanks in advance!
 » 5 months ago, # |   0 In div1 Problem A, at 2*(F(n) + F(m) — 1) formula we are subtracting 1 because by adding F(n) , we have already covered one row ... is that so ??
•  » » 6 weeks ago, # ^ |   0 no...i think its beacuse chessboard case is included in both (no two same colored adjacent cells)
 » 5 months ago, # |   0 I don't understand these lines : "**Then find i— index of the minimum balance and perform a cyclic shift of the string by i to the left. The resulting line never has a balance below zero, which means it is a correct bracket sequence. Further we will work only with it**" , from div1 'B' editorial . Can anyone explain it?? Advance Thanks
 » 3 months ago, # |   0 Why is div 2 B $O(n\log(n))$, shouldn't it be $O(n+\log(n))$ because all of the lines can be sorted in $O\log(n)$, and the pieces are iterated through once.
 » 6 weeks ago, # |   0 Thank you. It was excellent information.