NMNMX - Editorial

editorial
, ,
1

PROBLEM LINK:

Div 1
Div 2
Practice

Author: Full name
Tester: Full name
Editorialist: Oleksandr Kulkov

DIFFICULTY:

EASY

PREREQUISITES:

Fermat’s little theorem, modular arithmetics, basic combinatorics

PROBLEM:

You’re given sequence of distinct integers a_1,\dots,a_N and integer K. For each of its subsequences of size K you have to calculate product of all the elements except for minimum and maximum ones. After that you have to calculate product of these values among all subsequences.

QUICK EXPLANATION:

Sort the sequence, after that multiply all elements raised to power \binom{N-1}{K-1}-\binom{i-1}{K-1}-\binom{N-i}{K-1} using Fermat’s theorem.

EXPLANATION:

Since it doesn’t matter in this problem if we consider subsequences or subsets, we can suppose that array is sorted. Now element a_i will occur in \binom{N-1}{K-1} subsequences. Among them in \binom{i-1}{K-1} it will be the maximum element and in \binom{N-i}{K-1} it will be minimum element, so you should subtract these values from \binom{N-1}{K-1} to get number of subsequences in which particular element a_i will actually be counted in product. Now to calculate final product we can raise each element to the power equals to number of subsequences it will be counted in. To do this we’ll use Fermat’s little theorem:

a^{p-1}=1 \pmod p

Which is true for prime p and a \neq 0 \pmod p. Since 1=a^0 for any a, we could say that a^x=a^{x \pmod{p-1}}\pmod p. Now the only thing left to do for us is to calculate binomial coefficients modulo p-1. This is not prime number thus we can’t do it by calculating factorials and their reverses in advance but since N is sufficiently small, we can just calculate all binomial coefficients in N^2 using following recurrent formula:

\binom{n}{r}=\binom{n-1}{r}+\binom{n-1}{r-1}

This one is very famous, has many interpretations and can be easily proven. For example, number of ways to choose r items among n can be split between subsets having n-th item and subsets which don’t have it. Number of first ones is \binom{n-1}{r-1} and number of second ones is \binom{n-1}{r}. Given all that you can solve the problem precalculating all binomial coefficients modulo p-1 and using binary exponentiation to raise a_i in corresponding powers. Complexity of whole solution should be O(N^2+N \log p).

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.

4 Likes
2

a^x=a^x(modp−1)(modp) how???

1 Like
3

I would like to know if someone can find an issue with my combinatorics logic,

The power to which a_i should be raised, (when the array has been sorted and is 0-indexed ):

\binom{N-3}{K-3}*(i)*(N-i-1)

The reason behind this is, for a given number to contribute in a sequence, I would have to chose the number, then I would have K-1 places to fill. Out of which 1 would have to be from the i elements before it, and 1 would have to be from N-i-1 after it, which can be done in i and N-i-1 ways respectively.

Now I have remaining, K-3 elements which need to be chosen from N-3 elements and can be done in
\binom{N-3}{K-3}*(i)*(N-i-1) ways.

Hence the solution to the problem is :

\sum_{i=0}^{N} {a_i^{{\binom{N-3}{K-3}*(i)*(N-i-1)}\mod (p-1)} \mod p}

Can anyone see any issue with this explanation?

4

I used Chinese remainder theorem and Gaussian algorithm to find the remainder modulo (p-1) which is a composite number. Since p-1 = 10^9+6 has only two prime factors (2 and 500000003). Calculating modulo w.r.t. 2 and 500000003 and then using Gaussian algorithm to find the remainder w.r.t. the product (i.e. p-1) will work as expected.

For those who are not aware:

Chinese remainder theorem

Let n1,n2,…,nr be positive integers such that gcd(ni,nj)=1 for i ≠ j. Then the system of linear congruences

x ≡ c1 (mod n1); x ≡ c2 (mod n2); … ; x ≡ cr (mod nr)
has a simultaneous solution which is unique modulo n1n2…nr.

Gauss’s algorithm

If x ≡ c1 (mod n1); x ≡ c2 (mod n2); … ; x ≡ cr (mod nr) and
let N=n1n2n3…nr then

x ≡ c1N1d1 + c2N2d2 + … + crNrdr (mod N)
where Ni = N/ni and di ≡ (Ni)-1 (mod ni).

Hence, in our case, N = 10^9 + 6. n1 = 2 and n2 = 500000003.

N1 = 500000003 and N2 = 2.

Also, the remainders w.r.t. 2 and 500000003 can easily be calculated and applied in the Gaussian formula above.

5

I have used python3. So I need not have to bother about a^m mod p for large value of m. The in-build pow(a,m,p) would do that in an efficient way.

Now suppose we have n=6, k=3 and we have sorted array -

                                                   A = [1 2 3 4 5 6]

If we consider every element in every subset then each of the elements comes \binom{n-1}{k-1} times. In this case total = \binom 5 2

If we consider all the 3 element subsequences involving 1(A[0]) then the number of subsequences where 1 is minimum is equal to number of ways to choose 2 elements from the array (2..6) i.e. ( A[1]…A[n-1]) = \binom 5 2 as A[] is already sorted

Similarly the number of subsequences where 2 is minimum is equal to number of ways to choose 2 elements from array (3..6) i.e. (A[2]..A[n-1]) = \binom 4 2 and so on.

So we have created an array min_count[] where i^{th} element represents the number of times A[i] is minimum in a 3 element subsequences involving A[i].

In this case min_count = [\binom 5 2\ \binom 4 2\ \binom3 2\ \binom 2 2\ {0}\ {0} ]

Look carefully, element 5,6 will never be minimum in any 3 element subsequences .In general if i>n-k then i^{th} element will never be minimum.

So, in general min_count = [\binom {n-1} {k-1}\ \binom {n-2} {k-1}\ \binom{n-k-1} {k-1}\ \binom {n-k}{k-1}\ {0}\ {0} ..0 ]

Using Similar logic we created an array max_count[] where i^{th} element represents the number of times A[i] is maximum in a 3 element subsequences involving A[i].

max_count = [0\ 0...\binom {k-1} {k-1}\ \binom {k} {k-1}\ \binom{k+1} {k-1}....\binom {n-1}{k-1}\ ]

Now come to main problem. The total number of A[i] comes in all the subsequences excluding minimum and maximum = total -(min_count[i]+max_count[i]) which is our Power[i]

Our answer will be Ans = \prod\ A[i]^{Power[i]} mod p

Wow, We are getting right answer. But wait, what if N = 5000 ?

It will take too much time to calculate min_count if we individually calculate \binom {n-1} {k-1} , \binom {n-2} {k-1}…\binom {n-k} {k-1} .

So we have used little combinational knowledge to calculate \binom {n-2} {k-1} from \binom {n-1} {k-1} by this - \binom {n-2} {k-1} = \binom {n-1} {k-1}\ * (n-k)/(n-1)

Now think carefully, the max_count is the reverse of min_count. i.e max_count[i]=min_count[n-i-1]

So Power[i]= total - (min_count[i] + min_count[n-i-1])

Again you will see Power[i] = Power[n-i-1]. i.e A[i] and A[n-i-1] will come same number of times.

Now we have to calculate product from i= 0 to n/2

Ans will be \prod\ (A[i]*A[n-i-1]^{Power[i]}) mod p

Here is my solution -
link text

3 Likes
6

One can also read “Euler Totient Function” theory for understanding the modulo part. Link : Euler's totient function - Wikipedia

7

A beautiful problem and equally beautiful editorial - Thank You

8

What is the use of Fermat little theorem here ? could it be done just by using modular exponentiation ?

9

Since 1=a0 for any a, we could say that a^x=a^x(modp−1)(modp).

I am trying but not able to figure out how the statement comes out of Fermat’s little theorem and the fact that a raised to 0 becomes 1.

Can someone please elaborate?

10

For people having difficulty in understanding why we mod the power with (m-1) :

This is a very neat proof.

Please upvote if I helped so that I can qualify to upvote others. :))

1 Like
11

Hello everyone Refer my answer for query about \mod{p-1}

#link: NMNMX whats wrong - #4 by l_returns - general - CodeChef Discuss
Feel free to ask queries :smiley:

12

Some good discussion also happened here- https://discuss.codechef.com/questions/131430/july-18-problem-discussion?sort=votes&page=1

Do have a look :slight_smile:

1 Like
13

You’re counting some cases more than once. Say, i is 5 and k is 4. You pick index 3 in your ‘pick a smaller number’ part and pick index 2 (there is only one number left to pick) in your (n-3, k-3) part. But that case is counted again when you pick index 2 in your ‘pick a smaller number’ part and index 3 for the (n-3,k-3) part.

I’m not 100% sure though. Try to calculate some values and see if they’re greater than expected.

14

Answer my question instead, please.

15

this link gives answer to your question only… I commented for only u but thought someone else also get the same doubt…

16

Since a^{p-1}=a^0 \mod p we can say that a^{x-k \cdot (p-1)}=a^x \mod p. If we take k = \left\lfloor\dfrac x {p-1} \right\rfloor, we will get mentioned equation.

17

Thanks to both. A little query, why can’t I add comment to any other answer except this one?

18

you need to have 50 reputation points for that. Currently you have 13.

19

Refer “new karma system” blog on discuss… For knowing minimum reputation to do stuff…

20

https://discuss.codechef.com/questions/68246/karma-on-codechef