ico-arrow-big-left

Marathon Match 26 - Marathon Match 26

Key Information

Register
Submit
The challenge is finished.
Show Deadlines

Challenge Overview

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)
    
"1"
Returns: "N=3<br><a href=/contest/problem/Permute/1.txt>download</a>"
1)
    
"2"
Returns: "N=5<br><a href=/contest/problem/Permute/2.txt>download</a>"
2)
    
"3"
Returns: "N=10<br><a href=/contest/problem/Permute/3.txt>download</a>"
3)
    
"4"
Returns: "N=20<br><a href=/contest/problem/Permute/4.txt>download</a>"
4)
    
"5"
Returns: "N=50<br><a href=/contest/problem/Permute/5.txt>download</a>"
5)
    
"6"
Returns: "N=159<br><a href=/contest/problem/Permute/6.txt>download</a>"
6)
    
"7"
Returns: "N=992<br><a href=/contest/problem/Permute/7.txt>download</a>"
7)
    
"8"
Returns: "N=290<br><a href=/contest/problem/Permute/8.txt>download</a>"
8)
    
"9"
Returns: "N=352<br><a href=/contest/problem/Permute/9.txt>download</a>"
9)
    
"10"
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.

Payments

Topcoder will compensate members in accordance with our standard payment policies, unless otherwise specified in this challenge. For information on payment policies, setting up your profile to receive payments, and general payment questions, please refer to ‌Payment Policies and Instructions.