This match was quite easy compared with the previous one, I particularly found problem C the easiest problem in the match, problem A had a tricky case that cause a lot of re-submits. Problem B was not impossible but need some insight about how to represent the data.
A. Two Problems
http://www.codeforces.com/contest/203/problem/A
A friend of yours told you that he got x points in a programming contest. Because you do not believe him you decide to verify his score.
The contest time is of t minutes. There are only two problems in the contest from which your friend can solve any of them. The first problem had an intial cost of \(a\) points and every minute the cost reduced \(d_{a}\) points. In the same way, the second problem had a initial cost of \(b\) points and every minute the cost reduced \(d_{b}\) points.
Print "YES" if your friend could have earned \(x\) points in the contest otherwise print "NO".
The solution to this problem is brute force. There are four possibles cases we need to consider:
(1) Our friend did not solve any problem.
In the case were \(x = 0\) the answer is "YES". Is always possible that our friend was not able to solve any of the problems in the contest. A lot of people (including myself) miss this case during the competition.
(2) Our friend solved the first problem.
Iterate over all the possible penalty times between \(0 \leq t_{i} < t\) if \(x = a - t_{i} \cdot d_{a}\) print "YES".
(3) Our friend solved the second problem.
Analogous to the previous case, iterate over all the possible penalty times between \(0 \leq t_{i} < t\) if \(x = b - t_{i} \cdot d_{b}\) print "YES".
The overall time complexity of this solution is \(O(t^{2})\).
B. Game on Paper
You are given a \(n\) x \(n\) board. Initially all the cells of the square are white. In each turn you paint a cell black. You task is to return the minimum amount of turns that you need to have a 3 x 3 black square. If no such move exists, print -1.
Because \(n\) is at most 1000, we can easily construct a \(n\) x \(n\) matrix within the memory limits. This matrix is going to keep record of the turn when certain cell was paint for the first time. For convenience unmarked cells are going to be marked as +\(\infty\). Let's consider the first sample case, the propose data-structure should look like this:
Once we have this, the next step is to check all possible 3 x 3 squares. For each value \(A[i][j]\) of the square, we keep record of the highest turn.
Why? because this is the last cell painted in that black square. There is one detail left to cover, how about if we check a square that did not have all the cells painted in black. Because we initialized everything to +\(\infty\) that square will end up having infinity as the highest turn and is not going to be consider as a solution. The last step is iterate over all the maximum turns founded in each square and keep the one with lower value of the turn. If the value is +\(\infty\) the answer become -1.
C. Photographer
http://www.codeforces.com/contest/203/problem/C
You are a professional photographer (or something like that... :P). Your clients usually request one or more photos in two of the following types: low quality and high quality. Low quality photos takes \(a\) megabytes of data. High quality photos takes \(b\) megabytes of data. Your camera can only store \(d\) megabytes of data. Your task is to pleased at most clients as you can; to please a client you need to store in your memory all the photos this client is requesting.
The solution of the problem is greedy, the key idea is to forget about that we have two types photos. We just need to focus in the total amount of megabytes to pleased the \(i\)-th client. We can calculate this with the following formula:
We sort all the clients in non-decreasing order of \(w\), and using this order we served each client until there is no space left.
No comments:
Post a Comment