NEED HELP IN PERIODIC
Let's define a periodic infinite sequence S (0-indexed) with period K using the formula Si=(i%K)+1.
Chef has found a sequence of positive integers A with length N buried underground. He suspects that it is a contiguous subsequence of some periodic sequence. Unfortunately, some elements of A are unreadable. Can you tell Chef the longest possible period K of an infinite periodic sequence which contains A (after suitably filling in the unreadable elements) as a contiguous subsequence?
Example Input
3
3
-1 -1 -1
5
1 -1 -1 4 1
4
4 6 7 -1
Example Output
inf
4
impossible
Chef has found a sequence of positive integers A with length N buried underground. He suspects that it is a contiguous subsequence of some periodic sequence. Unfortunately, some elements of A are unreadable. Can you tell Chef the longest possible period K of an infinite periodic sequence which contains A (after suitably filling in the unreadable elements) as a contiguous subsequence?
Example Input
3
3
-1 -1 -1
5
1 -1 -1 4 1
4
4 6 7 -1
Example Output
inf
4
impossible
Here's the link to the challenge
https://www.codechef.com/SNCK1A19/problems/PERIODIC/
https://www.codechef.com/SNCK1A19/problems/PERIODIC/
i can tell the logic for periodic problem if anyone can give me logic for 100 points chefadd problem
For the first problem, Chef can't read any of the numbers. They could be any numbers for a sequence of any length, so the answer is inf(infinite).
For the second one, notice the transition from 4 to 1. This can only happen at the end of a sequence, and in this case, it tells you that K mus be 4 if the sequence is valid. The other unknowns will work when k==4 so the answer is 4.
The third one can't be a valid sequence because "4 6" can never appear in a valid sequence. If Si is X then Si+1 must be X+1 or 1.
For the second one, notice the transition from 4 to 1. This can only happen at the end of a sequence, and in this case, it tells you that K mus be 4 if the sequence is valid. The other unknowns will work when k==4 so the answer is 4.
The third one can't be a valid sequence because "4 6" can never appear in a valid sequence. If Si is X then Si+1 must be X+1 or 1.
Topic archived. No new replies allowed.