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>" | |
|