PROBLEM LINK:
Author: Anudeep Nekkanti
Tester: Constantine Sokol
Editorialist: Florin Chirica
DIFFICULTY:
Easy-Medium
PREREQUISITES:
binary search, sorting, BFS / DFS, backtracking, amortized analysis of number of states
PROBLEM:
On OX axis, x values can be of two types: clean or dirty. You can walk only on clean coordinates, making steps of +1 or +2. Let’s calculate number of ways to reach final destination. This number of ways is called a “good” number. Answer queries which ask you to find k-th good number from range L and R.
QUICK EXPLANATION
We can generate all good numbers. It turns out the number of good numbers is relatively small. Let’s keep the list sorted. Now, to get k-th good number which is between L and R we can use binary search.
EXPLANATION
First consider the reverse problem
Let’s consider the reverse problem: given a string, calculate the number of ways to reach last position from the first one. Since this subproblem asks “number of ways”, it’s natural to think at dynamic programming.
Let ways[i] = number of ways to reach i-th position from the string. If at i-th position there’s a # character, then obviously we can reach it in 0 ways. Otherwise, if there’s a “.”, I should reach it. How can I do it? Let’s think at last step I did, after which I reached i-th position. It can come either from i – 1 or from i – 2. I need to think now at number of ways to reach i – 1 or i – 2. But this numbers are already calculated in ways[i – 1] and ways[i – 2]. So ways[i] = ways[i – 1] + ways[i – 2], if i-th character is “.”. If string is 0-based, then ways[0] = ways[1] = 1.
Now consider the actual problem
Why was it important to consider the reverse problem? We can build our string character by character. In parallel, we can also count in how many ways we can obtain our current string.
Let’s note a state (a, b) to correspond the current string, if number of ways to reach last character is b and number of ways to reach the character before the last one is a. From a state (a, b), we can go to a state (b, a + b) or to a state (b, 0). I’m interested in all numbers x such as state (x, 0) is reachable.
How to determine them? And more important, how to store them? Apparently, there are O(x ^ 2) states, too much to keep in memory (where x = 10^8). Let’s add from a state (a, b) only “.” characters. Very soon, number b will grow a lot. This means that the number of states (a, b) can’t be too big. To determine a relative number of states, it’s enough to count only states (a, 0). States (a, b) with b != 0 will grow so fast that we’re not interested in counting them?
So how many states (a, 0) can be? Worst case, there can be at most O(x) states. But like last time, it turns on that this number is overrated. We ran a program and saw the number of states is about 3 * 10^4 for x = 10^8.
How to generate numbers? Let’s build a graph with nodes (a, b) and edges between (a, b) and (b, a + b) and (b, 0). We can run a BFS / DFS / another graph traversal algorithm. Each time a node (b, 0) is reached, we can add it to a special list of “good” numbers. For reconstruction of solution for a (x, 0) we can keep track of character added (if going from (a, b) to (b, a +b) we added “.”, otherwise we added “#”).
To answer queries, the task reduces now to: given L, R and N, answer which is N-th value which has value between L and R. Let’s sort the list of good numbers. Now, for any L and R, all good numbers between L and R will be a contiguous subsequence in the sorted list.
Use binary search
Since the good numbers list is sorted, we can use 2 binary search to find i and j where
- i is the minimal index such as list[i] >= L
- j is the maximal index such as list[j] <= R
-
All elements that lie between L and R are {list[i], list[i + 1], ..., list[j – 1], list[j]}. More, they are given in increasing order. So, N’th good value would be simply list[i + N -1]. If i + N – 1 > j, we need to print “-1”.
Alternative Solutions
Let’s present an alternative solution now. Suppose so far we added only “.” and we reach state (a, b). Then, let’s add “#”. The state becomes (b, 0). We are forced to add “.” now (otherwise, we’ll go in (0, 0) and there’s nothing to be done from there). After adding “.”, we go from (b, 0) to (b, b). Now all numbers are a multiple of b. Sum of two numbers multiple of b will also be a multiple of b. This means, as long as we add “.”, the state (x, y) in which we are will have a and b divisible by b. Let’s take an example: we add a “#” and then only “.”
(a, b) → (b, 0) → (b, b) → (b, 2 * b) → (2 * b, 3 * b) → (3 * b, 5 * b) → (5 * b, 8 * b) → …
If we divide by b the states, we’ll get Fibonacci numbers! So suppose our final state is (x, y):
(b, 0) → (b, b) → (b, 2 * b) → … → (x, y) → (y, 0)
If we divide y by b we obtain a Fibonacci number. y = b * some_fibonacci_number. Let’s see how (b, 0) was obtained. There are 2 cases
-
**No extra “#” was added**
(0, 1) → (1, 1) → (1, 2) → (2, 3) → (3, 5) → (5, 8) → … → (b, 0)
Obviously, b is a Fibonacci number, so y = some_fibonacci_number * another_fibonacci_number. -
At least one “#” was added
(b’, 0) → (b’, b’) → (b’, 2 * b’) → (2 * b’, 3 * b’) → … → (b, 0)
If we divide b by b’, we’ll get b = fibonacci_number_1 * b’. So y = fibonacci_number_1 * fibonacci_number_2 * b’. We can apply same logic for b’, so it will be written as a product of Fibonacci numbers. We get that a reachable (x, 0) state is a product of Fibonacci numbers.
For here we get the alternative solution for calculating list of “good” numbers: let’s precalculate all Fibonacci numbers. We can do a backtracking to get all products of Fibonacci numbers up to 10^8!
Another argument that proves the number of “good” numbers is low is that the products of Fibonacci numbers grow really fast. It’s very easy for a product of Fibonnaci numbers to become greater than 10^8. Intuitively, the number of products of Fibonacci numbers up to 10^8 is small enough.
After getting the list of “good” numbers, we apply algorithm described above to solve queries (sort the list of numbers and do binary search).
Time Complexity
Denote by cnt number of good numbers. The time complexity is O(cnt * log(cnt) + T * log(cnt)), steps necessarily due of sorting and binary search.