PERIODIC - EDITORIAL

easy-medium
gcd
pattern
periodic
sequences
snck1a19
taran_1407

#1

PROBLEM LINK:

Practice
Contest

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] eq 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] eq 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] eq 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] eq 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 :stuck_out_tongue:

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. :slight_smile:


#2

Hi,my approach to this problem was just same as your explanation. But,my solution failed in some test cases. After the contest was finished,I copied one of the codes, which produced correct results and tested it with more than 1000 test cases against my code(I used an input generator and an output checker) and both the codes produced same results. Then I myself looked for any corner cases left behind but unfortunately I couldn’t find it. So, after spending 3-4 hours, I couldn’t find that test case in which my solution went wrong. Can you please provide me that test case?

Link to my solution is: https://www.codechef.com/viewsolution/21104966


#3

I ran my code over 200 test cases and I looked at the code for one whole day but still couldn’t find why it was giving WA for the 2nd subtask.

Link: https://www.codechef.com/viewsolution/21108442

I know my code isn’t commented and can’t be read by anything else than a debugger but if anyone has any idea why it failed, it would be nice to know :slight_smile:


#4

You are taking minimum of all possible values. Instead take gcd. You will get AC :P.


#5

Someone please help me! if you can provide me with those test cases, it will be a great help to me @admin


#6

Hello @arkadeep_2000

I cannot provide you with the test cases, as it is against codechef’s guidelines.


#7

But, the contest has ended and I just want to know where my program went wrong. Its for the sole purpose of learning. I also don’t want entire set of test cases, just provide me any of the test cases, in which my solution produced wrong results! @taran_1407


#8

First thing, I myself do not get access to test cases.

Second thing, I cannot share test cases even if I have access.

Although it is possible that someone may find a test case which fails your solution.


#9

Okay! Now I get it! Hope somebody helps!


#10

@vichitr Thanks :slight_smile: that was so foolish of me :confused:


#11

We made the same mistake. Haha