Contest hosted on DMOJ https://dmoj.ca/contest/bts24
P1 — Kicking
You can solve each row independently of each other. Using window sums, you can count the number of A
or B
in any contiguous section of $$$K$$$ cells, and thus detect whether any player has an opposing player in front of them.
Time complexity: $$$O(NM)$$$
P2 — Cheating
The key observation is that you can think of the students as a queue standing from $$$1$$$ to $$$M$$$. The students that answer the $$$i$$$-th question are always the first $$$B_i$$$ students in front of the queue, then they move to the back of the queue in the same order that they were in before. We could prove this by induction; if we assume that the difference between the scores (also assume each student $$$j$$$ starts with a score of $$$j \cdot \varepsilon$$$ for some small real number $$$\varepsilon$$$, to preserve tiebreaking order) of the $$$B_i$$$ and $$$B_i + 1$$$ st student in the queue is $$$< A_i$$$ (trivially true for $$$i = 1$$$), answering the question and moving the students to the back of the queue ensures the students are still correctly ordered for question $$$i+1$$$, since $$$A_i$$$ is non-decreasing.
This gives an $$$O(NM)$$$ solution, but we could optimize it by realizing that since scores are always added to up to two contiguous segments of students, we could use a finite difference array (to add $$$x$$$ to a contiguous segment $$$[l, r]$$$ of the original array, we add $$$x$$$ to $$$D_l$$$ and subtract $$$x$$$ from $$$D_{r+1}$$$) and restore the answer by its prefix sum.
Time complexity: $$$O(N + M)$$$
P3 — Tournament
The tournament is modelable as a perfect binary tree, where the first round are the leaves of the tree, the next round are their parents, and so on. Let each node of the tree contain both the maximum number student and the sum of the "underwhelmingness" of the matches in its subtree. To shift the missing student means updating two leaves of the tree and their ancestors, which takes $$$O(\log N)$$$ each time.
The perfect binary tree can be modeled as an array indexed from $$$1$$$ to $$$2N - 1$$$; the leaves are nodes $$$N$$$ to $$$2N-1$$$, and each parent node $$$i$$$ has children $$$2i$$$ and $$$2i + 1$$$. If you are familiar with a data structure called a segment tree, it should form this perfect binary tree when $$$N$$$ is a power of $$$2$$$.
Time complexity: $$$O(N \log N)$$$
P4 — Candidates
First, reorder the candidates by the given ranking, indeed, you may want to do this even before trying to solve this problem, as it makes things easier to visualize. For example, the sample input becomes
3 4 4
3 4 4
1 4 4
4 4 2
2 4 2
1 4 1
4 3 4
2 3 3
4 1 4
2 1 2
1 1 2
Time complexity: $$$O(K (N + \log K))$$$