I won't write this if my elimination to finals doesn't depend on this.

During the contest when I pressed submit button, 4 of 5 my submissions were duplicated with same code and submit times with less than 10 second difference. This costed me two extra penalty, for problems B and C and without this bug I am in top 25 in current standings. I know at least two participants faced the same bug but it happened with less probability. I already submitted bug report to codejam@google.com and hope they will review submissions.

What's test #5? Didn't manage to pass it and too lazy to spend time on upsolving.

Passed G with the following solution.

Increase $$$hp_1$$$ such that $$$n$$$ is divisor of $$$\sum hp_i$$$. $$$m$$$ times choose greedily maximum group size such that it's possible to attack with this group without affecting the answer and then simulate this attacks randomly.

Any idea why this solution works?

Actually, intended solution for H was with convolution repeated times, but we failed to set time limit properly.

I have some kind of "editorial" for G.

Recall the algorithm for building automaton. Let's calculate expected number of cloned states then add n + 1. Consider adding last character of string s. Let t be the longest suffix which occurs more than once and let a be the character preceding t. Then vertex cloning had happened iff there is character b ≠ a such that it preceds each occurence of t except for the last one.

For string s denote sequence |s|, |π(s)|, |π(π(s))|, ... 0 as chain(s) (here π(t) is longest suffix shorter than t equals to prefix of t). Let's calculate all possible triples (chain(t), chain(at), chain(bt)), where a and b are different characters. Also for each triple we need to know the number of triples of strings (t, at, bt) which corresponds to this triple. Knowing only (chain(t), chain(at), chain(bt)), it's possible to calculate number of strings s such that vertex cloning happened.

The solution is to find all different rows of the table one by one and then in n² queries restore it.

If you have found k rows, you need to find any string that is not a substring of any of these k rows. Then it can be expanded to the whole row in at most 2n queries.

Consider a trie of all substrings of already found rows. You can try to go by non-existent transitions of the trie and ask if there is such a string in the whole table, do this in the order of length increase. However, in its simplest form, it will work in cubic number of queries. Here comes the trick to make it 2n² overall — if you already know that some substring of the string you are about to ask doesn't exist, skip this query.

If you consider the trie as a suffix automaton of k strings, you can prove this upper bound. There will be at most 2n² states in the automaton and among all transitions by the same character from each vertex you will ask only about the shortest string, skipping the others.

LOL

I came up with the same solution but with hashes instead of LCP's. I think(but not sure) it can be modified to O(N²). For each fixed l we can precompute maximum prefix at which substring can be extended for each r simultaneously in linear time. The rest part of the solution remains the same.

I didn't realize there is an easy solution in L and solved it in O(n²) time similarly to this problem

I think the following trick should work. Append a unique delimiter to the end of each string and after adding the string to the tree, set our current position in the tree to the root.

With suffix automata the same magic even without delimiters worked for me. But in case of suffix trees the delimiters are necessary as we have to create all terminal nodes.

UPD: Instead of just setting the position to the root you should go up by suffix links until the root and mark all nodes on this path as terminal for the current string.

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

I have not seen problems from the latest CF but I don't regret that I missed that round because of Codesprint. Very cool problems, especially one about coins on the tree.

Same question. Neither t-shirt, nor prize.

Very handsome tool! I will write you about bugs and features!

P.S. Nice quotes for AC :)

Of course, yes. And, please, fix 11 example. Probably it has encoding problems. My browser shows ??/ instead of backslashes.

Another one

#include <iostream>
using namespace std;
 
int main() {
    long long a = 1e18 + 1;
    cout << a << endl; 
    return 0;
}

It's not correct. Try test:
6
10 2 26 5 3 9
or its permutations. System tests are weak.