А. Guilty — to the kitchen!
Let us reformulate the statement: we need to find the maximum possible value of x (mentioned in the statement) so that the amount of each ingredient will be enough. Clearly, such x equals min(b_i / a_i). Now it suffices to take minimum of the two values: soup volume we gained and the volume of the pan.
В. Game of chess unfinished.
In this problem you are to check exactly what the statement says: if the king's position and all the positions reachable by him in one turn are "beaten", — that's a mate. Thus, we have to determine "beaten" positions correctly. Let us remove the black king from the chessboard, leave the positions of the rooks "unbeaten" (not to forget about possible taking of the rook by the black king), mark positions reachable by rooks "beaten" and then mark positions reachable by white king as "beaten".
С. Safe cracking.
The answer in this problem is always affirmative, which means it is always possible to make all the numbers equal to one. Greedy approach (here we somehow make two adjacent numbers even and then divide them by two) leads the sum of numbers to become less or equal to six in logarithmic (and certainly less than 1000) number of operations. There are several ways do deal with extremal cases: for instance, many of the participants coped with this by the analysis of all of the cases left. The greedy approach only is not sufficient: the crucial test for hacks was (1 1 1 2).
D. Strange town.
Let us associate some numbers a_i with the vertices of the graph. If, for each edge, we assign it the sum of its endpoints' numbers, then the sum of prices along arbitrary hamiltonian cycle will be equal to the doubled sum of a_i. Therefore, it suffices us to devise such numbers a_i so that their pairwise sums will be distinct (as the edge prices should be distinct). As all of the edge prices are bounded above by 1000, we have to think of an efficient strategy to obtain such a_i. Let's choose them in greedy way, so that newly added a_i should not be equal to (a_p + a_q - a_k) for each triple of already chosen a_p, a_q, a_k. It is clear that a_n = O(n^3) as there are O(n^3) "blocking" triples (p, q, k).
Another idea lies in that equality AB+CD=AC+BD should hold for every quadruple of distinct vertices A, B, C, D (summands stay for edge prices), because a hamiltonial cycle with edges AB and CD can be easily rearranged in the cycle with edges AC and BD and the sums of these cycles should be equal.
You may think of how this idea was used by jury to check your solutions in exact and fast way.
The solution of the problem E will appear soon.
Let us reformulate the statement: we need to find the maximum possible value of x (mentioned in the statement) so that the amount of each ingredient will be enough. Clearly, such x equals min(b_i / a_i). Now it suffices to take minimum of the two values: soup volume we gained and the volume of the pan.
В. Game of chess unfinished.
In this problem you are to check exactly what the statement says: if the king's position and all the positions reachable by him in one turn are "beaten", — that's a mate. Thus, we have to determine "beaten" positions correctly. Let us remove the black king from the chessboard, leave the positions of the rooks "unbeaten" (not to forget about possible taking of the rook by the black king), mark positions reachable by rooks "beaten" and then mark positions reachable by white king as "beaten".
С. Safe cracking.
The answer in this problem is always affirmative, which means it is always possible to make all the numbers equal to one. Greedy approach (here we somehow make two adjacent numbers even and then divide them by two) leads the sum of numbers to become less or equal to six in logarithmic (and certainly less than 1000) number of operations. There are several ways do deal with extremal cases: for instance, many of the participants coped with this by the analysis of all of the cases left. The greedy approach only is not sufficient: the crucial test for hacks was (1 1 1 2).
D. Strange town.
Let us associate some numbers a_i with the vertices of the graph. If, for each edge, we assign it the sum of its endpoints' numbers, then the sum of prices along arbitrary hamiltonian cycle will be equal to the doubled sum of a_i. Therefore, it suffices us to devise such numbers a_i so that their pairwise sums will be distinct (as the edge prices should be distinct). As all of the edge prices are bounded above by 1000, we have to think of an efficient strategy to obtain such a_i. Let's choose them in greedy way, so that newly added a_i should not be equal to (a_p + a_q - a_k) for each triple of already chosen a_p, a_q, a_k. It is clear that a_n = O(n^3) as there are O(n^3) "blocking" triples (p, q, k).
Another idea lies in that equality AB+CD=AC+BD should hold for every quadruple of distinct vertices A, B, C, D (summands stay for edge prices), because a hamiltonial cycle with edges AB and CD can be easily rearranged in the cycle with edges AC and BD and the sums of these cycles should be equal.
You may think of how this idea was used by jury to check your solutions in exact and fast way.
The solution of the problem E will appear soon.
just to keep at one place..