CNPIIM - Editorial

[darkshadows]

PROBLEM LINK:

Practice
Contest

Author: Bruno Oliveira
Tester: Shiplu Hawlader and Mahbubul Hasan
Editorialist: Lalit Kundu

DIFFICULTY:

EASY

PREREQUISITES:

Number Theory

PROBLEM:

Find number of 2X2 matrices such that trace=N (N<=2500) and determinant is greater than zero.

EXPLANATION:

Let matrix A=
[ a b ]
[ c d ]

So, a + d = N and a * d > b * c. (From definition of trace and determinant).
We traverse over all possible values of a (ie. from 1 to N-1) to find the solution.

So,

ans=0     
for i=1 to N-1:   
    a=i    
    d=N-i     
    ans += number of pairs b,c such that b*c <= (a*d) -1   
print ans    

So, our problem now is given a P, find number of ordered pairs (since [a1,b1] and [b1,a1] will be counted as different because matrix will be different) A,B such that A * B <= P.
Our solution for above problem can be written as:

sum [over B=1 to P] number of multiples of B less than P+1

The above sum can be written as

summation [B=1 to P] { ⌊ P/B ⌋ }

At this point a very handy fact comes to our rescue.

The sequence ⌊ P/i ⌋ has at most 2 * √P distinct values.

This is because for i > √P, ⌊ P/i ⌋ < √P. Therefore for i = √P + 1 to P, it has only √P distinct values.

The above fact can be used to our advantage. We can sum up the series by summing up, for each distinct value in the sequence, its number of occurrences.

⌊ P/i ⌋ = K
⇒ K ≤ P/i < K+1
⇒ P/(K+1) < i ≤ P/K
⇒ ⌊ P/(K+1) ⌋ < i ≤ ⌊ P/K ⌋

Here is the code to find number of ordered pairs A,B such that A * B <= P.

 sum = 0
 K = P
 imin = 1
 while imin ≤ P
     imax = ⌊ P/K ⌋
     sum += K*(imax - imin + 1)
     imin = imax + 1
     K = P/imin
 print sum

So, overall complexity would be N*√P ie. N*N.

Reference taken from COOLGUYS editorial

AUTHOR’S AND TESTER’S SOLUTIONS:

To be updated soon.

[theshubhamgoel]

Explain in some more detail how u calculate no of order pair

[bibip]

I just calculate all possible multiplication first, then save it in array

like this :

int MAK = 2500 * 2500;
long total[] = new long[MAK + 1];
for (int i = 1; i <= MAK; i++) {
for (int j = i; j <= MAK; j+=i) {
total[j]++;
}
}

for (int i = 1; i <= MAK; i++) {
total[i] += total[i - 1];
}


then get the result :
 for (int i = 1; i < n; i++) {
int b = n - i;
int c = b * i;
 
ou += total[c - 1];
}

http://www.codechef.com/viewsolution/3752329

[shivamtiwari93]

for N = 4, there are 11 possible matrices. However, I can identify only 9 of them. (in form of abcd) : 1123, 1213, 1113, 3121, 3211, 3111, 2122, 2212, 2112. Please help me find other 2 matrices!

[haccks]

I solved this question in the following way:
Take an example first; N = 8. A 2x2 matrix have determinant greater than 0 if and only if A₁₁xA₂₂ > A₁₂xA₂₁, where A_ij is the element of the determinant and i, j = 1, 2 and A₁₁ + A₂₂ = N. Now we need to find all the pairs of A₁₁ and A₂₂ and corresponding to it all the pairs of A₁₂ and A₂₁ such that the above condition get satisfied. The pairs A₁₁ and A₂₂ for N = 8 are
1 7 | 7 1
2 6 | 6 2
3 5 | 5 3
4 4
Total pairs = 7. It is clear that For each of A₁₁ != A₂₂, there exist two pairs and same goes for A₁₂ and A₂₂. So, we need to find all the pairs for A₁₂ and A₂₁ corresponding to each pair of A₁₁ and A₂₂. It can be observed that all the pairs of antidiagonal are same for both pair (ex: 7 1 and 1 7) of main diagonal, hence we could optimize our calculation to N/2 by calculating pairs for any one of them and then multiply it by 2. For more clarity, I am explaining it further:
For pair 1 7 anti diagonal pairs are

1 1 1 2 1 3 1 4 1 5 1 6 | Sub total = 6*2 - 1 = 11
2 2 2 3 | Sub total = 2*2 - 1 = 3
. Total = 14
Now double it for both of 1 7 and 7 1: 14*2 = 28—> all the matrices having pair 1 7 and 7 1 as main diagonal. Similarly you can find number of matrices for 2 6 and 6 2, 3 5 and 5 3 is equal to 2*(21+7+1) = 58, 2*(27+11+3) = 82 respectively. Now when calculating for pair 4 4, keep in mind that you do not have to double the total (as I explained above, why ? ), which is 45!
Total number of matrices = 28 + 58 + 82 + 45 = 213.

Here is my C program implementing the above algorithm.
Feel free to ask if you find any difficulties in this algorithm :).

---

EDIT: While answering this I thought no need to explain about the mathematics behind it and assumed that readers will figure it out themselves, but I was wrong!
See the mathematics behind calculation of number of order pairs:

Let the final answer for a test case be total and the partial answer for each of main diagonal pair is Sub_total. Let x = i and y = N-i, where i = 1, 2, ...., N/2, such that x+y = N.
First we need to find total number of antidiagnol pairs for each of diagonal pair. To do this, if we divide x*y by A₁₂ and subtract A₁₂-1 from it then we will get the total number of antidiagonal order pairs with that particular i, let it be stored in count. Keep in mind that you need to consider the even and odd behavior of x*y. See the further explanation for more clarity:

For the above example, N = 8, taking x = 4 and y = 8-4 = 4. Here i = 4. Now for A₁₂ = 1, dividing x*y = 16 by A₁₂ , i.e by 1 we will get 16 and store it in count ( count = x*y/A₁₂ - (A₁₂ - 1) ). So the number of order pairs for A₁₂ = 1 is 16 and if we calculate them manually, they are

1 1 1 2 1 3 1 4 ..... 1 14 1 15 1 16
But notice that we need to exclude the pair 1 16 as 1*16 = 16 = 4*4 and it will make the determinant of matrix to 0. This problem comes only with even x*y. So, for each of even x*y we need to decrement count by 1 (count--). By this, we have now 15 order pairs. Now just double it (2*count) for A₂₁ = 1 (no need to calculate again!!). After that we will get 30, but here keep in mind that 1 1 is repeated twice, so again we have to decrement our 2*count by 1 and finally we will get 29, store it in sub_total (sub_total = 2*count - 1).
Now similarly for A₁₂ = 2, x*y/2 = 8 we will get sub_total = 2*6 - 1 = 11. Here we need to exclude the pairs

• 2 1, as it has already been counted in our previous calculation, and this will be done by and the sub-expression A₁₂ - 1 in count = x*y/A₁₂ - (A₁₂ - 1).
• 2 8, as it is equals to 4*4, and this will be done by the expression count-- for even x*y.
• one of 2 2 pair, as it is considered twice, and will be done by sub_total = 2*count - 1.

Repeat this util you get a A₁₂ such that A₁₂*A₁₂ >= N. In this case A₁₂ = 4.
Now double the sub_total if x != y and print the total.

[kenden23]

An easy problem, which just toke me so long time. And I think the editorial didn’t give an explicit explanation.
It would be nice to elaborate the math behind this problem.
Anyway, I use the formula to solve this question, but I still not quite get how to deduct this formula.

[tukku26]

Amazing question! Reduction of a step from O(N) → O(sqrt(N)) complexity was a bit tricky to realize though!
Here’s how i did it for step of finding all pairs(x,y) : x*y < Prod
( Additionally understand Sieve of Eratosthenes so as to how complexity reduction happened )
for a product P lets suppose P=10
we have following pairs valid:
1,1 1,2 1,3 … 1,9

2,1 2,2 2,3 2,4

3,1 3,2 3,3

4,1 4,2

5,1

6,1

7,1

8,1

9,1

now if we use all values in range [1,sqrt(N)]:

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

2,1 2,2 2,3 2,4

3,1 3,2 3,3

now we reverse each pair (x,y) in the above to generate all distinct pairs with some repetitions…
Now we remove repetitions:

1- First of all remove all occurrence of (i,i) once from the final count
2- Second for a particular row lets say row 3

3,1 3,2 3,3 3,4 3,5 … 3,n

we have 3,1 3,2 already repeating already in row 1 and row 2 and hence we need to remove this count as well.
For rest left over count multiply by 2 since we need ordered pairs.

Additionally i used hash map to store previously calculated values to avoid repetitive calculations
Here’s the code for the technique. O(Nsqrt(N)) for each query:
http://www.codechef.com/viewsolution/3791652

Thanks darkshadows for the question.

[abcdexter24]

I found out the solutions using brute force code. Then simulated for about 14 hours using file handling and stored and in an array…
And then ACd answer AC with O(1) time complexity and O(N) space…

[midhul]

The complexity should be O(Nsqrt§) which is in the worst case equal to O(nn) since P is at most of order N^2

[darkshadows]

Yes, correct. Good observation.

[vikrant1433]

What is the intuition behind this solution? kindly explain.

[bibip]

first we need to know the total number of pair that the product of them is x

it is generated by

for (int i = 1; i <= MAK; i++) {
for (int j = i; j <= MAK; j+=i) {
total[j]++;
}
}
which is equal to
for (int i = 1; i <= MAK; i++) {
for (int j = 1; j*i <= MAK; j++) {
total[i * j]++;
}
}
this is the simulation if the maximal is multiplication is 4 
total[1 * 1]++;
total[1 * 2]++;
total[1 * 3]++;
total[1 * 4]++;
total[2 * 1]++;
total[2 * 2]++;
total[3 * 1]++;
total[4 * 1]++;

now we know, total[4] = 3, total[3] = 2, total[2] = 2, total[1] = 1

[bibip]

but, if we want to know the number of pairs that <= 4, we must sum from 1 to 4

we pre-calculate them again, by adding all of them by their previous value

for (int i = 1; i <= MAK; i++) {
total[i] += total[i - 1];
}
then, if we want all possible pair that's less than A*B, we just need to call total[A*B-1]

[hitesh091]

I had similar approach but was giving tle. Btw, thanks for the insight.

[rhlc92]

two more… 2132 2312

[rhlc92]

i used the same approach and got tle… CodeChef: Practical coding for everyone
i tried optimizing further and calculated only till i=n/2 as value for i*(n-i) would be same as value for (n-i)*i… but still got tle… CodeChef: Practical coding for everyone

[garakchy]

@haccks, bro i used same approach and couldnt get AC: CodeChef: Practical coding for everyone. dont know why.

[haccks]

Your approach is right but you need to remove the inner loop for(int c=1; b*c<a*d; c++) cnt++; to reduce the time complexity.
I have edited your code. See the changes. Now you can submit it :).

[garakchy]

@haccks, tnx bro. but i didnt get the idea. cnt = ad/b - (b-1); and when ad % b = 0 you deduct cnt–; partial answer: part_ans += 2cnt - 1 and you stop the loop when (b+1)(b+1) >= a*d; can you explain the idea pls.

[haccks]

@garakchy, Edited my answer. See the edit. I tried my best and hope you will get this time