PROSUM - Editorial

editorial
, , , ,
29

problem is in two*x…

30

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 .

31

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

32

@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 - ywYmic - Online C++ Compiler & Debugging Tool - Ideone.com also using long long for variables is correct answer, my comment was an addition - another possible approach…

33

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

34

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?

35

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.

36

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

37

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

38

Try using scanf().

39

declare the variables as unsigned long long .Here is the link to the corrected code CodeChef: Practical coding for everyone . This may help you.

40

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

41

Its my pleasure !! :wink:

42

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

43

still getting WA with this :-

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 twoes=0,others=0;
REP(i,n)
{
if(arr[i] == 2)
twoes++;
if(arr[i] > 2)
others++;
}
ll ans = twoesothers1LL;
ans += (1LLothers(others-1))/2;
cout<<ans<<endl;
}
}

44

Can you provide a code without defines, or the full code with defines you used? I am not able to get “ll ans = twoesothers1LL; ans += (1LLothers(others-1))/2” Is multiplication going on here? You should store twoes and others as long long int, as overflow will occur. (Try changing data type of twoes and others to long long int)

45

https://www.codechef.com/viewsolution/13198472

47

https://www.codechef.com/viewsolution/33104731

please someone help me with this.
why this code is wrong?

48

Assume A[i]==2 , then if you put this in the given condition , then we will have A[ j]>2.
Therefore , we count the number of Two’s and numbers greater than 2. For every ‘2’ in the array, we need an element greater than 2.

49

Some one help me find where am I failing …

#include <bits/stdc++.h>

#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define sp ' '
#define nl '\n'
#define ll long long
#define ull unsigned long long
#define all(v) v.begin(),v.end()
#define vi vector<int>
#define range(a , min , max) a >= min and a <= max

using namespace std;

void solve() {
    ull n;
    cin >> n;
    
    vector<int> v(n);
    for(auto &it : v)
        cin >> it;
        
    ull cnt = 0;
    ull ans = (n * (n - 1)) / 2;
    
    for(int i = 1; i <= n; i ++) {
        if (v[i - 1] == 0 || v[i - 1] == 1) {
            ans -= (n - i);
        }
        
        if (v[i - 1] == 2)
            cnt ++;
    }
    
    if (cnt > 0)
        ans -= (cnt * (cnt - 1)) / 2;
    
    cout << ans << nl;
}

int main() {
    int tc;
    cin >> tc;
    while(tc--) {
        solve();
	}

    return 0;
}