Hi everyone,

The second round (qualifiers for the finals) of the contest organized by Bending Spoons was held today. The problemset was very interesting and challenging, although it's currently hidden by the organizers, I think I can recall most of it from memory.

https://www.codechef.com/BENDSP02

Let's discuss the problems in the comments. Here are the abridged statements. They may not be 100% accurate.

Problem 1: Given $$$n$$$ nonzero vectors with integer coordinates and different directions, find $$$n$$$ points such that the $$$i$$$-th point is in the same direction as the $$$i$$$-th given vector (looking from the origin), and these $$$n$$$ points are the vertices of a strictly convex polygon (in some order). $$$|v_i|, n \leq 50$$$, printed points can have coordinates up to $$$10^9$$$ by abs. value.

Problem 2: Given a directed graph on $$$n$$$ nodes, each edge is labeled with a positive integer. You start from node $$$1$$$ with energy $$$0$$$. When traversing an edge with label $$$x$$$, your energy becomes $$$e' := e/2+x$$$. For each node, find the infimum of the set of values of energy you can have in that node, or $$$-1$$$ if it is unreachable. $$$n, m \leq 100000$$$

Problem 3: This problem was interactive, there's an $$$n \times m$$$ board, where $$$n \leq m$$$ and both $$$n,m$$$ are odd, and it's tiled with $$$(nm-1)/2$$$ dominos (so exactly one field is not tiled), the arrangement of dominos is not known to you. You can ask about a field and as a reply you get the other field covered by the same domino, or some special value meaning that the field is not tiled. Figure out which field is not tiled by asking no more than $$$n(ceil(\log_2(m/n)) + 3)$$$ queries. The interactor may be adaptive. $$$n,m \leq 1000$$$

Problem 4: Given an array, in one move you must choose a subarray $$$[l,r]$$$ of length at least two, add $$$(r-l+1)$$$ times the minimum element of that subarray to your score, and replace those $$$r-l+1$$$ elements with one element, their sum. The game is finished when there's only one element left. What's the highest score you can attain? $$$n \leq 60$$$, $$$|a_i| \leq 10^9$$$, so, elements can be negative. In one subtask, all elements are nonnegative.

Problem 5: Given a rooted tree, for each node $$$u$$$ compute the number of ways to pick a set of paths (can be empty) starting from $$$u$$$ and going away from the root, such that any two of these paths intersect only in $$$u$$$, and the XOR of their lengths (measured in number of edges) is zero. Find the answer mod $$$998244353$$$. $$$n \leq 500000$$$.