### LeiviniaBirdway's blog

By LeiviniaBirdway, history, 3 months ago, ,

1245A - Старая добрая раскраска чисел

Tutorial
Solution

1245B - Камень-ножницы-бумага с ограничениями

Tutorial
Solution

1245C - Аппарат Констанции

Tutorial
Solution
Solution (Arpa)

1245D - Шичикуджи и электросеть

Tutorial
Solution
Solution (PikMike)

1245E - Хиякугоку и лестницы

Tutorial
Solution

1245F - Даниэль и весенняя уборка

Tutorial
Solution

• +191

 » 3 months ago, # |   0 Auto comment: topic has been updated by keima915 (previous revision, new revision, compare).
 » 3 months ago, # |   +9 Auto comment: topic has been updated by keima915 (previous revision, new revision, compare).
 » 3 months ago, # | ← Rev. 2 →   +27 fastest editorial :D It also shows that the blog was made 4 hours ago
•  » » 3 months ago, # ^ |   +25 even made before the contest :) This round is excellent, good job!
 » 3 months ago, # |   0 orz keima915Please, don't stop creating CF rounds!!
•  » » 3 months ago, # ^ |   +27 Sorry, what is orz mean?
•  » » » 3 months ago, # ^ |   +40 Orz (or more commonly, orz) is an emoticon that represents someone who has fallen over or is bowing down on their knees and perhaps pounding their head on the floor. The o is the head, the r is the arms and upper torso, and the z is the rest of the body and legs.
•  » » » » 3 months ago, # ^ |   +55 I think it's easier to understand =))
•  » » » » » 3 months ago, # ^ |   0 orz
•  » » » » 7 weeks ago, # ^ |   0 Codeforces community is awsome
•  » » » 3 months ago, # ^ | ← Rev. 2 →   +40 "orz" is a verb. The original meaning of "orz someone" is "kneel down for someone", and the extended meaning is "show respect to someone".
 » 3 months ago, # | ← Rev. 2 →   +60 A smooth Contest without any DDOS attack and any waiting judgement problem!
•  » » 3 months ago, # ^ |   +40 wooooo
 » 3 months ago, # |   +3 Thank you for so fast editorial! :)
 » 3 months ago, # |   +11 I solved A without knowing proof. =)))
•  » » 3 months ago, # ^ |   +7 Me too xD
•  » » 3 months ago, # ^ |   +8 Story of all solver of today's A xD
•  » » » 3 months ago, # ^ |   +3 very true !
•  » » 3 months ago, # ^ |   0 Can you please explain your approach. I'm unable to understand the editorial.
 » 3 months ago, # |   +1 Wow, the fastest editorial I've ever seen! Thanks for the round. Keep hosting rounds further!
 » 3 months ago, # |   +10 Fastest Tutorial ! Cool !
 » 3 months ago, # |   +5 I just hope there are 2:15 minutes
 » 3 months ago, # |   +17 (A) is the Chicken McNugget Theorem!
•  » » 3 months ago, # ^ |   +8 cool theorem name XD
•  » » 3 months ago, # ^ |   +18 This conclusion was also used in a problem of NOIP2017, whose name is Xiao Kai's doubt (小凯的疑惑 in Chinese). In fact, (A) is an excellent number theory problem. Thanks to keima915 for this perfect round. :)
•  » » 3 months ago, # ^ |   0 Can someone explain to me proof of Chicken McNugget Theorem (for n = 2)? Here are some of the resources I have tried comprehending but couldn't :(It is easy for $x > ab$. But how is it for $x > ab - a - b$.
 » 3 months ago, # |   +8 I remained stuck in problem 1 for an hour until I realized I have been reading the question all wrong...
 » 3 months ago, # | ← Rev. 3 →   +3 Is there any way to push dp value ahead for E? I was getting wrong answer for no ladders case, and I couldn't figure out why.After contest, I saw some solutions ( namely neal's solution, PS: please share some insight ), and I had missed the case when the player is at the last 6 squares, after which he will waste some moves standing there itself. How to implement this using push dp? I understand the pull from previous 6 version. Is it not possible to push in this case?
•  » » 3 months ago, # ^ |   +11 There is a theorem on bernoulli trials that says if there is a probability $p$ of an event happening on a turn, then the expected number of turns to reach the event once is $1/p$. With some logic you can see that for the closest 6 squares to the end, the answer will be 6 for all of them.
•  » » » 3 months ago, # ^ |   +3 This result is so beautiful. Thanks.
•  » » 3 months ago, # ^ |   +3 I implemented push dp for E, calculating p[i] for the possibility for square i to be reached, and dp[i] for the expectation of runs before reaching square i. Also precalculate to[i] for the endpoint for ladder which starts at i.Then this code can give currect answer to first two pretests: for(int i=1; i<100; i++){ int t = to[i]?to[i]:i; for(int j=max(i-6, 0); j<=i-1; j++){ int k = min(6, 99-j); // k is 6 except for last few squares p[t]+=p[j]/k; dp[t]+=p[j]*(dp[j]+1)/k; } if(p[i]>0) dp[i]/=p[i]; } auto ans = dp[99]; for(int i=1; i<=5; i++){ ans += p[93+i]*(i/6.)/(1-i/6.); // expectation of standing still } But later i found out that using this method you cannot judge optically whether using the ladder or not. Because this requires information from the upper values. So i think this problem can only be dp'ed from top to bottom.
•  » » » 3 months ago, # ^ |   0 I don't understand why you say 'requires information from the upper values'. In fact, it is the opposite, for every cell that is the top of some ladder(s) you require answer from the bottom of the ladder(s).
•  » » 3 months ago, # ^ |   +3 I get accepted using push DP in 64069972. I hope its helpful to you.
 » 3 months ago, # |   0 keima915 Thanks for the amazing round.
 » 3 months ago, # | ← Rev. 3 →   +9 I thought of solving D with MST but statement confused me and I gave up XD. Just came back after contest end to see the clarification.
•  » » 3 months ago, # ^ | ← Rev. 2 →   +8 It was indeed intended to be MST. To not get confused by statement, you can always simplify the statement.Simple idea here is, if all vertices are numbered from $1$ to $N$, then make a new vertex with number $0$, and for each $c_i$ given, make an edge from $0$ to $i$ with weight $c_i$, $1 \le i \le N$. This edge signifies making power station at $i$.Apart from this, make edges between $i$, $j$, as mentioned, in $O(n^2)$ time. Then, it is just simple MST.( EDIT: just realized Editorial has the same thing written xD ).
•  » » » 3 months ago, # ^ |   +3 Amazing explanation. Things just clicked for me after you added the explanation of an additional vertex $0$
•  » » 3 months ago, # ^ |   +3 Exactly D was very deceiving. At first I thought about MST. Then I realised, that constraints are very low, so MST shouldn't be the answer(and it was D question). so I started looking in some other direction. Something like $O(N^2)$. After the contest I realised, that my assumption was incorrect. The solution could be MST because though the number of nodes is less, Number of edges are very significant( in worst case around $4 * 10^6$).
•  » » 3 months ago, # ^ |   +6 Actually MST is a poosible solution, and once you saw this problem you might think of MST. Each city is a point in the graph, and you add an edge for each pair of points $(i, j)$ with weight $(k_i + k_j) \cdot (|x_i - x_j| + |y_i - y_j|)$. According to the statement, we can build a power station in any city. This can be solved by adding a point indexed $0$. For each point $i$ we add an edge between $i$ and $0$ with weight $c_i$, and this edge means to build a power station in city $i$ and costs $c_i$. Our purpose is to choose some edges to make all the points connected (including point $0$). And clearly it's the MST problem.However, we've got two algorithms to solve the MST problem — Kruskal and Prim. Kruskal needs to sort all the edges, so its time complexity is at least $O(m \log m)$. There are about $n^2$ edges in our graph, so maybe you'll get a TLE. Prim is different. It is similar to Dijkstra and has time complexity $O(n^2)$ and you can easily use it to get an AC in this problem.
•  » » » 3 months ago, # ^ |   +8 Kruskal still pass it.
•  » » » 3 months ago, # ^ |   0 So true... Got a TLE with Prim
 » 3 months ago, # |   0 Could someone help me figure out where am I going wrong in Problem D. Here is my submission 64039688. Thanks in advance.
•  » » 3 months ago, # ^ |   +3 I Had made the same mistake, found it by trying one of the later test cases. Try the following test case 6 802169 415058 438621 719382 427378 361095 938841 703007 651689 546630 543902 45803 928313110 402257489 40475518 321650025 335526487 752229521 91 19 18 39 15 99Correct answer:- 171488866 1 3 5 3 5 2 5 4 5 1 5 3 6
•  » » » 3 months ago, # ^ |   0 What was wrong in the logic of your code. Could you please elaborate
•  » » » » 3 months ago, # ^ |   0 We were picking the cities with min cost, then comparing its cost with cost if it was connected with any of the taken cities. This fails since like in the above test case. order of the cities acc. to thier cost would be 3 4 5 2 6 1 so we picked 3, then 4. connected it to 3. But here it would have been better to instead pick 5, connect 3 and 5 and then connect 4 to 5.
 » 3 months ago, # |   0 In case someone wants to know the reason behind dp[i]=dp[i-1]+dp[i-2]Eg: Suppose you want to know answer for uuuu, u =1 {u}, uu=2 {uu,w}, uuu=3 {uuu,uw,wu}. Think of uuuu as follows: Uuuu = u+ uuu (Just add u to the strings created by uuu). Also, Uuuu =w+uu (Just add w to the strings created by uu) considering w, because uu case would be considered in previous one)Hence, uuuu={u+(uuu,uw,wu)}+ {w+ (uu,w)}
•  » » 3 months ago, # ^ |   +1 Are you sure it is the reason? I suppose it's due to the fact that by pressing one button we can add either one or two symbols (m -> nn or n -> n) so the number of ways to get to i'th position is dp[i-1] + d[i-2] (e.g. in string "ann" dp[2] = 2 because we could've either written m->nn after "a", that's dp[i-2] ,or just added n in the end of "an", that's dp[i-1])
•  » » » 3 months ago, # ^ |   0 You are saying the same thing, your way of understanding it is a bit different than mine
 » 3 months ago, # | ← Rev. 2 →   0 Can anyone suggest me a solution of problem C using modular inverse?
 » 3 months ago, # |   +3 Can somebody explain me please what is wrong with this approach to problem B.Let dp[i][j][k] — maximal number of games we can win if we i times choose R, j times P and k times S.So if we are at condition r,p,s than we can do the following:if r+1 <= a than we can choose R one more time and move to r+1,p,s and if our opponent chooses S than we will win one more game so dp[r+1][p][s] = max(dp[r+1][p][s],dp[r][p][s]+1), if our opponent chooses something different dp[r+1][p][s] = max(dp[r+1][p][s],dp[r][p][s]).Also we remember that if wins we can get with now is bigger than we already know we can, than parent[r+1][p][s] = 1And we do the same for p and sAfter that we check if 2*dp[a][b][c] < n and say "NO"else we can win this game and recover the answer.
•  » » 3 months ago, # ^ |   0 Idea doesn't seem to be wrong. According to checker, you have printed only $9$ characters, whereas you should have $10$ chars for input$n=10, a=5, b=0, c=5, string = RPRSRSRPPS$Your output: $RSRRSRSSS$Actual output : $RRSRRSSSSS$
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 Thanks for your answer.That is strange,because when i do it in my pc it says SSSRRRRSSR and it's correct answer
•  » » » 3 months ago, # ^ |   0 ok,i got it, it was my previous submission. there i got situation where parent[r][p][s] == 0, so that means i cant get there but i didnt check for that. If i check it i cant find sol for this one at all
•  » » » » 3 months ago, # ^ |   0 Well, an easy way to solve it is greedily. DP is too complicated, and possibly could give TLE as well. Your solution looks like $O(10^8)$.Easier way is to solve greedily.If Bob plays $r_b$ Rocks, $p_b$ Papers, $s_b$ Scissors, and we have $a$ Rocks, $b$ Papers, and $c$ Scissors.Then maximum wins are $min(r_b,b) + min(p_b,c) + min(s_b,a)$.Then, just assign $min(r_b,b)$ places of Rocks in Bob's string by Paper. Similiarly for the rest.
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 I just quickly wrote the same DP code. ( Check it here. )It seems the problem is that you should initialize dp with $-1$ instead of $0$. Because in case you have Bob's string as $RRRRRR$ and you don't have any Paper with you, i.e. $b=0$, then answer is zero. But, since you are updating by checking strict inequality, parent is never updated, even though something like $SSS$ has parent $S$.Okay, I might be explaining it in a very bad way, but I think you get the gist of it. I have done similiar errors. Some basic question like, return index of maximum element in array. I initialize $mx = 0$ and $ind = -1$ and return $-1$, instead of actual index of an element with value $0$.
•  » » » » » 3 months ago, # ^ |   +7 I tried initialize dp as -1 and still get wa.After that i rewrote my whole dp once more and finally get ac. No idea what was wrong in my last one
 » 3 months ago, # |   0 WA for problem B. Can anyone figure out what's wrong in my code? Thanks in advance
•  » » 3 months ago, # ^ |   0 You append thing in the "out" variable only when alice can win, but you should append something when alice loses too.
•  » » » 3 months ago, # ^ |   0 Thanks a lot, murugappan_s
 » 3 months ago, # |   0 I am unable to understand the editorial for problem F.
 » 3 months ago, # |   +6 Can someone explain why my code is wrong.Link to submission:- https://codeforces.com/contest/1245/submission/64040834Logic Explained:-For every city, I calculate the minimum cost of providing electricity to it (either by joining with someother city or by installing a power station in it, the former includes adding an edge between the two cities and the latter introduces no new edge.) Then I calculate the cost for every connected component using dfs.Any help would be highly appreciated.Thanks in advance
•  » » 3 months ago, # ^ |   0 i also did a similar approach and got WA test case 13, see my comment
•  » » 3 months ago, # ^ | ← Rev. 3 →   +3 Test case 5 5 15 19 13 19 13 24 14 20 13 2 10 20 10 2 6 4 2 4 5 Credits goes to GLAYS More details : https://ibb.co/dD8sJcM
 » 3 months ago, # |   -26
 » 3 months ago, # |   +4 for D, what was the intended corner case for test case 13? here is my submission:64025515.my idea was: consider the graph where every node x is connected to every other node y with edge weight cost dist(x,y)*(k[x]+k[y]). for every node, join them with union find to the closest node in the graph, unless it is cheaper to just add a power station to that node (in this case, don't join this node to any other node). then, assign one power station (the cheapest one) for every connected component. can anyone point out the flaw in my algorithm? thanks.
•  » » 3 months ago, # ^ |   +6
•  » » » 3 months ago, # ^ | ← Rev. 2 →   +1 thanks! update: the mistake in my algorithm was that i wasn't considering the scenario where the node that has a cheaper power station cost than any neighboring connections could actually be "helpful" to its neighbors and lower the overall cost.
 » 3 months ago, # | ← Rev. 3 →   0 Who can explain proof for D from editorial? I stuck on the case, when there is smaller cost in component. Why is it true that putting power plant there gives more profit? I think myself understanding wrong this point. Here is my exmple breaking this statement: City1 : c = 10001, k = 1 City2 : c = 10001, k = 1 City3 : c = 10000, k = 2And let take coordinates such as dist(City1, City2) = 2, dist(City1, City3) = dist(City2, City3) = 100let our optimal city to be City1 There are only 3 cases: Leave all without changes. Then we have cost = 10000 + 2 * (1 + 1) + 100 * (1 + 2) = 10403 Assign new power plant at City3. Obviously, cost > 20000 Reassign power plant to City3. Then cost will be 10001 + 100 * (1 + 2) + 100 * (1 + 2) = 10601 So best power plant is City with c = 10001 So to take the lowest c_i appears not to be optimal.
•  » » 3 months ago, # ^ |   0 "Reassign power plant to City3. Then cost will be 10001 + 100 * (1 + 2) + 100 * (1 + 2) = 10601",There's an issue here... Looks like you've connected City 3 with 1 and 2, but you should have connected City 3 with City 1 and then provide power to city 2 to via City 1. The answer would be 10000 (Station at City 3) + (1+2)*100 + (1+1)*2 = 10304
 » 3 months ago, # |   +9 In Problem F, Shouldn't f(0,r) = 2 * r — 1 + f(1, r) ?
•  » » 3 months ago, # ^ |   +5 Ahh yes, thanks for pointing it out. It has been updated now.
 » 3 months ago, # |   0 Can anybody help me with my solution of D. here is my code https://ideone.com/tRcPzZ
•  » » 3 months ago, # ^ |   0 it gives the wrong answer to test 13 with a slight difference. please help submission https://codeforces.com/contest/1245/submission/64048567
•  » » » 3 months ago, # ^ |   0 leave it I got where I go wrong.
 » 3 months ago, # | ← Rev. 2 →   0 For problem C , how it is reduced to fibonacci ?
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 let's suppose we have i n's in sequence ( nnn....n i times ). Now two cases can be there:-(1) last character is n(2) last character is m ( disguised as nn )hence dp[i] = dp[i-1] + dp[i-2].The first term for the first case and the second term for the second case.Hence, fibonacci
•  » » » 3 months ago, # ^ |   0 I still didn't get it. Can you explain case (2)
•  » » » 5 days ago, # ^ |   0 thanks bro got it
 » 3 months ago, # | ← Rev. 3 →   0 In problem C, what is wrong with this approach?Find the number of consecutive n or u.Then find the number of possible strings that can create it.eg. number of consecutive n = 4.With 0 m, number of possible string = 4!/4! = 1With 1 m, number of possible string = 3!/(2!*1!) = 3With 2 m, number of possible string = 2!/2! = 1Total = 5
•  » » 3 months ago, # ^ |   +3 It is correct approach and gives AC.Link to submission:-https://codeforces.com/contest/1245/submission/64014595
•  » » » 3 months ago, # ^ |   0 Thanks. I was getting WA because of an overflow :(
•  » » 3 months ago, # ^ |   +3 Nothing, that's exactly what fibonacci is ! Memoize what you just said and you'll have the fibonacci sequence ! Either way will get to the same answer, just that your way the calculation will get a bit lengthy soon! Better just observe how it can be generalized.
•  » » » 3 months ago, # ^ |   0 Thanks. I was getting WA because of an overflow :(
 » 3 months ago, # |   0 Regarding Problem C, what is the intuition behind applying Fibonacci( dpi=dpi−1+dpi−2 ),i mean do i try all possible combinations for small input and then deduce the Sequence is Fibonacci. Any help will be appreciated, Thanks in advance.
•  » » 3 months ago, # ^ |   0 Here is my explanation:-https://codeforces.com/blog/entry/71080?#comment-555410
 » 3 months ago, # |   0 D using greedy idea given in editorial. Just different implementation using priority queue https://codeforces.com/contest/1245/submission/64051184
 » 3 months ago, # |   0 Hi, can anybody explain why my solution to D is wrong. For each two city x, y add edge between them if (k[x] + k[y]) * d(x, y) is less than building a power station in at least one of them. Then for each component build a power station in city where has the minimum cost and calculate MST for each component for edges that we have to make.
•  » » 3 months ago, # ^ |   +3
•  » » » 3 months ago, # ^ |   0 https://codeforces.com/contest/1245/submission/64059625 here is my code. I'm not getting WA on your test
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 Lets say you have 3 nodes 1,2,3dist(1,2)=10dist(2,3)=20dist(1,3)=30let k be 1 for allC[1]=5C[2]=50C[3]=10you try to put them all in one same component,because edge cost for 1,2 would be 20 but max(c[1],c[2]) would be 50. Same explanation for 2,3.Now you assign power station to minimum C value node in each component. So here in this example it would be 1, and for rest of the node in the component you use MST of edges.This fails for the above mentioned example. The above mentioned example in terms of input would be,35 1015 1035 105 50 101 1 1The answer for this input would be 35, power stations on 1 and 3 and edge 1,2This fails because you join things to same component when edge weight is less than max of c values of nodes.When one of the nodes has a c value less than the edge weight, but unfortunately in MST, the node with max c weight can be assigned first, you shouldn't use that edge in this scenario, because instead of the edge, creating a power station on the min C weight node would give better answer.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 thanks
 » 3 months ago, # |   0 Can someone tell me what the DP transition for problem C would be if 'nn' and 'uu', instead of being replaced by one letter each, 'm' and 'w', could be replaced by more. Say 'nn' could be either 'm' or 'l'.
 » 3 months ago, # | ← Rev. 2 →   0 For 1245E, let's say there are no ladders. After flattening the array, why push dp is wrong. I am getting 28.0476190Pushing logic is straightforward. for(int d= 1;d<=6;d++) dp[f(i +d)]+=(1.0 + dp[i])/6.0 f(x) is the new move as mentioned in editorial.Here is the code : https://ide.geeksforgeeks.org/BvBaJFwLip
•  » » 3 months ago, # ^ |   0 During each turn, the player rolls a standard six-sided dice. Suppose that the number shown on the dice is r. If the Goal is less than r squares away on the path, the player doesn't move (but the turn is performed).
 » 3 months ago, # | ← Rev. 4 →   0 Thank you for the beautiful contest, keima915 ! Here are my thoughts on the problems — $A$ — It was a very elegant problem on Bezout's Identity $B$ — Good Greedy Construction Problem $C$ — DP $D$ — It reminded me of this problem on AtCoder — Various Sushi 116D. I was trying to use a similar idea here. After sorting the power stations by their cost, I thought of first, making power stations in only the first power station and building connections for all the other stations. Then, to make a power station in only the first 2 power stations and build connections in all other power stations. And so on. However, this was $O(n^3)$ and I couldn't find a way to make it shorter. The MST solution is quite surprising ! $F$ — Again it reminded me of 2 AtCoder questions — Sum Equals XOR 129E and XOR Sum 2 098D. The main difference between $129E$ and this question was that in $129E$, only $a + b$ had to be $< L$, but here both $a, b$ had to be in $[L, R]$. I was trying to build on the solution to these problems for this one. By the way, here are my solutions to the problems of this contest so far in case anybody wants to refer them.
•  » » 3 months ago, # ^ |   0 another similar problem in AtCoder 138F Coincident
•  » » » 3 months ago, # ^ |   0 Thanks for sharing !
•  » » 3 months ago, # ^ |   0 You seem to put two same links
•  » » » 3 months ago, # ^ |   +3 Thanks, I fixed it.
 » 3 months ago, # |   0 Is it possible to solve F using digit-dp like algorithm?
•  » » 3 months ago, # ^ |   +35 Yes.Alternate solution to problem F: you can use digit dp to find the answer :) You need to keep track of 5 states. Let, $dp[f1][f2][f3][f4][p]$ = Number of pairs of binary numbers with $p$ digits and $f1, f2, f3, f3$ are $0/1$ values indicating:$f1 = 1$ means first number is bigger than $l, 0$ otherwise $f2 = 1$ means first number is smaller than $r, 0$ otherwise $f3 = 1$ means second number is bigger than $l, 0$ otherwise $f4 = 1$ means second number is smaller than $r, 0$ otherwise Ideally, when you have $f1 = f2 = 1$, that means our current number is already within $[l,r]$ giving us the freedom of putting any $0/1$ as current digit. Other cases? You can easily figure that out. So using $f1, f2$ we can find some $[l1, r1]$ bound for current digit of first number. And using $f3, f4$ get another bound for second number $[l2, r2]$. Now bruteforce on all possible pairs other than $1,1$ pair :) My submission 64025375
•  » » » 3 months ago, # ^ |   0 could you elaborately explain your approach with few examples.
•  » » 3 months ago, # ^ |   +4 I recommend to try out few digit-dp problems otherwise you may not understand anything.My digit-dp approach:Let $f(x, y)$ be a function which returns all pairs $(a, b)$ such that $a + b = a \oplus b$ where $0 \le a \le x$ and $0 \le b \le y$.Now to calculate $f(x, y)$ we will use digit-dp approach. In our digit-dp we will consider bit representation of $x$ and $y$ rather than decimal representation which is generally used(as this is obviously a bit manipulation problem :P). Let $dp[i][f1][f2]$ = Number of pairs possible such that $a \& b = 0$ $(0 \le a \le x$ and $0 \le b \le y)$ considering $i$ rightmost bits. Here $f1$ signifies if $35 - i$ leftmost bits are same as that of $x$ or not. $f2$ signifies same but for $y$.Now, answer will be $f(r, r) - 2 \times f(l - 1, r) + f(l - 1, l - 1)$. Answer ExplainationLet us take an example $l = 10$ and $r = 20$. $f(20, 20)$ will also contain all pairs $(a, b)$ for $0 \le a \le 9$ and $10 \le b \le 20$ and all pairs $(a, b)$ for $10 \le a \le 20$ and $0 \le b \le 9$ which needs to subtracted. Hence, we subtract $2 \times f(9, 20)$.If you notice we have subtracted all pairs $(a, b)$ for $0 \le a \le 9$ and $0 \le b \le 9$ twice but in $f(20, 20)$ it was coming once. Hence, we added $f(9, 9)$.Link to Code
•  » » » 3 months ago, # ^ |   0
 » 3 months ago, # |   0 can some explain what is mean by "minimum expected number of turns" in problem E?
•  » » 3 months ago, # ^ |   0 It means assuming that the player plays optimally. In this specific problem, whether to take the ladder or not.
 » 3 months ago, # |   0 Problem A is very, very beautiful. Sad that many of us (including me) solved it without being aware of the complete proof. (I only proved the Bezout's theorem part).
 » 3 months ago, # |   0 Please help me. Im getting wrong answer Testcase 9 for Problem C. I think my logic is correct as the alternative solution. Still doesn't work. How to even debug in such cases?64029232
•  » » 3 months ago, # ^ |   +1 rep(i,2,100002) { dp[i] = sum[i-2]+1; sum[i]=sum[i-1]+dp[i]; }won't you get an overflow here?
•  » » » 3 months ago, # ^ |   0 why? after I change to dp[i]=dp[i-1]+dp[i-2] I still get signed integer overflow. Im unable to see why its overflow, dp size is big enough? 64068550
•  » » » » 3 months ago, # ^ |   +1 Um, yes, but integer/long long size is not big enough. You should be doing operations mod10^9+7
•  » » » » » 3 months ago, # ^ |   0 Oh, I see now. all I had to do was dp[i] = ( dp[i-1]+dp[i-2])% mod and it works. Jeeez... my bad. Thanks a lot :)
 » 3 months ago, # |   0 for the problem f I am checking accepted solution and here I found one in which I am not able to understand this line. solution link — https://codeforces.com/contest/1245/submission/64013273line ===>> int ans = f(r, r) — 2 * f(l — 1, r) + f(l — 1, l — 1);How above line gonna work . Anybody ..thankyou.
•  » » 3 months ago, # ^ | ← Rev. 4 →   0 I think that in function f is gets pairs, which a <= l && b <= r && a ^ b == a + b in the rectangle 0, 0, l, r. This line is getting the value of function f in rectangle l, l, r, r, which is rectangle(0, 0, r, r) -rectangle(0, 0, l-1, r) -rectangle(0, 0, r, l-1) + rectangle(0, 0, l-1, l-1)
•  » » » 3 months ago, # ^ |   0 Could please explain little better .I am not able to understand what are you talking about the rectangle thing...
•  » » » 3 months ago, # ^ |   +5 @DimmyT I got it thankyou..Takes a time but now understand completely..thankyou :)
•  » » » » 3 months ago, # ^ |   0 You're welcome)
•  » » 3 months ago, # ^ |   0 Anyone who can explain in a better way ..Please thankyou
 » 3 months ago, # | ← Rev. 8 →   +8 Problem E is quite interesting; I did manage to figure out the DP logic but I didn't know how to calculate the sum for the squares near the goal... however there is a kick-yourself-simple solution I found once I coded it according to the editorial.$dp_i$ for $94 \leq i \leq 99$ is... always exactly $6$. Why? Because consider: you have a $p = \frac16$ chance of rolling the right number to reach the goal exactly, and the expected number of turns require to hit it is the mean of its geometric distribution, $\frac1p = 6$. But if you roll a lesser number, your new square still only has a $\frac16$ chance of getting the right number, so though you're closer to the goal physically, you're still no closer in terms of the turns required to roll the right number, so you might as well not have moved at all.
•  » » 3 months ago, # ^ |   0 I got your point, moving not at all and moving some pieces ahead has no difference as it won't affect the number of expected turns, So it's always 6 for that region. Nice observation.
 » 3 months ago, # |   0 Can anyone explain A?I didn't understand the solution.
•  » » 3 months ago, # ^ |   0 I venture most people just solved A by staring at it for a while and conjecturing the correct solution. Actually proving it is somewhat harder.
•  » » 3 months ago, # ^ | ← Rev. 4 →   0 OK, here's a perhaps simpler "proof" based on the images in my head when I solved this problem.Assume WLOG $a < b$. Consider the sequence $an \mod b$ for integers $n$ incrementing from $0$. If and only if $\gcd(a, b) = 1$, it will eventually cover the entire ring of integers $\mod b$ (forming a discrete Weyl sequence), which is equivalent to the cells colored white as you consider chunks of length $b$ moving to the right, thereby limiting the black cells to a finite number.
 » 3 months ago, # |   +4 Even I don't know how works my ac code of 1245A. But how i got ac !!! :o
 » 3 months ago, # |   0 Thanks for the Editorial
 » 3 months ago, # |   0 Can someone please help me in problem D? Here is my code: CodeI've used Kruskal using DSU to solve this problem by sorting all the edges by weights and then merging the nodes if the cost of wire to connect them is less than the maximum of their cost of building powerhouses(because on making connection, there will be one powerhouse needed which should be minimum of both).
 » 3 months ago, # |   -13 Arpa's soluion for Problem C:
 » 3 months ago, # |   0 Can someone please explain the proof of problem A in an easy way?
•  » » 3 months ago, # ^ |   0 if we can reproduce number with any remainder of division by one number using another number, then answer is Finite, otherwise answer is Infinite. This can be checked using GCD (if GCD of two numbers is 1, then answer is Finite, otherwise Infinite).
 » 3 months ago, # |   0 My solutions to some of the problems: B: 64089807, C: 64086504, D: 64086519, E: 64086541.
 » 3 months ago, # | ← Rev. 3 →   +3 C can be solved by normal PnC too.My solution
 » 3 months ago, # | ← Rev. 3 →   0 I am not able to understand the Question F tutorial form the below points: Somebody help me with this. Thanks in advance.What if l and r are not both even? Define a function g as follows: let x and n be non-negative integers, then g(x,n) should be the number of integers y such that the following conditions are satisfied:0≤y0 and g(x,n)=0 otherwise. Moreover, it is easy to implement h so that its time complexity is logarithmic with respect to n.
 » 3 months ago, # |   0 What does this "Arpa" stand for in the solution of seco
 » 3 months ago, # |   0 wrong answer The number of throws of each kind doesn't match (a, b, c) resrictions. In problem B,what is this error. My output is same as jury's output.
 » 3 months ago, # |   0 Do we have to necessarily connect a city in a group to it's parent? Or we can connect it to any city in the group which will give us the minimum connection cost(basically which has electricity but not a power station necessarily)?PS: Parent of a group is the one with a power station
•  » » 3 months ago, # ^ |   0 The latter is the case.UPD : My code is giving me WA on Test case 13. Could someone please help me with it? I've tried a lot. But couldn't debug it. My code
•  » » » 3 months ago, # ^ |   0 I think TC 13 means: You were asked to make all of cities have electricity, and to do it, you don't need all cities connected each other, you only need each city to belong to 1 connected component which has at least 1 city containing power state. To simplify problem, you add a dummy city and make all components connect each other. Now you only need to find the MST of $n+1$ city (including dummy city).
•  » » 3 months ago, # ^ | ← Rev. 4 →   0 The statement only says,You must provide electricity to all cities ( either by making a power station there, or connecting it to "some" other city that already has electricity ).And the second part basically says, that electricity is transitive, i.e. if City $A$ has a power station and City $B$ is connected to it, then $B$ also has electricity, and thus, if you connect City $C$ with $B$, then $C$ also has electricity.Also, about your code. It seems you are using a greedy strategy, by making the cheapest power stations, but that is not correct. There could be a possibility to make a costlier power station that supplies all cities, instead of making cheap power stations in each city. ( Read my short explanation here ).
•  » » » 3 months ago, # ^ |   0 Can you please explain to me, what does 'rt' and 'sz' mean in your code? And what exactly does 'connect' function does!
•  » » » » 3 months ago, # ^ | ← Rev. 3 →   0 It's just DSU ( Disjoint Set Union ). Read about it online.This is a good resource.UPDATE: Also, I think I didn't explain it clearly, so, we use DSU as part of Kruskal's algorithm for finding a MST ( Minimum spanning tree ) for a graph.
 » 3 months ago, # |   0 Problem D is tagged with trees.Can any one explain this problem according to trees algorithms.And thanx in advance.Happy coding.
•  » » 3 months ago, # ^ |   0 It can be solved using MST (Minimum Spanning Tree) like this. You can use either Prim or Kruskal algorithm. But in this problem, Prim is better.You can learn more about this in Wikipeia. (Poor Chinese, we can't link to the Wiki page!)
•  » » » 3 months ago, # ^ |   0 @iyym could you please explain me this line in your solution question f . calc(b,b)-calc(a-1,b)-calc(b,a-1)+calc(a-1,a-1)). Thankyou
 » 3 months ago, # |   0 Can someone please explain solution to problem A in detail.
 » 3 months ago, # |   0 I got the logic of B but I am getting WA.What am I doing wrong?? My code link
 » 3 months ago, # |   0 I don't know if it is right for you to say that f(2l,2r) = 3*f(l,r). Suppose we are looking at the interval 2,5. Your argument implies that, when counting f(4,10), we must consider the case where we chose for the first one's less significant bit number 0, and, for the second one's less significant bit, number 1, and the other ones we chose, for instance, 10 and 101, respectively (that are pairs found in f(2,5) ). But that does not give the answer. In fact, f(2,5) = 6 and f(4,10) = 16.
 » 3 months ago, # |   0 can somebody please explain the function 'f' in the editorial solution of "Daniel and Spring cleaning" problem?
 » 3 months ago, # |   0 Really good editorial!
 » 2 months ago, # | ← Rev. 2 →   0 Hello guys!I was wondering if I could get some help on problem D. I can't seem to find a corner case or prove why my solution is wrong. My solution follows this idea that was already mentioned in the comments by anakib1 in the Announcement page."I had following idea to D. Lets make minimum spanning tree of graph with edges c(i,j)=(ki+kj)∗d(i,j) for all i,j. Firstly lets add the cheapest plant. Then sort edges in non-increasing order and we will try to delete every edge. If we are considering edge (x,y) let c1 will be component with vert x of tree without edge (x,y) and c2 will be component with vert y of tree without edge (x,y). Only one of this components has installed plant now. Let it be c2 . Then find cost of the cheapest plant in c2 and check if its better to add plant instead of edge from spanning tree. If its better to add plant, we delete edge (x,y) and add plant."I did get to test 32, but can't analyze the test case since its quite large (N = 2000). I would really appreciate if anyone can help me find my mistake. I've added comments in the my submission, hope it helps. Thanks! 64906030
•  » » 2 months ago, # ^ |   +3 Hello.Here is the generator used for test 32: https://dpaste.de/hSQnTo generate test 32, compile it (you'll need the testlib.h file), and run with command-line arguments 21 2000 100. So for example, if I would do it on my Linux machine, after compiling using g++ file.cpp, I would type ./a.out 21 2000 100 > in and then the testcase would be saved in file in. Hope this helps.
•  » » » 2 months ago, # ^ |   0 Thank you for the quick reply! I will check this out!
 » 2 weeks ago, # |   0 https://codeforces.com/contest/1245/submission/68647690what is wrong in my approach?
 » 10 hours ago, # |   0 For problem D, can somebody point out what's wrong in my approach first iterate over all cities one by one for each city i , find the minimum of all costs to connect this city j ( 1 <= j <= n) let's call it min_cost now we have two scenario either this city i has its own power house or is connected to some other city which will have a power house just compare C[i] with min_cost a. if(C[i] < min_cost) , we can simply have a individual plant for this city b. otherwise we connect this to city j, which gave us min_cost now we have a graph with simply iterate over all connected components for each component find the minimum C[i] and add it to final cost answer, since we are planting a power plant at this i'th city rest of this connected component let's just find the MST and add this to final answer , since all the other cities would be connected to some other city with wires having power connection repeat 7
•  » » 8 hours ago, # ^ | ← Rev. 2 →   0 yeah this logic is incorrect because i might miss some of the edges which could help reduce the overall cost see this example copied from above cmt55 1519 1319 1324 1420 132 10 20 10 26 4 2 4 5