JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: Marathon Match 26
Problem: Permute

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)
    
N=3
download
1)
    
N=5
download
2)
    
N=10
download
3)
    
N=20
download
4)
    
N=50
download
5)
    
N=159
download
6)
    
N=992
download
7)
    
N=290
download
8)
    
N=352
download
9)
    
N=1000
download

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)2010, TopCoder, Inc. All rights reserved.