### pabloskimg's blog

By pabloskimg, history, 3 weeks ago,

Hi. Just posting this blog so we can discuss the solutions to the problems of the 2020-2021 ACM-ICPC Latin American Regional Programming Contest.

Mirror on Gym: https://codeforces.cc/gym/103185

Happy discussion :)

• +118

 » 3 weeks ago, # |   +13 A. tagbactracking with pruning. hint 1You can only build heights of the form $\frac{1}{n}$, for some natural $n$. hint 2With heights $a^{-1}$ and $b^{-1}$ you can make the height $(a + b)^{-1}$ hint 3You can see all the created elements as an increasing sequence. hint 4With a backtracking approach, you can generate the biggest element with lowest elements in the sequence. hint 5(pruning) do not repeat the largest element, i.e. with sequence 1, 2, 3, x, x = 4 can make with 2 + 2 or 3 + 1. hint 6(pruning) the maximum length is 10 for $m$ between 1 and 100 (hardcoding). hint 7(greedy pruning?) I have not been able to prove this, but the sequence is $f_1 = 1$, $f_i = f_{i-1} + f_{i - a_i}$, for some $a_i$ between $1$ and $i-1$. codes first code second code (backtracking / greedy)
•  » » 2 weeks ago, # ^ |   +6 I also tried greedy from hint 7 without proofs and it runs significantly faster than without it. It would be interesting either to see if it fails at some point (outside of the bounds of this problem of course), or a proof that it is correct.Some intuition about the greedy: Greedy intuitionWhenever you "create" a number, this number will be used to create the following number, i.e numbers created are used immediately in the chain. A counter example to the greedy would look like this. Suppose you have the set $S$ of numbers available. From this set you create numbers $A$ and $B$ only from numbers in $S$, and then get $C = A + B$. This is not the only counter-example since chains can be longer, but this is a possibility.
•  » » » 2 weeks ago, # ^ |   +11 https://en.wikipedia.org/wiki/Addition_chain#Brauer_chain if I understood this correctly then it works until 12508
 » 3 weeks ago, # |   0 How to solve M?
•  » » 3 weeks ago, # ^ |   +23 Maintain the suffix array of the reversed string (prefix array?) online with hashes and binary search (in a set with custom comparator). Now just count the total number of different substrings and subtract the number of substrings that appear exactly once. Both of these things are easy to calculate via the LCP of adjacent suffixes in the suffix array, so you can easily calculate the difference that each update causes in the answer.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   +37 Alternatively you can create a trie and do the suffix (prefix?) array of that trie using the same deterministic suffix array algorithm that doubles information + power of 2 ancestors.
•  » » » » 2 weeks ago, # ^ |   +8 This is my code using this idea, i.e. no hashing.I tried to add few tests to avoid several hashes. But of course it is very hard to avoid them on ICPC.
•  » » 2 weeks ago, # ^ | ← Rev. 4 →   +5 Edit: Wrong solution, sorry. I got AC but really the time complexity is bad because of the rollbacks. Thanks to brunomont for the clarification.I solved it using suffix automaton: here my code. To solve it with this structure I thought two things: How to remove the last inserted character from the suffix automaton How to keep the answer updated after each operation (insert and remove) For the first one, we can use stacks (I used five) to keep enough information that allows us to recreate the changes that occurred when inserting that last character and thus be able to undo those changes.For the second one, keep in mind that each different subtring is only contained in a single state of the suffix automaton and that the number of different substrings contained in a state $u$ $(u \not = 0)$ of the suffix automaton is equal to $len(u) - len(link(u))$.Every time we insert a character a new state is created, let's call it $u$, if at the end of the insertion $link(u) \not = 0$, that means the substrings contained in the $link(u)$ state already occur more than once in the string, so we can add $len(link(u)) - len(link(link(u)))$ to the answer. However, we only have to add that value to the answer the first time that $link(u)$ is assigned as a suffix link. To do this (and also to undo changes) we can add to the states a counter that stores how many times that state has been assigned as a suffix link when inserting a character (this counter must also be copied when creating a clone state in the insert algorithm).About suffix automaton: https://cp-algorithms.com/string/suffix-automaton.html
•  » » » 2 weeks ago, # ^ | ← Rev. 2 →   +13 Are you sure this is the correct complexity of your solution? From what I understand, suffix automaton have only an amortized $O(1)$ cost for adding a character, and linear worst case. So I don't see how this would not be quadratic when trying to do rollbacks.I tried your code on the following instance: $AAAA....AB-B-B-B-...$, and it took more than one minute, which would indicate the quadratic behavior.
•  » » » » 2 weeks ago, # ^ |   +3 I have almost no experience using suffix-automaton, but without understanding much about the internals, I think you can make the solution work by using persistent arrays to store all information for the SA. That way you can go back to the previous version by restoring the old root for each array in $O(1)$.There is an extra log factor both for memory and time, but that is probably ok.
•  » » » » » 2 weeks ago, # ^ |   +13 I'm not entirely sure I understand how that would work, but I think this instance would break it:$AAAAAA...A$$B--B--B--B--...$The idea is that each new $B$ would take time linear on the current string size, and I don't think memorization/persistence would help in this case.
•  » » » » 2 weeks ago, # ^ |   0 Totally, you are right. After thinking a lot about how to do the rollbacks I lost the notion of the amortized complexity and in the end I code this that seemed to work. I sent the code without doing exhaustive tests and with the AC I was wrongly convinced. Now I feel a little bad about getting the AC. Thanks for the clarification!
•  » » » 2 weeks ago, # ^ |   +3 Is it possible that the time consumed by your solution on removals is $O(n)$ in the worst case? Since the changes done by adding one character can be up to $O(n)$ right, and they need to be reversed.If this is the case, on an adversarial test, your solution is forced to add and remove a character that triggers this behaviour all the time, and it can take up to $O(N \cdot Q)$.
 » 11 days ago, # |   0 How to solve G?
•  » » 5 days ago, # ^ | ← Rev. 2 →   +11 I liked the problem, congratulations to the author. Here is the solution.Step 0: The probability that two cards are equal is way below the required precision, hence we may assume that the $2n$ cards are distinct.Step 1: Alice should place her cards in increasing order on the slots.Let $x_i$ be the number on the card Alice puts on the $i$-th slot. Assume that Bob's cards are fixed. Let $C(x_1, x_2,\dots, x_n)$ be the amount gained by Alice if Bob plays optimally. With a swapping argument (encoded in the following lemma) one can show that $C(x_1,x_2,\dots, x_n)$ is maximized when the $x_i$ are increasing.Lemma: If $ix_j$, then $C(x_1, x_2,\dots, x_i, \dots, x_j, \dots, x_n) \le C(x_1, x_2, \dots, x_{i-1}, x_j, x_{i+1}, \dots, x_{j-1}, x_i, x_{j+1}, \dots, x_n) \,.$proof. Let $y_i$ be the card put by Bob on the $i$-th slot in an optimal solution when Alice cards are $x_1, x_2, \dots, x_{i-1}, x_j, x_{i+1}, \dots, x_{j-1}, x_i, x_{j+1}, \dots, x_n$. Let us split in $3$ cases: If the $i$-th slot and the $j$-th slot go to the same person, Bob can achieve the same gain also when Alice puts the cards as $x_1, x_2, \dots, x_n$ by swapping $y_i$ and $y_j$. If the $i$-th slot is won by Bob and the $j$-th slot is won by Alice, Bob can increase his gain when Alice puts the cards as $x_1, x_2, \dots, x_n$ by swapping $y_i$ and $y_j$. If the $i$-th slot is won by Alice and the $j$-th slot is won by Alice, Bob gains the same (or more) when Alice puts the cards as $x_1, x_2,\dots, x_n$ by not changing anything. Step 2: Bob should place his cards greedily starting from the largest one.Let $x_i$ be the card placed by Alice on the $i$-th slot (thanks to the previous step we can assume that $x_i0$, we decrement $q$. If $s_i=0$ and $q=0$, we add $p$ to $res$, where $p$ is such that $s_i$ is the $p$-th zero in the string $s_1,s_2,\dots, s_{2n}$. At the end of the algorithm, the variable $res$ contains the amount gained by Alice.Step 5: Solve the problem for all possible card orderings via dynamic programming.It is well-known that, if we want to compute the expected value of a certain algorithm on a family of inputs, dynamic programming is often the solution.Let $din[z][o][q]$ be the sum of the amounts gained by Alice over all binary strings $s_1,s_2,\dots, s_{z+o}$ with $z$ zeroes and $o$ ones such that, if we perform the algorithm described in step 4, at the end the number of unused Bob's cards is $q$. It is easy to check that the value of $din[z][o][q]$ depends only on the values of $din[z-1][o][q+1]$, $din[z][o-1][q-1]$ (and possibly $din[z-1][o][0]$ if $q=0$).The answer to the problem is $\frac{\sum_{q=0}^n din[n][n][q]}{\binom{2n}{n}}\,.$The complexity of this solution is $O(n^3)$.
 » 5 days ago, # |   0 How to see solution of other people?pabloskimg