Posted in C++

ZCO 2013 – Solution : Tournament

The problem statement is described here.

The first impulse would be to calculate all the match revenues and then sum up… but it would be O(n^2) which isn’t good enough for the second subtask.

The key to the problem lies in an observation. Let’s consider an examples and then generalise it.

Let us take a different example than the given sample case.

4

3 10 7 5

Now the revenues for each match are :

10-5 +10-7 + 10-3 + 7-5 + 7-3 + 5-3 = 23

but wait that’s not what we will do… Look at it in the following manner :

10 * (3-0) + 7*(2-1) + 5*(1-2) + 3(0-3)

If you didn’t get the above expression, take all 10’s common in previous expression and similarly for all rest.

Now note that if we sort them the order is : 3 5 7 10

And Indices are                                            0 1 2  3

Thus more formally we may write :

Total revenue = ∑ {strength[i] * ( i – (n-i-1))} = ∑ {strength[i] * (2*i – n +1)}

This can be coded for a O(n+n log(n) ) = O(n log(2n)) solution which is sufficient for our purpose. Be wary that we need to sort the array first before we use the above logic.

Thus you should now be able to code it easily passing both the subtasks.

Happy Coding.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s