Ripatti's blog

By Ripatti, 13 years ago, translation, In English

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))

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I think there is a mistype in the solution for the C problem. Instead of the

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>=0

there 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
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Is O(n2) algorithm optimal for problem B? I mean, can we construct the boolean array in O(n)?
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I think in O(n log n) we can . Sorting array and then use Fenvik tree!
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I'm sorry I have some questions on analysis of problem E.
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 of line thatpasses through this point and is perpendicular to choosen line

Do you mean the line  in the whole space or just in this flat plane as mentioned above. But if it is in the flat plane, there can only be one line  perpendicular to choosen line?

2) 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

 two neighbour of them, what does  the them refer 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? 

Many thanks.
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I am not able to formulate solution for problem E.Tell what I should study before going for developing solution to this problem
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Hill climbing algorithm or three ternary search in convex space.
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
nice tutorial, thanks for it. .
by the way, this isn't too important, but you have a mistake in the title of the post. .
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    The problem can be subdivided into problems where types of dough can be reduced as well as the summation of answer from different subproblems can be used to find the answer to the original problem(OPTIMAL SUBSTRUCTURE PROPERTY).

    Hence divide the problem with 2 states: the amount of dough left and types of stuffing, total cases possible is O(1000*11) and each case can take at most O(100) time Since a[i]/b[i] is maximum 100 so total time is O(1000*11*100) = O(10^6) solvable within 1 sec. Don't forget to add memoisation in the recursion used.

    Solution in C++

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone plz suggest some more problems like C

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks. good editorial