Editorial for Wesley's Anger Contest 4 Problem 4 - The Almighty Acorn

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Zeyu

Subtask 1

For subtask 1, we can simulate the process of creating the infinite string. This can be done by concatenating the first $1000$ ~1000~ numbers together and then using a standard substring finding function. We can observe that any string of length $|S|$ ~|S|~ can be found within the first $10^{|S|}$ ~10^{|S|}~ positive integers. This applies to strings with leading zeroes as well, since we can use the nonzero digits at the end of the string to create a new valid number. For example, the string 008 can be found in the concatenation of $800$ ~800~ and $801$ ~801~.

The edge case to watch out for is the string 000, which appears with the number $1000$ ~1000~.

Time Complexity: $\mathcal{O}(10^{|S|})$ ~\mathcal{O}(10^{|S|})~ to create the string from $1$ ~1~ to $1000$ ~1000~, and $\mathcal{O}(|S| \cdot 10^{|S|})$ ~\mathcal{O}(|S| \cdot 10^{|S|})~ to find its leftmost occurrence using naive string search.

Subtask 2

For subtask 2, we can build on the idea of "creating" a valid number. Since smaller numbers appear earlier in the infinite string, the problem then becomes finding the smallest valid number that when concatenated with its successors, contains $S$ ~S~ as a substring.

To generate a potentially valid number, we can loop for its size in increasing order, and then loop for the possible offset positions of this valid number. To check if this generated number can form $S$ ~S~, we can simulate the addition by $1$ ~1~ and concatenate it with the first number until the new string's length exceeds $|S|$ ~|S|~. Comparing the two strings in linear time will suffice for this subtask.

Using the smallest valid number, we can determine its position in the infinite string. If the number has more than $D$ ~D~ digits, then there are at least $D \cdot 9 \cdot 10^{D - 1}$ ~D \cdot 9 \cdot 10^{D - 1}~ digits preceding it. If $N$ ~N~ is the smallest valid number, $K$ ~K~ is the number of digits in $N$ ~N~, and $M$ ~M~ is the offset, then the index can be defined as:

$\displaystyle K \cdot \left(N - 10^{K - 1}\right) - M + \sum_{D = 1}^{K - 1}{D \cdot 9 \cdot 10^{D - 1}}$

Note that while BigInteger libraries can help with some of these steps, it does not bring the complexity down and does not make this subtask simpler to implement.

Time Complexity: Since we have a loop for the length, a loop for the offset, and an $\mathcal{O}(|S|)$ ~\mathcal{O}(|S|)~ string check, the total time complexity is $\mathcal{O}(|S|^3)$ ~\mathcal{O}(|S|^3)~.

Subtask 3

For the full solution, let's improve the $\mathcal{O}(|S|)$ ~\mathcal{O}(|S|)~ string check. There are a few possible approaches such as using a suffix array, but the method that will be described here will use hashing.

Instead of building the concatenation, we can check on $S$ ~S~ itself. For a valid string, there should be a chain of non-overlapping substrings that always increase by $1$ ~1~ from left to right. For a chain of size $K$ ~K~, there will be $\mathcal{O}\left(\left\lceil \frac{|S|}{K} \right\rceil\right)$ non-overlapping substrings. We can compare adjacent substrings to check for the validity.

To perform a comparison, let's define two hashing functions:

$\operatorname{hash}(x)$ ~\operatorname{hash}(x)~, which hashes the substring $x$ ~x~,
$\operatorname{next}(x)$ ~\operatorname{next}(x)~, which hashes the substring $x + 1$ ~x + 1~.

To check if two adjacent substrings have a difference of $1$ ~1~, we can use $\operatorname{next}$ ~\operatorname{next}~ and compare it with the hash value of the adjacent substring using $\operatorname{hash}$ ~\operatorname{hash}~.

Calculating $\operatorname{hash}(x)$ ~\operatorname{hash}(x)~ is straightforward and can be done in constant time. This will not be further explained as there are other string problems which use this technique such as this problem.

Calculating $\operatorname{next}(x)$ ~\operatorname{next}(x)~ is trickier and requires a few observations. First, hash values will only increase by $1$ ~1~ if the string's last digit is not a $9$ ~9~. Second, the trailing $9$ ~9~s will all become $0$ ~0~ when incremented, and increase the rightmost digit that is not a $9$ ~9~. We can precompute the number of trailing $9$ ~9~s that end at each specific position in $S$ ~S~ and use it to adjust the hash value accordingly. A proper implementation should be able to calculate $\operatorname{next}(x)$ ~\operatorname{next}(x)~ in constant time as well.

How much does this bring the complexity down? With $\mathcal{O}\left(\left\lceil \frac{|S|}{K} \right\rceil\right)$ comparisons for the string check, the time complexity can be modelled as:

$\displaystyle \sum_{K=1}^{|S|} \sum_{M=0}^{K-1} \mathcal{O}\left(\left\lceil \frac{|S|}{K} \right\rceil\right) = \mathcal{O}(|S|^2)$

Careful implementation must be done to avoid edge cases and will be left as an exercise for the reader.

Time Complexity: $\mathcal{O}(|S|^2)$ ~\mathcal{O}(|S|^2)~

Comments

There are no comments at the moment.