zco 2013 tournament

general
,
1

I am new .Solved some easy problems. My algorithm for this question is not working.
the question is

Tournament

N teams participate in a league cricket tournament on Mars, where each pair of distinct teams plays each other exactly once. Thus, there are a total of (N × (N-1))/2 matches. An expert has assigned a strength to each team, a positive integer. Strangely, the Martian crowds love one-sided matches and the advertising revenue earned from a match is the absolute value of the difference between the strengths of the two matches. Given the strengths of the N teams, find the total advertising revenue earned from all the matches.

Input format
Line 1 : A single integer, N.
Line 2 : N space-separated integers, the strengths of the N teams.

Output format
A single integer, the total advertising revenue from the tournament.

Sample input
4

3 10 3 5

Sample output

23

1 Like
2

Let me describe my algorithm which got me an AC after 3 TLEs.

What exactly we are doing in this problem is: For all combinations of pairs of elements, we are adding up the absolute values of the differences between the elements of the pair. i.e. Consider the sample input

3 10 3 5

Ans (Take only absolute values) = (3-10) + (3-3) + (3-5) + (10-3) + (10-5) + (3-5) = 7 + 0 + 2 + 7 + 5 + 2 = 23

Notice that I have fixed 3, iterated through the remaining elements, found the differences and added them to Ans, then fixed 10, iterated through the remaining elements and so on till the last element

Unfortunately, N(N-1)/2 iterations are required for the above procedure, which wouldn’t be ok for the time limit.

Could we better it?

Let’s sort the array and repeat this procedure. After sorting, the sample input is now
3 3 5 10

Let’s start by fixing the greatest element, 10 and iterating through the array like how we did before (of course, the time complexity is the same)

Ans = (10-3) + (10-3) + (10-5) + (5-3) + (5-3) + (3-3) = 7 + 7 + 5 + 2 + 2 = 23

We could rearrange the above as

Ans = (10)(3)-(3+3+5) + 5(2) - (3+3) + 3(1) - (3)

Notice a pattern? Let’s generalize it.

Suppose we have an array of strengths arr[N] of size N indexed from 0

Ans = (arr[N-1])(N-1) - (arr[0] + arr[1] + … + arr[N-2]) + (arr[N-2])(N-2) - (arr[0] + arr[1] + arr[N-3]) + (arr[N-3])(N-3) - (arr[0] + arr[1] + arr[N-4]) + … and so on

Right. So let’s put this new idea to work. We’ll introduce a ‘sum’ variable. Some basic DP to the rescue.

For i=0 to N-1

sum = sum + arr[i]

Ans = Ans + (arr[i+1]*(i+1)-sum)

That’s it, you just have to sort the array and iterate only once through it. Excluding the sorting part, it’s down to N iterations from N(N-1)/2, I suppose that’s called O(N) time EDIT: That is O(N log N) time overall

Hope it helped!

2 Likes
3

The time complexity is O(N log N) becuase sorting takes N log N.

4

Sorry, I am bad with these notations. I have edited it now.

5

Can anyone say what is wrong with my solution?

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define MAXN 200000
using namespace std;
long long arr[MAXN],sum[MAXN];
int main(){
long long n,s=0,su=0,diff;
scanf("%lld",&n);
for(long long i=n-1;i>=0;i--)
    scanf("%lld",&arr[i]);
for(long long i=0;i<n;i++){
    su+=arr[i];
    sum[i]=su;
}
for(long long i=n-1;i>0;i--){
    diff=(arr[i]*i)-(sum[i-1]);
    s+=(diff<0)?-diff:diff;
}
printf("%lld",s);
return 0;
}
6

swagatochatt do u need so many long long’s? Just use int’s dude

7

Here is my code for this problem.

8

What is wrong with my code?
getting wrong answer in task #4 and #5

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

help please

9

@akash_sharma27

Try putting your code in “<>” of “pre<>” command.

Eg-

      import java.util.; 
    ``class tournament { public static void main(String args[]) 
    {
     Scanner sc=new Scanner(System.in); 
    int n=sc.nextInt(); 
    int team[]=new int[n]; 
    for(int i=0;i<n;i++) 
    {team[i]="sc.nextInt();}"
     int="" rev="0,k=n-1;" 
    arrays.sort(team);="" 
    for(int="" i="n-1;i">=0;i--)
`` { rev=rev+(team[i]k);
 k-=2; } 
    System.out.println(rev); 
`}
`
 }

I cant get what you did in your code (comments/approach used would had been appreciated) but I can help you on how to do it (Your submission link is giving “Access Denied” )

Firstly, the answer is the sum of absolute value of strength difference in all matches.

Hence-

pre<`for(i=0;i<n-1;i++)
{
    for(j=i+1;j<n;j++)
    {
        ans += abs(a[i]-a[j]);/*This should give the ABSOLUTE difference of all strength and add it*/
    }
}>

What I suspect is that you didn’t check for difference being negative in your code. Either that, or suffered from overflow (not sure, cause I cant see constraints of the Q)

10

@vijju123 thank you for helping…i just changed the data type from int to long and it passed all the cases.

11

Ahh so it was a case of overflow (I said it in last line. I didn’t know the constraints so wasn’t sure tho. But m glad you were able to solve the problem!! :slight_smile: )

12

Borrowing from @sandy999’s answer,

Ans = (arr[N-1])(N-1) - (arr[0] + arr[1] + … + arr[N-2]) + (arr[N-2])(N-2) - (arr[0] + arr[1] + arr[N-3]) + (arr[N-3])(N-3) - (arr[0] + arr[1] + arr[N-4]) + … and so on …(1)

can be used as it is without any implementation of DP in O(n) time.

Let 3 10 5 3 be your test case.
sort it in ascending order to get arr = 3 3 5 10.

After that make a prefix sum array which will be stated as : 3 6 11 21

Now, the answer is simply :

for i in range(n-1, 0, -1):
    s += (arr[i]*i) - prefix[i-1]

which happens to be a simple implementation of the above formula (1) and uses a single pass through the sorted array