Hello Codeforces users!
I invite all of you to participate in the DMPG '16 online mirror contests. The DMPG '16 is a set of 3 contests divided into three divisions, Gold (harder), Silver (medium), and Bronze (easier). Each contest is a 3-hour virtual contest with a problemset of 6 problems which are disjoint from the other divisions, so you can choose to participate in any subset of the contests (or, if one division is too hard, you can switch to an easier division). These contests will not impact any rating on any platform, so feel free to just enter and look at the problems without any obligation to write code for them. The contests will be hosted on the DMOJ platform. I strongly recommend you all to try the Gold division!
Gold Contest | Silver Contest | Bronze Contest
The contest window is 10 hours beginning at 11:00 EDT; you may pick any 3 hour interval at your convenience during the larger contest window to solve the problems in. You should start within 7 hours of the window starting time if you want to use the full 3 hours to solve problems.
The scoring format will be in the form of subtasks; you get partial marks for each subtask you solve correctly. Additionally, each of the 6 problems have a maximum of 100 points, so a perfect score will be 600 points. During the contest you will have full feedback. Ties in the scoreboard will be broken by the sum of highest-scoring submission times.
The difficulty of the Gold contest will be similar to a CF Div 1 round, except that the easiest problem will be harder and the hardest problem will be easier. A similar situation applies for the Silver contest and a CF Div 2 round, and if CF had Div 3 rounds that would be the difficulty of the Bronze contest.
I was involved only in the preparation of the Gold contest. The authors of the Gold contest are me (FatalEagle), cheezecake, and mrthefakeperson. I would also like to thank Reyna for helping us test the problems for the Gold division.
UPD: You may now begin your virtual contest.
UPD2: The contest is over. Thanks to everyone who participated!
It starts in a few hours :)
I see upsolving is available after the virtual contest has ended. Will editorials be published too, after the timer expires?
I don't have editorials prepared, but I can write some short solution sketches on this blog after the contest.
Solution sketches:
P1: There are two solutions. The first is straightforward: enumerate the number of 1 you are going to use for addition, then add them to the smallest numbers. Compare solution with logs. With some preprocessing, this solution runs in O(N * max(A)) time. The second is greedy. It's best to make 3s with your 1s and 2s, then with your 1s, and any leftover should be dealt with separately.
P2: The main idea is inclusion-exclusion. We decide which subset of letters we must NOT include, and count empty rectangles. This is a well known problem that can be solved in N^2, so we can solve the problem in O(2K * N2), where K = 5.
P3: When a new edge is added, all the edges on the path in the tree that the edge connects will not be a bridge. For each bridge in the tree, we add its contribution to the answer. Assume the tree is rooted. Let sz be the size of the subtree of the lower point of an edge. If the bridge is on the path from the query vertex to the root of the tree, it will contribute N — sz to the sum. Otherwise, it will contribute sz to the sum. We can use heavy-light decomposition and lazy propagation to delete a range of bridges and query the sum.
P4: If you are going to use a technique, it's best to use the technique that counters the current attack. Then you have two choices: either do nothing this turn, use the technique and immediately turn it off to prepare to use the next, or keep the technique going until the next occurrence of this attack. This can be implemented with a simple DP that keeps track of whether you are using an attack at this moment in time, or not. The time complexity is O(N).
P5: Editorial is here.
P6 (solution by Reyna): Divide the array into sqrt(N) blocks. Compute this sum for an element that appears x times: 1 + 2 + 3 + ... + x. Then the original answer can be recovered by 2 * sum + x. Precompute this sum for each interval that starts at the endpoint of a block. During a query, find two closest answers we precomputed to the query interval, one that includes the left query endpoint and one that includes the right query endpoint. We can use a sort of prefix sum idea to get the final sum. Here's an ASCII picture to think about it: (x|y|z). We know the answer for xy and yz. Now the answer for xyz is xy + yz — y + (contribution of x into z). Since the size of x and z are sqrt(N), we can calculate the contribution in sqrt(N) time.
Wow. Thanks a lot for the effort. :)
How to solve P6 in the silver contest?
min-cut/max-flow