THREEDIF - Editorial

PROBLEM LINK:

Practice
Contest

Author: Anton Lunyov
Tester: Hiroto Sekido
Editorialist: Anton Lunyov

DIFFICULTY:

SIMPLE

PREREQUISITES:

Rule of product in combinatorics, Modulo operation

PROBLEM:

You are given 3 positive integers N1, N2, N3 up to 1018 and need to count the number of triples (X1, X2, X3) such that 1 ≤ Xi ≤ Ni for i = 1, 2, 3. You should output the answer modulo 109 + 7.

QUICK EXPLANATION:

By sorting input numbers we can assume that N1 ≤ N2 ≤ N3. Then the answer is N1 * (N2 − 1) * (N3 − 2). Watch out for integer overflows during calculation of this number modulo 109 + 7.

EXPLANATION:

If we sort numbers N1, N2, N3 the answer remains the same. Hence let’s assume that N1 ≤ N2 ≤ N3. Then for X1 we have N1 choices, for X2 we have N2 − 1 choices and for X3 we have N3 − 2 choices. Indeed:

  1. X1 can be any number from 1 to N1, inclusive. There are N1 such numbers :slight_smile:

  2. X2 can be any number from 1 to N2, inclusive, which is not equal to X1. Since X1 ≤ N1 ≤ N2, there are N2 − 1 such numbers (numbers from 1 to N2, inclusive, with excluded X1). Clearly, if N1 = N2 = 1 then the answer is zero since the only choice for X1 and for X2 is 1, so any such triple will have equal numbers.

  3. Finally, if N3 ≥ 2 then X3 can be any number from 1 to N3, inclusive, which is not equal to X1 and X2. Since X1 ≤ N1 ≤ N3, X2 ≤ N2 ≤ N3 and X1 ≠ X2, there are N3 − 2 such numbers (numbers from 1 to N3, inclusive, with excluded X1 and X2).

Now using rule of product in combinatorics we get that the answer is simply the product of N1, N2 − 1 and N3 − 2 as mentioned above. Note that when N2 = 1 this formula also works so we don’t need to handle this case separately.

Probably the trickiest part is to output the answer modulo M = 109 + 7 having numbers Ni up to 1018. There are several things you should notice in order to get AC:

  1. You should use 64-bit integer type to store and input numbers Ni.

  2. When you want to multiply two numbers up to 1018 modulo 109 + 7 you should at first take them modulo 109 + 7 and then do the multiplication using 64-bit integer type. Otherwise the result will be wrong due to overflow. Even such code is wrong
    A % M * B % M
    since you will multiply numbers A % M and B at the second step and this will lead to overflow (A % M is about 1e9 and B is about 1e18, so their product is about 1e27 which does not fit in 64-bit integer type). Such overflow will occur on almost every random test.

  3. Another common mistake is to do like that
    A = N1 % M
    B = (N2 - 1) % M
    C = (N3 - 2) % M
    ans = A * B * C % M
    Here at the final step you multiply three numbers up to about 1e9. Their product could be up to 1e27 which does not fit in 64-bit signed integer. Therefore integer overflow occurs. The correct code would be
    ans = A * B % M * C % M
    Here we take the product A * B modulo M so it becomes smaller than M and at the final step you multiply two numbers up to about 1e9. Their product is up to about 1e18 and fits in 64-bit integer type.

  4. You can’t replace numbers Ni by their residues modulo 109 + 7 before sorting. Indeed, the order of numbers can change after that and you get completely another number as the answer. The reference test is: 2 3 1000000008. Actually it happens often on any large random test.

  5. If after sorting you replace numbers Ni by their residues modulo 109 + 7 and then calculate the answer as
    ans = N1 * (N2 - 1) % M * (N3 - 2) % M
    then your answer could be negative in the end. The reference test is: 1 2 1000000008.
    Hence if you are using this method make the check
    if ans < 0 then ans = ans + M
    after that.

  6. As mentioned one of the ways how to do all properly is to calculate answer as follows
    ans = (N1 % M) * ((N2 - 1) % M) % M * ((N3 - 2) % M) % M
    Note that at first sight this way also could lead to negative answer. But this does not happen here. See comments in tester’s solution for explanation.

Actually, it is easy to see that this solution could be generalized to any number of variables instead of 3. Namely, if we have numbers N[0], N[1], …, N[K-1] and want to count the number of arrays (X[0], X[1], …, X[K-1]) such that 1 ≤ X[i] ≤ N[i] for i = 0, 1, …, K-1, and all X[i] are different, then after sorting numbers N[i] the answer will be the product of N[i] − i for i = 0, 1, …, K-1. See tester’s solution as a reference.

ALTERNATIVE SOLUTION:

The problem could be solved using inclusion-exclusion principle. The formula for the answer in this case is
N1 * N2 * N3 − min{N1, N2} * N3 − min{N2, N3} * N1 − min{N3, N1} * N2 + 2 * min{N1, N2, N3}.
See author’s solution as a reference. It also contains explanatory comments to this formula.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

RELATED PROBLEMS:

Rabbit Numbering - Topcoder SRM 463, Div I, Easy
Pick And Delete - Topcoder SRM 512, Div I, Hard

5 Likes

This is also a related problem, using somewhat similar idea: PickAndDelete.

1 Like

@Anyone: CodeChef: Practical coding for everyone why does this code did not work? I have checked the editorial but cannot make out any reason on why it would give wrong result.

can u plz why my code still give wa --id: 1745871

CodeChef: Practical coding for everyone -
could anyone plz check this code and find whats the error in it?

My doubt is the following :
Just consider the case of 25 12 2012 . If I choose it without sorting, wouldn’t my answer be different ? It would rather be 25 times 11 times 2010 which does not equal 12 times 24 times 2010, which is the answer obtained after sorting ?!

1 Like

Thanks. I have added it.

Hi ! You should take modulo after subtraction. See i just changed this and it’s accepted.
http://www.codechef.com/viewsolution/1726238

1 Like

Thanks anuraganand, got it. Silly mistake.

Read paragraph 4 in editorial after the sentence
“There are several things you should notice in order to get AC:”

It makes sense to sort. For your mentioned example {25 12 2012} , if we take 25.11.2010 , you would certainly miss some cases. For X1 we are taking {1,2,3…24,25}. But for X2 to be valid we need to exclude numbers that occur in X1. But by 25*11 you are including {1,2,3,4,…12} which already occurred in X1.