Problem Statement |
| | For 0 <= i,j < N, you will be given wi,j.
You should find a permutation of 0..N-1: {p0,
p1, ..., pN-1}, such that the sum over i <
j of wp_i,p_j is maximized.
Each of the weights will be selected randomly from a normal distribution with mean 0 and variance 1. The weights will be given to you as an array w, where w[i*N+j] gives wi,j (you may deduce N as sqrt(length(w))). You should return an array with N elements, specifying the permutation p.
Your score for each test case will be the sum mentioned above, divided by N*sqrt(N*log(N)-N)/100. Your overall final score will simply be the average of your individual scores.
|
| |
Definition |
| | | Class: | Permute | | Method: | findOrder | | Parameters: | double[] | | Returns: | int[] | | Method signature: | int[] findOrder(double[] w) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | There are 100 system tests. |
| - | If your sum is less than 0, it will be increased to 0. |
| |
Constraints |
| - | N will be between 100 and 1000, with the exception of some of the examples. |
| - | The elements representing wi,i will be 0. |
| - | The time limit is 30 seconds, and the memory limit is 1024M. |
| |
Examples |
| 0) | |
| | | Returns: "N=3<br><a href=/contest/problem/Permute/1.txt>download</a>" | |
|
| 1) | |
| | | Returns: "N=5<br><a href=/contest/problem/Permute/2.txt>download</a>" | |
|
| 2) | |
| | | Returns: "N=10<br><a href=/contest/problem/Permute/3.txt>download</a>" | |
|
| 3) | |
| | | Returns: "N=20<br><a href=/contest/problem/Permute/4.txt>download</a>" | |
|
| 4) | |
| | | Returns: "N=50<br><a href=/contest/problem/Permute/5.txt>download</a>" | |
|
| 5) | |
| | | Returns: "N=159<br><a href=/contest/problem/Permute/6.txt>download</a>" | |
|
| 6) | |
| | | Returns: "N=992<br><a href=/contest/problem/Permute/7.txt>download</a>" | |
|
| 7) | |
| | | Returns: "N=290<br><a href=/contest/problem/Permute/8.txt>download</a>" | |
|
| 8) | |
| | | Returns: "N=352<br><a href=/contest/problem/Permute/9.txt>download</a>" | |
|
| 9) | |
| | | Returns: "N=1000<br><a href=/contest/problem/Permute/10.txt>download</a>" | |
|
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)2020, TopCoder, Inc. All rights reserved.