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
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(N \log N)$$$