ivan100sic's blog

By ivan100sic, history, 4 years ago, In English

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$$$.

  • Vote: I like it
  • +61
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Nice!!

»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    How to solve the last problem?

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +28 Vote: I do not like it

      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

      $$$ \sum_{i=0}^{len(B)} A_{a_1}[i]B[i] \,. $$$

      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).

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it +18 Vote: I do not like it

        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.

»
4 years ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

P1: Do the printed points need to be integral points?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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).

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If I recall correctly, an absolute or relative error of $$$10^{-6}$$$ was accepted.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)$$$.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I only could solve the 3º problem...

Here is my solution:

Spoiler

How to solve the 1º problem!?!

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it
    First problem solution
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Is there a simple argument why such points form a convex polygon other than comparing with convex hull?