hochesh's blog

FII Code 2020 Round #3 Discussions
By hochesh, history, 5 years ago, translation, In English

FII Code 2020 Round #3 has just finished!

I propose to discuss tasks and there solutions here.

I am really interested how to solve problem E and would be very grateful if somebody will explain.

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

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

Auto comment: topic has been translated by hochesh (original revision, translated revision, compare)

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

It is basically oeis problem — calculate ev of times a_i would be added to jth vertex if i is ancestor of j and path length between them is k. Turns out if this value is b_k, then b_k * k! is oeis sequence with linear recurrence. And as tree is random we can easily calculate the answer

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    Or you can solve it legit, with slighly more brain power.

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

      Can you describe solution please?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        I think the editorial should be available by now, but as a short description, you want to consider every pair $$$(node, ancestor)$$$ and compute $$$ancestor$$$’s contribution to $$$node$$$. Summing up these answers would yield the true total due to linearity of expectation.

        It’s good to notice that only the nodes in the path from $$$ancestor$$$ to $$$node$$$ are relevant, so let’s consider these for now. If you fix a specific permutation, you can see that $$$ancestor$$$’s value is added to $$$node$$$ exactly once for each subsequence of the permutation in which nodes go downwards. In essence, the ‘oeis’ sequence is actually the expected number of increasing subsequences starting with $$$1$$$ for a random permutation of size $$$n$$$.

        After calculating that array $$$b$$$ (we’ll keep the notation), the contribution is $$$val(ancestor) * dp(d) * n choose d * (n - d)! / n!$$$, where $$$d$$$ is the number of nodes in the path between $$$ancestor$$$ and $$$node$$$

        → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      while authors continue to not check if their problem is solved by oeis, this will remain pretty legit and prudent thing to check

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

        We did check. Still, we considered the task to be a good fit for the set (mainly because we thought oeis would be overkill after making the necessary observations). Maybe we were wrong.

        → Reply
»
5 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

Problem D is similar to task which was on Open Olympiad in Informatics last Friday/Saturday in Russia. Key idea is to notice that string A(Ar)A can be represented by two string A(Ar), and (Ar)A which are palindromes. So we need to calculate number of positions (i < j) such as exist palindrome in center i covering j and palindrome in j covering i.

We can precalculate by Manaker algorithm for each position pos val[pos] — maximal k that s[pos-k-1...pos+k] — is a palindrome. In these terms condition to (i, j) is the following: val[i] >= j — i

val[j] >= j — i

we can iterate overall positions i and we need to find out number of such i + val[i] >= j > i: val[j] >= j — i

val[j] — j >= i

j — val[j] <= i

so we need to calculate number of j in [i+1...i+val[i]] such as j — val[j] <= i.

It can be easily done by scanline with Fenwick Tree in O(NlogN) time.

I wonder if it exist linear solution. If somebody knows it — write please!

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

For Double Palindromes, I got the manacher array of even palindromes.

Now, for each index $$$i$$$, I want to check if it can be the start of $$$A^{r}$$$ part. This is equivalent to finding cardinality of set $$$ \{ l | 1 \le l \le d_2[i], d_2[i+l] >= l \} $$$ and adding for all $$$i$$$.

With some manipulation, you can make new array $$$ a[i] = d_2[i] - i $$$, and now, for each $$$i$$$ I want to count number of elements in $$$a$$$ from $$$i+1$$$ to $$$i+d_2[i]$$$ such that $$$a[j] \ge -i$$$. I used Merge Sort tree for this, but I got MLE.

In general, how to solve quickly ( implementing fast ) such problem: Given an array $$$A$$$, answer queries $$$L$$$, $$$R$$$, $$$X$$$ ( preferrably online ) where you need to find number of $$$ L \le j \le R $$$ such that $$$ A[j] >= X $$$.

Also, Is there a way to use the very versatile order statistics tree in this type of problems? Except for the Merge sort type of way, where you keep an order statistics tree in each node of segment tree.

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

    I think order statistics tree will get TLE here.

    The best way to solve this task about (L, R, X) (IMHO) is to sort all queries by X and add elements in decreasing order to Fenwick tree. So when we have query (L, R, X) all elements in Fenwick are >= X, so we need just to ask sum(L...R) which is fast due Fenwick low constant factor.

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

      I know of this solution, but couldn't morph the problem into this way. That's why I would like to know if it is possible to answer queries online without reordering them.

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

        Online it's possible to do in O((N+Q)logN) time using Persistent Segment Tree, but I don't think it will pass time limit in this task.

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        Usually this kind of 2D query formulations have an extra $$$O(log(N))$$$ complexity factor when implemented on-line as far as I’m aware. It is a good idea to familiarize yourself with the scanline approach for this type of scenarios, as it often improves the complexity of the solution (both in the asymptotical sense, and in the implementation sense).

        → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I tried solving C using sparse table but got MLE, is there any easier way or any optimization suggestions https://ideone.com/Hxu5SO ?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    There's a way to do it faster. 1. len l = |s|

    Let go[x][y][k] = {nx, ny} — our position if we start in (x, y) and move along s 2^k times.

    For example if s is LLRU go[x][y][2] will be our position if we do these operations: LLRU LLRU LLRU LLRU.

    Now, when you have query (x, y, z) you do binary jumps up to z/l times. Then you just simulate process by hands z%l times.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what's the approach for problem C -the grid with queries problem?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    For each cell calculate where you will be after 1, 2, 4, 8... full program runs. Then for each query use binary cascade to get your position after all full runs, and do remainder naively

    → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

I'm wondering if there's an easier or more obvious solution to the problem C, Confused Robot.

My idea was to precalculate the end position after 1 full application of the instruction string $$$S$$$, for each possible starting position. This lets the robot "skip" every $$$|S|$$$ moves, but unfortunately it's not enough to get us under the time limit.

So the second idea is to precalculate $$$2, 4, 8, ..., 2^k$$$ applications of $$$S$$$. That's a matrix $$$N \times M \times log_2(Z) < 10^8$$$, which is OK.

After that, for each query $$$X, Y, Z$$$, take the starting position and find the largest $$$k$$$ so that $$$|S| \cdot 2^k \leq Z$$$: jump and set this as the new position. Repeat until $$$k$$$ goes to 0. The remaining $$$\leq 100$$$ moves after that can be trivially simulated.

To be clear, this works, but I'm not sure if that was the intended solution.

→ Reply