| # | User | Rating |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 153 |
| 2 | nik_exists | 151 |
| 3 | maroonrk | 150 |
| 4 | maspy | 149 |
| 5 | AmShZ | 146 |
| 6 | Um_nik | 143 |
| 7 | Errichto | 139 |
| 8 | adamant | 135 |
| 9 | BledDest | 134 |
| 10 | cry | 130 |
|
+58
My 96-point solution for In my opinion, this is just a extension of the 80-point solution which have been mentioned for many times. But I don't think there's an easy way to get a full solution by improving this algorithm. Solution First we consider how to transfer a 01-string $$$A$$$ from Anna to Bruno. Anna's work Just like other solutions, $$$T$$$ is a fixed vector $$$[0,1,0,1,0,1,...]$$$ For each continuous segment of zeros or ones in $$$A$$$ of length $$$N$$$ , we add $$$2 \times N + 1$$$ zeros or ones into $$$S$$$. For example, if $$$A = [0,0,1,1,1,0,1]$$$ , then $$$S = [0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,1,1,1]$$$. Bruno's work Now we are considering how to get $$$A$$$ through a riffle shuffled 01-string of $$$S$$$ and $$$T$$$. Assume that the shuffled string is $$$U$$$, we construct $$$V$$$ by the following steps.
Assume the remaining elements in $$$U$$$ is $$$U'$$$ . It's easy to find out that all the elements moved to $$$V$$$ must come from $$$S$$$ in the process of riffle shuffle. And $$$U'$$$ is in the form of $$$[0,1,0,1,...]$$$, which has the same starting character and the ending character as $$$T$$$. However, the length of $$$U'$$$ may be greater than $$$T$$$, because some of the elements remained in $$$U$$$ may come from $$$S$$$ . Since the form of remaining elements in $$$U'$$$ is very similar to the form of $$$T$$$, the elements in $$$U'$$$ that come from $$$S$$$ should satisfy a strong condition. That is, the elements from $$$S$$$ in $$$U'$$$ have to be some disjoint consecutive segment $$$[0,1]$$$ or $$$[1,0]$$$. For example, if $$$U' = [0,1,0,1,0,1,0,1]$$$ and $$$T = [0,1,0,1]$$$ Then the elements from $$$S$$$ in $$$U'$$$ can be $$$[0,1,(0),(1),0,(1),(0),1]$$$ or $$$[0,1,0,(1),(0),(1),(0),1]$$$ or $$$[(0),(1),0,(1),(0),1,0,1]$$$ or something else, such that $$$U' - $$$ $$$($$$ elements from $$$S$$$ in $$$U'$$$ $$$)$$$ $$$= T$$$ So look at $$$V$$$ and $$$S$$$, the only difference is that some consecutive segment $$$[0,1]$$$ or $$$[1,0]$$$ of $$$S$$$ is missing in $$$V$$$(which is mentioned above in $$$U'$$$). And we can recover that by going through each consecutive segment of zeros or ones in $$$V$$$. if the length of the current segment is even, then we can realized that a character is missing in the end of this segment, since the length of each consecutive segment of zeros or ones in $$$S$$$ is odd. And we should add $$$[1,0]$$$ or $$$[0,1]$$$ to the end of this segment in this case, then continue looking at the next consecutive segment. After that, we can make a small trick. That is, the first character in $$$S$$$ isn't necessary to be transferred. Since the first three characters in $$$S$$$ have to be the same, the first two characters in $$$V$$$ have to be the same. So we can know the first characters in by looking at the second character in $$$V$$$. Similarly, the last character in $$$S$$$ isn't necessary to be transferred either. After knowing how to transfer a 01-string $$$A$$$ from Anna to Bruno, we need to translate an integer $$$x(x \leq 1e18)$$$ to a $$$01$$$ string $$$A$$$, satisfying that the length of 01-string $$$T$$$ (which Anna constructed by $$$A$$$) is less than $$$N+2$$$ ($$$N = 145$$$ in my solution), since the first and the last character don't need to be transferred. We can use a vector $$$P$$$ and a boolean $$$B$$$ to describe a 01-string $$$A$$$. Each element in the vector stand for a consecutive segment of zeros or ones, and $$$B$$$ stand for the first element of $$$A$$$. For example, if $$$A = [1,1,0,0,0,1,0]$$$, then $$$B = 1$$$ and $$$P = [2,3,1,1]$$$. We can find out that the length of $$$T$$$ is less than $$$N+2$$$ if and only if vector $$$P$$$ satisfied that $$$2 \times sum + size \leq N +2$$$. So you can just sort these vectors by any order you like and transfer the 01-string related to the $$$x$$$-th vector to Bruno when receiving the integer $$$x$$$. We set $$$B = 1$$$ if and only if $$$x \gt 5e17$$$ and abstract $$$5e17$$$ from $$$x$$$ in this case. Since there are more than $$$6e17$$$ vectors satisfying that condition, it's enough to translate each integer $$$x(x \leq 1e18)$$$ to a boolean and a vector satisfying that condition, and these can be translated to a 01-string which can be transfered from Anna to Bruno. Anna.cpp Bruno.cpp Sorry for my poor English. Look forward to a full solution. |
| Name |
|---|


