Oleksiy PylypenkoOlympiad Years

NetOI — All-Ukrainian Internet Olympiad

NetOI-2002, Vinnytsia (online), Nov 2002 – Feb 2003 · November 2002

17th overall · 170 points · winners listRank 17170 ptsWinners list

By late 2002 the school olympiad calendar had grown an online branch: NetOI-2002, run out of Vinnytsia by olymp.vinnica.ua, was one of the first all-Ukrainian contests you could sit without leaving your house — over a dial-up connection, downloading a round's problem set as an HTML page and mailing or web-submitting source files back within the round's open window instead of writing to paper under supervision. It ran in stages between November 2002 and February 2003, with separate general and "Ukrainian schools" standings, plus a later real-time fourth round for the leaders.

Each of the graded rounds set five problems, and — unlike the strict all-or-nothing paper contests — scoring was partial per test rather than per problem, so a program that got most of a task's test cases right still banked points instead of zero. Round 1 went almost perfectly: 94 points from a 20/20/20/20/14 split, good for 20th place in the Ukrainian-school category (46th overall). Round 2 was rockier — 76 points from a 13/–/–/23/40 split, with two of the five tasks scoring nothing. The two rounds together summed to 170 points, enough for 17th place overall and a place on the published NetOI-2002 winners list.

Problems

Problems from this contest

The Column

Задача CONSTRUCTION

geometry3dshortest-pathunfolding

Statement

Builders were putting up a column shaped like a rectangular box {(x, y, z) | 0 <= x <= A, 0 <= y <= B, 0 <= z <= C}. To make the job easier they need to stretch a rope of minimum length along the surface of the column from the point (x1, y1, z1) to the point (x2, y2, z2) — both points lying on the box's surface. The rope may run over any point of the column's surface. Help the builders find the square of the length of rope they need.

Input / Output

You read, in order, 9 integers separated by spaces: A B C x1 y1 z1 x2 y2 z2 (each of A, B, C does not exceed 100).

You output a single number: the square of the shortest surface path's length.

Constraints

  • each of A, B, C ≤ 100 (positive integers)
  • both endpoints lie on the surface of the box [0, A] × [0, B] × [0, C]

Example

Input: 3 4 4 1 2 4 3 2 1
Output: 25
Solution idea

This is the classic "shortest path on the surface of a box" problem. First work out which face (or faces, if a point sits on an edge) each endpoint lies on. If both points share a face, the answer is just the ordinary 2D squared distance within that face. Otherwise, "unfold" the box: for every sequence of faces that connects the face of the first point to the face of the second point across shared edges, lay those faces out flat into a single plane (rotating each face about the shared edge with its neighbor, like opening a cardboard box), which turns the surface path into a straight line in 2D. Compute the straight-line squared distance for each valid unfolding — a rectangular box only has a handful of distinct face-adjacency paths worth trying — and keep the minimum. Because the box's opposite faces never need to be unfolded through more than two intermediate faces, checking all of these candidate unfoldings is enough to guarantee the true shortest path is found.

Corsair's Route

Задача CORSIAR

geometrycross-productorientation

Statement

The heirs of an old sea corsair found a hand-drawn map of an uninhabited island in their ancestor's house. The map marks, as pairs of Cartesian coordinates, the spots where the corsair once buried his treasures. The heirs quickly sailed to the island and visited every burial spot, walking in straight lines from treasure to treasure in exactly the order they were listed on the map, then walking straight back from the last treasure to the first. Their paths never crossed each other. They split the treasure peacefully, but afterwards none of them could remember whether they had walked the route clockwise or counterclockwise. Help them figure it out.

Input / Output

You first read one number — the number of test cases K (1 <= K <= 100). Then, K times, you read the number of treasures N (1 <= N <= 20) followed by N pairs of real numbers, the coordinates of each treasure in map order (first number is the abscissa, second is the ordinate).

You output a single line of K characters, each 0 or 1: 1 if that test case's route was walked clockwise, 0 if counterclockwise.

Constraints

  • 1 ≤ K ≤ 100
  • 1 ≤ N ≤ 20
  • The route is a simple (non-self-intersecting) closed polygon.

Example

Input:
3
3 0 0.2 1.2 1.2 2.7 0.8
4 4 4 8 4 8 8 4 8
3 10 10 10.6 15 5 15

Output:
100

The first test case (triangle (0, 0.2) → (1.2, 1.2) → (2.7, 0.8)) is walked clockwise (1); the second (the square (4, 4) → (8, 4) → (8, 8) → (4, 8)) and third are walked counterclockwise (0), giving the combined answer 100.

Solution idea

Since the path never self-intersects, its winding direction is the same as the sign of its signed area. Compute the shoelace sum S = Σ (x_i · y_{i+1} − x_{i+1} · y_i) over the N vertices in map order (indices taken cyclically). A positive S means the polygon was traversed counterclockwise (output 0); a negative S means clockwise (output 1). This is an O(N) scan per test case, well within the limits for N ≤ 20 and K ≤ 100.

The Country of Hits

Задача HITS

simulationjosephuslinked-list

Statement

One of the recent debates in Ukraine's political life was how many members Parliament should have and how they should be chosen. To settle it, the country could borrow the method used by the country of Hits. Each of its N upstanding citizens is given a personal number from 1 to N, and the citizens are arranged into a list in some arbitrary order. A special program starts counting citizens along the list: 1, 2, 3, …. Whenever the current count matches a citizen's own personal number, that citizen is removed from the list of ordinary citizens and moved to the list of parliament members; counting then restarts from 1 at the very next citizen in the list. When the count runs off the end of the (remaining) list, it wraps back around to the beginning. The program ends the election as soon as its counter reaches N + 1 without producing a match. Find how many people end up in parliament, and their personal numbers, in the order they were selected.

Input / Output

You read the number of citizens N (9 <= N <= 100000), then N personal numbers — a permutation of 1..N giving the order of the list.

You output the number of parliament members followed by their personal numbers, in selection order, all separated by spaces.

Constraints

  • 9 ≤ N ≤ 100000
  • the N numbers form a permutation of 1..N

Example

Input: 9 1 3 5 7 9 2 4 6 8
Output: 2 1 8

Input: 9 9 7 3 1 2 4 5 6 8
Output: 3 3 1 7
Solution idea

Keep the citizens in a circular doubly linked list in their given order, with a pointer at the current citizen and a local counter c starting at 1. At each step: if c equals the current citizen's own number, remove that citizen (splicing the list), record them as a new parliament member, reset c to 1, and move the pointer to the citizen who is now next; otherwise increment c and advance the pointer by one. If c ever reaches N + 1 without a match since the last reset, the election is over — stop and report the recorded members. Tracing the first example by hand: citizen 1 is hit immediately (c = 1), counting restarts at 3, and after wrapping around the shrinking list once more, citizen 8 is hit at c = 8; a further full pass of length N + 1 = 10 with no match ends the election, giving exactly the two members 1 8. A linked list keeps each removal O(1), so the whole simulation costs O(N) per full unmatched pass plus O(N) per hit.

Palindrome

Задача PALINDROME

dpstringspalindromelcs

Statement

A palindrome is a word that reads the same from both ends. Write a program that turns any given word into a palindrome by deleting the smallest possible number of letters. A "word" here is a sequence of lowercase Latin letters.

Input / Output

You read one word from the keyboard — a sequence of lowercase Latin letters with no spaces, at most 255 characters long.

You output a single number: the minimum number of characters that must be deleted so the word becomes a palindrome.

Constraints

  • 1 ≤ length of the word ≤ 255
  • the word contains only lowercase Latin letters

Example

Input: qwerrewtq
Output: 1

Input: qwert
Output: 4
Solution idea

Let dp[i][j] be the minimum number of deletions needed to turn the substring s[i..j] into a palindrome. The base case is dp[i][i] = 0 (single letters are already palindromes) and dp[i][i-1] = 0 (empty substring). Then:

  • if s[i] == s[j], the two matching ends can stay: dp[i][j] = dp[i+1][j-1]
  • otherwise one end must go: dp[i][j] = 1 + min(dp[i+1][j], dp[i][j-1])

Filling this table by increasing substring length gives dp[0][n-1] as the answer in O(n²) time and O(n²) memory, comfortably fast for n ≤ 255. Equivalently, the answer equals n minus the length of the longest common subsequence of the word and its reverse, since the longest subsequence kept on both ends untouched is exactly the longest palindromic subsequence.

Ranking Ordered Sums

Задача SUM

combinatoricsstars-and-barsrankingmath

Statement

Consider all ways to write a natural number N as an ordered sum of K non-negative terms (1 <= N <= 32, 2 <= K <= 32). Sums that differ only in the order of their terms count as different (so this is about ordered tuples, not partitions in the usual sense). List all such tuples in decreasing lexicographic order — compare the first term first (larger first), then the second term, and so on — and number them starting from 1. Write a program that, given a rank, outputs the corresponding tuple, or, given a tuple, outputs its rank.

For N = 4, K = 3 the numbered list begins:

#1st2nd3rd
1400
2310
3301
7130
8121
9112
15004

(rows 4–6 and 10–14 follow the same descending pattern and are omitted here for brevity).

Input / Output

You first read 0 if you need to find the tuple given its rank, or 1 if you need to find the rank given the tuple. In the first case you then read the number of terms K, the sum N, and the rank of the tuple you want. In the second case you then read the number of terms K followed by the K terms of the tuple. All numbers are separated by spaces. You output either the tuple or its rank, as requested.

Constraints

  • 1 ≤ N ≤ 32
  • 2 ≤ K ≤ 32
  • terms are non-negative integers summing to N

Example

Input: 0 3 4 9
Output: 1 1 2

Input: 1 3 1 2 1
Output: 8
Solution idea

The key tool is a counting function: the number of ways to write a non-negative integer s as an ordered sum of p non-negative terms is the stars-and-bars count C(s + p - 1, p - 1). Precompute these binomial coefficients in a table for s, p up to around 32–63.

To go from a tuple to its rank, walk the terms left to right. At each position, for every value strictly larger than the chosen term (but still leaving a non-negative remainder for the rest of the tuple), add the number of ways to complete the remaining positions with that larger value fixed — this counts every tuple that is lexicographically ahead of the given one at this position. Summing these counts over all positions, plus 1, gives the rank.

To go from a rank to a tuple, do the reverse: at each position, try the largest possible value for that term; the stars-and-bars count tells you how many tuples start with each candidate value, so you can subtract counts block by block (largest value first) until the target rank falls in the current block, fixing that position's term and moving on with the reduced rank and reduced remaining sum. This is the same "convert a rank into a combinatorial object one digit at a time" technique used for ranking permutations or combinations, adapted to a stars-and-bars counting rule.

Sources

  1. [1]Winners list (NetOI-2002, resurrected site)
  2. [2]Round 1 results
  3. [3]Round 2 results
  4. [4]Archive mirror of round problem sets