OLYMPIC - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY-MEDIUM

PREREQUISITES

sorting, factorials, inverse modulo a prime, basic combinatorics

PROBLEM

The problem is, given count[1…n], the number of chocolates to be included from each village, we need to pack the chocolates into minimum number of boxes of a given size S. No two chocolates from different villages should be places in same box. Given that different villages get different colored boxes, find the total number of distinct gift packs possible. Two gift packs are considered same if and only if they have the same order of colored boxes, even in reverse. “ABC” is same as “ABC” and “CBA”.

EXPLANATION

First lets see how we can solve the problem of uniquely counting distinct gift packs by taking care of reverse order too. Suppose there are B1 boxes of type 1, B2 boxes of type 2 , … Bk boxes of type K, then the total number of gift packs possible can be found using the following multinomial.

SUM = B1 + B2 + … + Bk
Total possible ways, T = ( SUM! / ( B1! B2! B3! … Bk! ) )

But T may include duplicate items, where two items are same if reversed. Consider “AABBC”. T counts both “AABBC” and “CBBAA” differently and we need to take care of this.

Let P = total number of palindromic strings, where a string is palindrome if its exactly same as its reversed string.

Let U = total number of non-palindromic strings

Our desired answer = ( U + P ) , but the value of T = ( 2 * U + P ), as it counts each non-palindromic
string twice. Finding the number of non-palindromic strings directly may not be easy, so instead we will
find the value of P, the number of palindromic strings. A palindromic string is uniquely defined by its first half, so we will half the counts of each character and find the number of possible halves. Note that P = 0, if the number of characters having odd count > 1 , as only one character can take the middle position in case of odd count.

SUM2 = B1/2 + B2/2 + … + Bk/2
Total number of palindromes, P = ( SUM2! / ( (B1/2)! (B2/2)! … (Bk/2)! ) )

If we have the values of T and P, we can find the desired answer = U + P = ( T + P ) / 2

So the problem is reduced to finding the values of T and P. Till this part, its a common approach. For further main part of the solution, refer any of setter’s or tester’s approach below.

SETTER’S SOLUTION

Can be found here

APPROACH

Consider count[i] = 20 and find the number of boxes needed, if size S varies from 1 to 20.

Size of each box S 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Number of boxes Bi 20 10 7 5 4 4 3 3 3 2 2 2 2 2 2 2 2 2 2 1

The main idea is, instead of finding the value Bi for each size of the box S, we only visit the indices where there is a change in the number of boxes Bi required. Once we have this, we can scan the array linearly and propagate the values among the indices in between. The good part of it is, we mark the changes for each count[i] in the same array and propagate the values in O(n) time, once for all. So, given count[i] , here is how we can visit only the changes.

Each size in the interval [lo…hi] requires x boxes
Initially, lo = count[i], hi = count[i], x = 1;
while(lo>1)
{
hi = lo - 1;
x = (n+hi-1)/hi;
lo = (n+x-1)/x;
}

We maintain the SUM array and DEN array, for finding the numerator and denominator respectively, as shown in the equation for T above. Initially, for all indices i, SUM[i] = 0 and DEN[i] = 1. These arrays store the change in the values from previous index.

In the table above, B[2] = 10 and B[3] = 7

We store the change as SUM[3] += -3 and DEN[3] *= 10!/7!

After noting all these changes for all the K types of boxes, a linear prefix sum is run on the array SUM, so that SUM[i] now has the desired numerator as shown in equation for T above. Similarly, we run a linear prefix product on the array DEN, so that DEN[i] has the desired denominator as shown in equation for T above. A similar approach is used to find the arrays SUM2[] , DEN2[] and ODDCOUNT[] , to find the value of P. Once we have these arrays, each query can be answered in constant time.

TESTER’S SOLUTION

Can be found here

APPROACH

(needs further improvement)

Here we describe the method for counting palindromic strings P and finding the value of T is similar.

Sort the queries at first, such that S1 < S2 < … < S[Q].

Suppose, at first S = 1, and it is increasing.

Let

SUM = sum of count[i]/2 (integer division)

ODD = the number of odd elements of count

FACT = SUM! / (count[1]/2)! / (count[2]/2)! / … / (count[N]/2)! be precalculated.

Then, the answer for S = 1 is FACT if ODD ≤ 1, 0 if ODD ≥ 2.

Let k = ceil(count[i] / j), then when S goes from k-1 to k, the number of boxes corresponding to count[i] will go from j+1 to j.

Precalculate all time of decreasing the number of box, and sort this array.

After that, all we just need to simulate as follows.

When count[i] decreases,

if(count[i] is even)

{

FACT will be multiplied inverse_of(SUM) * count[i]

SUM will be SUM-1

ODD will be ODD+1

count[i] will be count[i]-1

}

else

{

ODD will be ODD-1

count[i] will be count[i]-1

}

  • We will try to explain the tester’s approach with more clarity soon. Feel free to add your own approach till then

3 Likes

This problem can be solved in O(S + Q * sqrt(S)) time, where S is the sum of count[i]. Just note that there are no more than sqrt(2*S) different values of count[i]. So we can store pairs (x, cnt), where x is some integer present in array count and cnt is the count of x in array count. Now we can represent answer as
sum!/Product[x[i]!^cnt[i],1<=i<=len], where len is the total number of different pairs. x[i]!^cnt[i] can be found in O(log(cnt[i])) time. I believe that because of Sum[x[i]*cnt[i],1<=i<=len]=S we have Sum[log(cnt[i]),1<=i<=len] = O(len + log(S)) or something similar. I think it would be better to make constraints like N <= 10^6, sum of counts <= 10^6, number of queries <=10^6. Then such simple solution would not pass and we will have more balanced contest with more challenging hardest problem.

UPD. Forget to mention that I save results for all s in map so when I see s that was before I simply output saved answer. After damians comment I checked what would be if I remove this hack and I also got TLE. So it means that test data are weak :slight_smile: The worst set of counts for such solution is 1,2,3,…,446 and it seems that test data does not contain this test with all different queries.

UPD 2. What is even more fun that my solution is almost the fastest among all solutions though it should get TLE :slight_smile:

3 Likes

Hi coders,

In contest I thought that answer is

sum! / ( 2 * B1! * B2! * … * Bk!)

but I’m wondering how to calculate this. AFAIK modulo is not working with division, so what’s the trick?

Thanks

5 3 12
4
For this test case, B1=ceil(5/4)=2, B2=ceil(3/4)=1, B3=ceil(12/4)=3, so T=(6!/(2! 3!))=60
For this test case, B1=2/2=1, B2=1/2=0, B3=3/2=1, so P=(2!/(1! 1! 0!))=2

So, ans should be (60+2)/2=31, but actual ans is 30. Will anyone clarify this??

Thanks

1 Like

In fact when I got AC with previously described solution I was surprised and quite disappointed since I have already knew how to make it very fast :slight_smile:

Now I will describe improved version of my solution.

Let M = max{count[i] : 1 <= i <= N} and SUM = sum{count[i] : 1 <= i <= N}

During reading values count[i] we can compute for each value 1 <= x <= M the number of occurrences in array count[]. Denote these values by num[x]. Next we can compute values

snum[x] = num[1] + num[2] + ... + num[x]

by the recurrence

snum[0] = 0
snum[x] = snum[x-1] + num[x]

Clearly snum[x] is the total number of values in array count[] that are <= x.

All these preparations take O(N + M) time and O(M) memory. We do not save actual array count[] hence we need only O(M) memory for array snum[].

Of course additionally we need to save all factorials K! modulo MOD = 10^9 + 7 with K up to SUM:

fct[0] = 1;
for (int k = 1; k < SUM; ++k) {
  fct[i] = fct[i-1] * i % MOD;
}

Now consider some value of S for which we need to calculate the number of corresponding strings.
Note that for all values count[i] that lie in the interval (K * S - S, K * S] the number of boxes will be the same and equal to K. Clearly there are snum[K * S] - snum[K * S - S] values count[i] in this interval. Hence the number from the editorial

(SUM_of_B)! / (B[1]! * B[2]! * ... * B[N]!)

is equal to

(SUM_of_B)! / (1!^(snum[S]-snum[0]) * 2!^(snum[2*S]-snum[S]) * ... * L!^(snum[L*S]-snum[(L-1)*S]))

where L = Ceiling[M / S].

Using binary exponentiation method described in editorial for GROWGOLD we can calculate this value in

O(log(snum[S]-snum[0]) + log(snum[2*S]-snum[S]) + ... + log(snum[L*S]-snum[(L-1)*S]))

time, which is formally can be bounded by O(L * log N) but in fact it is much lower. I believe that it is O(L + log(N)). Of course we can use the same approach for calculating palindromic strings.

Now we combine this new method with previously described approach. Namely if len < L then we use old method for S otherwise we should use new method. Recall that len is the total number of different values in array count[].

Now we can even precalculate answers for all S <= M by simple loop through S from 1 to M and applying the best from the two approaches. So for 1 <= S <= M/len we have L > len and we use first method which take O(M/len * (len + log N)) ~ O(M) in all and for M/len < S <= M we use new method which take O(M/(M/len) + M/(M/len+1) + ... + M/M) = O(M * (log M - log (M/len)) = O(M log len))

For S > M answer will be the same as for S = M.

The total complexity is O(SUM + M * log L + Q) if we use fast precalc of factorials and inverse factorials from here. The term M * log L is unproved.

I think with this solution we could safely replace 10^5 to 10^6 everywhere in the constraints with almost saving the time limit.

3 Likes

Got TLE using this approach :slight_smile:

I did not implement this approach because i thought i would get TLE. :slight_smile:
Now I wonder, what was the motive behind keeping sum(c[i]) <= 10 ^ 5 ?

I tried with N = 10^6, and just filling the arrays factorial[1…N] and invFactorial[1…N] as a preprocessing step takes a lot of time on codechef server and many just do this preprocessing step. So kept it at 10^5 finally.

1 Like

You will be glad to know, that to find (A/B) % Mod, where Mod is Prime, you can find ((A%Mod)*((B^(Mod-2))%Mod))%Mod. Both are same.(proved by application to Fermat’s Little Theorem)

4 Likes
"B1=2/2=1, B2=1/2=0, B3=3/2=1, so P=(2!/(1! 1! 0!))=2 "

You don’t need to calculate this in this case.
Since, B2=1 and B3=3 both are odd. You cannot make any palindrome string with more than one particular character being odd.
So,

"B1=2/2=1, B2=1/2=0, B3=3/2=1, so P=(2!/(1! 1! 0!))=2 "
, is not needed here.
That is only needed when number of odd Bi is less than or equal to 1.
1 Like

You can check how I did this this preprocessing here

It took only O(SUM) time. So with this approach 10^6 is possible.
And since it is the hardest problem of the contest it would be fine to require such fast preprocessing from the contestants.

2 Likes

@anton_lunyov, I would be thankful if you could tell me how the inv[] works ?
EDIT: Got it.
Here’s the proof in case someone else want to know:
(P % P) = 0.-----(1)

Let there is some x, writing P as P = x * (P/x) + P%x. (division by x).
now (1) can be re-written as:

(x*(P/x) + P%x) % P = 0.

=> x*(P/x) = - P%x , modulus P.

Now, dividing both sides by x*(P%x).

=> (P/x)*inv(P%x) = -inv(x), modulus P.

What should be (9/4)%11=5 ?