Oct 232016

I am back!

Link to the contest: http://codeforces.com/contest/732

Problem C:
Brute-force is enough for this one. Enumerate the 4 configurations for the first day, and the 4 four configurations for the last day. For example, the 4 configurations for the first day: arrive before breakfast, before dinner, before supper or after supper.

After that, assume Vasiliy have a breakfasts, b dinners and c suppers on the other days -- then he needs to stay for max(a, b, c) additional days to finish that many meals. Choose the best configuration from the 4 * 4 different configurations.

Problem D:
Binary search + Greedy. One observation: if we could pass the exam for course i on k different dates, choose the last date is always the best, so that we could prepare on some other course earlier.

Thus, we could do binary search on the answer, and judge if it is possible to pass all exams.

Problem E:
The most important thing: each socket can only connect to at most ONE computer.

Sort the power of sockets in ascending order. Then for each socket i with power s_i, check if there is a computer with power s_i, s_i / 2, s_i / 2 / 2, \cdots, 1. You must check in this order to ensure minimum number of adapters are used.

Get TLE using Python, faint. I will try C++ later... -- Got accepted with C++.

 Posted by at 10:38 AM