Editorial for An Animal Contest 1 P2 - Alpaca Racing

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: danielz1000

Subtask 1

Notice that $D$ ~D~ is not necessary to solve the problem, as distance is constant for all racers. In this subtask, $X = 100$ ~X = 100~, meaning you can "eliminate" each alpaca with a higher speed than you by using your special power once. Therefore, simply count the number of alpacas that are faster or have the same speed as you and compare the result to $K$ ~K~.

Time Complexity: $\mathcal{O}(N)$ ~\mathcal{O}(N)~

Subtask 2

Here, we explain a simple approach. For every alpaca, it is necessary to lower its speed until it is slower than your alpaca. Simply keep on lowering each alpaca's speed while it is greater than $P$ ~P~ and count the amount of times you do this in order to compare with $K$ ~K~.

Notice that this approach with no optimization may not pass cases where the difference between a certain $a_i$ ~a_i~ and $P$ ~P~ is large and $X$ ~X~ is sufficiently small. To fix this, simply stop looping and incrementing $cnt$ ~cnt~ when $cnt$ ~cnt~ becomes greater than $K$ ~K~, as it is already known that it is impossible to win by this point.

Time Complexity: $\mathcal{O}(K)$ ~\mathcal{O}(K)~

Comments

0

oDrowned_ commented on Sept. 12, 2024, 4:55 p.m. ← edited →

good problem!

0

HisMonDon commented on Sept. 14, 2024, 10:16 p.m.

wsg

0

htoshiro commented on Sept. 13, 2024, 3:19 p.m.

glorious king