Yandex Algorithm Round 2.2 problems analysis

Правка en1, от GlebsHP, 2015-06-13 23:11:17

Good evening Codeforces, let me briefly describe solutions for all problems of today's morning yandex algorithm round. Thanks everyone who participated, I apologize for making problems a bit too tough and viscous for a 100 minutes contest. Anyway, I hope everyone found something interesting.

I would like to thank lperovskaya for organising this competition and managing Yandex.contest, snarknews and SergeiFedorov for their help with the problemset, Endagorion, PavelKunyavskiy, AleX, glebushka98, gustokashin, map and boris for testing. Special thanks to Gassa and my girlfriend Marina Kruglikova for fixing mistakes and disambiguations in English and Russian statements.

Let's get it started.

Problem A. Odysseus Sails Home.

There is no tricky idea behind this problem: one just needs to check if the vector (xf - xs, yf - ys) can be represented as a convex combination of vectors (xi, yi). One of the easiest approaches for the general case is to try all pairs of wind vectors and check if the target vector lies inside the cone they form. However, the devil is in the details. One shouldn't forget to:

  • Check if it's possible to get to Ithaca using only one wind direction;

  • Special if for case (xf, yf) = (xs, ys);

  • Ignore wind vectors (xi, yi) = (0, 0);

  • Avoid usage of doubles — everything fits in long long.

Problem B. Chariot Racing.

For the fixed value t = const we can easily calculate the intersection of all segments (chariots) as max(0, min(bi + vi * t) - max(ai + vi * t)). The problem was to find maximum for t ≥ 0.

Both min(bi + vi * t) and max(ai + vi * t) are convex functions. min(bi + vi * t) is concave upward, because it's derivative only decreases, as faster chariots overtake slower one. Similar max(ai + vi * t) is convex down. This means function min(bi + vi * t) - max(ai + vi * t) is concave upward, and this, in turn is sufficient condition for applying ternary search.

Ternary search was enough to solve the problem, but the solution which does binary search on derivative is faster and more stable to precision. We need to find the maximum t such that the leading chari

Problem C. Equality and Roads.

Problem D. Sequences of Triangles.

Thanks to snarknews — the author and developer of this problem.

Problem E. Strong Squad.

Thanks to SergeiFedorov — the author of this problem.

Problem F. Lexicographically Smallest String.

Теги yandex.algorithm, analysis

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en20 Английский GlebsHP 2015-06-22 19:44:36 4 Tiny change: ' \leq n - 1 - a$ hold' -> ' \leq n - a$ hold'
en19 Английский GlebsHP 2015-06-18 22:03:21 0 (published)
en18 Английский GlebsHP 2015-06-16 04:36:28 0 Tiny change: '(S) < c + $Answer(S')' -> '(S) < c + Answer(S')'
en17 Английский GlebsHP 2015-06-16 04:36:04 6 Tiny change: '(S) < c + $Answer(S')' -> '(S) < c + Answer(S')'
en16 Английский GlebsHP 2015-06-16 04:35:01 1 Tiny change: '(S) < c + $Answer(S')' -> '(S) < c + Answer(S')'
en15 Английский GlebsHP 2015-06-16 04:32:18 6 Tiny change: '(S) < c + $Answer(S')' -> '(S) < c + Answer(S')'
en14 Английский GlebsHP 2015-06-16 04:30:28 4 Tiny change: '(S) < c + $Answer(S')' -> '(S) < c + Answer(S')'
en13 Английский GlebsHP 2015-06-16 04:28:49 1 Tiny change: '(S) < c + $Answer(S')' -> '(S) < c + Answer(S')'
en12 Английский GlebsHP 2015-06-16 04:27:51 3551 (saved to drafts)
en11 Английский GlebsHP 2015-06-14 10:57:57 0 (published)
en10 Английский GlebsHP 2015-06-14 10:53:58 0 Tiny change: 'ity: $O(n log MaxC)' -> 'ity: $O(n \cdot log MaxC)'
en9 Английский GlebsHP 2015-06-14 10:53:20 7 Tiny change: 'ity: $O(n log MaxC)' -> 'ity: $O(n \cdot log MaxC)'
en8 Английский GlebsHP 2015-06-14 10:52:20 6 Tiny change: 'ity: $O(n log MaxC)' -> 'ity: $O(n \cdot log MaxC)'
en7 Английский GlebsHP 2015-06-14 10:51:48 6 Tiny change: 'ity: $O(n log MaxC)' -> 'ity: $O(n \cdot log MaxC)'
en6 Английский GlebsHP 2015-06-14 10:51:06 16
en5 Английский GlebsHP 2015-06-14 10:48:33 127
en4 Английский GlebsHP 2015-06-14 10:38:39 1957
en3 Английский GlebsHP 2015-06-14 00:07:24 116
en2 Английский GlebsHP 2015-06-14 00:00:05 1306
en1 Английский GlebsHP 2015-06-13 23:11:17 2786 Initial revision (saved to drafts)