ANUTDP - Editorial

[elfus]

PROBLEM LINK:

Practice
Contest

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

1. **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.

2. 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.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution

[chalubhalu]

Weird Editorials…

[dpraveen]

Editorialist has put a lot of efforts, there are some formatting changes, which we should help correcting as the article is in community wiki.

[zeus07]

I tried it doing in this way:

Let n be the Limit.

First Create an array A such that A[i]=1 if i is a fibonacci number.

For i= 1 to sqrt(n)

If(A[i]=1)

    For j= i to n

    If(A[j]=1 & A[i*j]=0)

            A[i*j]=1

            B[i*j][0]=i

            B[i*j][1]=j

End

Now if A[i]=1 means that i is a good Number

Then taking the inputs and finding the nth good number

If i is the Nth good number from L to R

      PR(i)

End

PR(i):

If A[i]=1

     Print i times '.'
     Print '#'
Else
PR(b[i][0])
PR(b[i][1])

Can anyone tell me will this work everytime ???

[betlista]

The problem was really really nice, but it was not easy to understand the problem statement in a contest.

If I describe it from the end to the beginning…

As stated in problem statement - well known problem is: “If we have path of length n meters, how many ways are there if we can do step of 1 or 2 meters only?” - answer is Fib(n). Fib(1) = 1, Fib(2) = 2, Fib(3) = 3, Fib(4) = 5…

When there are dirty cell (and there cannot be two in a row, otherwise it’s the end of the path) they split the path => ...#.....#.... to pats of length 2, 4 and 3 so the number of ways is F(2) * F(4) * F(3) and this is the good integer.

So we came to the beginning, from this good integer we have to generate the path, but first we have to find the Nth good integer in interval [L, R]…

[alok_code]

please answer me I’m stuck on this statement (a, b) -> (b, 0) -> (b, b) -> (b, 2 * b)…
if we move from (a,b) then we should get either (b,a+b) or (b,0) (depend on . or #) then how from (b,0)
we are moving to (b,b). I think it should be (a,b)->(b,0)->(0,b)->(b,b)…please correct me if i am wrong

[betlista]

I think it will work if you change Print i times '.' to Print i+1 times '.'. Hopefully, you know how to implement “If i is the Nth good number from L to R”

[zeus07]

won’t linear search work ?? or will it give tle ??? thanx for the reply @betlista

[shikharsav]

Basically a good integer can be written as a product of Fibonacci numbers (2 or more).
Therefore, x is a good integer iff x = f1 * f2 * …fn where all fi are fibonacci numbers.
Suppose Fib is the set of all Fibonacci numbers. We want set Good.
An element of Good is the product of elements of any subset of Fib.
Therefore to compute Good we need to compute all subsets of Fib(or we might miss some “good” number). However this is exponential and seems computationally infeasible.

[betlista]

It is even more complicated, because we do not want only subset, but also 9 is good for example, because 9 = 3², but the limit 10⁸ works for us - as written in editorial:

Another argument that proves the number of “good” numbers is low is that the products of Fibonacci numbers grow really fast.

There is only 33817 good numbers <= 10⁸ the last two are 99980400 and 10⁸.

[beroul]

Very nice problem

But, the problem statement could have been more explicit about some conditions…
Eg:
Is 0 a good number ?

(actually it’s yes. But not obvious from the statement)