PROSUM - Editorial

editorial
, , ,
21

well two * x is correct , answer is coming from that . here two denotes count of 2 and x denotes count of numbers greater than 2 . So he is two * x counts the combination of 2’s with numbers greater than 2 . then he adds x*(x-1) to this for other combinations of numbers greater than 2 . So i think that is correct .

22

got it thanks for help …
Missed a question in challenge.

23

@rishabh1994: I refered to two * x for technical problem - int overflow, not logical bug… @pardeep_gill was aware of that problem (((long long)x*(x-1)), but forgot to handle it in all places see here - http://ideone.com/ywYmic also using long long for variables is correct answer, my comment was an addition - another possible approach…

24

what is wrong with this code??? Its giving wrong answer…

#include<stdio.h>
void main()
{
int t;
long long int s,n=0,ctr=0,ctr1=0,tot=0;
scanf("%d",&t);
while(t–)
{
scanf("%lld",&s);
ctr=0;ctr1=0;
while(s–)
{
scanf("%lld",&n);
if(n>2)
ctr++;
else if(n==2)
ctr1++;
}
tot=ctr*(ctr1+((ctr-1)/2));
printf("%lld\n",tot);
}
}

25

good question of Mathematics :slight_smile:

26

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;
}
27

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

28

Thanks for the solution…But I have seen that formula in almost every solution…can you please tell me what is wrong with my solution or can you please provide the test case where my solution fails?

29

Your logic has some minor mistake, because for
Input :
1
5
1000000 0 9999 100 10 1000000
Output:
6

But your code gives answer as 3, which is wrong. So, better check for extreme limits of given constraints.

30

Its always better to check for constraints of the problem, before writing the code ! :slight_smile:

31

Thanks for the help but for your given test case my above code is also giving answer as 6!

32

Try using scanf().

33

declare the variables as unsigned long long .Here is the link to the corrected code http://www.codechef.com/viewsolution/3619806 . This may help you.

34

Finally! Thanks vikascingh…After using scanf() my code was accepted immediately…here is the link…but What was the problem with getchar_unlocked()?

35

Its my pleasure !! :wink:

36

getchar_unlocked() may be having some problem, if we read the large input. I am not sure of this !

37

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)

38

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

39

#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
40

@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