### magnified's blog

By magnified, history, 2 months ago,

It has been a wild ride the final 24 hours in the preparation of this contest! And we really hope you liked the problemset we gave today!

## 1737A - Ela Sorting Books

Author: low_

Tutorial
Solution snippet ( low_ C++)

## 1737B - Ela's Fitness and the Luxury Number

Author: low_

Tutorial
Solution snippet (low_, C++)

## 1737C - Ela and Crickets

Author: low_

Tutorial
Solution snippet (low_, C++)

## 1737D - Ela and the Wiring Wizard

Author: low_

Tutorial
Solution (magnified, C++)

## 1737E - Ela Goes Hiking

Author: ngfam_kongu

Tutorial
Solution snippet (low_, C++)

Author: 351F44

Tutorial
Solution (C++)

## 1737G - Ela Takes Dancing Class

Author: magnified

Tutorial
Solution (C++)
Tutorial of Dytechlab Cup 2022

• +38

 » 2 months ago, # |   0 Auto comment: topic has been updated by low_ (previous revision, new revision, compare).
•  » » 2 months ago, # ^ |   0 Do you have the Proof for C, that 'somehow' they can reach point (x, y) ?How did you come to this conclusion ?
 » 2 months ago, # |   -72 C is the worst competitive programming problem I've ever seen.
•  » » 2 months ago, # ^ |   +24 Glad that you learn something new today!
•  » » » 2 months ago, # ^ |   -26 learnt what? casework? man, make better problems.
•  » » » » 2 months ago, # ^ |   +39 You've not learned it enough if you cannot do it on your own. I can never stressed enough how caseworking is so so important, even for the simplest tasks!A word from a guy had multiple years of exp in the workforce ^_^
•  » » » » » 2 months ago, # ^ |   +8 you stressed enough today
•  » » » » » 2 months ago, # ^ |   -7 This task has purely no sense in case of competetive programming. One might say that corner cases have really important meaning in development of larger projects but its weird and utterly useless to make a cp task based only on corner cases. Every task should have at least some creative idea and should not be straight forward annoying paperwork. I find it really sad that instead of taking critique and trying to improve you just fixed your opinion on casework being cool.
•  » » » » » » 2 months ago, # ^ |   -10 I want to add that I indeed consider how hard it is to come up with good and creative problems but it is no excuse to be closed to opinion of everyone else. I really hope that next time you will be able to come with amazing problemset to everyone's liking! (Today I really enjoyed problem D but problems up to D were honestly not to my taste)
•  » » » » » » 2 months ago, # ^ |   0 It's actually a task based on immutability properties in game theory & discrete math. The idea is based on a "Grasshopper" chess game on Chess.com, and I came up with the idea with my co-workers in the brainstorming sessions and had them head scratched for the whole afternoon!The only case working was with "corner" cases (which is pretty direct tbh). So obviously, it's not a task "based on" corner cases.I think you're upset about how the problem slows you down. But hey, ppl wonder what if they had done better all the time. =)
 » 2 months ago, # |   0 Auto comment: topic has been updated by low_ (previous revision, new revision, compare).
 » 2 months ago, # |   +9 another day to be sad
•  » » 2 months ago, # ^ |   +3 same my friend, same
 » 2 months ago, # |   -116 And we really hope you liked the problemset we gave today!No, we didn't. Please, don't make contests again.
•  » » 2 months ago, # ^ |   -22 Can't agree more
•  » » 2 months ago, # ^ |   -19 Problemset was way too good. It's just that implementatiton was a lil tricky but the idea behind the question was really good.
 » 2 months ago, # |   +18 why are all the critiquing comments removed?
•  » » 2 months ago, # ^ |   +20 we aren't on web3 yet
•  » » 2 months ago, # ^ |   -10 Someone removed the level 1 comment, and then brought the whole subthread down to the void :D
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 The person who deleted the comment probably prevented long comments war thread XD so it might be for a good reason
 » 2 months ago, # |   -33 Amazing problems which require good Implementation skills. #ImplementationForces
 » 2 months ago, # |   +19 Is there any efficient way to count the number of [n] partitions with each part i, it must encounter all ants at position < i) We need ants to the right all to have weight < i. Notice that every ant with an initial direction to the left will form a new ant, and its size is given by the number of ants going to the right on its left + 1. => count ways to partition n elements so that each part has 1h.
•  » » 2 months ago, # ^ |   +18 I was also thinking along these lines, but this misses a crucial point. We don't need the ant $i$ to be bigger than all of the ants going to the right on its left because ant $i$ will get bigger each time it eats a new one! For example, if the ant has size $3$ and it's facing a series of ants of sizes $2, 4, 5, 10$, it will end up surviving.So the relevant combinatorial question isn't the number of ordered partitions of $[n]$ with each part containing $\leq k$ elements, but rather something like "in $n-k$-bit binary string, what's the probability there's a run of length at least $r+k$ starting at position $r$"?
•  » » » 2 months ago, # ^ |   +15 OMG you are right... I missed that observation :-(
 » 2 months ago, # | ← Rev. 3 →   -16 my head sucks :).
•  » » 2 months ago, # ^ |   0 It is probably due to floating point inaccuracy for large numbers.From the tutorial: Also note that, since large numbers can cause inaccuracies in floating point computation, we should use binary search to find the floor-value of a square root, instead of using the sqrt function in any language.
•  » » » 2 months ago, # ^ |   -36 but the error is not happening in pc.
•  » » » » 2 months ago, # ^ |   +3 Probably your Python environment or version or something is different from what Codeforces uses in the judge environment. It's possible that your PC would fail a test case that succeeds on Codeforces.In general, you need to be aware of such floating-point in accuracies for large numbers.
•  » » » » » 2 months ago, # ^ |   +3 yes i used integer sqrt.. it is accepted now.
•  » » » » 2 months ago, # ^ |   +2 Accept the flaw and learn from it. Never repeat it.
•  » » » » » 2 months ago, # ^ |   +3 yeah you are right
 » 2 months ago, # |   0 thanks for the great round !!
 » 2 months ago, # |   0 I really liked today's contest, Even though I only solve A, and got WA on B because of using sqrt. But because of this mistake, I will always be careful when using sqrt from now on.
•  » » 2 months ago, # ^ |   0 yes, thx to the contest, I learned it too!
 » 2 months ago, # |   0 If we don't use binary search in B problem, the answer would overflow right? (in a very "long long" test case)
•  » » 2 months ago, # ^ |   0
•  » » » 2 months ago, # ^ |   0 Ohh alright, the precision error was the problem here. Thanks!
 » 2 months ago, # |   +5 Sad to use sqrt instead of sqrtl in problem b ಥ⁠‿⁠ಥ
 » 2 months ago, # |   +26 huge gap between C and D
 » 2 months ago, # |   0 B: How come ((ll)sqrt(x) * (ll)sqrt(x)) be greater than x?AC: 175053872 WA: 175045921
•  » » 2 months ago, # ^ |   +9 Floating number precision loss.Maybe you could use sqrtl(x) to get $\lfloor\sqrt x\rfloor$
 » 2 months ago, # | ← Rev. 3 →   +12 we can prove that there is always a way to line up 2 pieces on the same-colored squares with the target square diagonally. [but we won't]If you can prove it, do it...
 » 2 months ago, # |   0 I didn't understand the equation of problem B how did we get it ? , can any one explain?
•  » » 2 months ago, # ^ |   0 (1 2 3) (4 6 8)(9 12 15)(16,20,24) and so on, if x=15, sqrt(15)=3 ans = 3*3 =9 =>(1,2,3,,4,6,8,,9,12,15)
•  » » » 2 months ago, # ^ |   0 This just an example what I mean is how we did conclude it
•  » » » » 2 months ago, # ^ |   +5 Let's say that $\left \lfloor{\sqrt{x}}\right \rfloor=y.$ That means that $y \leq \sqrt{x} •  » » » » » 2 months ago, # ^ | 0 good explanation , Thank you •  » » » » » 2 months ago, # ^ | ← Rev. 2 → 0 thank you dorijanlendvaj, you helped me too  » 2 months ago, # | 0 Can someone explain D test case 1? Why after change, time cost from Machine 1 to 8 is 6? •  » » 2 months ago, # ^ | +5 Disconnects$(2, 3)$and connects$(2, 8)$.  » 2 months ago, # | 0 What is this &mdash in solution code of E ? •  » » 2 months ago, # ^ | 0 Probably, after reading the editorial, it means minus"-". I don't know what's wrong but in some places "-" might be changed into "&mdash".  » 2 months ago, # | 0 Test data for Problem D are too weak.Some wrong answers can pass the test, for example, my code.A test case which output result 9 but the true answer is 8.1 11 11 1 8 5 8 9 5 9 10 5 10 11 5 1 5 5 5 6 5 6 11 5 1 7 100 2 3 1 3 4 5 4 9 5  » 2 months ago, # | ← Rev. 2 → -8 Difficult Round  » 2 months ago, # | +3 Can anyone please explain the 2nd case in the editorial of D Ela and the Wiring Wizard •  » » 2 months ago, # ^ | +8 If you try to find the answer for the sample test case #3 in the D, you will find that the 1st case in the solution is not able to find the correct solution.In this test case, the correct solution would be to -> take the edge connecting vertex 2, 5 -> connect it to 2, 6 take the now edge connecting vertex 2, 6 -> connect it to 2, 4 take the now edge connecting vertex 2, 4 -> connect it to 4, 4 take the now self loop edge connecting vertex 4, 4 -> connect it to 4, 7 take the now edge connecting 4,7 -> connect it to 4, 1 take the now edge connecting 4, 1 -> connect it to 1, 8The answer -> (22 * 6 + 22) = 154So what happened is we saw that the edge connecting the vertex 2, 5 might just be what we need for the best possible path but if we try the case 1 that we thought of then the total time won't be the shortest possible we could get. We could instead just take one of the vertex and connect it an intermediate vertex ( a vertex that is present in the shortest path from 1 to n). After this, we create a self loop on this intermediate vertex. (Total time up till now -> dist[u][x] + 1Now we can just expand this self loop on both sides -> dist[x][1] + dist[x][n]Now one last time of actually travelling this edge -> 1total time => (dist[u][x] + 1 + dist[x][1] + dist[x][n] + 1 ) * w •  » » » 2 months ago, # ^ | ← Rev. 2 → 0 good! •  » » » 2 months ago, # ^ | 0 I get that by applying the formula for case 1, the answer would be suboptimal. But how do you apply the case 1 to sample test case 3 in the graph? How to connect both 1 to u and v to n for the edge between (2,5)? •  » » » » 2 months ago, # ^ | +3 1 to u will be — (1,7,6,5) and v to n will be (2,5,6,4,8) The total time become (3+4+1)*22 equal 176Which is suboptimal so we go for the case 2 and get better answer •  » » » » » 2 months ago, # ^ | +1 That's fine what I want to know is how you break the edge. If you break it the way you mentioned above, that would cost 65 each time (since the edge between 1 and 7 costs 65). Do you get what I want to convey? •  » » » » » » 2 months ago, # ^ | ← Rev. 2 → +2 We break the edge between u and v. In the case I described, we break the edge b/w 2,5 and connect it to 2,6, then 2,7, then 2,1. Its cost becomes — dist[1][5] * 22Then we take the edge of 2,1 break it to join it to 1,5 then 1,6 then 1,4 then 1,8 Cost becomes dist[2][8] * 22This is.for case 1, for case 2 also we start by breaking the edge between 2,5 but once the u reaches an intermediate vertex we like we create self loop and expand both sides •  » » » » » » » 2 months ago, # ^ | 0 Firstly, you broke the edge between (2,5) so 2 and 5 are no longer connected. Then later on you connected 1 to 5 directly by breaking the edge between (2,1). How is it possible since 5 is not connected to 2 anymore? •  » » » » » » » » 2 months ago, # ^ | 0 Yeah, you are right. It is not possible like this Good find.Though it is still possible to achieve the same results, I will first break (2,5) to make self loop on (2,2) than expand one side to 1 and the other to 8 •  » » » » » » » » » 2 months ago, # ^ | 0 I think this isn't possible as well. That's because the self loop on (2,2) can't be expanded as there is no edge connecting to 2 other than the (2,5) which we broke. •  » » » » » » » » » 2 months ago, # ^ | +2 oh sorry,. i didnt see the graph again before replying. it should be self loop on (5,5) .i misremembered the graph  » 2 months ago, # | 0 Can someone please help clarify what the second and third cases for problem C are talking about and why they work? Thanks in advance.  » 2 months ago, # | 0 Why does the solution say that$[1,2 * i - 1]$and$[2 * i,n]$are independent in problem E?  » 2 months ago, # | 0 Why __int128 CE in C++14 and AC on C++ 20? •  » » 2 months ago, # ^ | +11 GNU G++14 on codeforces generates 32 bit executables, apparently. I don't think __int128 is available on 32 bit targets yet. •  » » » 2 months ago, # ^ | 0 Thanks  » 2 months ago, # | ← Rev. 2 → 0 Hey, I think there is a typo in tutorial for C. It should be : "Assuming that the central piece is on the light square, we consider 3 cases:"  » 2 months ago, # | 0 Does anyone know the reason of it? In problem B, when I typed x=sqrt(l),y=sqrt(r), I got wa in test 11. Though I tested the case and it gave corrrect answer in my IDE. when i typed x=sqrt((long double)l),y=sqrt((long double)r) I got AC. What can be the reason for it?  » 2 months ago, # | 0 How did the author write such an obscure topic? •  » » 2 months ago, # ^ | +2 Can you point out which one is obscure?  » 2 months ago, # | +16 In D how do you show the following things? 1. It's never optimal to touch any edge apart from the one that we are trying to put on 1-n spot? 2. Lower bounds provided are always feasible? Even the simplest case where you never 'merge' ends of the edge that is being moved. How to prove that the path "will not break" or something along the process? This doesn't seem very hard but I have some trouble finding clean proof. •  » » 2 months ago, # ^ | +11 maybe i have an answer to Q1. suppose shortest path a->c is a->b->c, WLOG, let dist(a,b) < dist(b,c) (cases with more edges are similar). so cost is dist(a,b)+dist(b,c)however we can rewire a->b to get a->c, then total cost is 2*dist(a,b) which is less than previous one. base on this, we can alway reduce the optimal answer to only one edge. •  » » » 2 months ago, # ^ | 0 Yeah, that's clear. I'm rather asking about cases like we rewire other edge(s) to deliver "our" edge to 1 — n faster (than we have only one edge from 1 to n in the end). •  » » » » 2 months ago, # ^ | +10 oh, sorry for misunderstandingso in general the answer is (number of rewiring/movement) * (edge weight), and now you are concerning about reducing the first term instead of simply use floyd shortest path, right? •  » » » » » 2 months ago, # ^ | +10 Roughly yes. And i can see some "sketch" of the proof of that, but there are so many (nested) cases etc. that it doesn't convince me at all. I assume there should exist something concise. •  » » 2 months ago, # ^ | ← Rev. 2 → +5 If its optimal to use any other edge then this is not the edge which will us give us optimal answer and this only happens when there is an edge with weight smaller than current one in this path. I wrote a proof to a similar question by my friend so I am copy pasting it here. QuestionWe can prove that it is always better to make an edge directly connect 1 and n. (quoting editorial)Can someone give proof of that? (Problem D) ProofImagine if you have a sequence of edges in a path, lets say it is${1}, {2}, {3}... {k}$for simplicity if the minimum weight among$w_{1}, w_{2}, w_{3}... w_{k}$is$x$then$w_{1} + w_{2} + w_{3}... + w_{k} >= x * k$and cost of rewiring everything such that 1 and n are connect by the edge with weight$x$is$x * (k - 1)$so you can always achieve$x * k$by rewiring so it never hurts. Note this is true for any path, since we are checking all the edges the path which gives optimal answer will also be included. •  » » » 2 months ago, # ^ | +13 I don't think you answered my question. Have you seen discussion above? I'm not concerning about the fact that optimal solution consists of exactly one edge, but rather whether fixed edge could possibly be delivered to 1-n faster using other rewires. •  » » » » 2 months ago, # ^ | 0 I guess only you read the "Question" part. My proof did contain it even tho he didn't ask for it. I will be more specific this time. Lets say if there was a segment${a} - {b} - {c}$(possibly${a} = {c}$) in some path after one operation we can "contract" it and make it${a} - {c}$. It doesn't induce any new paths but rather contract already existing ones. So we can say final edge is just a contraction of one of initial paths from${1}$to${n}$. Note this is true for any path not necessary shortest.But what's the Optimal way to contract a path? that's what I did in my proof. You only need one edge that has minimum weight in that particular path. Details of the first paragraph of previous comment.Lets say you need to use another edge with weight$x$to rewire current edge then its obvious$x < weight_{current-edge}$. So cost of rewiring everything in this path with weight$x$< cost of rewiring with current edge, its better not to use current edge at all. Note this is also true for any path. This by induction proves you only need one edge. ¯\_(ツ)_/¯I was asleep, this reply is a bit late. •  » » » » 2 months ago, # ^ | -6 If I understood correcty,You say that if we can wire our current edge from 1 to n faster by using another smaller weighted edge, why don't we use that edge to speed up our "rewiring"And badlad says that if we can use some another smaller weighted edge to speed up our "rewiring" process, there is no point to use our current edge to wire 1 and nBecause if we can use some edge to speed up our rewiring, that means this edge is in the same path as our current edge and its weight is smaller than our current edge And if we have another smaller weighted edge in a path that contains our current edge, there is no point trying to rewire our current edge (proof is given by badlad in the first reply) •  » » 2 months ago, # ^ | ← Rev. 3 → 0 For the final edge$f$which will be between$1-n$at the end, I think we can prove that using it only is optimal as follows:When we re-wire we have$2$options: Create a self loop, this does not shorten any existing path or add any new path in the equivalent unweighted graph (in fact it can disconnect existing paths). So, it does not make sense to use that except with$f$to transport it from a place to place. Make edge$e_1$with terminal nodes$u$and$v$bypass edge$e_2$with terminals$v$and$w$(so that$e_1$now has terminals$u$and$w$). If$f$was not connected to node$1$from the beginning, then at least one bypass is needed to connect it to node$1$, same with node$n$. For any edge$e$that is bypassed by$f$, if$e$already made$x$bypasses earlier, then we could have not done these$x$bypasses and make$f$do$x+1$bypasses instead. The same logic can be followed to prove the same for any edge bypassed by$e$and made some bypasses earlier. Conclusion of point$2$:We can always achieve a bypasses count by$f$alone no greater than when there are other edges as well contributing in the bypasses count. •  » » » 2 months ago, # ^ | 0 More elaboration on why we can use only$1$edge in all the re-wires:Observe that re-wiring works bidirectionally, e.g., for$e_1(u-v)$and$e_2(v-w)$, we can either use$e_1$or$e_2$to achieve the same new end points$u-w$. This means that whenever we make$2$rewires with different edges sharing an end-point, e.g., for$e_1(u-v)$,$e_2(v-w)$, and$e_3(w-x)$:$1^{st}$re-wire:$e_1(u-w)$,$e_3(w-x)2^{nd}$re-wire:$e_3(u-x)$then we could have always chosen the cheapest edge to perform both the re-wires while achieving the same new end points. e.g., if the cheapest is$e_2$, the sequence of re-wires could be:$1^{st}$re-wire:$e_2(u-w)$,$e_3(w-x)2^{nd}$re-wire:$e_2(u-x)$•  » » 2 months ago, # ^ | +6 I don't have an answer for you but I agree that these are points that should be addressed more carefully. For example, it is not true that for an arbitrary edge$e$, the cheapest way to move this edge to go between$1$and$n$involves operations with$e$only, Intuitively, the problem might be okay still because for these cases, any helper edges which are moved just end up being better choices as the final edge. (That is not a proof, of course.) •  » » » 2 months ago, # ^ | -15 The point is, if the rewiring could be sped up by using some other edgeto speed it up, our choice of the optimal edge to place between 1 and n is wrong, which is why this method works since it takes the minimum of all possible edges.To state it more mathematically, if an edge e can be placed faster between 1 and n by using an intermediate edge f to speed up the process, edge f is a bettee choice to place between 1 and n •  » » » 2 months ago, # ^ | -18 isn't it a true for a path though? If its initial length was k no matter how you reduce it to "the final one edge" its cost will always be sum of k terms. So the best you can do is just pick one edge that has minimum weight.Or am I assuming something wrong here? •  » » » » 2 months ago, # ^ | 0 why downvotes? if you can why explain why I am wrong then please do I want to know. •  » » 2 months ago, # ^ | 0 A bit late but you can prove it like this:Consider$\min(\min_x(dist(1, x) + dist(n, x) + dist(x, edge) + 1), dist(1, edge) + dist(n, edge))$for a fixed edge. You can prove that with any operation it decreases by at most 1 with a small case work.  » 2 months ago, # | 0 hi low_ sorry for the ping.Can u pls exaplin how u came up with the idea of problem c.Though the observaton was quite simple but it took me a long time to observe it.So want to know how u thought it in the first place.So that from next time I could try that way too.Sorry for bad english. •  » » 2 months ago, # ^ | 0 I put 3 pawns on the chessboard and move around like crickets and see the pattern.The idea I got from grasshopper chess variants, which you can find on chess.com •  » » » 2 months ago, # ^ | 0 Thanks for the reply.Really enjoyed the contest. •  » » » 2 months ago, # ^ | 0 Your chess.com id? •  » » » 2 months ago, # ^ | 0 And after finding some pattern on a chessboard, you thought, oh cool, this will make a nice competitive programming problem? It has absolutely nothing related with competitive programming. •  » » » » 2 months ago, # ^ | 0 What do you know abt competitive programming? XD •  » » » » » 2 months ago, # ^ | -14 I don't know much, but I know you're not a good problem setter. •  » » » » » » 2 months ago, # ^ | -17 well if C isn't related to competitive programming, then I don't know what is. •  » » » » » » 2 months ago, # ^ | -10 Well I can't ever argue with unranked ppl, can I? XD  » 2 months ago, # | +18 in problem D, "We can prove that it is always better to make an edge directly connect 1 and N."Here is the proof if anyone’s not getting the hang of it. Assume the shortest path between$1$to$N$after rewiring has more than one edge. Let's say the length of the path is$L$. Now take the lightest edge (with weight$W$) among all the edges on this path and rewire the whole path using this edge only. It will have the cost$(L-1) * W$. Which will be less or equal sum of all L weights on the original path. By contradiction We can say our assumption is false.  » 2 months ago, # | 0 https://codeforces.com/contest/1737/submission/175080288 same code gets ac when I used isqrt when sqrt used gives a wa on test 4 dont know why https://codeforces.com/contest/1737/submission/175044806  » 2 months ago, # | +3 We can prove that it is always better to make an edge directly connect 1 and n.Can someone give proof of that? (Problem D) •  » » 2 months ago, # ^ | +8 Imagine if you have a sequence of edges in the path, lets say it is${1}, {2}, {3}... {k}$for simplicity if the minimum weight among$w_{1}, w_{2}, w_{3}... w_{k}$is$x$then$w_{1} + w_{2} + w_{3}... + w_{k} >= x * k$and cost of rewiring everything such that 1 and n are connect by edge with weight$x$is$x * (k - 1)$so you can always achieve$x * k$by rewiring so it never hurts. Note this is true for any path, since we are checking all the edges the path which gives optimal answer will also be included.  » 2 months ago, # | -40 Trash problem. Coordinators should survey authors better. We've reached new peaks of stupidity.Marinush •  » » 2 months ago, # ^ | +21 little boy crying how cute •  » » » 2 months ago, # ^ | -11 Thank you for floppily bullying me. I will speedrun the days until you correct your paths, stop feeling so superior. Apologies if this does not fit your view.Marinush  » 2 months ago, # | 0 In B you should not write a new sqrt if you use c++ you can use int r2 = sqrtl(r)then r2 will be the floor of sqrt rbe careful to use sqrtl, not sqrt because the input is long long not int •  » » 2 months ago, # ^ | ← Rev. 2 → 0 didnot understood why should we use sqrtl •  » » » 2 months ago, # ^ | 0 sqrt is more accurate for int because its return doublebut sqrtl returns a long double and it's better to use this for accuracy and don't get overflow  » 2 months ago, # | 0 when i used sqrt i got wa , but when i used sqrtl i got correct . why i got wrong with sqrt. submission :- 175144961  » 2 months ago, # | -23 It has been a wild ride the final 24 hours in the preparation of this contest! And we really hope you liked the problemset we gave today! Based on the downvotes doesn't seem like there is any like.Couldn't solve a single question, and editorial for the first question...  » 2 months ago, # | 0 Can Anybody explain B's approach in detail?  » 2 months ago, # | ← Rev. 6 → +1 Proof for$C$:Assuming that the central cell is labeled$X$and the other two cells are labeled$O$, for the following initial configuration (and equivalently for the other three valid configurations as well):We can cover the following cells (A similar pattern can be achieved vertically as well):After analyzing this pattern we can see that all white diagonals (equivalently all white cells) can be covered, and all black cells which are in column similar in parity as$X$'s initial column (and equivalently rows similar in parity to$X$'s initial row) can be covered. Since each time we move 2 rows or 2 columns, black cells in columns (and equivalently rows) with different parity are already unreachable by definition.However, the previous pattern requires that at least one of$X$'s initial row and column to be neither$1$nor$n$(for the initial$X$to not be in a corner), otherwise the previous pattern cannot be achieved and only the initial row and column of$X\$ can be covered.
 » 2 months ago, # |   0 anyone with the solution code of the problem 1737A Ela Sorting Books. Please help!
 » 2 months ago, # | ← Rev. 2 →   0 Can anyone please explain test case 3 of problem D? ok nvm found it above
 » 2 months ago, # |   0 can someone tell why it is optimal to directly connect 1 to n and how we thought of using 1 weight shortest path .please help
 » 2 months ago, # |   0 Can anyone explain the need of creating the self look in problem D
 » 7 weeks ago, # |   0 can anyone tell what's wrong with my code https://codeforces.com/contest/1737/submission/176973217
 » 5 weeks ago, # |   0 1737B — Ela's Fitness and the Luxury Numberwhy do we need to start with right = 2000000123,we can also start with right = x right because sqrt(x) will be anyways less than xwhat is the significance here using the number 2000000123?
 » 9 days ago, # | ← Rev. 3 →   0 Can anyone tell me how to solve C[1400-1600 rated Problems] faster? What I have observed is Spoiler- 1. too much observation based which takes me a lot of time to find. - 2. In some cases not able to find it to even for a long time. - 3. Proof of observation is too difficult to I have to solve on the bases of intuition. Whatever I am able to figure out. Without proof, it becomes hit and trial. Sometimes I suppose that what I have thought is right but it fails in some cases and submits the same logic with minor changes again and again. - 4. Sometimes examples also become too difficult to figure out.