### dalex's blog

By dalex, 2 months ago, translation, ,

Hello everyone,

At March 29 there was an annual programming contest in Samara University (online, of course), and yet again we copy it into Codeforces Gyms. The gym contest takes place on Sunday, April 5, at 11:00 MSK.

Fifth time in a row it is a personal contest. So we ask everyone to participate solo. The skill of competitive programmers in the university became significantly lower, so the contest is the most interesting for blue and cyan coders, but we have something for violets and oranges too.

• +51

 » 2 months ago, # |   +14 Is there going to be any Editorial?
 » 2 months ago, # | ← Rev. 4 →   0 Reminder: it starts in 1 hour 30 minutes 10 minutes 1 minute.
 » 2 months ago, # |   0 How to solve L? I tried to write inclusion, exclusion dp just like knapsack using recursion. But couldn't implement it right.Can you briefly tell what you did? Thank you!
•  » » 2 months ago, # ^ |   0 Sort the array $a$ in decreasing order. Obviously, if you choose to fight exactly $k$ dragons, it is optimal to take the $k$ largest amounts of gold, and you will lose $k * (k + 1) / 2$ on repairs. Now you just have to find the maximum over all $k$.
•  » » » 2 months ago, # ^ |   +1 Thanks a lot!
•  » » » 2 months ago, # ^ |   +1 It should be also mentioned that Problem L, important statementIf for some optimal $k$ the profit is positive, it always remains positive, not depending on what order we will kill the dragons. Otherwise we can skip the worst dragons and get better result.
•  » » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 Can anyone tell me why this piece of code is giving WA in L.  Codeint ans, cost; ans = 0; cost = 1; for(int i = 0 ; i < n ; i++) { if(a[i] - cost > 0) { ans += a[i] - cost; cost++; } } cout << ans << endl; 
•  » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Spoiler3 2 3 4 Tip: you don't need to kill the first dragon.
•  » » » » » » 5 weeks ago, # ^ |   0 Got it !! Thanks !!
•  » » » » » » 5 weeks ago, # ^ |   0 Hey, Have you solved Problem J of this round ? I have done the brute-force to find out the solution. but, do you have any formal method or derivation of it ?? Can you pls give me ans : james007, dalex, sandoval, Kais_Hasan, ...
 » 2 months ago, # | ← Rev. 2 →   +3 I'll describe just the hardest problems. Others are too easy and everyone should have solved them. Anyway, if you have questions, ask them and someone will answer (hope not me). The hardest problemsProblem GIs taken from the book: Steven S. Skiena — The Algorithm Design Manual, page 128 Problem DFirst run BFS from the vertex n and find d[x] — the distance from n to x. Why from n, not from 1? We do that, because we will go from 1 to n in the next part of solution, so we will be able to choose the next letter greedily.Now all vertices form layers. The first layer is the vertex 1, and the i-th layer contains all vertices y, such that for all vertices x from the layer (i-1) the equality d[x] == d[y] + 1 holds. Now find the minimal letter written on all outgoing edges in the current layer, and follow all edges with this letter, forming the next layer. Repeat until you reach n. On each layer, we follow only the minimal letter, it guarantees that the string will be minimal. Test 72If you run the BFS from 1 to n, not from n to 1, when you got a vector with all vertices in some layer, you might have forgotten to call unique on it. Problem CRotate points 45 degrees, now |x1-x2| + |y1-y2| becomes max(|x1-x2|, |y1-y2|). Do binary search on answer. You will have to calculate the number of points inside squares {x +- mid, y +- mid} and compare it with k. It is done with coordinate compression and Fenwick tree, and it is N*log^2N. Unfortunately, you get TL.How to deal with TL? There are three parts of solution which give log^2: coordinates compression, events sorting and Fenwick tree. We will get rid of the first two, leaving only log^2 from Fenwick, and instead of C++ solution working for 4 seconds, get Java solution working for 0.75 seconds: https://pastebin.com/JmFieuUDFirst, events sorting. There are three types of events: square begins, square ends and the query event. Their comparison keys are y[i]-mid, y[i]+mid and y[i], respectively. We can sort y[i] outside the binary search, and inside the binary search just merge three arrays: {y[i]-mid}, {y[i]} and {y[i]+mid} in linear time.Then, coordinate compression. Our Fenwick tree will have not 3N, but N coordinates. Sort x[i] outside, and then for each query find the leftmost and the rightmost index in the fenwick tree. Previously they were lower_bound(x[i] — mid) and lower_bound(x[i] + mid), and you have spent the additional log factor, but they can be found with two pointers and the same merge-like technique.Oh, and this is the video of unfreezing and the editorial in Russian by Slamur: https://www.twitch.tv/videos/578322224
•  » » 2 months ago, # ^ |   0 Hi,can u explain this line " Why from n, not from 1? We do that, so that there always be only one next vertex when we will go from 1 to n in the next part of solution". and provide the source code to understand it better and some similar problem or topic. Thanks.
•  » » » 2 months ago, # ^ |   0 I updated it, and this is the solution: https://pastebin.com/mzSvFaVp
•  » » » » 2 months ago, # ^ |   0 Thanks for providing solution, can u explain this "**Why from n, not from 1? We do that, so that there always be only one next vertex when we will go from 1 to n in the next part of solution**"
•  » » » » » 2 months ago, # ^ |   0 Counter test5 5 1 2 a 1 3 b 2 4 a 4 5 a 3 5 b With bfs run from 1 to n, how to find the path 1-3-5? At least, how to find it SO EASILY?With bfs run from n to 1, you will always consider edges leading to n as fast as possible. But if you run bfs from 1, you find the edges leading to 1 as fast as possible. These are different things.Because of lexmin, we must restore the path from 1 to n, and the edges leading to n are our friends.
•  » » » » » » 2 months ago, # ^ |   0 Thanks, now i understand it.
•  » » » » » » 2 months ago, # ^ |   0 In this example vertex (4,3) was put in same layer but vertex (1,2) put in same layer or not as this property{ the i-th layer contains all vertices y, such that for all vertices x from the layer (i-1) the equality d[x] == d[y] + 1 holds.} condition is not satisfied. so can u tell how layers are formed in this example. Thanks.
•  » » » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 d[1] = 2 (path 1-3-5), d[2] = 2 (path 2-4-5), so the edge 1-2 is not processed at all — it doesn't lie on any shortest path.And three layers are just {1}, {3} and {5}.
•  » » » » » » » » 2 months ago, # ^ |   0 Thanks.
•  » » 2 months ago, # ^ |   +11 "How to deal with TL? There are three parts of solution which give log^2: coordinates compression, events sorting and Fenwick tree. We will get rid of the first two, leaving only log^2 from Fenwick"What is the point of making constant optimizations ? The difficulty of the problem is not how wtf it would fit in 2 seconds, instead of write some decent $O(n$ $log (n)$ $log (4*10^8))$
•  » » » 2 months ago, # ^ |   0 Because they give x7-x8 boost all together. My first solution worked a bit more than 4 seconds, and the last solution with all these improvements — 0.5-0.55 seconds. This is a huge speedup, deserving to be kept.You will still get accepted without doing all of them. One of those two optimizations is enough. Some participants wrote another (better) approach to process events, it doesn't require additional log and passes too.
•  » » » » 2 months ago, # ^ |   +3 Just my opinion: I think that the main purpose of the time limit in a problem is to differentiate a $log^3$ from $log^2$ or $log$ from $log^2$ etc... not force the contestant to do constant optimizations...
•  » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 If I kept my first solution, with TL = 2 * author TL = 8 seconds, who knows what trash could have passed. It would be too much.+ I find these optimizations very beautiful.
•  » » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 ok, put 3 or 4 seconds not 2I have another completely different beautiful solution with same complexity, but I need two fenwick instead of one and that's why I got TLE, so after many many many optimizations finally I got AC with the monster that my solution became 75647531
•  » » » » » » » 7 weeks ago, # ^ |   0 Could you please provide a link of your code on an online ide.this submission link is not opening !!!
•  » » » » » » » » 7 weeks ago, # ^ | ← Rev. 3 →   0 You need coach mode or solve the problem to see the solution, so here are the codes:optimized solution AC 1747 msoriginal solution TLE
•  » » » » 7 weeks ago, # ^ |   0 it doesn't require additional logIs that overall $O(n\log)$? I couldn't find a solution with such complexity on CF, can you explain it?
•  » » » » » 7 weeks ago, # ^ |   0 No, in those solutions the preparation of events and iteration over them takes NlogN, but Fenwick and lower_bounds in compression still take Nlog^2. Example: 75556991. This is the fast one, there are others with typical running time 1000-1500 ms.
 » 2 months ago, # |   0 How to solve problem J?
•  » » 2 months ago, # ^ |   +8 Spoiler3 7 7 7 3 5 5 10This is one of many possible solutions (Found it by brute force)
 » 2 months ago, # |   0 How to do K? I got WA on test 18.
•  » » 2 months ago, # ^ | ← Rev. 2 →   +6 Problem KLet's say that the sorted heights are a, b, c, d. Then you have two ways: straightforward 1st year mathWe don't care about lengths and widths, so let's say they are x and y, and the legs stay at points (0 0), (x 0), (0 y), (x y).Four points lie on the same plane if: $\begin{vmatrix} x_1-x_4 & y_1-y_4 & z_1-z_4 \\ x_2-x_4 & y_2-y_4 & z_2-z_4 \\ x_3-x_4 & y_3-y_4 & z_3-z_4 \\ \end{vmatrix} = 0$or, with our points, $\begin{vmatrix} x & 0 & b-a \\ 0 & y & c-a \\ x & y & d-a \\ \end{vmatrix} = 0$ which is equal to$a + d = b + c$. to think a bitand understand that the diagonals of the surface should intersect, which instantly gives the same result$a + d = b + c$.
•  » » » 2 months ago, # ^ |   -8 Interesting result. I kept on trying to solve 4 cases where each case had different number of distinct elements.
•  » » » 2 months ago, # ^ |   0 why we sort the heights.
•  » » » » 2 months ago, # ^ |   0 Why not? It doesn't affect anything (jury could give us the sorted test, and the answer would be the same), and it gives the opportunity to make more assumptions.
•  » » » » » 2 months ago, # ^ |   0 thanks, so answer is same if we take points in random order?
 » 2 months ago, # | ← Rev. 2 →   0 can someone explain B ? binary search was giving me a wrong answer on test 29
•  » » 2 months ago, # ^ |   0 This test case may help Spoiler3 4 -2 -1 1
•  » » » 2 months ago, # ^ |   0 how to solve I.
•  » » » » 2 months ago, # ^ |   0 Split the array by colors, each resulting array must be sorted
•  » » » » » 2 months ago, # ^ |   0 thanks, now i get it
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 yeah it worked that was a tough observation thanks!!
•  » » » » 2 months ago, # ^ |   +1 Don't know what is your observation, but the solution is simple and well-known: Problem BFor each point >= 0 (including 0!) go to it, then go left as far as possible.Then invert all signs and repeat once more. (maybe you didn't do it)
•  » » » » » 2 months ago, # ^ |   0 yes
 » 2 months ago, # |   0 Can someone explain Problem-H Tree Painting ?? Thanks in Advance... And also can anyone post the link of editorials??
•  » » 2 months ago, # ^ |   0 First of all, it is not a rated round, and we don't have to provide editorial. It requires some time, you know. There is a video editorial we recorded just after contest, but for obvious reasons it is not in English. I think people can help each other in comments without any editorial. Problem HYou should calculate the number of leafs and divide it by two, rounding up. Obviously the answer can't be less.Why it works? Consider any dfs-ordering. Let's say you have k leafs, denote them 1, 2, ... k, according to the dfs-ordering. Assume k is even (if k is odd, it's just +1 to the answer). Then paint the paths between leafs 1 and k/2+1, 2 and k/2+2, ..., k/2 and k. This paints the whole tree. I know this pattern from the old problem from NEERC.If you didn't know it, you could look at the number of accepted solutions and just output it.
 » 2 months ago, # |   0 Getting wrong ans on testcase 70 in problem G, any hints??
•  » » 2 months ago, # ^ |   0 You exceed query limit. HintTry to estimate the number of requests your solution makes on sorted inputs.See more in my comment above.
 » 7 weeks ago, # |   0 Can somebody explain why this solution to problem B gives WA Submission
•  » » 7 weeks ago, # ^ |   +8 A couple of things I can see is that: In main(), you have two for loops using the same variable i, so that would lead to overshadowing (but that won't cause a problem unless you use the outer variable in the inner loop). On line 62, it says a[i — 1] where i may be 0. On line 62, shouldn't you be checking if a[i] >= 0 instead of > (and same on line 69 — or you can simply remove line 69, as it changes nothing)? The algorithm I used is: My AlgorithmTry moving directly to each point >= 0, and then reaching a point as far left as possible from there (find which one this is using binary search). Then do the same for all points < 0 (the other way), or simple invert signs and repeat the first step.(Keep a variable that stores maximum bonuses collected and update it every time you find a new best)Here is my submission: 75994294My submission was accepted — open at your own risk ;)
 » 7 weeks ago, # |   0 Could somebody explain how to solve problem D without Memory Limit Exceeded? My code reached test 32 but MLE was the problem (used Dijkstra's shortest path).
•  » » 7 weeks ago, # ^ |   +1 Because strings in your Node struct can be O(N) length, so they eat O(N^2) memory in total.
•  » » » 7 weeks ago, # ^ |   0 Yes, I thought so. Thank you. So then I would need to split it into two parts — finding the distance and then finding the lexicographically smallest path of that distance.
 » 7 weeks ago, # |   +5 Does anyone have the tutorial for problem D with a c++ solution? I tried dijkstra but exceeded the memorty limit.
 » 6 weeks ago, # |   0 Im new to Code Forces. Can anyone give the solution to Problem A , as I had tried it a lot..