ClimbingCombined | Topcoder Archive

Problem Statement

Sport climbing should have been a new event at the 2020 Summer Olympics in Tokyo, Japan. Sadly, we will still have to wait for its introduction to the Olympics.

Sport climbing consists of three separate disciplines: speed climbing, bouldering, and lead climbing. Each individual discipline produces a separate ranking. There are no ties: if there are N climbers, in each discipline, each of the ranks 1 to N is assigned to one of the climbers.

The jury opted to use a rather strange method of combining the results of those three disciplines to get the final standings of the event. The contestants are ordered according to the product of their ranks in the three individual disciplines. Obviously, smaller product is better.

Contestants with the same product share the best of their positions. Formally, a contestant's final rank is 1 + the number of contestants who reached a strictly smaller product of ranks in the individual disciplines.

N climbers are taking part in a sport climbing event. We will number them from 0 to N-1. You are given the int[] S. For each valid i, climber i had rank i+1 in the first discipline and rank S[i] in the second discipline. The third discipline is yet to take place.

You now want to assist the Olympic TV studio. For each climber i, determine their best possible final rank F[i] after the third discipline. Return the sum of all F[i].

Definition

Class:: ClimbingCombined
Method:: findBestPlacements
Parameters:: int, int[]
Returns:: int
Method signature:: int findBestPlacements(int N, int[] S)
(be sure your method is public)

Notes

Watch out: the maximum possible product of three ranks can overflow a 32-bit integer variable.

Constraints

N will be between 1 and 3,000, inclusive.
S will contain exactly N elements.
The elements of S will be a permutation of 1 through N.

Examples

```
8
```
```
{5, 7, 1, 8, 2, 3, 4, 6}
```
```
Returns: 12
```
This example corresponds to the first two rounds of the women's competition in the 2019 USA Climbing Combined Invitational. Climber 2 (Kyra Condie) is currently leading the competition. Her rank in the first discipline was 3 and she won the second discipline, so her current product is 3*1 = 3. Climber 7 (Claire Buhrfeind) is currently last, with her partial product being 8*6 = 48. Five of the eight climbers can still theoretically win the whole event. Climber 6 (Ashima Shiraishi) is currently in sixth place with product of ranks 7*4 = 28. Clearly, she can no longer win, because climber 2 (Kyra) is guaranteed to have a final product at most 3*1*8 = 24. With a good effort and a lot of luck, Ashima can still be second overall.
```
8
```
```
{1, 2, 3, 4, 5, 6, 7, 8}
```
```
Returns: 17
```
The climbers finished in the exact same order in both disciplines. The event isn't decided yet, but the final ranklist will certainly look similar to the current one. For example, now there are only two possible winners: either climber 0 or climber 1 will win the event, everything else is mathematically impossible.
```
3
```
```
{2, 3, 1}
```
```
Returns: 3
```
It is possible that the third discipline ends {3, 1, 2} and everyone will be tied for first place with product = 6. Thus, everyone's best possible rank is 1.
```
10
```
```
{8, 3, 2, 4, 1, 7, 10, 6, 5, 9}
```
```
Returns: 17
```
Almost everyone can still win. The climber who's currently last (climber 9, current product of ranks 90) can be at most 5th, and climber 6 (current product 70) can be at most 4th. Climber 7 (current product 48) can be at most tied for 1st if everything goes according to their plans, but tied for first place still counts as being first.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.