Oleksiy PylypenkoOlympiad Years

Kyiv City Olympiad in Informatics

Stage III, Kyiv 2001 · February 2001

Diploma I (Σ 22)Rank 222 ptsDiploma I

One point behind the top score in the grade-9 group (Bohdan Yakovenko, Σ 23).

The Kyiv city stage is the third of the four stages of the Ukrainian school olympiad system in informatics: winners from every district round converge on a single hall in the city, and the problems finally stop being easy. February 2001 was also the first time I sat this stage representing UPML — the Ukrainian Physics and Mathematics Lyceum — rather than my old school, and the step up in the field was immediately obvious against six problems covering everything from chemical-equation balancing to a Koch-snowflake drawing routine.

The result was a Diploma I with Σ = 22 out of a maximum 130, built almost entirely from full marks on the polygon-drawing task (12/12) plus partial credit on two others — one point behind Bohdan Yakovenko at the very top of the grade-9 protocol. It was a strong enough showing to carry into the national stage in Odesa a month later, and it marked the point where competitive programming stopped being a hobby and started being the thing I was actually good at.

ContestantSchoolGradeΣDiploma
Bohdan YakovenkoSchool 241923I
Oleksiy PylypenkoUPML922I
Mykhailo VovnenkoSchool 145919II
Yevhen SlyusarSchool 145917II
Serhiy DashevskyiSchool 171911III
Grade-9 protocol, city (stage III) olympiad, 2001 — top of the group. — Official results spreadsheet (kievoi.ippo.kubg.edu.ua)

Problems

Problems from this contest

Chemistry Equation Balancer

Хімія

simulationsearchchemistry

Statement

Write a program chemie.* that finds the smallest natural-number coefficients (each no greater than 30) to place in front of every chemical formula in a reaction so that the equation balances — the number of atoms of every element is the same on both sides — and then writes out the correctly balanced equation.

Input / Output

File chemie.dat contains the formulas of the reaction's reactants, separated by + and written to the left of =, and of its products, separated by + and written to the right of =. There are at most 10 substances in total. Every chemical element symbol (row 1 of the file) starts with an uppercase Latin letter; an atom count greater than 1 is written below and to the right of the symbol (row 2). A symbol may appear more than once in one formula, and a parenthesized group may carry its own repeated-atom-count subscript. File chemie.res reproduces the input with any coefficient other than 1 inserted before the corresponding formula in row 1, and the matching number of blank positions added to row 2 beneath that coefficient.

Constraints

  • at most 10 substances (reactants + products) in total
  • coefficients are natural numbers not exceeding 30
  • the input guarantees a solution exists and is unique

Example

Input:  Ba(OH)2 +HCl=BaCl2 +H2O
Output: Ba(OH)2 +2HCl=BaCl2 +2H2O
Solution idea

Parse each formula into a multiset of {element: atom count}. Balancing then becomes an integer linear system: for every element, the sum of coefficient × count over the reactants must equal the same sum over the products. Because there are at most 10 species and coefficients are capped at 30, the small search space lets a direct search (or solving the stoichiometric matrix's integer null space and scaling to the smallest positive integer vector) find the unique balancing coefficients.

Polyhedron Faces

Многогранник

graphsplanar-graphsgeometry

Statement

Write a program solid.* that, given the vertex-adjacency (edge) structure of a polyhedron whose surface can be continuously and bijectively mapped onto a sphere, reconstructs its faces.

Input / Output

File solid.dat: line 1 holds a natural number n, the number of vertices. For j from 1 to n, line j+1 lists, in increasing order, the numbers of the vertices connected to vertex j by an edge. Output file solid.res has one line listing n3, n4, …, nm — the number of triangular, quadrilateral, …, m-gonal faces, where m is the largest face size. File l.res (for every face size l that occurs) has nl lines, each listing the vertex numbers of one l-gonal face in order around its perimeter; distinct faces get distinct lines, and lines are ordered so their (rotated) vertex sequences increase lexicographically.

Constraints

  • at most 2000 vertices
  • at most 4000 edges
  • at most one face has more than 8 edges

Example

A tetrahedron (n=4, each vertex adjacent to the other 3) has solid.res equal to 4 (four triangular faces), and 3.res lists the four vertex triples of those triangles.

Solution idea

The adjacency lists describe a planar graph together with a rotation system (the "increasing order" convention around each vertex). Trace each face by walking directed edges: from a directed edge into vertex v, continue along the next edge in v's adjacency order to trace the boundary of one face, repeating until every directed edge has been used exactly once (each face is traced once). Group the traced faces by length and reorder each face's vertex list into the required lexicographically smallest rotation before printing.

Private Interests

Приватні інтереси

dpgame-theorygrid

Statement

Coins are placed on the cells of an m×n grid. Two players alternately move a single pawn either right or up by one cell; player 1 starts at the bottom-left cell and moves first. The game ends once the pawn reaches the top row or the rightmost column. On every move the mover collects the coins on the cell the pawn lands on. Both players play with full information (each knows the coin layout and the pawn's position at all times, and each knows the other plays optimally and identically), always choosing the move that maximizes their own final total, and moving right only when moving up would strictly reduce that total. Write privat.* to predict the final result and the pawn's path.

Input / Output

File privat.dat: line 1 holds m and n. Lines 2 through m+1 give the grid of non-negative integer coin values, row by row, left to right. File privat.res: line 1 holds the two players' final totals (mover 1 first, then mover 2). Line 2 holds the move sequence from first to last move as a string of u (up) and r (right).

Constraints

  • total number of grid cells does not exceed 12346
  • each player's maximum possible winnings do not exceed 65432

Example

Input:
4 4
1 1 2 0
3 7 8 9
3 0 7 1
0 3 3 1

Output:
19 11
uurrr
Solution idea

This is a two-player, perfect-information game on a DAG — the grid, with moves restricted to up/right — so it is a classic minimax computed by dynamic programming from the terminal row/column backward. For each cell, the mover who lands there always takes the option (up or right) that maximizes their own eventual total given optimal play from both sides afterward; ties are broken by the stated rule (move right only when up is strictly worse). The DP has O(mn) states, one per grid cell, each combining the two possible next states.

Recursive Fractal Polygon

Багатокутник

graphicsfractalsrecursion

Statement

Write polygon.* that draws the sides of an equilateral triangle — white on a black background, one side horizontal along the bottom, at maximum size on the screen. Each time Enter is pressed, every straight segment of the current figure is divided into three equal parts, and the middle third is replaced by a two-segment "tent" of the same combined length, with the new vertex pointing outward, away from the area enclosed by the previous figure. After the sixth Enter press, the program stops.

Input / Output

There is no file input or output — the program is interactive. The Enter key advances the figure by one iteration; the screen always shows the current iteration's figure at the largest size that fits.

Constraints

Exactly six iterations are performed after the initial triangle is drawn.

Example

This is the classic Koch-snowflake construction, carried out for six iterations starting from an equilateral triangle.

Solution idea

Keep the figure as an ordered list of vertices. On each iteration, replace every edge (A, B) with four new edges: insert two new points at 1/3 and 2/3 of the way from A to B, plus one new "tip" vertex obtained by rotating the middle third's segment 60° outward around its own midpoint (the standard Koch-curve step). Fix the on-screen scale once, before the first iteration, so that the final and largest iteration still fits the screen, then simply redraw the updated vertex list after each Enter press.

Round-Table Party

Вечірка

logicconstraint-satisfactionstrings

Statement

Write party.* to work out how guests are seated around a round table (facing the center) and each guest's profession, from a list of clues about their relative positions.

Input / Output

Each line of party.dat has 3 parts separated by spaces: a guest's name or profession, a relation symbol, and a second name or profession. The relation symbol is < ("to the left of"), > ("to the right of"), or | ("opposite"). Every line but the last ends with a comma; the last ends with a period. File party.res: each line gives one seating consistent with every clue, listing guests counter-clockwise (viewed from above — so each next guest sits to the right of the previous one) starting from whichever guest's name comes first in Ukrainian alphabetical order, each name followed by that guest's profession in parentheses, entries comma-separated, line ending in a period.

Constraints

  • the number of guests, the length of each word, and the number of clue lines are each at most 25
  • all names and professions in the file are distinct

Example

Input:
philologist | Kyrylo,
Kyrylo < historian,
biologist > Vitaliy,
Fedir > Yevhen,
chemist > Fedir.

Output:
Vitaliy (chemist), Kyrylo (biologist), Yevhen (historian), Fedir (philologist).
Solution idea

Model each clue as a constraint on relative circular position: "left of" adds an offset of +1, "right of" an offset of −1, and "opposite" an offset of half the table size (the number of distinct guests). Build a graph of these relative offsets between guests and professions (treating a profession-clue as referring to whichever guest holds it) and propagate them from an arbitrary anchor to assign every guest a position modulo the table size. If the constraints are consistent, this fixes the seating up to rotation, and the "start from the alphabetically first name" rule then pins down the unique starting point to print.

Square Root by Long Division

Корінь квадратний

bignumarithmeticsimulation

Statement

Write root.* that computes the square root of a positive decimal fraction using the classic manual "long division" square-root algorithm: split the number's digits into 2-digit groups outward from the decimal point (the leftmost group may hold a single digit), then determine the root's digits one at a time the way it is done by hand, producing an exact finite or periodic decimal result when one exists, otherwise a truncated approximation.

Input / Output

File root.dat: one line holding a finite or periodic positive decimal fraction a (up to 1000 characters, including the decimal point and any periodic-part parentheses) and a natural number n not exceeding 100. File root.res: one line holding √a, written as a finite or periodic decimal fraction if one represents it exactly, otherwise √a truncated to n digits after the decimal point.

Constraints

  • a has up to 1000 characters
  • n does not exceed 100

Example

25         -> 5
0.69(4)    -> 0.8(3)
65432.109  -> 4255.7970   (truncated to n=4 digits)
Solution idea

Implement the manual digit-by-digit algorithm directly on the decimal-digit representation: split into 2-digit groups around the decimal point, and at each step search digits d = 0..9 for the largest d such that (20 × root_so_far + d) × d does not exceed the current remainder with the next group appended — exactly mirroring the textbook long-division method. For a periodic input, either expand enough repetitions of the period to guarantee n digits of precision, or track the sequence of intermediate remainders (as in ordinary long division) to detect when they start repeating, which reveals whether — and how — the output itself becomes periodic.

Sources

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