Snackdown 2019 Problem Teammate

October 19, 2018

Snackdown 2019 Problem Teammate

Hii everyone!

Me and my friend Deepankar Sharma got Rank 1 in the Qualifier round of Snackdown 2019 and here is the question I liked the most.The math behind this problem was solved by me and Rishabh Verma and the code was figured out by me and Deepankar Sharma.I'll keep it simple just the question as it is from codechef and the solutions in terms of Math/logic and followed by the code in Python.Please try atleast once to solve it yourself then only you will understand the beauty of this question.To fork peep into my github account www.github.com/fivecube.
So here's the question...

Math/logic

The answer will be different for Odd and Even repetitions.

Let's solve for odd first:

Odd Case:

F=1

You might have figured out that the problem occurs when their are multiple people with same index score. If it would have only distinct Skill index then we would have said the answer is 1 in each case.
So what comes to mind at a first glance is what if we just sort the skill index and then start making tuples of 2. Like if we have
3,8,4,1,9,6,2,5,7,14
skill indexes of 10 people then sorted will be
1,2,3,4,5,6,7,8,9,14
and thus the valid pairs are clearly one which is
(1,2),(3,4),(5,6),(7,8),(9,14)
So ans is 1 in this case.

F=3

Skill index list(sorted)-: 1,1,1,2,5,7,9,15

So the 3*1=3 pairs would be

(1,1),(1,2),(5,7),(9,15)
(1,1),(1,2),(5,7),(9,15)
(1,1),(1,2),(5,7),(9,15)

and also these are not valid pairs if above are already considered-

(1,1),(1,2),(5,7),(9,15)
(1,1),(1,2),(5,7),(9,15)
(1,1),(1,2),(5,7),(9,15)

because like in 1st green and red are in the same team so changing their place does not count.

You can see the same result with permutation as 2 can form pairs with 3 different one so ans is 3.

F=5

Now what about skill index(sorted) -: 1,1,1,1,1,2,5,7,9,15
So the 5*3*1=15 pairs would be

(1,1),(1,1),(1,2),(5,7),(9,15)
(1,1),(1,1),(1,2),(5,7),(9,15)
(1,1),(1,1),(1,2),(5,7),(9,15)
(1,1),(1,1),(1,2),(5,7),(9,15)
(1,1),(1,1),(1,2),(5,7),(9,15)
(1,1),(1,1),(1,2),(5,7),(9,15)
(1,1),(1,1),(1,2),(5,7),(9,15)
(1,1),(1,1),(1,2),(5,7),(9,15)
(1,1),(1,1),(1,2),(5,7),(9,15)
(1,1),(1,1),(1,2),(5,7),(9,15)
(1,1),(1,1),(1,2),(5,7),(9,15)
(1,1),(1,1),(1,2),(5,7),(9,15)
(1,1),(1,1),(1,2),(5,7),(9,15)
(1,1),(1,1),(1,2),(5,7),(9,15)
(1,1),(1,1),(1,2),(5,7),(9,15)

You can better understand it with permutations and combinations. 2 can be paired with any five 1's (Red,Green,Blue,Pink and Black). Also the left 2 tuples of 1's like (1,1),(1,1) can also occur in 3 ways as seen in Even Case(look below) So total 5*3*1=15 ways.
It is awesome that this logic can be applied to more odd cases similarly.

Generalized Result for odd times(n) repeated index

n(n-2)(n-4)........ ..... .... . . . 1

Even Case:

F=2

Skill index list(sorted)-: 1,1,2,3,4,5,6,9

So there would be only 1 pair that is

(1,1),(2,3),(4,5),(6,9)

But what if the Skill index list(sorted) is -: 0,1,1,2,3,4,5,6 the pair would be 2 as follows

(0,1),(1,2),(3,4),(5,6)
(0,1),(1,2),(3,4),(5,6)

The difference is that 1 somehow appeared in 2 tuples because of it's relative positioning.
So the ans is 2*(1)=1

F=4

Skill index list(sorted)-: 1,1,1,1,2,3,4,5,6,9

So there would be only 3 pairs-:

(1,1),(1,1),(2,3),(4,5),(6,9)
(1,1),(1,1),(2,3),(4,5),(6,9)
(1,1),(1,1),(2,3),(4,5),(6,9)

You can understand the same with Permutation and combinations as well.If we stick one 1 to a tuple than it can make pair with 3 other 1.Hence 3*1=3

But what if the skill index lis(sorted) is -: 0,1,1,1,1,2,3,4,5,6

So there would be 12 pairs-:

(0,1),(1,1),(1,2),(3,4),(5,6)
(0,1),(1,1),(1,2),(3,4),(5,6)
(0,1),(1,1),(1,2),(3,4),(5,6)
(0,1),(1,1),(1,2),(3,4),(5,6)
(0,1),(1,1),(1,2),(3,4),(5,6)
(0,1),(1,1),(1,2),(3,4),(5,6)
(0,1),(1,1),(1,2),(3,4),(5,6)
(0,1),(1,1),(1,2),(3,4),(5,6)
(0,1),(1,1),(1,2),(3,4),(5,6)
(0,1),(1,1),(1,2),(3,4),(5,6)
(0,1),(1,1),(1,2),(3,4),(5,6)
(0,1),(1,1),(1,2),(3,4),(5,6)

Here also the difference is that 1 somehow appeared in 3 tuples instead of just 2 as in prior part of the same case.So the ans is 4*(3*1).

Clearly from permutation and combination point of view, we can see that similar results will appear.

Generalized result for Even times(m) repeated index

(m-1)(m-3)(m-5).... .. . . . . *1 (if they appear in m/2 tuples only)

m(m-1)(m-3)(m-5).... .. .. . . . 1 (if they appear in more than m/2 tuples)

Bonus part

Q: How can we know this information of appearance of Even times repeated index is in m/2 tuples or more?

A: We can know the position of the first/last repeated element in the sorted index list and then we can conclude that if it appears in m/2 or more tuples based on if it is even or odd. See how...

For F=4

1,1,1,1,2,3,4,5,6,9

Position of last 1 is 4(even) (In python it is 3(odd))

But in 0,1,1,1,1,2,3,4,5,6

Position of last 1 is 5 (odd) (In python it is 4(even))

Thank You So Much!!!

Here's the code : Click here to go to my github repo.

 from collections import Counter  
 foo = {1: 1, 2: 1, 3: 3, 4: 3}  
 last = 3  
 MOD = 10**9 + 7  
 for x in range(5, 10**5, 2):  
   p = (x*last) % MOD  
   foo[x] = p  
   foo[x+1] = p  
   last = p  
 for t in range(int(input())):  
   n = int(input())  
   a = list(map(int, input().split()))  
   a.sort()  
   c = Counter(a)  
   inds = {e: i for i, e in enumerate(a)}  
   ans = 1  
   for e, f in c.items():  
     ans *= foo[f]  
     if f % 2 == 0 and inds[e] % 2 == 0:  
       ans *= f  
     if ans > MOD:  
       ans = ans % MOD  
 print(ans % MOD)

Search This Blog

5Cube