IOI 2018

A secret string S of length n is composed of characters from \ A, B, X, Y\. The function press(p) returns the length of the longest common prefix of S and the string p. Determine S using at most n+2 calls to press.

We are given a connected undirected graph with N vertices and M edges. Two hidden vertices s t were chosen. For each query we assign every edge weight A or B (A < B), and the grader returns the shortest-path distance...

Build a switching network of binary switches (Y-shaped connectors called ``switches'') to route a ball through a sequence of triggers A_1, A_2,, A_m in order. Each switch has two outputs (X and Y) and alternates betwe...

There are n mountains with heights H_0,, H_ n-1. For a query (L, R), choose a meeting point m [L, R] to minimize: cost(m) = _ i=L ^ R _ j [ (i,m), (i,m)] H_j. Return the minimum cost.

An H W grid has seats numbered 0 to N-1 (N = HW), each at a unique cell. A prefix \ 0, 1,, k-1\ is ``rectangular'' if these seats occupy a contiguous rectangular subgrid. After each swap of two seats, count the number...

For each query (S,E,L,R), determine whether there exists a vertex T such that: S can reach T using only vertices with index at least L; E can reach T using only vertices with index at most R. This is exactly the condi...