PROSUM - Editorial

editorial
, , , ,
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\n",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)

1 Like
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[i] == 1)
ones++;
if(arr[i] == 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:

1 Like
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[I] 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:

4 Likes
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…

1 Like
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.

1 Like
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!

2 Likes
21

try to replace long int i,count,a,c; with long long int i,count,a,c; …

22

But your description is different to what is your last submission - CodeChef: Practical coding for everyone

23

Please edit your code or add a link to submission (hopefully with better formatting).

Did you noticed that n*n will lead to int overflow for n up to 10^5 ?

24

Sorry to have mislead you. What I have done is I calculated the 1’s and 0’s in c. Then I reduced n(the total no. of elements) by c.So,now n is the total no. of elements >=2. And count is the number of 2’s. Then i applied the formula n*(n-1)/2 - count*(count-1)/2. Also, replacing by long long int didn’t work.

25

Maybe I did something wrong, but your last submission is not working at all - bvezTB - Online C++ Compiler & Debugging Tool - Ideone.com

26

there was scanf("%ld",&a);, I replaced it with scanf("%lld",&a); …

27

Ok. The above got AC.But why would they need to be declared as long long int. Wouldn’t they get converted automatically when n is formulated ?