All submissions for this problem are available.
You recently visited The Great Circus at Pilani. You saw a few jugglers at the circus and you really liked their performances. Being really good at math and analytical skills, you can't help but look at juggling from a mathematical perspective.
So what exactly is juggling? Before defining it, we will try to get a feel of what it is by looking at various examples.
What you see here are different 'patterns' of juggling.
Definition of juggling
Making a move with a hand: When a juggler makes a move with a hand, he checks if there is a ball in that hand. If there is a ball in that hand, he throws it (this is called a normal throw). Otherwise, he doesn't do anything with that hand (this is called an empty throw).
- A juggler cannot have more than one ball in a hand at any given time.
- A juggler makes a move alternately with his left and right hands (i.e. he cannot move with both his hands or make 2 consecutive moves with the same hand).
- The time interval between any 2 consecutive moves is constant. That constant is known as a tick.
Formalizing a juggling pattern
In juggling, there are many different ways of throwing a ball (you can notice that in the examples). Suppose a ball is thrown at time t1. It is caught at rethrown at time t2. Then t2-t1 divided by the duration of a tick is called the order of that throw. Order of an empty throw is 0.
We can characterize a juggling pattern by the order of its throws. For eg, in the first example all throws are of order 3. In the second example, throws of order 5 and 3 are alternating. Since juggling patterns are periodic, we write a few throw orders and assume that the throw orders keep repeating. This representation of a juggling pattern is called 'Throw Order Sequence' (TOS).
For the examples given above, these are the TOSes:
- [5, 3]
- [5, 1]
- [4, 4, 1]
- [5, 0, 5, 0, 5]
- [5, 3, 4]
More specifically, let S be a TOS of length N. That means that the (i+1)th throw has order S[i%N], where i is any non-negative integer. The (i+1)th throw happens at time i (counting in ticks). Further, if i is even, the (i+1)th throw is made using the right hand. If i is odd, the (i+1)th throw is made using the left hand.
A sequence of numbers may or may not be a TOS of any juggling pattern. You will be given a sequence of integers and you have to tell whether it is a valid TOS.
The first line contains an integer T, the number of test cases.
The first line of each test case contains a single integer N, the number of elements in the sequence.
The next line contains N space-sepatated numbers, which is the sequence you have to analyze.
For each of the T sequences, output (on separate lines) "Valid" if the sequence is valid and "Invalid" otherwise.
1 ≤ T ≤ 10000
1 ≤ N ≤ 100000
The sum of N for all test cases does not exceed 106.
The numbers in the sequence range from 0 to 109. There will be at least one positive integer in the sequence.
7 3 5 3 4 2 5 3 9 5 3 4 5 3 4 5 3 4 2 3 5 3 4 4 2 2 4 1 4 8 0 4 0
Valid Valid Valid Valid Invalid Invalid Valid
The 3rd TOS is equivalent to the 1st TOS and the 4th TOS is equivalent to the 2nd one. This is because juggling is periodic. The first and the third TOS correspond to the throw orders
...53453453453... and the 2nd and 4th TOSes correspond to throw orders
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, RUBY, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.