Most recent 8 posts

See also all posts ordered by categories.

Lazy segment tree

Maintain a numerical table tab that implements the following operations in logarithmic time: for a range of table indices, query the maximum value, query the minimum value, query the sum, set all entries of that range to some value, add some value to all entries of that range.

Traffic Jam

Given a grid containing some segments, find the minimum number of times segments need to be displaced such that a particular segment can escape from the grid.


Given a boolean formula consisting of Horn clauses, set a minimal number of variables to True in order to satisfy all clauses.

Sprague-Grundy theorem

Given a 2 player impartial game, decide for a given configuration if there is a possibility for the first player to win assuming the second player plays perfectly.

SWERC 2016 in Porto

Le logo du concours ACM/ICPC

Did you know? SWERC 2016 was held in Porto (Portugal) on November 19–20th. It stands for: the SouthWestern European Regional Contest of the ACM ICPC (International Collegiate Programming Contest).

  • 11 problems
  • 5 hours
  • 3 people and 1 keyboard per team

Meeting 12 Novembre 2016

Jussieu, room 26-25/105, from 9:00-12:00 only the ecole polytechnique teams, from 13:00-18:00 (+discussions) open to everyone.

Counting inversions

Given a table, find for every entry how many elements there are to left that are larger and how many elements there are to right that are smaller. In other words find out how many swaps bubble sort will do on the table.

Shortest cycle

Find a shortest cycle in a given undirected graph.