PROBLEM LINK:
Setter: Hasan Jaddouh
Tester: Misha Chorniy
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Periodic sequences, Factorization would be helpful. Pattern finding.
PROBLEM:
Given a sequence A of length N, with probably some elements unreadable, we need to determine, what is the largest value of K, such that given array will be a contiguous subsequence of sequence i \bmod K+1 (i being 0-indexed), assuming we can fill unreadable characters with any characters of our choice.
SUPER QUICK EXPLANATION
- Unreadable elements at either end of array are useless. If there are x unreadable elements between any two consecutive readable elements A[p] and A[q] and A[q]-A[p] \neq q-p and x < a[q], answer is impossible.
- If we get take any pair of consecutive readable positions p and q, p < q, and a[q] \neq a[p] -p+q, having exactly x unreadable elements in between, Then, answer if exists, is a factor of x - (a[q]-1) + a[p]. Also, answer, if exist, is always greater than or equal to maximum element in array.
- So, We just find for every consecutive readable numbers pair p and q satisfying a[q] \neq a[p] -p+q, Take x-(a[q]-1)+a[p] and Find it’s Greatest Common Divisor. If this GCD is greater than or equal to maximum element of array, This value is answer, otherwise answer is impossible.
EXPLANATION
This problem has multiple solutions, So, I will be explaining setter and tester solution (same), after which I will give an idea of my solution.
Defining cycle as one repetition of the sequence 1 2 3 \dots K.
The first thing to notice is that If there are unreadable elements at either end of the array, They don’t matter at all. Ignore them (I deleted them).
Now, first element is always readable. Suppose Period of sequence is N. Then the sequence will look like x, x+1, x+2, \dots N, 1, 2 \dots x-1.
Try subtracting index of an element from it. You’ll get x, x, x, \dots x N times. So, what does this teaches us? That if we know starting term and distance from starting term (index of position), we can predict the value at that position. The only thing to consider here is, that after value at position reach N, it goes back to 1, resulting in negative values. So, just add N to these terms, This will always give x.
The reason is, as we move rightward, index increases by 1, as well as element increases by 1.
So, we know how the cycle looks like and how to find the ith term of the cycle, if we know its position from the first element of the sequence which is 1.
Now, Try to solve some examples.
If the position of value 5 is 8, find positions of value 9 in the array, if cycle length K is 10 and length of the array can be any large value you can think of.
We can see that first few positions having value 9 are 12, 22, 32, 41 and so on. The important thing to notice is that a value repeats itself after K elements.
Let’s work in general terms. If element at position p is A[p], then try to estimate value of A[q]. For simplicity, p < q.
I’m sure you all can figure out it’s A[p]-p+q. Because A[p]-p+1 gives location of starting element of sequence, and from there, we find A[q] by adding q-1, resulting in expression A[p]-p+q.
So, moving toward original sequence, we see first of all, that for any consecutive readable positions p and q, having x unreadable elements in between, if A[q] \neq A[p]-p+q, then either the sequence is invalid, or the sequence has once (or more than once) again repeated.
If the sequence has repeated, we know, that last A[q]-1 elements from the end of this unreadable elements should be, 1,2,3 ... A[q]-1. So, if x < A[q]-1, then answer is impossible. Now, it is possible, that sequence may be running at position a[p]. So, how to handle this?
Take an example where the sequence is running from readable elements.
1 2 -1 -1 2 3
In this example, we can manually find that answer is 1 2 3 1 2 3. How to know that sequence from last readable position will continue. How to handle that? Since we actually don’t know the cycle length, It’s hard for us to remove y = K-A[p] elements from x-A[q]-1. But, We know, that x-(A[q]-1)-(K-A[p]) elements may contain multiple **complete sequence from 1 to K, so, x-(A[q]-1)-(K-A[p]) is a multiple of K. Add K to this, we get x-(A[q]-1)+A[p] which is independent of K and a multiple of K. Assume z = x-(A[q]-1)+A[p].
This way, for every consecutive pair of readable positions p and q having x elements in between, we can calculate z for every pair, and know, that K is a factor of all these values of z.
So, Any guess for the largest length of the cycle, which may divide all values of z we found just now? Yes, your guess is accurate. It’s just the Greatest Common Divisor of all these z. This is the largest value which satisfies our problem, Say ANS. But, the array cannot contain any value greater than ANS, since given infinite sequence having cycle K cannot have any element greater than K. So, if any readable element is greater than answer, we cannot choose this value as the answer. We cannot choose any higher value as an answer as they won’t satisfy dividing z for some pair (p, q). This means that we have reached an impasse, So the answer is impossible in this case. Otherwise, we can print this answer.
But, Suppose we do not get any value of z at all? Wondering when this happens? See example test case 1, as well as the array -1 2 3 -1 5 -1
Got any values of z? No, because every readable value pair satisfied A[q] == A[p]-p+q. Answer in this case is Infinite.
Editorialist’s solution
He likes different solutions, so, what he did, used prime factorization again (You may know he likes prime factorization a lot if you read SnackDown qualifier editorials). Instead of Finding the value of z for all consecutive readable value pairs, He just found the first value of z, factorized z and tried each factor of z. Out of all values which can be the cycle in given array, if the maximum value is greater than or equal to the maximum value of the array, the answer is that maximum value from possible cycle lengths we just found. Otherwise answer is impossible.
Bonus problem
Same problem except that the infinite sequence given in the problem is defined as (i \bmod K)*2+1. Enjoy solving 
Time Complexity
Time complexity is O(N).
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Tester’s solution
Editorialist’s solution
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 
