Merry Christmas everyone
As the editorials of Technocup rounds usually comes later than expected, I hope that this problem analysis could help out whose wants the questions immediately.
Div2A: Santa Claus and a Place in a Class
This is a trivial implementation question, by a bit math we could derive that:
Number of row: (k-1) // (2*m)
Number of desk: ((k-1) mod (2*m)) // 2
( x // y means the integral part of x/y )
And the side of the desk solely depends on the parity of k, as each row has even number of desks.
Div2B: Santa Claus and Keyboard Check
We could solve the question by saving the status of the keys, i.e. not pressed, swapped in pairs, or confirmed in original position, initially all keys have the not pressed status.
When iterating through the pattern, if we’ve found out that the matching of line1[i] and line2[i] different from the current status, we output -1. Finally, we output whose has the swapped status.
One of the hack cases that have gained a lot of points is by exploiting some codes which does not keep the “confirmed in original position” status, which conflicts against the “swapped in pairs’ status.
Div2C: Santa Claus and Robot
Intuitively, we can tell that if the robot changes the vertical / horizontal direction, then the current position of the robot may lie one of the point.
One of the way to approach this question is by keeping whether the robot is free to change it’s vertical or horizontal direction without declaring an extra point. Obviously, when a new point is reached, the robot is allowed to change it’s horizontal and vertical direction for once. By greedy we will make use of this “free to change” status and add points only when we must, thus reaching the minimized amount of points.
Div2D: Santa Claus and a Palindrome
A key observation is that all strings have the same length, therefore if a string: “111 222 333 444 555” is a palindrome, so is “222 111 333 555 444”.
In order to effectively process the strings, we hash them into groups and sort their beautiful value (In C++, use std::map<string, vector > does the job.)
Next, we class each string into one of the following conditions:
The string itself is not a palindrome We will reverse the string to find it’s “counterpart” (i.e. concatenating the two strings would produce a palindrome). We greedily select the largest pair available from the two groups until it is not profitable.
The string itself is a palindrome This implies that the string could be used alone (to be placed right at the middle of the final string), or be used twice just as the other case. As the alone string case could only occur once, we shall greedily update the beautiful value of the alone string. This is left as an exercise to the reader.
Div2E: Santa Claus and Tangerines
Note that if we don’t have enough tangerine to spare, we would always to divide the largest ones first.
Using this fact, we would iterate the joy from 1e7 to 1. If there is enough tangerine, we immediate print that as the answer, the question now reduces to maintaining the amount of tangerines.
We could maintain it by keeping track of all tangerines that we have already counted, to avoid duplicated calculation of the partial parts of the larger ones, we could use another array to make a mark at (Size+1) / 2, as we the amount of tangerines collected effectively increases only when we also include the tangerines of Size/2.
If there is no solution even for joy = 1, print joy = -1.
Div2F: Santa Clauses and a Soccer Championship
http://codeforces.net/problemset/problem/700/B
This is an easier version of Div2F. The main idea is to make use of the fact that the most expensive solution will have all its’ path going through the centroid of the tree. Yes, that is exactly what we needed, we could therefore conclude we only need one city to accommodate all teams, don’t be fooled.
Read this editorial, and the discussions in the blog to learn how to find the centroid of the tree for this question.
http://codeforces.net/blog/entry/46283
The rest to do is grouping, we can do that keeping track of the dfs traversal order, which is relatively easy compared to the main dish.
