PROSUM - Editorial

cakewalk
editorial
march14
simple-math

#1

PROBLEM LINK:

Practice
Contest

Author: Vivek Hamirwasia
Tester: Mahbubul Hasan
Editorialist: Jingbo Shang

DIFFICULTY:

Cakewalk

PREREQUISITES:

Simple Math

PROBLEM:

Given a sequence of numbers A[1…N], find the number of pairs of i, j (i < j), such that A* * A[j] > A* + A[j].

EXPLANATION:

This problem is similar to this one occurred in OCT Long 2013. It is easy to find that if both A* and A[j] are greater than or equal to 2, the inequality A* * A[j] > A* + A[j] always holds. It is worth noting that, if any one of A* and A[j] is 0 or 1, the inequality will never hold. It is also not held for both numbers are 2.

Denote C2 as the number of 2s in the given array. And C is the number of numbers which are greater than 2.

As analyzed before, the answer is C2 * C + C * (C - 1) / 2.

AUTHOR’S AND TESTER’S SOLUTIONS:

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


#2

"It is easy to find that if both A and A[j] are greater than or equal to 2, the inequality A * A[j] > A + A[j]** always holds."* - What if both A* and A[j] are equal to 2?
I think the solution should count the numbers of 2s and count those greater than 2, then supposing C2 is the count of 2s and C is the count of numbers greater than 2 the solution would then be: C * C2 + C * (C - 1) / 2.


#3

I hope there is a test case

3
100000
0 0 0 ...
100000
1 1 1 ...
100000
2 2 2 ...

:smiley:


#4

I can’t submit my solution for this problem. The algorithm I applied was to store the number of elements >=2 in a variable c and then calculate all distinct pairs using the formula c*(c-1)/2 and then subtract the number of (2,2) pairs from them.So the final formula will be c*(c-1)/2-c2*(c2-1)/2. In theory, it sounds as good as the above mentioned solution and my code gives correct output for dozens of test cases I have tried but still no AC. Can anyone point out the error ?


#5

Well I used the following code and its giving me wrong answer. Can anyone tell me why.

 #include<stdio.h>            
 int main(){
    	int c, res, n0, n1, n2, no, tot, n, i, t, j, n22, n10o, n11, n00, n10;
        for(i=!scanf("%d", &t);i<t;i++) {
        	for(j=!scanf("%d", &n);j<n;j++) {
        		scanf("%d", &c);
        		if(c==0) n0++;
        		if(c==1) n1++;
        		if(c==2) n2++;
        	}
        	n22=((n2-1)*n2)/2;
        	n10o= (n1+n0)*(n-n0-n1);
        	n11=((n1-1)*n1)/2;
        	n00=((n0-1)*n0)/2;
        	n10=n0*n1;
        	tot=((n-1)*n)/2;
        	res=tot-n22-n10o-n11-n00-n10;
        	printf("%d

",res);
}
return 0;
}


#6

Getting WA ?
http://www.codechef.com/viewsolution/3619770


#7

good question of Mathematics :slight_smile:


#8

Can Anyone please tell me what is wrong with this code? I have tried a lot of test cases but I am unable to find the one which is responsible for giving me WA

#include<stdio.h>
#include<stdlib.h>
long long int input()
{
  long long int n = 0;
  int ch;
  ch = getchar_unlocked();
  while(ch >= '0' && ch <= '9')
    {
      n = (n << 3) + (n << 1) + (ch - '0');
      ch = getchar_unlocked();
    }
  return n;
}
int main()
{
  long long int t;
  t = input();
  while(t--)
    {
      long long int n, count = 0, temp = 0, greater_2 = 0, equal_2 = 0, i;
      n = input();
      for(i = 0; i < n; i++)
	{
	  temp = input();
	  if(temp == 2)
	    {
	      count = count + greater_2;
	      equal_2++;
	    }
	  else if(temp > 2)
	    {
	      count = count + greater_2 + equal_2;
	      greater_2++;
	    }	  
	}
      printf("%lld

",count);
}
return 0;
}


#9

I think, this will give you better understanding of the problem. See my solution…
http://www.codechef.com/viewsolution/3563346


#10

could anyone please tell me tha whay we need to use, long long int, for c2(count of 2) and c9count of numbers greater than 2)


#11

I don’t have enough karma to ask a question. Guys help me please.


#12

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define REP(i, N) FOR(i, 0, N)
#define RREP(i, N) RFOR(i, N, 0)
#define FILL(A,value) memset(A,value,sizeof(A))

#define all(V) V.begin(), V.end()
#define sz(V) (int)V.size()
#define pb push_back
#define mp make_pair
#define pi 3.14159265358979

typedef long long ll;
typedef unsigned long long ull;
typedef vector VI;
typedef pair <int, int> PII;

const int INF = 2000000000;
const int MAX = 1000777;
const int MAX2 = 2007;
const int BASE = 1000000000;

int main()
{
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
VI arr;
REP(i,n)
{
int a;
cin>>a;
arr.pb(a);
}
int ones=0,zeroes=0;
REP(i,n)
{
if(arr* == 1)
ones++;
if(arr* == 0)
zeroes++;
}
ll sum1=0;
ll num = ones+zeroes;
for(int i=1;i<=num;i++)
{
sum1 += (n-i);
}

    ll k = (n*(n-1))/2 - (sum1);
    // if(k<=0)
    //     cout<<0<<endl;
    // else
        cout<<k<<endl;
}

}

can someone tell why im getting WA with this logic ??

Thanks !! :slight_smile:


#13

@brijwasi1995 This test case is giving your problem dear.

1
3
2 2 2

Here, your code is giving output of 3 but correct output is 0. See that 2x2= 2+2 and the condition of a* x a[j] being STRICTLY GREATER does not hold.

That’s why you are asked to count number of element equal to 2, number of elements greater than 2 and apply Permutation and combination logic to derive the answer, which is given in formula. Ping me in case of doubt :slight_smile:


#14

Am I missing something??

import java.util.;
import java.io.
;
class Sol
{
public static void main(String args[])throws IOException
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st,st1,st2;
String s2=br.readLine();
st2=new StringTokenizer(s2);
int t=Integer.parseInt(st2.nextToken());
while(t-- > 0)
{
String s1=br.readLine();
st1=new StringTokenizer(s1);
int n=Integer.parseInt(st1.nextToken());
int GT2=0;
int twos=0;
String s=br.readLine();
st=new StringTokenizer(s);
for(int i=0;i<n;i++)
{
int x=Integer.parseInt(st.nextToken());
if(x==2)
twos++;
if(x>2)
GT2++;
}
long ans=(GT2*(GT2-1))/2+GT2*twos;
System.out.println(ans);
}
}
}


#15

Can anyone prove me mathematically why do we need to add (number of 2’s)(number of elements greater than 2)
to (c
(c-1)/2). Hope you do prove mathematically??


#16

Take all the elements in array =2 of any size…Inequality never holds true yet we get some finite answer…


#17

Denote C0 as the number of 0s in the given array. And C1 is the number of 1s. C2 is the number of numbers which are greater than or equal to 2. As analyzed before, the answer is C2 * (C2 - 1) / 2.

I think this part of editorial is wrong. Say, array = {2, 2, 2, 2, 2}.
C1 = 0, C2 = 5. The answer is not 10 but 0.


#18

Didn’t see your comments before I posted my answer.


#19

Oh sorry, my mistake. I treat the problem as >=. I will modify it now. Thanks!


#20

Oh sorry, my mistake. I treat the problem as >=. I will modify it now. Thanks!