All posts by date

Jussieu, room 26-25/105, 14:00 until 17:00

Draw a spiral in an s by s grid. Or better, given the coordinates of a grid cell, determine in constant time its color.

Given a grid with a source cell, a destination cell and obstacle cells, find the shortest path from the source to destination, where every direction change along the path costs 1.

Java style identifiers consist of lower and upper case letters, starting with lower cases. C++ style identifiers consist of lower case letters and the underscore sign. Given a word you should detect its style and translate it into the other style, or produce the string “Error!” if it not in one of the styles.

Given a 01-string we have to decide in linear time if it can be obtained by starting with the empty word and repeatedly inserting the word 10 in an arbitrary position.

You have to maintain a consistent system of equations of the form \(x_i - x_j = d\). Write an operation add(i,j,d) that decides if the equation \(x_i - x_j = d\) is consistent with the system and if yes adds it to the system. Complexity should be almost constant time per request.

Consider a 2 player game that plays on a row of coins. Players in turn remove either the leftmost or the rightmost coin until the row is empty. What is the maximum amount that the first player can collect if both players play optimally?

2 hours of competition, followed by discussions.

We read some problems solved by Miguel Oliveira. Let’s learn how to think as the problem setter Miguel Oliveira.

Two vertices u,v are twins if they have the same neighborhood. They are false if uv is not an edge and true twins if uv is an edge. Find a false twin pair in time \(O(|V|+|E|)\).

Given a partition of {0,1,…,n-1} into disjoint sets \(C_1,\ldots,C_k\) and a set \(S\) modify the partition such that each set splits according to membership in S, i.e. produce the partition \(C_1\cap S, C_1\setminus S, \ldots, C_k\cap S, C_k\setminus S\). Find a data-structure representing partitions that allow this operation in time \(O(|S|)\) while preprocessing and space is \(O(n)\). See also wikipedia:partition refinement.

Given an integer table t1,…,tn compute for every position 1≤i≤n the rank of t[i] among the suffix t[i,…,n] that is the number of j≥i such that t[j]≤t[i].

Given a table with n integers, compute the permutation which comes lexicographically next, or answer that the given order is maximal.

Given a permutation on {0,1,…,n-1} find its rank for the lexicographical order. Given a rank find the corresponding permutation.

Accessibility in a grid consisting of cells with heights and water flooding.

Given a bipartite graph \( G(U,V,E) \) find a vertex set \( S \subseteq U \cup V \) of minimum size that covers all edges, i.e. every edge has at least one endpoint in S.

Given a complete oriented arc-weighted graph find a cycle that visits every vertex exactly once (a Hamiltonian cycle) and that has minimal length.

A K by K grid has to be tiled with L by W tiles which can be taken vertically or horizontally. Given K find L, W such that this tiling is possible and (max(L,W)-min(L,W), L+W) is lexicographically maximal subject to W < L < K. All numbers are positive integers.

Given a grid with two openings and two sided mirrors in some grid cells, find an orientation for the mirrors at 45 or -45 degrees, such that a laser beam entering one opening would be reflected all the way to the second opening.

There are n persons that all have to cross a bridge, using a single torch. Person i takes \( t_i \) minutes to cross the bridge. At most 2 persons can walk on the bridge at the same time and need to carry the torch with them. If persons i and j cross together their crossing time is \( \max{ t_i, t_j } \). Minimize the total crossing time.