Educational Codeforces Round #108 ABCD Solutions

A. Red and Blue Beans

Solution:

Take the minimum value of $r$ and $b$ as $min$ and the maximum value as $max$ .

Then distribute them to $max-min$ packets. Each packet put only 1 red bean and 1 blue bean.

Then the rest of the $max$ is divided into each packet to see if there are packets more than $d$ beans.

Code:

B. The Cake Is a Lie

Solution:

The cost is fixed. The cost must be $n -1+(m -1)\times n$ .

Code

C. Berland Regional

Solution:

Calculate the prefix sum of skill point of student at each university. Then directly solve it with brute force.

It will not get TLE. Because for each university, we can skip when the $k$ exceed the number of students.

Code:

D. Maximum Sum of Products

Solution:

It can be regarded as a DP problem, although its essence is brute force.

Define $base=\sum\limits_{i=1}^n a_i \cdot b_i$ . Which is the sum without reverse anything.

We define $dp[i][j]$ to represent the sum after reversed $[i,j]$ from $a$ . It's not hard to find that: $dp[i][j]=a[i]\cdot b[j] + a[j]\cdot b[i] - (a[i]\cdot b[i] + a[j]\cdot b[j]) + dp[i+1][j-1] + base$

Of course, $dp[i][i]=base$ . And $dp[i][i+1]$ is quite easy to find out.