You are not logged in. Please login at www.codechef.com to post your questions!

×

NMNMX - Editorial

3
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.

This question is marked "community wiki".

asked 16 Jul '18, 05:16

melfice's gravatar image

4★melfice
811737
accept rate: 0%

edited 16 Jul '18, 23:04

admin's gravatar image

0★admin ♦♦
19.7k350498541

1
(17 Jul '18, 00:07) vijju123 ♦♦4★

Why do subset or subsequence doesn't matter?

(12 Sep '18, 02:27) ay23063★

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

link

answered 17 Jul '18, 17:25

sayantan11995's gravatar image

1★sayantan11995
462
accept rate: 25%

edited 20 Jul '18, 23:28

1

thanks till now the clearest explanation.

(20 Jul '18, 06:43) harrypotter04★
1

Thanks bro.

(20 Jul '18, 23:26) sayantan119951★

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

link

answered 16 Jul '18, 23:14

rahul1995's gravatar image

3★rahul1995
23114
accept rate: 0%

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

link: https://discuss.codechef.com/questions/131526/nmnmx-whats-wrong/131541

Feel free to ask queries :D

(16 Jul '18, 23:19) l_returns4★

Answer my question instead, please.

(17 Jul '18, 18:23) rahul19953★

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

(17 Jul '18, 21:15) l_returns4★

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.

(18 Jul '18, 00:46) melfice4★

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

(18 Jul '18, 08:13) rahul19953★

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

(18 Jul '18, 08:30) tamiliit3★

Refer "new karma system" blog on discuss... For knowing minimum reputation to do stuff...

(18 Jul '18, 11:15) l_returns4★

This is the euler totient function For prime numbers it is (p - 1). for the rest https://en.wikipedia.org/wiki/Euler%27s_totient_function#Computing_Euler's_totient_function

(18 Jul '18, 19:23) kukreja_vlk3★
showing 5 of 9 show all

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

https://stackoverflow.com/questions/45458628/calculating-a-pow-b-mod-m-for-very-large-a-and-b-stored-in-string

This is a very neat proof.

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

link

answered 30 Jul '18, 04:07

iprakhar22's gravatar image

4★iprakhar22
324
accept rate: 0%

edited 30 Jul '18, 04:09

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?

link

answered 17 Jul '18, 05:10

mehwhatever's gravatar image

2★mehwhatever
161
accept rate: 50%

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.

(17 Jul '18, 10:43) psaini724★

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.

link

answered 17 Jul '18, 05:44

ritam777's gravatar image

4★ritam777
12
accept rate: 0%

edited 17 Jul '18, 06:04

@ritam777 During the contest, I was trying to do this but could not. Thank you so much as I now understand it :))

Sorry I am not qualifed to upvote otherwise I would have.

(30 Jul '18, 04:08) iprakhar224★

One can also read "Euler Totient Function" theory for understanding the modulo part. Link : https://en.wikipedia.org/wiki/Euler%27s_totient_function

link

answered 18 Jul '18, 12:45

p1p5_5's gravatar image

3★p1p5_5
708
accept rate: 0%

Yes I gave same answer

(18 Jul '18, 13:37) l_returns4★

A beautiful problem and equally beautiful editorial - Thank You

link

answered 18 Jul '18, 21:29

sapace88's gravatar image

1★sapace88
1
accept rate: 0%

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

link

answered 20 Jul '18, 13:53

krishankantray's gravatar image

2★krishankantray
163
accept rate: 20%

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?

link

answered 26 Jul '18, 18:02

ruddradev's gravatar image

3★ruddradev
1245
accept rate: 7%

1

Try 3-tower coloring question of hackerrank and read its editorial.

(26 Jul '18, 18:54) vijju123 ♦♦4★
1

@vijju123: Thank you. That explanation was very helpful.

(27 Jul '18, 23:44) ruddradev3★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,497
×3,709
×120

question asked: 16 Jul '18, 05:16

question was seen: 5,922 times

last updated: 27 Jul '18, 23:44