This post is a French translation of this previous post. — Ce billet est une traduction française du billet original en anglais, réalisée avec Mc et Jill-Jênn.

En avril 2014, Google Paris a organisé un concours de programmation dans ses locaux à Paris : le Google Hash Code. Le problème à résoudre était plutôt amusant. Nous le présentons dans cet article, en précisant certaines stratégies adoptées par les équipes des Écoles normales supérieures. L'édition 2015 du concours est en cours, l'épreuve de qualification a eu lieu jeudi 12 mars (les inscriptions sont closes) ; c'est la nouvelle édition de l'épreuve qui nous a motivés pour rédiger notre solution pour l'épreuve de l'an dernier.

Les Écoles normales supérieures se sont particulièrement bien défendues lors de l'édition 2014, en décrochant les rangs 1, 2, 3, 4, 5, 7, 10 (les auteurs de cet article ont obtenu les rangs 5 et 7) et ont amélioré leurs résultats significativement dans les jours qui suivaient l'épreuve, l'échéance ayant été repoussée afin de pouvoir accueillir de nouvelles solutions.

Description du problème

L'énoncé complet est disponible sur le site officiel du concours.

On dispose d'une carte de Paris (à partir de données OpenStreetMap) qui décrit toutes les intersections et rues de la ville¹. Comme dans la vraie vie, certaines rues sont à sens unique. Les segments sont étiquetés par leur longueur (en mètres) et leur durée de parcours (en secondes). Le problème est le suivant : à partir de 8 voitures Street View qui partent des locaux de Google Paris (rue de Londres), combien de mètres de rues est-il possible de parcourir au maximum en un temps limité de 15 heures ? On peut choisir d'emprunter certaines rues plusieurs fois, mais leur longueur ne sera comptée qu'une seule fois dans le total des mètres parcourus.

Le but est donc de déterminer un itinéraire pour les 8 voitures afin de parcourir un maximum de mètres différents de rues de Paris dans le temps imparti.

La méthode exhaustive

Naturellement, on peut en principe résoudre le problème en énumérant toutes les routes possibles pour les 8 voitures et en choisissant la meilleure. Il y a un nombre fini de telles routes, donc cette approche identifiera nécessairement la solution optimale. Ceci peut suffire pour un mathématicien, mais pas pour un informaticien : les chemins sont trop nombreux, ainsi il serait impossible de tout les explorer en pratique. (Le concours lui aussi est en temps limité…)

À titre de comparaison, s'il s'agissait de n'énumérer que les routes possibles en 10 heures pour une voiture atteignant à chaque minute une nouvelle intersection d'où partent au moins deux routes, il y aurait déjà $2^{10\times 60}$ chemins possibles, soit environ ${10}^{180}$. Même si chaque atome du système solaire était un supercalculateur, on ne parviendrait pas à explorer toutes ces routes avant l'extinction du Soleil.

L'algorithme glouton

À l'inverse, une des approches les plus simples (outre les méthodes purement aléatoires) consiste utiliser un critère d'optimisation glouton : par exemple, choisir la rue la plus longue, la rue la plus rapide à parcourir, etc.). On planifie le parcours des voitures rue par rue, et on utilise le critère à chaque intersection pour choisir simplement la rue dans laquelle on se dirige ensuite.

Glouton basique

On considère pour commencer une unique voiture. Adoptons l'approche suivante : lorsque la voiture aboutit à une intersection qui lui permet de traverser des rues qu'elle n'a pas encore explorées, on choisit l'une d'entre elles : la plus longue, ou bien celle où l'on pourra visiter le plus de mètres par seconde. En revanche, si toutes les rues accessibles ont été visitées, on en choisit une au hasard. On réitère ce procédé tant qu'il reste du temps, et on fait de même pour les autres voitures.

Cette méthode gloutonne aura une performance correcte. Cela dit, de nombreux ajustements sont possibles, par exemple : planifier l'itinéraire de toutes les voitures simultanément plutôt que l'une après l'autre, ou bien commencer par envoyer les voitures à des intersections bien réparties dans Paris pour que chacune n'empiète pas sur le territoire des autres.

Cependant, l'inconvénient principal des solutions gloutonnes est qu'elles sont incapables d'anticiper. Par exemple, lorsqu'on choisit une rue au hasard parmi celles déjà visitées, on ne tente pas de se rapprocher d'un gisement de rues non visitées. Ainsi, une réflexion hâtive (c'est de là que vient le mot "glouton") à partir d'informations partielles risque d'entraîner les voitures dans un dédale de rues déjà visitées.

Méthode gloutonne avec anticipation

On peut combiner la méthode gloutonne avec une recherche exhaustive qui se limite aux quelques prochains choix à faire. En d'autres termes, pour choisir la prochaine rue à suivre à chaque intersection, on ne le fera pas uniquement sur la base des mètres que cela permet de visiter en une étape. À la place, on peut par exemple considérer tous les chemins possibles de longueur 10 et choisir de traverser la première rue de celui qui donne les meilleurs résultats en dix étapes. On peut ensuite planifier le trajet de toutes les voitures en parallèle suivant cette idée. La longueur des chemins à considérer (dans cet exemple, "10") est bien entendu paramétrable ; en général, plus elle est longue, meilleurs seront les résultats, mais plus il sera difficile de les calculer.

Cette idée simple est facile à implémenter et donne des résultats plutôt satisfaisants. Une de nos équipes l'a essayée avec des chemins de longueur 17, sauf erreur, et il semble que plusieurs des dix meilleures équipes l'ont également suivie.

La méthode intelligente

Bien sûr, l'objet de ce billet est de décrire la solution intelligente, celle que l'on a implémentée au terme de l'épreuve, pour le concours étendu.

Voir le problème comme une recherche de chemin eulérien

Pour avoir la bonne intuition, il faut remarquer le lien entre le problème étudié et celui de la recherche d'un chemin eulérien dans un graphe, c'est-à-dire un chemin qui passe par chaque arête une et une seule fois (ou, autrement dit, parcourt le graphe "sans lever le crayon"). En effet, si l'on voit le plan de Paris comme un graphe, où les intersections sont les sommets et les rues sont les arêtes, un chemin eulérien dans ce graphe serait la solution idéale, qui parcourt chaque rue une unique fois sans perdre de temps dans des rues déjà visitées.

Bien sûr, il faut un peu se forcer pour faire ce rapprochement. Déjà, il y a huit voitures ; mais pour l'instant on supposera qu'il n'y en a qu'une seule, et on partagera le parcours entre les huit voitures plus tard. Ensuite, il y a une limite de temps, et toutes les rues n'ont pas la même valeur en termes de nombre de mètres photographiés ; mais on négligera cela et on prétendra être capable de visiter toutes les arêtes dans le temps imparti (on verra que ce n'est pas une supposition si irréaliste ;)). Ainsi, on ignore complètement la valeur en mètres des rues, et on ne s'intéresse qu'au temps nécessaire pour les parcourir.

Enfin, et c'est là la principale difficulté, le graphe d'entrée est un peu inhabituel, car certaines arêtes ne sont pas orientées, mais d'autres le sont, à savoir les rues à sens unique. À cause des sens uniques, il va falloir s'intéresser au problème du graphe eulérien orienté, et il va donc falloir choisir une orientation pour les arêtes non-orientées.

Soyons précis : à proprement parler, il sera impossible de trouver un chemin eulérien. Il est facile de démontrer la célèbre caractérisation suivante des graphes qui ont un chemin eulérien (appelons-les les graphes eulériens) : le degré entrant de chaque nœud (le nombre d'arêtes qui pointent vers lui) doit être égal à son degré sortant². Bien sûr, le graphe d'entrée n'a aucune raison de remplir cette condition. Cependant, pour le problème du Hash Code, il n'est pas vraiment interdit de parcourir la même arête plusieurs fois ; c'est juste qu'on préfère éviter de le faire parce que ça fait perdre du temps.

Ainsi, on tente de rendre le graphe eulérien, en deux étapes. Premièrement, on choisira une direction pour orienter toutes les arêtes qui ne le sont pas, et ce d'une manière qui aide à rendre le graphe "plus eulérien". Ensuite, on ajoutera des arêtes pour le rendre réellement eulérien, afin de matérialiser la possibilité (dispendieuse) de parcourir une deuxième fois des arêtes visitées par ailleurs (c'est-à-dire des arêtes déjà visitées ou qui seront visitées de toute manière à un point ultérieur de la solution).

Orienter les arêtes non-orientées

Pour se ramener au problème du calcul d'un chemin eulérien orienté, il faut choisir une orientation pour toutes les arêtes non-orientées du graphe. Pour que ce problème de recherche de chemin eulérien soit plus facile à résoudre sur le graphe ainsi obtenu, on tentera d'orienter les arêtes d'une façon qui minimise la somme, sur tous les sommets, de la différence entre degré entrant et degré sortant. Intuitivement, plus cette valeur est petite, moins il faudra ajouter d'arêtes pour rendre le graphe eulérien.

Introduisons un peu de terminologie. Un sommet est dit surchargé (dans le graphe original, ou dans un graphe orienté obtenu à partir de ce dernier pour un certain choix d'orientation d'arêtes) si son degré entrant, en ne comptant que les arêtes orientées, est plus petit que son degré sortant. Il est dit sous-chargé dans le cas contraire, et équilibré si les deux degrés sont égaux. La charge d'un sommet est la différence entre son degré entrant et son degré sortant (elle est strictement positive pour un sommet surchargé, et strictement négative pour un sommet sous-chargé).

Comment choisir à présent la meilleure orientation pour les arêtes ? Le choix terminologique donnent déjà des indices : on voudrait orienter les arêtes de sorte à permettre aux sommets initialement surchargés de "transférer" une partie de leur charge aux sommets sous-chargés, suivant des chemins orientés, qui doivent être disjoint pour éviter de compter deux fois les arêtes intermédiaires. Il se trouve que l'on peut formuler cela proprement comme un problème de flot maximum.

Les sommets surchargés et sous-chargés sont respectivement représentés comme des sources et des puits dont la capacité est égale à leur charge. Chaque arête non-orientée est représentée comme une paire d'arêtes orientées allant dans chaque direction, leur capacité étant fixée à 1. Les arêtes déjà orientées sont ignorées.

Le problème de flot correspondant peut être résolu à l'aide de n'importe quel algorithme de flot. Par le théorème des flots entiers, le flot suivant chaque arête est de 0 ou de 1. Ainsi, le résultat du problème de flot décrit une façon d'orienter certaines des arêtes non-orientées (mais pas toutes), suivant la direction du flot qui passe par elles.

Il reste le problème que certaines arêtes du résultat n'ont pas d'orientation spécifiée, à savoir celles qui n'étaient pas utilisées du tout dans le flot optimal. Pour régler ce problème, il suffit d'orienter toutes les arêtes restantes au hasard. Bien sûr, ceci peut faire croître la somme que l'on cherche à minimiser, et pour remédier à cela on effectue ensuite l'amélioration suivante, que l'algorithme de flot avait déjà vérifiée avant la phase d'orientation aléatoire : pour tout chemin orienté qui utilise exclusivement les arêtes nouvellement orientées, si l'on peut diminuer la somme à optimiser en inversant la direction du chemin (c'est-à-dire que l'origine du chemin était sous-chargée et sa destination était surchargée), alors on inverse l'orientation de cette manière. Ceci incrémente la charge de l'origine, décrémente la charge de la destination, et ne change rien aux autres charges, donc c'est une amélioration. Pour effectuer cela de façon efficace, notez qu'il suffit de considérer toutes les paires de sommets. Dès que l'on trouve une paire d'un sommet sous-chargé et d'un sommet surchargé¸ on peut rechercher un chemin allant de l'un à l'autre, et l'inverser si on en trouve un.

Ainsi, à la fin de ce processus, on obtient un graphe orienté où l'on a tenté de minimiser la somme des différences entre le degré entrant et le degré sortant, sur tous les nœuds, pour rendre le graphe aussi eulérien que possible. Il reste à le rendre véritablement eulérien en ajoutant des arêtes pour que tous les sommets soient équilibrés.

Ajouter des arêtes

Intuitivement, les arêtes que l'on veut ajouter pour rendre le graphe eulérien correspondent à la possibilité d'ajouter au chemin des arêtes parcourues par ailleurs.

En d'autres termes, si on ajoute une arête du sommet $i$ au sommet $j$, cela signifie que l'on va aller du sommet $i$ au sommet $j$ suivant un chemin d'arêtes qui seront visitées par ailleurs. Tout le temps passé dans de tels chemins est perdu, et ne contribue en rien à l'objectif. Ainsi, le coût d'ajouter une arête de $i$ à $j$ devrait être la durée nécessaire pour aller de $i$ à $j$ suivant n'importe quel chemin dans le graphe. Pour être plus précis, on peut dans ce cadre suivre un chemin qui viole l'orientation que nous avions choisie pour les arêtes non-orientées, et cela ne pose pas problème ; donc on parle vraiment de la durée d'un plus court chemin dans le graphe original.

Ainsi, on commence par précalculer la durée du plus court chemin entre toutes les paires de sommets du graphe original, à l'aide de l'algorithme de Floyd-Warshall.

Ensuite, on représente le problème de choisir les arêtes à ajouter comme un problème de couplage de poids minimal dans un graphe biparti pondéré. D'un côté du graphe biparti, on place les sommets qui sont surchargés dans le graphe obtenu à l'issue de la phase précédente, copiés en un nombre d'exemplaires égal à leur charge. On crée de la même manière l'autre côté du graphe biparti avec les sommets sous-chargés³. Le graphe biparti dispose également d'une arête entre chaque paire de sommets de chaque partie, dont le poids est le temps du plus court chemin du premier au second.

À présent, un couplage parfait dans ce graphe biparti représente une façon d'ajouter le bon nombre d'arêtes d'une manière qui équilibre tous les sommets, et imposer que le poids d'un tel couplage soit minimal signifie que l'on veut minimiser le temps perdu à suivre des arêtes qui sont visitées par ailleurs. On utilise ainsi l'algorithme hongrois pour résoudre ce problème, et pour compléter le graphe orienté obtenu à l'issue de la phase précédente pour le rendre eulérien.

Construction du chemin eulérien

Le graphe obtenu est maintenant orienté, et chaque sommet est équilibré, donc on peut y construire un chemin eulérien. Pour le calculer, une simple approche gloutonne suffit. (Il y a peut-être des améliorations possibles pour optimiser par rapport aux étapes suivantes, mais nous n'en avons pas cherché.)

Depuis le chemin eulérien, en remplaçant les arêtes qui ont été ajoutées dans la phase précédente par les plus courts chemins auxquels elles correspondent, nous obtenons un itinéraire qui est une assez bonne solution pour le parcours de toutes les rues de Paris par une unique voiture en le moins de temps possible.

Partage du chemin entre voitures

On se rappelle à présent que l'on a huit voitures et non une seule, et qu'il faut donc découper la route obtenue entre les voitures.

Voici la méthode suivie. Prenons la première voiture, et faisons-lui suivre le début du chemin jusqu'à un quart du temps alloué. Ensuite, en considérant le reste du chemin qu'elle peut parcourir jusqu'à la fin de son temps, on cherche le sommet qu'elle traverse qui est le plus rapide à atteindre depuis le point de départ (dont on rappelle qu'il s'agit des bureaux de Google). La première voiture va jusqu'à ce point, et s'arrête. La voiture suivante prend le plus court chemin jusqu'à ce point, poursuit sa route suivant la suite de l'itinéraire pendant un quart du temps alloué, puis continue jusqu'au point le plus proche du point de départ obtenu de la même manière. On répète cela jusqu'à la dernière voiture, qui s'occupe de tout le reste de l'itinéraire.

Bien entendu, si l'on coupe le chemin à un point proche du point de départ, c'est pour minimiser le temps perdu par la voiture suivante pour reprendre l'itinéraire. Cette solution donnera toujours trop de travail à la dernière voiture, mais on verra plus tard comment équilibrer la durée des trajets des voitures. Si on force les voitures à parcourir l'itinéraire pendant au moins un quart du temps alloué, c'est pour rendre cet équilibrage plus facile, en garantissant que les parcours de toutes les voitures sont suffisamment longs pour se rencontrer de nombreuses fois.

Le trajet obtenu constitue la solution initiale pour huit voitures. Il reste à l'optimiser.

Optimisations

On itère maintenant un certain nombre d'optimisations destinées à modifier légèrement le chemin en l'améliorant, jusqu'à ce que l'on juge que la qualité du résultat est suffisante.

Bien entendu, toutes les optimisations ne sont pas aussi efficaces, et l'ordre dans lequel elles sont appliquées peut engendrer des différences significatives. Il est difficile de retrouver exactement l'ordre dans lequel elles ont été appliquées pendant le concours, ni le nombre d'itérations, mais il n'y avait de toute manière pas beaucoup de logique pour justifier ces choix.

Écrémage

Pour tout sous-chemin d'un chemin d'une voiture, qui consiste uniquement d'arêtes déjà visitées par ailleurs, on peut le remplacer par un plus court chemin entre les extrémités du sous-chemin, calculé à l'aide du Floyd-Warshall précédemment évoqué.

Échange de boucles

Supposons qu'une voiture se déplace d'un sommet $i$ à un sommet $j$, puis effectue un cycle $C$, puis se déplace à nouveau de $j$ à $i$, et l'arête entre $i$ et $j$ est déjà visitée par ailleurs. Si on peut trouver une voiture qui passe par n'importe lequel des sommets de $C$, alors cette voiture peut s'occuper de tout le cycle $C$ sur son chemin, et la première voiture peut économiser $C$ et l'aller-retour entre $i$ et $j$ (l'économie totale est donc de deux fois la longueur de l'arête $i$—$j$).

Bien entendu, ceci peut contribuer à déséquilibrer la longueur du trajet des voitures, mais on s'occupera de ces situations plus tard.

Raccourcissement

Si une voiture termine son chemin par un sous-chemin déjà visité par une autre voiture, on peut simplement le supprimer.

Exploration exhaustive

Pour tout sous-chemin de chaque chemin de chaque voiture, jusqu'à une certaine longueur, on vérifie si le sous-chemin peut être remplacé par un chemin plus court, qui visite tout de même toutes les rues du chemin qui ne sont pas visitées par ailleurs. Dans ce cas, on remplace le sous-chemin par le chemin trouvé. Ceci diffère de l'écrémage en ce sens que les sous-chemins peuvent inclure des arêtes qui ne sont pas visitées par ailleurs ; dans ce cas, le remplacement devra également passer par ces arêtes, possiblement dans un ordre différent.

Équilibrage

Jusqu'ici, on n'a pas tenu compte de la contrainte de temps maximal (15 heures). Celle-ci a besoin d'être satisfaite par toutes les voitures ; on ne peut donc pas se contenter d'une solution où une voiture a un trajet beaucoup plus long que les autres. Du reste, si on parvient à trouver une solution qui passe par toutes les arêtes (et ce fut le cas !), la qualité d'une solution est jugée selon son temps restant, c'est-à-dire $T-{max}_{c\in 1,\dots ,8}{t}_c$ où $T$ est la limite de temps, et $t_c$ le temps pris par la voiture $c$.

Idéalement, on voudrait donc que toutes les voitures effectuent des trajets qui prennent le même temps. Ceci signifie qu'il est souhaitable d'échanger des portions longues du trajet des voitures les plus occupées avec des portions plus courtes du trajet des voitures moins occupées.

En pratique, on recherche des paires de sommets $x$ et $y$ telles que deux voitures passent par $x$ puis par $y$. En général, les chemins des deux voitures entre $x$ et $y$ auront une longueur différente. Ainsi, si échanger les chemins permet de diminuer la différence de durée entre l'itinéraire des deux voitures, alors on procède à l'échange.

Cette méthode gloutonne peut être itérée aussi longtemps que nécessaire. En fait, comme les chemins des voitures ont tendance à se croiser très souvent, la méthode fonctionne très bien et converge rapidement vers un état où toutes les voitures suivent des itinéraires dont la durée est la même, à la seconde près, peu importe les itinéraires initiaux.

Résultats

La stratégie intelligente décrite ici parvient à parcourir toutes les rues de Paris dans le temps alloué (et même en 9 minutes de moins). Dommage de ne pas l'avoir réussi pendant le concours lui-même (plutôt que pendant l'extension), mais c'est déjà ça ! :)

État de l'art

Nous avons développé toutes ces méthodes par nous-mêmes, et n'avons pas regardé sérieusement l'état de l'art des méthodes utilisées par des gens qui ont déjà essayé de résoudre des problèmes similaires. En fait, notre problème est connu comme le problème du postier chinois, car il est également utile pour optimiser les distributions postales (et a été étudié par un mathématicien chinois).

Plus spécifiquement, notre version est le "$k$-mixed postman problem", car on a plusieurs voitures ($k$=8), et car le graphe est mixte : certaines des arêtes sont orientées, d'autres non. De manière assez surprenante, la solution optimale peut être calculée en temps polynomial pour les versions orientées et non-orientées⁴, mais la version mixte est NP-difficile⁵.

Il serait intéressant de comparer le résultat de notre méthode à l'état de l'art. Nous nous sommes rapidement comparés à des résultats de référence sur des jeux de données existants et nous n'avons pas de raison de penser que nos algorithmes sont meilleurs. Mais peu importe, nous nous sommes bien amusés. :)

Remerciements

Les idées de ce billet ne sont pas les miennes : à peu près tout a été fait par d'autres élèves de l'ENS. Les étapes de la solution intelligente, hormis les optimisations subséquentes, ont été conçues et implémentées par gnomnain (code). Et les optimisations par elarnon (code), and Mc and mehdi (code). (Tout le code est "en écriture seule" (write-only) et ne contient aucune documentation d'aucune sorte, je déconseille de tenter de l'utiliser.)

Ce billet a été écrit à partir d'une version préliminaire de Mc. Merci à Jill-Jênn, elarnon, Armavica et gprano pour leur relecture et remarques sur la version originale.

The Google Hash Code 2015 selection round was yesterday. This post summarizes the problem of the contest, and the approach followed by my team (ENS Ulm 1), providing code for a simplified version of our approach that achieves a score of 388 with less than 100 lines of code.

You can read the problem statements in French and English and the input file. In brief, the task was a knapsack variant where you had to assign servers to positions in a grid, and then assign the servers to groups to maximize a certain function that favors balanced assignments.

The decision problem associated to the task (is it possible to achieve score n given the set of constraints) is NP-complete. It is in NP because one can represent solutions to the problem in polynomial space, and test in polynomial time whether a solution achieves the required score and satisfies the input constraints. Hence, an NP algorithm to solve the problem is to guess a solution, check that it is indeed a solution, and check that it achieves the required score. It is NP-hard by a reduction from the NP-hard partition problem. Consider a multiset of numbers that is the input to the partition problem. Create an instance of the Hash Code problem by making this the multiset of the capacities of servers, with all servers having size one. Now, say you have only two rows, a number of columns that is larger than the number of servers, no forbidden squares, and one single group to create. The maximal possible capacity (half of the total capacity) can be achieved if and only if the original multiset of numbers can be partitioned in two sets with equal sums (the set of servers in the first row, and the set of servers in the second row; clearly it is never useful to not use a server in this case, because all can fit on the grid). This reduction from the partition problem to (a very restricted case of) the Hash Code problem shows that it is NP-hard.

Of course, this hardness proof is not relevant in practice, because the contest task was to solve the problem on one specific instance. Hence, in the four hours or so that the contest lasted, the idea was to try heuristics to reach the best possible solution on that specific instance.

My team (ENS Ulm 1) reached the top position one hour after the start of the contest, and stayed there for almost two hours until other teams caught up with us. So we found a fairly good basic solution quickly but then we didn't optimize it very well. (By contrast, we were beaten by teams that had a worse initial solution but better incremental optimizations.) The goal of this post is to explain the basic strategy that we coded in one hour. I give an explanation of the strategy in English, and then a cleaned-up version of the code for it (less than 100 lines!). As this is a simplification of our solution, its final score is 388 (and not 400 as we finally achieved); we conclude by the additional ideas that are not shown in the code.

Strategy

The solution is entirely greedy, meaning that it never changes its mind about the choices that it makes, and does all choices in sequence, in a certain order, and optimizing certain criteria.

We try to place each server sequentially. However, we consider them according to a smart (greedy) order: we sort them by decreasing capacity per cell. In other words, we try to place first the servers that give the most capacity divided by the number of cells that they use up. In case of ties, we sort servers by decreasing size, because when packing it is more efficient to pack larger items first.

For each server, we greedily assign it to a group by choosing the group with lowest guaranteed capacity. This means that we compute the guaranteed capacity of each group: the capacity that is guaranteed to remain for any row deletion, which is just the total capacity of servers assigned to the group minus the maximum over rows of the capacity of servers of this row assigned to the group. Once the group is chosen, we try to find room for the server on the grid. If we can, we will place it there and assign it to the chosen group.

To place the server, we consider all rows in the following order: we sort them by ascending capacity for the chosen group. The intuition is that we would rather put the server on a row where the existing capacity for this group is as small as possible, to balance the capacity of the group on all rows and minimize the impact of the row deletion. Then, in every row considered in that order, we try to place the server greedily by finding the first sequence of contiguous free cells of sufficient size. We place the server whenever we find a suitable location for it, otherwise we choose not to use the server. We then continue with the next server.

To make this faster, we maintain the following information: the table of used cells (initialized with the forbidden cells and updated as we place servers), the sum of the capacities assigned to each group, and the sum of the capacities assigned to each group on each row.

Code

The code is written in C++ for speed, in the terse and monolithic style of programming contests. It is optimized for programmer time and running time, not at all for readability or reusability. However, I went over the code to clean it up, ensure that variables names were logical (if succinct), and add a few critical comments. This code produces a solution with score 388, runs instantaneously, and is about 100 lines long.

#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

// generous bound on all possible inputs and sizes
#define MAXN 1002

struct Server {
  int id, z, c;
  Server(int id = 0, int z = 0, int c = 0) : id(id), z(z), c(c) {}
  // sort servers by decreasing c/z then decreasing z
  bool operator< (const Server &s) const {
    // a/b < c/d iff da < bc and (e, f) < (g, h) with f,h < N iff eN+f < gN+h
    return z*s.c*MAXN + s.z < s.z*c*MAXN + z;
  }
};

// declaring those globally means we don't have to initialize them
int R, S, U, P, M;
vector<Server> serv;
char grid[MAXN][MAXN]; // filled grid cells, indexed by row, col
int capa[MAXN]; // capa[g]: total capacity allocated to group g
int gcapa[MAXN][MAXN]; // gcapa[r][g]: total capacity for group g in row r
vector<pair<int, pair<int, int> > > out; // group, row, col

int main(int argc, char **argv) {
  scanf("%d%d%d%d%d", &R, &S, &U, &P, &M);
  for (int i = 0; i < U; i++) {
    int r, s;
    scanf("%d%d", &r, &s);
    grid[r][s] = 1; // grid cell is occupied
  }
  for (int i = 0; i < M; i++) {
    int z, c;
    scanf("%d%d", &z, &c);
    serv.push_back(Server(i, z, c));
    out.push_back(make_pair(-1, make_pair(-1, -1))); // server is unused
  }

  sort(serv.begin(), serv.end());

  for (int s = 0; s < M; s++) {
    // place server s
    int guar[MAXN]; // guar[g]: guaranteed capa for group g
    for (int g = 0; g < P; g++)
      guar[g] = capa[g];
    for (int r = 0; r < R; r++)
      for (int g = 0; g < P; g++)
        guar[g] = min(guar[g], capa[g] - gcapa[r][g]); // capa if killing row r
    int mguar = guar[0], mg = 0; // min and argmin of guar over all groups
    for (int g = 0; g < P; g++)
      if (guar[g] < mguar) {
        mguar = guar[g];
        mg = g;
      }
    // mg is the group with lowest guar, assign s to mg if we can place it
    vector<pair<int, int> > rows;
    for (int r = 0; r < R; r++)
      rows.push_back(make_pair<int, int>(gcapa[r][mg], r));
    sort(rows.begin(), rows.end()); // sort rows by inc capa for group mg
    int fr = -1, fc = -1; // row and col to place s
    for (int rr = 0; rr < R; rr++) {
      int contig = 0; // count contiguous free cells
      fr = rows[rr].second;
      for (int c = 0; c < S; c++) {
        if (!grid[fr][c])
          contig++;
        else
          contig = 0;
        if (contig == serv[s].z) {
          fc = c - (serv[s].z - 1); // we can place s at (fr, fc)
          rr = R; // break out of both loops
          break;
        }
      }
    }
    if (fc >= 0) {
      // assign s to mg and place it at (fr, fc)
      capa[mg] += serv[s].c;
      gcapa[fr][mg] += serv[s].c;
      for (int d = 0; d < serv[s].z; d++)
        grid[fr][fc+d] = 1; // squares occupied by s
      out[serv[s].id] = make_pair(mg, make_pair(fr, fc));
    }
  }

  for (int i= 0 ; i < M; i++)
    if (out[i].first >= 0)
      printf("%d %d %d\n", out[i].first,
          out[i].second.first, out[i].second.second);
    else
      printf("x\n");

  return 0;
}

Extensions

To improve the performance of our solution by 12 points, we changed a few additional things:

• Once the list of servers was sorted, we kept the top of that list with the servers whose total size filled all the free space in the grid, and, assuming optimistically that we would be able to place those servers, we sorted them by decreasing size to help the packing.
• When considering the rows when choosing where to place a server, we broke ties on the assigned capacity by examining first the rows with the most free space left.
• We did random unprincipled tweaks which happened to make our solution better by one or two points.
• The last point (from 399 to 400) was gained by a brute-force incremental optimization that tried to perform random swaps.

Our brute-force incremental optimization was not very effective. I think that teams that beat us had a much more efficient approach.

There was a recent rumor about Dropbox accessing all files of your machine, and while it turns out that it was probably not true this time, I remembered getting a sinking feeling when reading this and worrying about whether my files were safe. Dropbox is one of the few pieces of proprietary software that I run, and this story reminded me that I was just blindly trusting it to not act wrong, as I was not restricting its interaction with the rest of my data in any way.

I had to change this. Hence this post, which can probably also serve as a more general description of how to properly restrict any kind of untrusted or possibly insecure programs. I should point out that I am using a Debian system, so this may vary for other Linux distros.

I want to stress that this is post is not an endorsement of Dropbox, even though it may have the unintended effect of encouraging privacy-conscious users to run Dropbox because they can more easily tame it. Dropbox is software I'd really rather not run: it is a proprietary client, for a proprietary protocol, for a centralized cloud service, with no suitable privacy guarantees, it fosters network effects by rewarding users if they can attract more users, it encourages collaboration within the ecosystem and does not facilitate it across ecosystems, and forkability is low (you can have your files, but unlike, e.g., git, I'm not sure it's easy to export the history). The problem is that I need to collaborate with other people who use Dropbox, and I don't know what to suggest to them instead if they won't use a real VCS (I have complained before about this). If you're one of the few people whom I have to use Dropbox to work with, I invite you to feel guilty about all the work that I have to do for you. ;)

So this post describes how to sandbox Dropbox if you have to use it, but keep in mind that the right solution is not to use it altogether.

I took the most part from an existing guide but deviated from it in quite many respects, that I will point out. There is another more paranoid guide about running Dropbox in a chroot, but this is a bit more heavy and the guide relies on Gentoo-specific tools, so I preferred to stick with the simpler approach of running Dropbox as its own user. (There would also be the even stronger approach of running Dropbox in a virtual machine, e.g., using KVM.)¹ Of course, the crucial parts below are those where you run Dropbox as a separate user with no access to your files or the X server, plus the necessary bindfs trick to access its files as your real user. The rest is icing on the cake.

Preliminary precautions

First, of course, for what we are doing to make sense, you should make sure that the permissions of your own files with your real user are properly set up, so that the restricted dropbox user that we will create is indeed unable to access them. This probably includes setting up a suitable umask and going over your files to set the right permissions. (If you haven't done this before, you should be prepared for some problems later. For instance, when first updating this blog with my new umask, I temporarily broke it because the permissions of the compiled files were not right.)

Second, you should ensure that access to your X server is suitably restricted. Verify that xhost is returning only SI:localuser:youruser, where youruser is your user name. Otherwise, set it up. To do so automatically, I use the following script when starting my X session (I wonder if there is a cleaner way):

xhost +si:localuser:`whoami`
xhost | sed 1d | grep -v `whoami` | while read l; do
  xhost "-$l"
done

Contrary to the other guide, we will not be setting up any form of access to the X server by the dropbox user. Indeed, from my attempts, Dropbox works fine on an entirely headless system. This simplifies things a bit.

It may the case that, no matter what xhost says, local connections to the X server are still allowed, so that the dropbox user will be able to connect to it in the next step. If this happens, you need to use xauth instead. This may already have been setup for you by your graphical display manager; otherwise, you can rely on startx to do it for you. However, beware: xinit will not do it for you.

Creating the user

We create a separate dropbox user to run Dropbox, with disabled password (i.e., password authentication is not permitted) and no login shell.

sudo adduser --disabled-password dropbox
sudo chsh -s /bin/false dropbox

Contrary to the other guide, everything Dropbox-related will run as that user and live within that user's home directory. In particular, we will not be installing Dropbox in /usr/bin.

Now, open a shell as the dropbox user by issuing:

sudo su -s /bin/bash dropbox

Try to go around the home directory of your real user and check that your precious files cannot be opened. Check that, even with the DISPLAY variable correctly set, you cannot run graphical applications (e.g., xeyes).

Disk usage

I like the idea of restricting quotas so I recap it from the other guide. Edit /etc/fstab to add usrjquota=aquota.user,jqfmt=vfsv0 as mount options to the partition where the home of the dropbox user is (let's say it's /home), and do the following, adapting for your Dropbox quota (4GB here):

sudo apt-get install quota quotatool
sudo mount -o remount /home
sudo quotacheck -cavm
sudo quotaon /home
sudo quotatool -bu dropbox -l 4000MB /home

By contrast with the original guide, this is using journaled quotas, which are supposed to be more resilient; and I only set up user quotas because group quotas do not seem needed here.

Test the setup as the dropbox user by issuing, e.g.:

dd if=/dev/zero of=test bs=1M count=5000

Check that this fails with a Disk quota exceeded error. As for persisting across reboots, with my config the quotas were automatically enforced at boot (you can check this with quotaon -p /home).

Memory usage

This section restricts the overall RAM usage of the dropbox user, so that the system would not malfunction if Dropbox started allocating too much memory. It generalizes to other restrictions that can be enforced using cgroups, e.g., IO and CPU priorities, etc., but I won't go into this here.

You need to install the cgroup-tools package. Check if memory support is enabled by issuing:

cat /proc/cgroups | grep memory | awk '{print $4}'

If this returns 0, as it seems to do by default in Debian, add cgroup_enable=memory to your GRUB_CMDLINE_LINUX in /etc/default/grub, run sudo update-grub2 and reboot. (Yes, it sucks having to reboot, but I don't know a different way.)

Now a confusing thing is that for cgroups to be created and tasks to be allocated to the right cgroup, you have to edit /etc/cgconfig.conf and /etc/cgrules.conf, but for this to do anything you need to arrange for cgconfigparser and cgrulesengd to be started at boot time, and there is apparently no init script to do it in Debian (see /usr/share/doc/cgroup-tools/TODO.Debian). As a crappy hack I added to /etc/rc.local:

cgconfigparser -l /etc/cgconfig.conf
cgrulesengd

Now we can setup the cgroup for dropbox, by adding the following to /etc/cgconfig.conf to define the group (adjust 256 MB to what you think is acceptable). (This is where additional restrictions (CPU shares, IO shares, etc.) would go if you wanted to add them.)

group dropbox {
    memory {
        memory.limit_in_bytes = 256000000;
    }
}

Now, add the following to /etc/cgrules.conf to assign tasks by the dropbox user to the right group. The first dropbox is the user, the second is the cgroup. (Note that memory would need to be changed to * if you added different kinds of restrictions.)

dropbox memory dropbox/

Now reload the groups and tell the cgrulesengd daemon to reload the rules (assuming you have started that daemon, at boot or otherwise):

sudo cgconfigparser -l /etc/cgconfig.conf
sudo pkill -SIGUSR2 cgrulesengd

To check that this works, open a shell as the dropbox user. Check that the shell is indeed in the dropbox cgroup, by issuing:

cat /proc/$$/cgroup | grep dropbox

To control that being in that cgroup prevents you from allocating too much memory, you can use the stress program (packaged as stress in Debian); note that it will also use CPU. Check that you cannot allocate 500M of memory:

stress -m 1 --vm-keep --vm-bytes 500M

This should fail (the process should get a signal). You can check that the memory limit is cumulative for all processes of the dropbox user: running stress to allocate 200 MB will work, but trying to run an additional such process will fail.

Network access

Unlike the other guide, I will not try to restrict Dropbox traffic to use Tor. However the official documentation says that Dropbox is using only the HTTP and HTTPS ports, so I will prevent it from connecting to anything else (except DNS, of course). I don't think I need the "Open button" or "LAN sync" features mentioned in the doc, so I didn't allow them. We have to configure rules both for IPv4 and IPv6.

for cmd in iptables ip6tables
do
  sudo $cmd -A OUTPUT -m owner --uid-owner dropbox -p tcp --dport 80 -j ACCEPT
  sudo $cmd -A OUTPUT -m owner --uid-owner dropbox -p tcp --dport 443 -j ACCEPT
  sudo $cmd -A OUTPUT -m owner --uid-owner dropbox -p udp --dport 53 -j ACCEPT
  sudo $cmd -A OUTPUT -m owner --uid-owner dropbox -j REJECT
done

You can make those rules persistent by installing the iptables-persistent package in Debian and saying that you want to save the current rules.

Installing Dropbox

Do as follows, as the dropbox user of course:

# required because Dropbox tries to access the display and crashes otherwise
export DISPLAY=""
cd
wget -O dropbox.py "https://linux.dropbox.com/packages/dropbox.py"
chmod 755 dropbox.py
./dropbox.py start -i
# required because you won't get the auth URL if the daemon is backgrounded
./dropbox.py stop
~/.dropbox-dist/dropboxd start

Say yes when asked to download the proprietary daemon. You should obtain an authentication URL. Open it in a web browser and authenticate. Then it should magically work and your files should synchronize in ~dropbox/Dropbox. You can ^C the daemon and run ./dropbox.py start to start it in background.

Whenever you need to interact directly with the Dropbox daemon as your real user, do, e.g.:

sudo su dropbox -s /bin/bash -c 'DISPLAY="" ~/dropbox.py status'

There's just one slight glitch left: how to access your Dropbox files as your real user?

Accessing the files

The original guide uses SMB as a hack to mount the Dropbox folder of the dropbox user to access it as your real user. I use a dedicated tool instead, bindfs, which I feel is slightly less hacky and more flexible, even though the resulting invocation is quite verbose. The following should be run as your regular user, not the dropbox user.

sudo apt-get install bindfs
sudo mkdir -p ~/mnt/dropbox
sudo bindfs --create-for-user=$(id -u dropbox) \
  --create-for-group=$(id -g dropbox) \
  --create-with-perms='f-x' \
  --chown-deny --chgrp-deny \
  --chmod-filter='of-x,gf-x,uf-x' -p 'f-x' \
  -u $(id -u) -g $(id -g) \
  ~dropbox/Dropbox ~/mnt/dropbox

This means that you can interact with your Dropbox files in ~/mnt/dropbox, with all existing files and new files appearing to be owned by your real user and its group, but they are actually owned by dropbox and its group in the home of the dropbox user. All chmod and chown operations in the mount from your real user will fail (which is right, as they make no sense), and files will never appear there as executable nor can be set to be executable (this approximates the noexec option and makes it harder to execute code from the Dropbox files, which is useful if you're paranoid about Dropbox smuggling harmful executables there).

I use a little script to pass commands to Dropbox and do the bindfs invocation if necessary, checking beforehand that Dropbox is suitably restricted. Again, the script should be run as your regular user, not the dropbox user. I think those tests are important: as the system is insecure by default, you want to test explicitly if the restrictions are still there; otherwise, if they break and Dropbox can start doing unpleasant things like connect to your X server, you will never find out about it (except the hard way).

Limitations

In comparison with the original guide I am not covering the use of AppArmor to restrict the dropbox program. (I don't feel this is that useful as my setup installs Dropbox locally to the dropbox user and not as /usr/bin, although it would be nice, e.g., to limit Dropbox's ability to investigate /proc.) I do not cover the question of starting Dropbox automatically (I run it manually and stop it when I'm done), only the question of maintaining the restrictions across boots.

I do not cover the question of encrypting files in Dropbox (as my use case is to collaborate with people who would not use encryption). I do not cover the question of having a GUI, status icons, nautilus plugins, etc. (I do not use those.)

Concluding remarks

All of this makes the installation of Dropbox on a new machine a bit more tedious. However, it's important to understand that the privacy-conscious user has no alternative: the Dropbox client is a proprietary program that they have no reason to trust, especially given that Dropbox is US-based, and the US have been known for massive privacy violations. Dropbox is a tool designed to upload your data to untrusted third parties, so it is very important that your computer enforces the necessary checks to ensure that it shares only the data that you want it to share.

There is a general principle at play here: whereas the general public is happy to install random apps and toys with little regard to which harm they could cause, the privacy-conscious user will always need more effort to integrate anything new into their computing infrastructure, because it needs to be done in a controlled and secure way.

I have a lot of files and I'm not fond of sorting them intelligently, so I usually give them long and descriptive file names and rely on locate to find them quickly. I was always a bit annoyed to see that locate was not instantaneous even though intuition suggested that it should be, but I was shocked to find out that locate is actually an antique, and that reimplementing a better version of it seems trivial. So I thought I had to investigate more, to replace locate with something that worked better.

Current setup

I am currently using locate, by which I mean mlocate, not slocate which is not packaged for Debian, and not the old locate from findutils.

My database in /var/lib/mlocate/mlocate.db takes 300 MB, and indexes about 10M files. Indexing is run every night, I don't know how much time it takes, mlocate is maybe smart about which files to examine, but I don't really care about that. (To be honest, I am a bit concerned about power consumption and hard drive and SSD wear, but that's rather hard to estimate.) Hence, I will focus on the performance of query evaluation only, not indexing. To estimate performance for typical use cases I grepped from my history file to find the latest locate commands that I ran:

grep ';locate' ~/.history |
  cut -d'|' -f1 | cut -d';' -f2 | grep -v '^grep' |
  cut -d ' ' -f2- > workload

That's 650 invocations (over a bit over 100k lines of history). I filtered them to remove those that did not run, and to remove the very rare cases where I used a locate-specific feature (there was one -0 and a few cases where I was searching simultaneously on multiple patterns, otherwise the only flag was -i), so that's exactly 646 queries (of which 527 are unique). Let's time all those commands, running it 3 times to avoid outliers, with no outstanding IO or CPU activity:

for a in 1 2 3; do
  time sed 's/^/locate /' workload | sh > /dev/null;
done

This takes around 1 hour, so about 5.5 seconds per query.¹ In terms of hardware, I should point out that the machine that I am using has an SSD, most specifically a 120 GB Samsung SSD 840, which hosts the system (plus some of the data, the rest is on hard drives), and of course I'm always storing indexes on the SSD. The CPU is an Intel Core i5-4570 at 3.20 Ghz with 4 cores, there is 8 GB of RAM.

For completeness I also timed locate.findutils (so locate from the GNU findutils) and it is marginally faster, taking about 50 minutes. The database is much more compact, however, and takes only 75 MB. I did not bother benchmarking slocate as Debian does not package it.

Making it faster

Let's try to replace locate by the simplest possible approach to optimize for pure speed.

sudo find / > files

This takes some time, but I don't care. The result is about 900 MB. Let's time the workload on it:

for a in 1 2 3; do
  time sed 's/^/grep /;s/$/ files/' workload | sh > /dev/null;
done

This takes about 19 minutes, so it's already about 2.5 to 3 times faster than locate. (Yes, ideally, I should have checked that it returns exactly the same results, or quantify the differences, but I didn't bother. I just verified for some example queries that the result made sense.)

It turns out one easy way to make grep faster is to set LC_ALL=C. This is unsafe with respect to multibyte characters, but I don't use those very often in file names and never in queries, and my understanding is in this case this option can only add false positives with low probability, which is OK for me.

for a in 1 2 3; do
  time sed 's/^/LC_ALL=C grep /;s/$/ files/' workload | sh > /dev/null;
done

This takes about 7 and a half minutes, so faster than the vanilla grep solution by a factor of 2.5 to 3.

How to make this even faster? It turns out that grep is CPU-bound in this case, so with a multicore CPU it is tempting to parallelize it. This is easy to do: we can clearly split the indexed files in buckets that we index and query separately, merging the results. I use 8 buckets here.

split files files. -nr/8

This splits files in files.aa, ..., files.ah, in a round-robin fashion.²

Let's now create a script grep.sh to grep the files in parallel, using the parallel command from GNU parallel. It is slightly confusing but we must re-quote the arguments to the grep.sh script in this strange way so that we can pass them to the command invoked by parallel:

ARGS=$(printf " %q" "$@")
ls files.* | parallel 'bash -c "LC_ALL=C grep '$ARGS' {}"'

The parallel command will spawn as many parallel jobs as there are CPUs (i.e., cores, so should be 4 in my case). Note that it would not be safe to use xargs or parallel from moreutils they could garble output by two parallel processes if they tried to write at the same moment; GNU parallel, by contrast, prevents this (with --group, which is implied by default). Now let's time this:

for a in 1 2 3; do
  time sed 's/^/.\/grep.sh /' workload | sh > /dev/null;
done

This takes around 3 minutes 30, so around 2 times faster than the non-parallel version. This amounts to 1/3 second per request (plus the overhead of displaying the results, which is not accounted for here), which I think is good enough for my needs.

Compressing the index

One respect in which this grep-based approaches is worse than locate is that its index is three times larger than that of locate. The original post about locate conjectured that this explained why locate's performance is worse than naive grep. However, as we will see, it is easy to compress the index and still be much faster than locate. First, let's simply compress the files with gzip:

split --additional-suffix=.gzip \
  --filter="bash -c 'gzip > \$FILE'" files files. -nr/8

The resulting index is 105 MB in size in total, so 10 times smaller than the uncompressed index, and still 3 times smaller than that of locate. We can then decompress these files when querying them, by replacing our search script with:

ARGS=$(printf " %q" "$@")
parallel -i bash -c "gunzip -dc {} | LC_ALL=C grep $ARGS" -- files.*.gz

The timing of this is 14 minutes, which is 4 times slower than the uncompressed version, but still 4 times faster than locate.

In fact, we can still make this much more efficient. One easy way is to use the pigz command to decompress, which spawns additional threads and is faster. Replacing gunzip by pigz in the above (which is packaged for Debian), we get a timing of 11 minutes for the same index size.

Of course, if we want to achieve different tradeoffs between file size and speed, we can look at different compression and decompression algorithms, optimized for speed. One possibility is lz4, packaged as liblz4-tool in Debian. The index is 160 MB in total, which is 50% more than with gzip but half of the size of the locate index, and replacing gzip by lz4 and timing, we get 8 minutes. So this last solution that assembles off-the-shelf tools with around 5 lines of bash is about 7.5 times faster than locate while using an index which is twice smaller.

Result summary

Concluding

I am considering replacing locate by the fastest of these approaches (the one with parallelization and no compression) for my own needs, but I just intend to do it as a personal hack; doing it in a reusable way would be much harder.

Of course, this post is just scratching the surface; the list of file names is not preprocessed in any way to make grep faster, whereas in principle it could. However, I could not find any standard Unix utility that could do index file > file.idx and search --index=file.idx pattern file, such that file.idx is not too large compared to file and the search operation is much faster than a grep (at least for patterns that are fixed strings).³ It would be fun to implement such a tool, based, e.g., on a suffix tree, but I probably won't bother as the grep approach is fast enough.

In addition to choosing the best algorithms, a good replacement of locate should also implement the various options of locate, so as to be a drop-in replacement for it. In fact, it would probably be relevant to index more metadata in addition to file names, to optimize searches, e.g., for recently modified files, etc. I am quite surprised that such a tool does not seem to exist. To be precise, it does exist in a stronger form in all the graphical desktop search tools, so this could alternatively be implemented as a usable CLI interface to such tools, intended as a locate replacement.⁴

Submitting a research paper to a conference or journal can be a stressful process; there are many things to remember, and mistakes can have dire consequences. Here is my attempt to summarize all the steps and my experience about some points, because it's easier to follow a checklist than to remember every time what you have to do. Note that I'm making some implicit assumptions, e.g., that you are using a revision control system, that you are using LaTeX, etc.; also, this list may not be sensible or exhaustive in all fields (I'm talking from the perspective of theoretical computer science).

TODO flushing.

There should be no tasks left before you start finalizing the submission. Of course, it's fine to remove a TODO because you decided to not do it because you did not have the time, the energy, it wasn't worth the effort, etc.; but the status of all TODOs must have been cleared, so you won't realize after proofreading that there were some changes left that you intended to do. Possible sources of TODOs to process:

• In the main text: those should be the most obvious.
• In LaTeX comments: I don't use those but some people do, consider grepping for "TODO" or such keywords (for this reason, TODOs that you gave up on should probably be moved to a separate file, not just commented out)
• In a separate TODO file: did you start jotting down things to do in separate files ("TODO", "ideas", "meeting_notes")?
• In your mailbox: if you have any mail in your inbox about the submission, you probably intend to get rid of it once submitted, so go through it before you start finalizing, and ensure nothing is left to do.
• In the reviews of a previous unsuccessful submission of the paper.

Once the only task left is "proofread the submission", you can continue.

Proofreading.

Go over the submission once, linearly, from start to end. You may want to do it on screen, or on paper (annotating the paper copy and then implementing any changes). If using a WYSIWYM editor such as LaTeX, when editing anything during proofreading, it is crucial to recompile and read again what you just changed, preferably the whole paragraph: fixing errors can easily introduce other errors, and you won't be proofreading again what you are currently changing.

Hopefully, at this point, the scientific content of the submission should not change. If it turns out you have to make significant fixes when proofreading, consider doing a second proofreading pass.

Check that you proofread the following, which are easily forgotten:

• Paper title, author information: especially affiliations, which are often filled in casually early on and may not be sensible.
• Section titles in the paper: go once through the paper looking just at section titles, to check that they make sense and match the "Paper structure" paragraph if you have one.
• Footnotes.
• Floats, figures, algorithms, etc.
• Formal statements: it's easy to focus on the prose, but you should double-check that the precise wording of theorems makes sense, no matter how they are framed.
• Bibliography: Do all references follow the same format? Are you consistent when abbreviating venue names? when including or discarding page numbers, addresses, publishers? Are all author names sensible? Are all acronyms and proper names correctly capitalized in titles (e.g., no "Designing an xml language for hadoop")?

Once you are done proofreading, you have a known good version. It may make sense, when doing further changes, to check their diff against that version to spot any errors that you would be introducing.

Spellchecking.

Use any spellchecking tool. Also check for notations and terms and other things that shouldn't be there anymore:

• Remove the definitions of macros that should no longer be used (for old macros, for TODO notes, etc.)
• If you introduced a macro to replace a notation and changed the notation, check for hardcoded instances of the notation or of previous notations.
• If a name has multiple variants and you have been using them inconsistently, standardize to one name (e.g., "foo bar" to "foo-bar"). When looking for occurrences of multi-word names, don't forget that there may be a line break in the middle (i.e., check for "foo" at end of line).

Typography.

Check for the following:

• Math identifiers at the beginning of lines: if "of x" is split, make the space between the words non-breaking.
• Overfull \hboxes: check for them in the LaTeX log and fix them by rewording, or tweaking hyphenation for technical terms that LaTeX does not know.
• General page layout: widows and orphans, spacing around environments and floats, positioning of section titles (not at the bottom of a column!), placement and numbering of floats, etc.

Sanity checks.

Verify the following one last time:

• Go through the call for papers and formatting instructions:
  • Did you get the page limit right? Including or excluding references?
  • Are you using the correct style file? Are the font size and paper size correct?
  • Should you be including author information? (depends if the venue is double-blind or not)
• Search a last time in the PDF and grep in the source folder for bad strings like "TODO", "FIXME", and other such stuff.
• Check the LaTeX log for bad errors like broken references or multiply-defined labels. Search for "??" in the PDF to double-check that there are no broken references.
• Will you be submitting your LaTeX source? If yes (e.g., on arXiv), make sure there are no embarrassing comments left in the LaTeX. See for instance the script in this arXiv FAQ entry. In addition to comments, do you have block comments with iffalse, the comment environment, or custom commands? Are some of the LaTeX files unused, i.e., not included in the compilation?
• Are all your changes committed to the revision control system? Check this on all the machines where you have been editing the document (to make sure that there aren't uncommitted changes on a different machine).

Submitting.

Submit the paper. Check the following:

• Are the title, author information, track, keywords, etc., correct on the submission interface?
• If you had to indicate conflicts of interest, did you do it?
• Are you supposed to submit additional things, like uploading an appendix elsewhere? If yes, don't forget them.
• Update the abstract on the submission interface.

Double-checking.

Re-download the file that you submitted from the submission interface and go through it to check that it looks good.

• Are all pages there?
• What is the last change that you did? Is it there?
• Did you submit the right file, for the right paper? This may sound stupid, but strange things happen at 5 AM. It is especially important if you have multiple submissions for the same deadline.

It's normal to find mistakes at the last minute when going over the PDF after submitting. Of course, when fixing them, be extra careful; at this stage you should probably be double-checking the changes that you make, and checking them again by proofreading the diff before you commit.

Concluding.

Decide you are done.

Let your coauthors know. Thank them for their hard work.

Then, celebrate as you see fit. :)

Aftermath.

The following are things that you should probably do, but there's no urgency in doing them, so the safest way to avoid doing them multiple times because of last-minute fixes is to wait for the deadline to be over.

• Ensure that your version control system knows what was the final submitted version.
• If applicable and not double-blind, upload your preprint on your website and/or a preprint repository such as arXiv.