Hello everyone :)
We are happy to announce that XXI Open Cup, GP of Belarus will take place on February 14, 2021 at 11:00 MSK.
The authors of the problems are gepardo, kimden, Mediocrity, 244mhq, Wind_Eagle, and PuRpLe_FoReVeR. Also greencis, aleex, RED_INSIDE, programmer228, mrboorger, Chmel_Tolstiy, and gosuto took part in preparing the contest.
This contest was in Petrozavodsk, so if you have been there and have seen the problems, do not solve it now.
Links: Div. 1, Div. 2. You need an Open Cup login to participate.
You can discuss the contest here after it's over.
Good luck everyone and I hope you'll enjoy the problems!
UPD: Editorial
UPD 2: The contest is added to gym now.
Hope you will enjoy the problems!
How to solve H, K, L?
For H, I tried the following (but got WA6; possibly due to a bug, not sure though)
If we have to go say south-east from (x1,y1) to (x2,y2), then we should take south as long as the x-coordinate is smaller than the y-coordinate. After we get to (k,k) cooodinates, we should keep alternately increasing x and y until we hit x2 or y2. Then, we increase the other coordinate.
I computed all the series by abusing wolfram alpha (though it was doable by hand) and directly wrote the final expressions.
I did casework for all similar cases; in another case, it turns out to be x <= -y.
The model solution is very similar (we consider many cases and use the optimal strategy for each of them), but there is one observation which makes the calculation much simpler. See the editorial for details.
Auto comment: topic has been updated by gepardo (previous revision, new revision, compare).
problem I nice solution)
Fun fact: F can be passed by $$$O(n^3)$$$ brute force.
code
Another fun fact: in B — $$$O(n^4)$$$ can get AC.
code
Our TLE solution was using bitset similarly but with
?and:instead ofifin the deepest loop. orz...Maybe the key is
#pragma GCC optimize("Ofast")#pragma GCC optimize("unroll-loops")It may speed up your program 1.5x as I remember.
maroonrk have written pragmas as if it is a common sense :)
We actually observed a speed up by changing e.g.
c = bs[k] ? c : 0intoif (bs[k]) c=0;somehow, so thanks for sharing your code...We have experienced that sometimes (in particular, some implementation of FFT)
ifis slower than?, that's why we used?today.Here's (a simplified version of) my TLE code. I believe it's very similar to your code, but still, yours runs 1.5x faster than mine on my computer. I really need help from a master of constant optimizations...
Changing "-unroll-loops" to "unroll-loops" gets your solution accepted in 5.88s (it is the wrong way to turn that pragma on, compiler warns "bad option -unroll-loops").
OMG I've been using this pragma for more than a year. Thank you so much!
For the sake of completeness, here is the editorial of Division 2 only problems.
Problem N (Div. 2). Bad Sets Usage. For pieces of each color and rank, check if there are enough of them in the first set. If not, borrow some pieces from the second set and remember them before printing. If there are still not enough, it is impossible to complete the first set.
Problem O. Blots Spilled Unluckily. This problem is an exercise in implementing a depth-first search or a breadth-first search on a grid.
Problem P. Bored Serving Users? We obviously prefer hubs with more sockets. Sort the hubs in non-increasing order by the number of sockets and find the least $$$i$$$ such that the first $$$i$$$ hubs are enough. Remember that connecting $$$i$$$ hubs requires $$$2(i-1)$$$ sockets, thus we have to check that $$$(\sum_{j=1}^{i} k_j) - 2(i-1) \ge N$$$. Also, we should store the indices $$$j$$$ of the hubs along with the values of $$$k_j$$$ to restore the answer.
Problem Q. Base Structure Under... Convert the years $$$A$$$ and $$$B$$$ into AUC, then iterate over all years in the range, represent them in the Roman number system, and find the length of the longest representation.
Auto comment: topic has been updated by gepardo (previous revision, new revision, compare).
Can any author confirm that why the Editorial link is not working ?
UPD:- Mentioning authors gepardo, kimden, Mediocrity, 244mhq, Wind_Eagle and PuRpLe_FoReVeR.
Does the problem still persist? The editorial link works for me.
If you still have an issue, I may try to re-upload it somewhere else.
It is not working for me.
Well, you can also try this link