Solution for problem Competition

We say competition I(p) is the configuration of winners if we simply insert a 0 between positions p and p + 1 in the array. We compute f(p), the total happiness given competition I(p).

O(N³)

We compute happiness of the competition for each of the N + 1 instances independently, as follows.

Given the array of winners, just keep a list of the people who receive a coin (using a frequency array, storing each person's frequency up to the current day). This list can be updated each day the following way:

• case 1: Someone from the list wins the day. This means he will be the only one to receive a coin on this day. So we can erase all others from the list and just keep him.
• case 2.1: The one who wins has its frequency incremented up the maximum frequency so far, so we just add him into the list.
• case 2.2: The one who wins still has a lower frequency than the maximum one, so the people who receive coin the current day are the same. List does not change.

Each day, after updating the list properly, we can go through the people in the list and add the happiness received from them this day. It is enough to know when was the time each person entered the list (if he entered more than once, we are interested only in the last time he entered the list), so we can keep an array start[x] = the last time x entered the list. We can keep this array by O(1) updates on it each day, treating properly the cases.

Because a² = (a - 1)² + 2a - 1, additional happiness obtained for a person in the a-th day of consecutive coin receiving is 2a - 1. So we can just add 2 * (day - start[x] + 1) - 1 (for each person in the list) and obtain the current total happiness.

This is O(N^3) because we compute the total happiness of some array of winners O(N) times. Each computation requires O(N) days, and on each day we go through all members in the list, and the list may have up to O(N) people.

Note there are easier O(N³) solutions, we showed this one because it is easier to get to the next step with it.

O(N²)

We just optimize the computation for a given situation of the competition. Instead of going through the hole list and add 2 * (day - start[x] + 1) - 1 for each of them, just keep this sum and the list size as two variables. We don't even store the list as an array as before, it will be stored only conceptually. Let's treat the cases: (suppose person x is the winner of the current day)

• case 1: sum = day - start[x]; size = 1;
• case 2.1: start[x] = day; size = size + 1;
• case 2.2: do nothing.

Then just add size to sum. Finally, when we want to add the happiness of the day, just add to our answer 2 * sum - size.

This is clearly O(N^2) because we compute the answer for each of the O(N) configurations of the competition we just go along the O(N) days and make some O(1) computation each day.

O(N)

In order to solve the task in O(N), we must avoid computing each f(p) independently. The first thing one can notice is that the coin distribution for I(p) is the same as for I(N) up to position p inclusive, and from position p + 1 to N + 1 the distribution is the same as for I(0). Here, we can imagine starting with I(N) and, after position p, simply move on to I(0) and go on from there. This is because, for positions p + 1 to N, having an artificially inserted 0 on position p or on position 0, it does not matter, as the order of numbers in the prefix is no longer relevant, only frequency matters.

Although this way we are able to know the coin distribution only by looking at I(0) and I(N), we are still unable to compute f(p) efficiently. We need a stronger claim.

Suppose you are in I(0) in position p and the days start passing by, and you only go in case 2. Until one first day, when you have a case 1 situation. Let this day be called t(p) = first breaking point strictly after day p in I(0). Now we will use it in the claim:

The distribution of coins in I(p), except for 0, is the same as in I(N) for all days up to t(p), and from t(p) to N it is the same as in I(0). This is true because artificially incrementing frequency₀ has no effect on "who receives a coin each day" until a case 1 situation.

The claim makes it possible to compute f(p) in O(1) due to the fact that there is only one person who "survives" day t(p). But what do we really need to compute the answer now?

At first, we will compute some partial sums for the happiness increase each day in I(0) and I(N). Also, for I(0), we need to keep some information on case 1 days: what day it is, who survives it, the left end of survivor's segment of coin receiving, the right end of survivor's segment of coin receiving. We can also compute all t(p) in O(N). Note that the claim excludes 0 from the coin distributions, so we will compute all we need to know about 0 separately. He will not enter the computations for the partial sums.

Now we can compute f(p) in O(1). At first, we will add the partial sum of happiness up to day t(p) in I(N), and the partial sum of happiness from day t(p) to N in I(0). Now, we must repair the computations for the segment who survived, because, if the survivor is not 0, the partial sums got him false happiness, which we can compute correctly using the data stored for each breaking point.

We must still treat the happiness of 0, but it can be computed efficiently in a similar manner, using its segments of coin receiving and some partial sums.

The final complexity is O(N) because we can obtain in O(N) all the precomputations about I(0) and I(N) and we can print each of the N + 1 numbers using O(1) time.

Request

Contacteaza-l pe autor daca te oferi sa traduci enuntul in limba romana.