Need Help!

help
, ,
1

I am solving this question

but i am getting accepted in task 0 only and wrong verdict in other cases
Logic

suppose we have 4 elements
3 10 3 5
here first team will play with 2,3,4 teams
so total revenue will be the absolute difference between the strengths of two teams playing the matches .

so i took suffix sum
21 18 8 5
now as first team will play with next 3 teams suppose we want revenue zero then among all others teams each team should have score 3 and so 9 for 3 teams but from suffix sum
tells that score by next 3 teams is 18 .
In this revenue will be abs(18-9) == 9
same for others

This works in O(N) .
Can anyone tell me why i am getting wrong ans ??

Here’s is my code :

vi a , suffix ;

void Go () {
    int n = 0 ;
    cin >> n ;

    a.assign(n,0) ;
    suffix.assign(n,0) ;

    for ( int i = 0 ; i < n ; i++ ) {
        cin >> a[i] ;
        suffix[i] = a[i] ;
    }

    for ( int i = n-2 ; i >= 0 ; i-- ) {
        suffix[i] += suffix[i+1] ;
    }

    int ans = 0 ;
    for ( int i = 0 ; i < n-1 ; i++ ) {
        int expected = a[i]*(n-i-1) ;
        int have = suffix[i+1] ;
        ans += abs(have-expected) ;
    }
    cout << ans << Endl ;
}
2

There are 2 major problems in your code.

  1. You are not sorting the list. Your logic is correct when either the data is sorted( in any fashion). This is because this piece of code abs(have - expected) only works when either the have is always smaller or equal to expected (or vice versa depending on how you traverse or sort).
  1. You are using int to store the answer when the answer can be bigger than INT_MAX.

I used the below logic to solve this question

\large f(n) = \large f(n-1) + \large (n-1) \large \times \large a_{i} \large - \large prefixsum(i-1)

Your logic is almost the same ( except in the direction of traversal).
This logic only works when I know that (n-1)*a_{i} is actually greater than or equal to prefixsum(i-1)

The reason the direction of traversal is irrelevant is that you are finally taking absolute.

1 Like
3

I didn’t got your first point . Can you please elaborate more ?

According to me .
let say we have 2 teams having scores
5 1
here first team plays with second team has same meaning as that of second team plays with first so why order should matter ?
As we are taking absolute value then order should not matter , isn’t it ?

second point is ok as i have defined my int as long long in my template which i
hadn’t printed here .