All posts by date

Find a shortest cycle in a given undirected graph.

You are given n pairs of time intervals. From each pair select exactly one such that the selected time intervals do not intersect.

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

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.