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$$$.
Nice!!
The problemset as a whole was very nice. Apart from problem 5, which was just an application of advanced (but standard) techniques, the other 4 problems were all cool.
Congratulations to the organizer.
How to solve the last problem?
Given a vertex $$$v$$$, let $$$A_v$$$ be an array such that $$$A_v[d]$$$ is the number of vertices in the subtree rooted at $$$v$$$ with distance $$$d$$$ from $$$v$$$.
Let $$$a_1,a_2,\dots, a_k$$$ be the sons of $$$v$$$. Up to pushing a $$$1$$$ in front of all the arrays, the answer to the problem is given by the $$$0$$$ entry of the xor-convolution of $$$A_{a_1},A_{a_2},...,A_{a_k}$$$. Let us assume that $$$A_{a_1}$$$ is the longest among the arrays $$$A_{a_i}$$$. We compute (with the fast Walsh-Hadamard transform) the xor-convolution of $$$A_{a_2},\dots, A_{a_k}$$$ and we obtain the array $$$B$$$. Then the answer is given by
In order to have a pseudo-linear complexity, we shall perform the xor-convolution of $$$A_{a_2},\dots, A_{a_k}$$$ with complexity $$$\big(len(A_{a_2}) + \cdots + len(A_{a_k})\big)\log(n)$$$.
Using the big-child trick it is possible to implement the above described solution with complexity $$$O(n\log(n)^2)$$$ (or maybe $$$O(n\log(n))$$$, I don't want to check).
It is $$$O(n \log(n))$$$. Infact, the sum of $$$ len(A_{a_2}) + len(A_{a_3}) + \ldots + len(A_{a_k})$$$ over all the nodes is precisely $$$n - 1 - d$$$, where $$$d$$$ is the maximum depth of a node. Proof : Each node except the nodes on the path from root to the deepest node contributes $$$1$$$ to this sum.
P1: Do the printed points need to be integral points?
yes
The problems seem really nice, but difficult. What is the output for 2, do we output to some decimal precision? I'm not sure about the infimum part (though I did check Wikipedia).
If I recall correctly, an absolute or relative error of $$$10^{-6}$$$ was accepted.
Well, there are 2 fairly obvious options: either there are no cycles, in which case infimum = minimum, or the last cycles can be repeated lim(infinity) times and everything before it is irrelevant. If the lowest value of (sum of edge weights) / (1-2^-length) for some cycle (we can prove it should optimally be simple) passing through a vertex $$$v$$$ is $$$m$$$, then the cost of getting to $$$v$$$ is at most $$$m$$$, and from that we can iterate paths with length at most $$$N$$$ in some kind of slow solution.
With floats, though, there's a super easy solution: in reverse, the cost of a path is last_edge + previous_edge/2 + ... + k-th-previous_edge/2^k, and only the first $$$O(log)$$$ edges matter, so for small $$$l$$$, we can calculate the smallest cost of a path to each vertex with length $$$l$$$ in $$$O((N+M)\log)$$$.
I only could solve the 3º problem...
Here is my solution:
If you have just one row, to find the special tile (the 1x1 tile) the best you can do is query the central position. If the central position is the special tile you have finished, else you will split your row into two halves, one having an odd number of tiles and the other having an even number of tiles, and you recurse with the part that has an odd number of tiles. Eventually, you will finish with just one tile.
Now, when you have more rows you can query one entire row or one entire column (depend on which one is shorter) and you will split the board into two parts, one having an odd number of tiles and the other having an even number of tiles, and recurse.
How to solve the 1º problem!?!
For each given vector $$$(v_x, v_y)$$$, print $$$(v_x, v_y) \times round(\frac{9 \times 10^8}{\sqrt{v_x^2+v_y^2}})$$$. Thus the points will be arranged approximately on a circle with radius $$$9\times 10^8$$$.
Is there a simple argument why such points form a convex polygon other than comparing with convex hull?