Educational Codeforces Round 104 ABCDE Solutions (C++/Java)

A. Arena

Solution:

If a hero is not the lowest level, then he can fight with lower-level heroes.

Code:

C++:

Java:

B. Cat Cycle

Solution:

To take the remainder easier. We change the napping spots index from 1-n to 0-(n-1). Also change the change the problem from "at hour k" to "after k hours". It still same thing.

Now we need calculate total steps which cat B moved. Not hard to find that: only if n is odd number, then every $\frac{n-1}{2}$ steps cat B will have one more step.

So, we can take the remainder and plus one as the answer.

Code:

C++

Java

C. Minimum Ties

Solution:

Can easily got this way: let $i$th team win the $i+1$th team.

So we can extend this way: every time let $i$th team win the $i+diff$th team. If can make sure every time can win a round, then we can keep the score same.

And it not hard to find that: if the number of remain games is more than n, it must can let every team win one game.

Code:

C++

Java

D. Pythagorean Triples

Solution:

Because $a^2=c+b$, so, $2\leq a^2 \leq 2\cdot 10^9$. And so, we can enumerate the value of a.
Put $c=a^2-b$ in $a^2+b^2=c^2$, we can get $b=\frac{a^2-1}{2}$. And then we can get the value of $c$.

So, we can get all possible $c$ between 1 to $10^9$ in preprocess. And for each n, we binary search out the max possible c and the index of it. The answer should be the index + 1.

Code:

C++

Java

E. Cheap Dinner

Solution:

Let go with a brute force DP first. $dp[i][j]$ represent the minimum cost of i-th course choose type-$j$. (drink is course 3)
So $dp[i][j]=\min\limits_{1\leq x \leq n_i}{(dp[i-1][x])}+cost[i][j]$.
But it will get TLE if we get the $\min\limits_{1\leq x \leq n_i}{(dp[i-1][x])}$ by loop. So, we need some way to find this min value.

For the disallow list, we sort the list by $y$ first.
Then, we sort by the cost of $x$-type in $(i-1)$-th course. And at the same time, we sort dp[i-1] in the same way.
Then we can get the first allowed course with minimum cost. (Because the dp[i-1] also sorted)

Code:

C++

Java