# Baltic Olympiad in Informatics 2007 - tasks and solutions by V.Naudziunas, L.Petrauskas, T.Fersch, A.Kugel, A.Truu,

By V.Naudziunas, L.Petrauskas, T.Fersch, A.Kugel, A.Truu, J.Radoszewski, E.Panzer, A.Bjorklund, J.Mardell, R.Opmanis, A.Hullmann

Similar nonfiction_3 books

Dual Citizenship in Europe: From Nationhood to Societal Integration

In an age of terrorism and securitized immigration, twin citizenship is of crucial theoretical and modern political drawback. during this quantity, the individuals examine rules concerning twin citizenship throughout Europe. a large spectrum of case experiences are supplied; from the rather restrictive German case to the extra tolerant Dutch case, to the Swedish case, within which twin citizenship is explicitly permitted.

A primer on mapping class groups

The learn of the mapping type team Mod(S) is a classical subject that's experiencing a renaissance. It lies on the juncture of geometry, topology, and crew concept. This e-book explains as many very important theorems, examples, and methods as attainable, quick and without delay, whereas even as giving complete info and maintaining the textual content approximately self-contained.

Extra resources for Baltic Olympiad in Informatics 2007 - tasks and solutions

Example text

That is why for l < r formula tab[l, r] = min(tab[l, i] + tab[i + 1, r] + M : l ≤ i < r) holds. Using this formula we can compute all values of array tab from the shortest to the longest segments. The total time complexity of this solution is O(n3 ), because there are n2 fields of array tab and computing each of them requires O(n) time. cpp — scores 30 points out of 100. 28 Task 6: Sequence A greedy observation To achieve a better time complexity of our solution we need to introduce some greediness.

We have n points on a line (corresponding to the elements of the sequence), so there are n − 1 line segments connecting pairs of adjacent points. In the beginning all n − 1 line segments are erased, so each point forms a single set. A single reduction is equivalent to drawing back one of these line segments, what results in joining the sets that contain the points corresponding to the ends of this line segment; the cost of this operation is equal to the maximal element of the resulting set. This interpretation of the reduce operation will simplify some of the following solutions’ descriptions (as in this version the sequence never becomes shorter).

In each of the following steps (for i = 2, 3, . . , n + 1), if ai is smaller than the element on the top of the stack, then ai is simply pushed on the stack, and in the opposite case all possible reductions are made. In other words, if the element from the top of the stack is not greater than ai , then this element is reduced with smaller of the elements: ai and the element second from the top of the stack. This operation pops the element from the top of the stack and the process continues. This loop stops at one of the conditions: • if i = n + 1 and the stack contains only two elements, one of which must be a0 = ∞ — this terminates the algorithm, the sequence was reduced to a single element, • if ai is smaller than the element on the top of the stack (in this case ai is pushed on the stack) — this terminates the loop in the case i < n + 1; there will surely be such a moment in the loop for every i < n + 1, because a0 > ai .