PLMU - Editorial

PROBLEM LINK:

Practice
Contest, div. 1
Contest, div. 2

Author: Vivek Chauhan
Tester: Ildar Gainullin
Editorialist: Oleksandr Kulkov

DIFFICULTY:
CAKEWALK
PREREQUISITES:
None
PROBLEM:
You’re given a sequence A_1, \dots, A_n. Find the number of pairs (i,j) such that A_i + A_j = A_i \cdot A_j.
QUICK EXPLANATION:
Keep an eye on twos and zeros.
EXPLANATION:
We may rewrite it as A_i=A_j(A_i-1), or A_j = \frac{A_i}{A_i-1}. Since A_j is integer it’s only possible when either A_i=A_j=2 or A_i=A_j=0, so we just have to calculate amount of occurences of 0's and 2's in the sequence.

void solve() {
	int n;
	cin >> n;
	map<int, int> cnt;
	for(int i = 0; i < n; i++) {
		int ai;
		cin >> ai;
		cnt[ai]++;
	}
	cout << cnt[0] * (cnt[0] - 1) / 2 + cnt[2] * (cnt[2] - 1) / 2 << endl;
}

AUTHOR’S AND TESTER’S SOLUTIONS:
Tester’s solution can be found here.
Editorialist’s solution can be found here.

@vivek_1998299 , can you please explain why we use n*(n-1)/2

nC2 = n*(n-1)/2 , is the number of ways to select 2 objects from n objects.

3 Likes

image

I just found this pattern and derived that formula.

1 Like

can you please explain the derivation…@manjot1151

formula of sum of first n natural number !! trying to find all possibilities !!

The positives are 1+2+3+...n and negatives are -1-1-1... n times. So you can say its the sum of all positives from 1 to n and n*-1 or -n. There is a formula for sum of integers from 1 to n that is n*(n+1)/2 So now if you subtract n from it. It will become
n*(n-1)/2 and you have to do it for both 0 and 2 and then add both

@suyashs52
\LARGE^{n}\textrm{C}_{2} = \frac{n!}{2!(n-2)!} = \frac{n(n-1){\color{Red} (n-2)!}}{2{\color{Red} (n-2)!}} = \frac{n(n-1)}{2}

This worked for you?
i did same in my code it was giving SIGFPE
pair+=(fact(c0)/(2*fact(c0-2))); // c0 is the count of number of zeros

consider the case where c0=0 means no zero present then in denominator fact(c0-2) becomes fact(-2) . same error will occur for c0 =1 .Have you handled these cases ?
Just guess the error . If it is not the reason then post you code or submission link.

1 Like

https://www.codechef.com/viewsolution/28192830
sorry for the delay

here in this question value of N≤40,000. Now assume that all are zero.In that senario is int capable of storing 400000! ? No lt can’t.Even long long is not capable of storing that huge value. So use the formula nC2 = n*(n-1)/2. In line no 19 change data type of ans[t] from int to long long and update the line no 42 to 50 as follows

long long pair=0;
if(c0>1)
		{
			pair+=(long long) (c0*(c0-1))/2;
		}
		if(c1>1)
		{
			pair+=(long long) (c1*(c1-1))/2;
		}

N.B-You can also change the data type of c0,c1 as long long in that case you don’t need the type casting.

1 Like