**A.** (link) Solution of this problem is written in the fourth paragraph of the statements. You should carefully read and implement it. Only one difficult part is how to to determine which card has higher rank. You can for every card iterate over array [ '6', '7', '8', '9', 'T', 'J', 'Q', 'K', 'A' ] and determine numbers of ranks in this array. Finally, just compare them.

**B.** (link) You can create array for all laptops where true for outdated laptop and false otherwise. Value of every cell of this array you can determine by iterating over all laptops and comparing all their parameters. At the end you should itarate over all laptops once again and choose cheapest one that is not outdated.**C.** (link) Let create array dp by size n x m. dp[i][j] means maximum number of tugriks that the baker can earn if he used i grams of dough and cook buns with stuffings of types 1..j.

Initially dp[i][0] is 0 for all i.

You can easily calculate this dp:

dp[i][j] = max{ dp[i-c[j]*k][j-1] + d[j]*k } for every k from 0 to a[j]/b[j], for which i-c[j]*k>=0

The answer will be max{ dp[k][m] + ((n-k)/c0)*d0 } for every k from 0 to n.

Of course, all divisions in editorial of this problem are integer.

Solution works in O(nma), where a is maximum a_i.**D. **(link) Solution is simulation of all insrtuctions from all of local sights. But naive solution doesn't fit into time limit. You should speed up this solution and do every instruction in O(1).

You can use one of following things.

1. For every position and every direction you can precalculate nearest position of sea. Now before than you do an instruction you should check that nearest position of sea further than position whereto you move after doing the instruction.

2. Let sea cells have 1 and all other ones have 0. For every cell (i,j) you can calculate sum of all cells in the rectangle with angles in (1,1) and (i,j). It can be done by the operations like:

sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + smth

where smth is 0 or 1 according to type of according cell (i,j). Now you can determine sum of numbers for all rectangles of the map. Before you do instruction you should chech that sum of rectangle on which you will go has sum 0.

Solution has complexity O(nm + kz), where z is number of local sights (this number no more than 26).**E.** (link) Author's solution is three ternary search for every demension that are nested within each other.

It works because the function is convex. Maximum of convex functions also convex function. Author not very well imagine convex function in 3 dimrnsions, therefore you can read following proof that algorithm is correct:

Let consider some straight line. Function of distance between points on this line and planet position will be convex (you can imagine it). If you get maximum of such functions it will be convex function too. Let's call this function f1.

Now let's consider flat plane and choose one straight line in it. Set for every point of this line a minumum of function f1 of line that passes through this point and is perpendicular to choosen line. Let's call function on this choosen line f2.

f2 is convex. It can be easily proved by contrary. If f2 is not convex, we can find at least two local minimums. Let's choose two neighbour of them. We can find this two minimums on the plane and drawn through them new line. f1 on this line will be not convex (you also can imagine it). Сontradiction.

Now let's consider all space. Choose one line in it and define function f3 on it. Values of f3 will be minimums of functions f2 of planes that passes through the line and is perpendicular to it. f3 also is convex. Proof of it is analogically to that is written in the previous paragraph. []

Now you can see that minimum can ge found by three ternary search over functions fi. You can add to these functions returning of value in which they reach a minimum.

Also there are solutions that uses idea of Gradient descent or Hill climbing. Author was unable to write this solution (not enough precision), but some participants got AC with such solutions.

There is exact solution O(n^4) (more exactly O(C_n^4)). This solution uses Helly's theorem and Jung's theorem that follows from the first one:

http://en.wikipedia.org/wiki/Helly's_theorem

In this solution you should itarate over all pairs, triples and fours of points and for every of them build minimal ball that cover them. Answer is center of ball with maximum radius.

Also you can google something like that

http://www.inf.ethz.ch/personal/gaertner/miniball.html

There are code and article, but the author of contest is not particularly delved into them))

dp[i][j] = max{ dp[i-c[

i]*k][j-1] + d[i]*k } for every k from 0 to a[j]/b[j], for which i-c[i]*k>=0there should be

dp[i][j] = max{ dp[i-c[

j]*k][j-1] + d[j]*k } for every k from 0 to a[j]/b[j], for which i-c[j]*k>=0^{2}) algorithm optimal for problem B? I mean, can we construct the boolean array in O(n)?1)Now let's consider flat plane and choose one straight line in it. Set for every point of this line a minumum of function f1 ofline thatpasses through this point and is perpendicular to choosen line2)If f2 is not convex, we can find at least two local minimums. Let's choose two neighbour of them. We can find this two minimums on the plane and drawn through them new linetwo neighbour of them,what does thethemrefer to? Two local minimums or sth else? What's more, I don't know how to choose them, only in the line or in the plane?by the way, this isn't too important, but you have a mistake in the title of the post. .

Why is problem C is tagged with "CRT" ? It is simple DP i guess. Can it be solved as a CRT question ?

yes i also want to know this !

Can you please elaborate how dp is helping in probelm C??