All posts by date

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.

café Fluctuat Nec Mergitur, July 9th, 2016, 9:00

Given 4 points, place them in clockwise order and determine the shape formed by these points: square, rectangle, rhombus, parallelogram, trapezium or ordinary quadrilateral.

You are given \( n \) rectilinear rectangles and a threshold \( k \), and want to find out the total area covered by at least \( k \) rectangles.

You are given $n$ rectilinear rectangles and want to find out the total area covered by their union.

Maintain a numerical table that implements the following operations in logarithmic time: query the entry at some index, add a value to all entries between two given indices.

Given a graph with edge weights and vertex heights find a shortest path from a given source to a given destination, that traverses vertices of first increasing and then decreasing heights.

Given a picture of overlaying rectilinear rectangles, detect which rectangle is above which one.

Find a longest path in a tree.

Some easy geometry problem.

Given a graph with expiring dates for every edge, when will the graph be disconnected?

Update Sep 28, 2024. This can also be solved as a binary search for the answer.

Divide a trapezoid into two halfs of same area.

Find a shortest path in the plane between two points avoiding given obstacles with disc shapes.

Two players move in turns a queen on a chessboard, either left, down or diagonally left-down. The first player to reach the lower left corner wins. For what initial positions is the starting player sure to win?

Apply some operations on arcs to make vertex weights non-negative.

Par JJV.

Par Guillaume Aubian.

Par Thomas Espitau.