LKP '18 Contest 2

Welcome to the second LKP Contest of 2018, and the last contest of the year.

The problem writers are KevinWan and george_chen

This round will be rated for all participants who submit at least once.

Before the contest date, you may wish to check out the tips and help pages.

This contest will consist of $6$ ~6~ problems, the difficulty of which may range anywhere from CCC Junior to CCO level.

The contest will use a pretest/systest format for problems 4-6. When you submit to these problems, you will only be judged on some of the test data, called pretests. After the contest, all submissions will be rejudged on the full test data. Pretests typically contain weak test data and do not necessarily include maximum or corner cases.

Some problems offer partial marks in the form of subtasks. If you cannot solve a problem fully, we encourage you to go for these partial marks.

You will have 3 hours to complete the contest. After the contest window begins, you may begin at any time. Once you enter the contest, your personal timer will start counting down and you will be able to submit until 3 hours from when you started, or until the hard deadline (12:00 EST of Dec. 31st), whichever comes first.

After joining the contest, you proceed to the Problems tab to begin. You can also go to Users if you wish to see the rankings.

We have listed below some advice as well as contest strategies:

Start from the beginning. Ties will be broken by the sum of times used to solve the problems starting from the beginning of the contest. The last submission time of your highest score will be used.
It is not guaranteed that the problems will be in order of increasing difficulty. Reading all of the statements is recommended.
Remove all extra debugging code and/or input prompts from your code before submitting. The judge is very strict — most of the time, it requires your output to match exactly.
Do not pause program execution at the end. The judging process is automated. You should use stdin / stdout to perform input / output, respectively.
It is guaranteed that all the problems will be solvable with C++.

At the end of the contest, you may comment below to appeal a judging verdict. In the case of appeals, the decision(s) of DMOJ staff is final.

Problems

Problem	Points	AC Rate	Users	Editorials
LKP '18 Contest 2 P1 - Food Lines	3	37.7%	1173
LKP '18 Contest 2 P2 - Secret Signal	5	23.6%	136	Editorial
LKP '18 Contest 2 P3 - Non-strategic Bombing	7	27.6%	103
LKP '18 Contest 2 P4 - The Zagonetka Machine	12p	14.0%	39	Editorial
LKP '18 Contest 2 P5 - Political Instability	17	21.6%	44
LKP '18 Contest 2 P6 - Reconstruction	25	7.9%	33

Comments

2

JustinXu commented on Jan. 4, 2019, 2:29 p.m. ← edit 2 →

EDIT: How does DMOJ detect cheaters?????????

2

Rimuru commented on Jan. 4, 2019, 3:06 p.m. ← edit 2 →

While undergoing investigation regarding cheating, the admins have decided that unrating is not a punishment, but bringing down rating is.

Edit (in response to your edit): Information cannot be disclosed.

-5

Riolku commented on Dec. 31, 2018, 5:39 p.m. ← edited →

Can we get editorials for these problems? The last LKP Contest didn't have any and it was rather disappointing.

This comment is hidden due to too much negative feedback. Show it anyway.

11
Kirito commented on Dec. 31, 2018, 6:26 p.m. ← edited →
The authors have promised full solutions later. Until then, here are some solution sketches:

For each person that joins the queue, print the minimum, and then add one to this element, this can be done in $\mathcal O(N^2)$ ~\mathcal O(N^2)~ or $\mathcal O(N\log N)$ ~\mathcal O(N\log N)~.

You are looking for the number of subarrays that are congruent to $0 \bmod K$ ~0 \bmod K~. This can be achieved by keeping track of the remainder of each prefix modulo $K$ ~K~, and then counting the number of pairs of identical remainders. This can be done in $\mathcal O(N)$ ~\mathcal O(N)~.

For each query, count the number of contained points with brute force. This gives an $\mathcal O(NQ)$ ~\mathcal O(NQ)~ solution. One way to check if a point $P$ ~P~ is contained is by checking if $|ABP| + |ACP| + |BCP| = |ABC|$ ~|ABP| + |ACP| + |BCP| = |ABC|~, where the notation $|ABC|$ ~|ABC|~ denotes the area of $ABC$ ~ABC~.

One algorithm that quickly solves the 4th problem is the Z-Algorithm. In $\mathcal O(N)$ ~\mathcal O(N)~ time, you can compute the longest prefix that matches the suffix starting from the $i$ ~i~th character for each value of $i$ ~i~. If the length of this prefix equals the length of the suffix, then that prefix is also a suffix. We can count all such strings in $\mathcal O(N)$ ~\mathcal O(N)~ time, and then count the occurrences of all such prefixes in $\mathcal O(N\log N)$ ~\mathcal O(N\log N)~ with binary search, or $\mathcal O(N)$ ~\mathcal O(N)~ with a difference array.

The problem is effectively finding the smallest $x$ ~x~ such that the sum of the $x$ ~x~ largest values is greater than half the total sum. This can be maintained with a balanced binary search tree that stores the values of $V[i]$ ~V[i]~. Each query can thus be answered by a single $\mathcal O(\log N)$ ~\mathcal O(\log N)~ traversal of the tree, leading to an $\mathcal O((N+Q)\log N)$ ~\mathcal O((N+Q)\log N)~ solution.

Note that this is probably not the most efficient implementation.
We decompose the tree with heavy-light decomposition. We store the LCA of all nodes that are currently crucial, and each node that is the LCA of two or more crucial nodes stores the LCA of all crucial nodes in each of its subtrees.
When a new crucial city is added, we can find all of the new edges we need to consider by querying the collective LCA of all currently crucial nodes and the new node: if this is equal to the old LCA, we can find the part of the path that is not part of the induced subtree and add it to a running sum, otherwise we add the whole path from the new node to the old LCA, and update the collective LCA.
A node can be removed by querying for the lowest common ancestor it shares with any node in the tree, which can be done in $\mathcal O(\log N)$ ~\mathcal O(\log N)~ by traversing the HLD chains, and subtracting this path's sum from the running sum. We also check the LCA information stored in the node: if it only has 1 child, then we should subtract the path sum from the running sum, and remove this node. Repeat the process until there is either only 1 node left, or we arrive at a node that has more than 1 child.
An edge update can be performed in the usual way, and the running sum should only be updated if the path is in the induced subtree, which can be checked in $\mathcal O(\log N)$ ~\mathcal O(\log N)~.
Finally, we print the running sum for each query. This yields an $\mathcal O(Q \log^2 N)$ ~\mathcal O(Q \log^2 N)~ solution.
Disclaimer: I have not tested the implementation of this solution.

-2

chelly commented on Dec. 29, 2018, 12:04 a.m.

Hi, I was just wondering whether or not the scoring change mentioned here will be implemented for this contest. Thanks.

-2

Xyene commented on Dec. 29, 2018, 2:09 a.m.

Not for this contest.