Thanks for the participation!
1248A - Integer Points was authored by voidmax and prepared by vintage_Vlad_Makeev.
1248B - Grow The Tree was authored by voidmax, cdkrot 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 vintage_Vlad_Makeev 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 budalnik.
1239E - Turtle was authored by voidmax and prepared by cdkrot.
1239F - Swiper, no swiping! was authored and prepared by voidmax.
can someone prove that answer for div2c is 2(Fn+Fm−1)?
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
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
got it, thanks
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
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.
Thanks,bro for such a beautiful explanation!
Here is the Link
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.
Thanks bro , you had the best explaination among all these here
Some observations:
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:
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.
thanks
you made the question worthy.
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?
If you have
...ww...
then you must place the black both before and after the repeat:..bwwb..
Nice explanation
I am finally got this problem solution idea thanks a lot :)
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.
Can any one Explain div2 C problem more clearly.
Div2 C I thought of it this way during the contest but Savior-of-Cross 's approach is more better and straight forward.
Think about the number of ways the first row can be formed.
Try assigning colors to the second row for all the ways in which two same colors are adjacent (atleast once) in the first row
For 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].
Great explanation.
$$$O(n)$$$ solution to Div2B: Since the range is only $$$10^4$$$, use element counting to sort or find the median?
Can you please elucidate a bit?
Look up "counting sort". Basically:
Here is my approach for D.
If we pick a set of indices for residents, we must pick the complement set for cats.
Ignore all the edges connecting same indices. Build a directed graph with the remaining edges.
Find 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.
Why do we need to pick SCCs?
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.
Ohh ok thanks!
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).
your recursive tree goes exponentially, and that probably causes memory overflow
Time complexity of recursive Fibonacci is exponential.
I demand you to stop RIGHT THERE NO STOP You're calculating nth fibonacci number explicitly NO STOP
MOD IT EVERY TIME YOU CALCULATE PLEASE
Also you did not use memoization try this
Thank you so much for helping me! Now I can solve recursion problems without getting TLEs or REs :)
No problem lol seems like my ranting explanation didn't get any upvotes :P
I think it would've got more than a dozen upvotes if the ranting part didn't exist lol
In D1 ,How can we arrive at that formula for cyclic Shifts?
Why in D1 the answer is minimum prefix balaneces count.
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)
You are supposed to swap reduce(decrease is better) and increase in the first line of your reply.
Is there any resource where I can learn about brackets and their corresponding properties?
the worst editorial ever
It is written on higher level than most of div2 participiants could understand.
C editorial should be extended as for me.
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.
Awesome! Didn't know about the problem you refer to, It turns that giving problems for contests is very useful sometimes.
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.
div2-Queue in the Train
Why is my method wrong?
wa in fourth test point
Can someone explain the meaning of line This problem is same problem about strip...
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$$$
Brilliant explanation.
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.
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?
"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
This is the optimal solution while the way to split these into two set of equal sum would lead to
Which answer is 14, larger than 13 in the former case.
Please look into it ch_egor
You should split 2n-2 items. Two smallest will be start and finish.
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.
How to solve Div2B in O(n)
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)$$$.
The editorial for E is wrong!
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.
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.
my comment
For div1F,what if a way between nodes-1 on nodes-2 have more than one edge between one node-1 and nodes-2?
I realized bfs can solve my problem
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?
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 here
Personally, 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!
My solution O(n^3)
As you can see it passed with 732 ms. I dont see much (or any) difference in our solution. So i guess, please submit the solution again with
at first just as i used and also change endl to \n (it also saves time)
if u still get tle, try chaning cin and cout to scanf and printf respectevly. (Although i dont think TLE will come)
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 ??
no...i think its beacuse chessboard case is included in both (no two same colored adjacent cells)
Thank you. It was excellent information.
I found this video on YouTube for div2C.