Oleksiy PylypenkoOlympiad Years

Kyiv City Olympiad in Informatics

Stage III, Kyiv 2003 · February 2003

Diploma II (Σ 70) · 2nd place70 ptsDiploma II

Diploma wording reads '2nd place' — one tier below the sole Diploma I finisher (Bohdan Yakovenko, Σ 150).

By 2003, my final year at UPML, the city stage's problem set had grown noticeably heavier — six problems worth up to 92 points each, including a Ukrainian-language kinship-inference puzzle and a modular power-tower computation — and the protocol itself had changed format, recording every contestant's full name and patronymic rather than a bare surname and initial. My own row reads "Пилипенко Олексій Валерійович," school "УФМЛ КНУ."

Σ = 70, anchored by full or near-full marks on the rectangle-gluing task (16/16) and the longest-common-subsequence task (28/35), earned a Diploma II — the diploma itself is worded "2nd place." Within UPML's own grade-11 cohort, which filled the top of the protocol that year, only Bohdan Yakovenko's outright Diploma I (Σ 150) sat above that tier, even though a handful of Diploma II holders, including teammate Yevhen Palamarchuk, posted higher raw sums while sharing the same diploma degree. It closed out three consecutive years at the city stage and fed directly into the national finals in Donetsk two months later.

ContestantSchoolGradeΣDiploma
Bohdan YakovenkoUPML KNU11150I
Yevhen PalamarchukUPML KNU1185II
Oleksiy PylypenkoUPML KNU1170II
Ihor OnyshchukUPML KNU1169II
Mykola PalamarchukUPML KNU1159II
Grade-11 protocol, city (stage III) olympiad, 2003 — top of the UPML block. — Official results spreadsheet (kievoi.ippo.kubg.edu.ua)

Problems

Problems from this contest

Cryptarithm Multiplication

Множення

cryptarithmbacktrackingsearch

Statement

Write сripto.* that reconstructs a long multiplication of two natural numbers from a "worked" column-multiplication layout in which the multiplication and addition signs have been removed and most digits have been replaced with *. The partial product coming from multiplying the first factor by a 0 digit of the second factor (if any) is omitted entirely, since it contributes only zeros.

Input / Output

File сripto.dat holds the obscured column-multiplication layout, one row per line, each line at most 60 characters, with spaces appearing only before the encoded numbers. File сripto.res must hold the two decimal factors, separated by a space. It is guaranteed the layout has at most one valid solution; if none exists, output No solution!.

Constraints

  • each line of the layout is at most 60 characters
  • the layout has at most one valid solution

Example

A layout encoding "135 × 979" decodes to:

135 979
Solution idea

The layout's line lengths and the positions of its visible digits and asterisks fix the digit-count of each factor and of every partial product. Treat each unknown digit position as a variable, and propagate constraints from the visible digits and from column-wise addition (with carries) of the partial products, backtracking over the remaining unknown positions. The search space stays small because every quantity's digit count is bounded by the 60-character line width, so a depth-first search with constraint propagation finds the unique consistent assignment (or proves none exists).

Regions on a Cube's Surface

Поверхня куба

geometrygraphscomputational-geometry

Statement

A cube has vertices with coordinates 0 or d. A closed, non-self- intersecting polyline with n vertices lies on the cube's surface, all vertex coordinates being non-negative integers. Write cubesurf.* to compute the areas of the regions into which this polyline divides the cube's surface.

Input / Output

File cubesurf.dat holds d and n, followed by the n vertices of the polyline in order, each given as x y z. File cubesurf.res holds the doubled areas of the resulting regions, listed in non-decreasing order.

Constraints

  • d < 10^9
  • n < 10^5

Example

With d = 1000 and the 3-vertex polyline (0,0,0), (1,0,0), (0,13,1), the output is a single doubled-area value, 11999997.

Solution idea

Unfold each of the cube's six faces into the plane, splitting any polyline segment that crosses a cube edge into two segments — one on each of the two adjacent faces — by introducing a new vertex at the crossing point. Each face then holds a planar arrangement of polyline segments partitioning it into polygonal regions, whose (doubled) areas can be computed directly with the shoelace formula. Finally, merge regions that lie on different faces but are connected across a shared, uncut cube edge — via a union-find over adjacent regions — before sorting all the merged regions' areas for output.

Family Relations

Сім'я

graphsstringsad-hoc

Statement

Write family.* that determines the kinship or in-law relationship between two named people, given a database of atomic relationship facts of the form "Name1 – (son | daughter | wife) – Name2", with Name2 written in the genitive case.

Input / Output

File family.who holds two lines, each a single person's name in the nominative case. File family.dat holds the fact lines described above (the statement gives the Ukrainian genitive-case formation rules needed to recover Name2's nominative form, including declension-specific exceptions). File family.res must hold one line: the name from family.who's first line, a dash, the relationship term, and the name from the second line in the genitive case — e.g. "Name1 – RELATION Name2", where RELATION is drawn from a large fixed vocabulary of roughly 40 Ukrainian kinship and in-law terms (father, mother, grandfather, grandson, uncle, cousin, father-in-law, brother-in-law, and so on), each precisely defined in the statement.

Constraints

  • names use only the two declensions covered by the stated rules
  • names are at most 20 letters long
  • fewer than 100 distinct people appear
  • names are case-sensitive: identical spellings with different capitalization denote different people

Example

Given the facts "Nadiya – wife – Borysa" and "Oleksandr – son – Nadiyi", querying (Borys, Oleksandr) yields:

Borys – father – Oleksandra
Solution idea

Parse the fact database into a family graph — nodes are people, typed edges are parent/child and spouse relationships — inflecting every genitive-case name back to its nominative form with the stated declension rules to identify the actual person referenced. Then run a breadth-first search from person 1 to person 2 over the parent/child/spouse edges, and classify the resulting path shape with a lookup table (for example: two "child" edges is a grandchild; a shared parent reached via a sibling edge gives uncle/aunt or cousin; a spouse edge followed by a parent edge gives an in-law) covering the full kinship vocabulary required by the output format.

Longest Common Subsequence

Підпослідовність

dpstringsclassic

Statement

Write subseq.* to compute the length of the longest common subsequence of two sequences {x_j} (length k) and {y_j} (length l).

Input / Output

File subseq.dat holds k, then x_1 … x_k, then l, then y_1 … y_l. File subseq.res holds the length of the longest common subsequence.

Constraints

  • k + l < 16000
  • every sequence value is less than 65432

Example

For x = (1, 2, 3, 4, 5) and y = (1, 3, 5), the longest common subsequence has length 3.

Solution idea

The textbook O(k·l) dynamic program applies directly: dp[i][j] is the length of the longest common subsequence of the first i elements of x and the first j elements of y, extended by 1 whenever x_i = y_j and otherwise taken as the best of dropping the last element of either sequence. Since only k + l < 16000 is bounded (not k and l individually), keep only the previous DP row in memory (a rolling array) so the solution stays within memory even when k and l are both close to 8000.

Power Tower Remainder

Остача

number-theorymodular-arithmeticrecursion

Statement

Write remain.* to compute the remainder modulo a_0 of the right- associative power tower a_1 ^ (a_2 ^ (a_3 ^ ( … ^ (a_{n-2} ^ (a_{n-1} ^ a_n)) … ))).

Input / Output

File remain.dat holds, in order, n, a_0, a_1, …, a_n, each between 1 and 65536, with n < 9. File remain.res holds the remainder.

Constraints

  • every a_i is between 1 and 65536
  • n < 9, so the tower has at most 8 levels

Example

For n = 5, a_0 = 4, a_1..a_5 = 3, 5, 7, 9, 11, the remainder is 3.

Solution idea

A power tower modulo m cannot be computed by simply reducing the exponent modulo m — that shortcut is only valid when the base and modulus are coprime. Instead use the generalized Euler identity a^b mod m = a^(b mod φ(m) + φ(m)) mod m, valid once b is at least log₂(m) (which power towers reach almost immediately). Apply it recursively, top-down: to evaluate the tower mod m, first recursively evaluate the exponent tower modulo φ(m) (tracking whether that exponent is "large enough" to need the +φ(m) correction), then combine. The chain of totients φ(φ(φ(...))) collapses to 1 within a handful of steps, well within the 8-level tower allowed here.

Rectangle Gluing

Склеювання прямокутників

geometryad-hoccombinatorics

Statement

Write rectang.* that decides, for each line of input describing four rectangles, whether the first three rectangles can be "glued" together edge to edge to exactly form the fourth, with no gaps or overlaps.

Input / Output

Each line of rectang.dat holds 8 natural numbers, 1 to 200: the width and height of rectangle 1, then rectangle 2, then rectangle 3, then rectangle 4 (each number right-aligned in a fixed 3-character field). File rectang.res reproduces each input line with the word "так" (yes) or "ні" (no) appended, depending on whether the first three rectangles tile the fourth.

Constraints

  • every width and height is between 1 and 200
  • each number occupies a fixed 3-character field in the input

Example

1 2 1 3 1 4 1 9   -> так
1 2 1 3 1 4 1 8   -> ні
Solution idea

Each of the three source rectangles may be used in either orientation (width/height swapped), and there are only a handful of distinct ways three rectangles can be arranged edge to edge into one larger rectangle — for example, all three placed side by side, or one placed atop a side-by-side pair, or two stacked next to a third. Enumerate the small number of orientation-and-arrangement combinations and check, for each, whether the resulting outer bounding rectangle's width and height match the target rectangle exactly with no gaps or overlaps.

Evidence

Scans & photographs

Sources

  1. [1]Official results spreadsheet (kievoi.ippo.kubg.edu.ua)
  2. [2]Stage III problem set (kievoi.ippo.kubg.edu.ua)