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.
Contest link
Virtual participation link
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.
The list of our previous contests
Is there going to be any Editorial?
Reminder: it starts in
1 hour30 minutes10 minutes1 minute.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!
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$$$.
Thanks a lot!
It should be also mentioned that
If 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.
Tip: you don't need to kill the first dragon.
Got it !! Thanks !!
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, sandoval95, Kais_Hasan, ...
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).
Is taken from the book: Steven S. Skiena — The Algorithm Design Manual, page 128
First 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.
If 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.
Rotate 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/JmFieuUD
First, 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
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.
I updated it, and this is the solution: https://pastebin.com/mzSvFaVp
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**"
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.
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.
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}.
"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
wtfit would fit in 2 seconds, instead of write some decent $$$O(n $$$ $$$log (n)$$$ $$$log (4*10^8))$$$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.
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...
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.
ok, put 3 or 4 seconds not 2
I 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
Could you please provide a link of your code on an online ide.this submission link is not opening !!!
You need coach mode or solve the problem to see the solution, so here are the codes:
optimized solution AC 1747 ms
original solution TLE
it doesn't require additional log
Is that overall $$$O(n\log)$$$? I couldn't find a solution with such complexity on CF, can you explain it?
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.
How to solve problem J?
3
7 7 7
3
5 5 10
This is one of many possible solutions (Found it by brute force)
How to do K? I got WA on test 18.
Let's say that the sorted heights are a, b, c, d. Then you have two ways:
We 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:
or, with our points,
$$$a + d = b + c$$$.
and understand that the diagonals of the surface should intersect, which instantly gives
$$$a + d = b + c$$$.
Interesting result. I kept on trying to solve 4 cases where each case had different number of distinct elements.
why we sort the heights.
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.
can someone explain B ? binary search was giving me a wrong answer on test 29
This test case may help
3 4
-2 -1 1
how to solve I.
Split the array by colors, each resulting array must be sorted
yeah it worked that was a tough observation thanks!!
Don't know what is your observation, but the solution is simple and well-known:
For 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)
yes
Saying that it's well-known makes me kinda upset :(
Can you explain what do you mean cause i didn't get it?
The idea is that in an optimal way of walking through the bonus points, you'll never change directions more than once.
So if you start by going right, you won't go left and then start going right again (if you're gonna try and go right, left, then right again, it's more optimal to just keep going right as long as necessary and then start going left).
Another observation is that if we start by going right, we'll turn to the left only when we're exactly on a bonus point (we won't walk partway to another bonus point and then turn around without collecting it).
So this leads to the solution idea of choosing the rightmost bonus point we'll walk to and then once we walk there, we immediately start going left for as long as possible.
We can iterate over what point will be the rightmost (which is O(n)) and with the time we have left, we need to see how far left we can go. You can figure this out with binary search or maintaining the optimal leftmost point as you sweep over what the rightmost point will be.
Of course, it might not be optimal to start off going right and then left (we might wanna go left and then right). To avoid copy-pasting code, you can reverse the array and negate all of the values and it becomes equivalent to solving the right-left version.
Let me know if something was unclear or if you have other questions.
Can someone explain Problem-H Tree Painting ?? Thanks in Advance... And also can anyone post the link of editorials??
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.
You 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.
Getting wrong ans on testcase 70 in problem G, any hints??
You exceed query limit.
Try to estimate the number of requests your solution makes on sorted inputs.
See more in my comment above.
Can somebody explain why this solution to problem B gives WA Submission
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:
Try 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: 75994294
My submission was accepted — open at your own risk ;)
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).
Because strings in your
Nodestruct can be O(N) length, so they eat O(N^2) memory in total.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.
Does anyone have the tutorial for problem D with a c++ solution? I tried dijkstra but exceeded the memorty limit.
About the problem G — Nuts and Bolts — I saw in the comments that the problem + solution is described on a book, but I didn't find anything there about the motivation behind the $$$5 \log_{2}n$$$ operations. Why $$$5$$$ and not $$$3$$$ or $$$7$$$?
The solution is randomized, and according to experiments, the multiplier is always in range [3, 3.5]. So we give 5 to make sure bad random doesn't hurt you.
That's quite interesting — I thought that there was something more formal about that choice, didn't think about the possibility of empirical estimation. Thank you.
Do you guys prepare these problems yourselves or are they previous CodeForces Problems, dalex?
Some of them are future Codeforces problems
WA on test 8 in D any help?
It's a small test. Just write stress (there is easy bruteforce solution).
I am sorry I didn't get what you mean
I was asking about Problem D the Lexicographically Minimal Shortest Path
I get wrong answer on test 8 with 2 different approaches
Read https://codeforces.me/blog/entry/83672, section "Don't ask people to debug your code"
I
Read https://codeforces.me/blog/entry/83672, section "Don't ask people to debug your code"
b
Read that section and learn what you should do when you are trying for 3 hours.