JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: Education Week MM
Problem: ConstrainedPermutation

Problem Statement

    You want to permute the numbers 0, 1, ..., N-1 in certain order p0, p1, ..., pN-1. You are given a set of constraints of form "I J", where I and J are 0-based indices of the positions in the permutation; these constraints tell you that pI should be less than pJ. There is at most one constraint for each unordered pair of indices.

Find a permutation of the numbers which will satisfy as many constraints of the given list as possible. It is not guaranteed that a permutation which satisfies all constraints exists.

Implementation

Your code should implement a single method permute(int N, String[] constraints). Each element of constraints describes one constraint in form "I J", where I and J are 0-based indices of the positions in the permutation.

You should return an array of N integers specifying the permutation p.

Scoring

The score is calculated as follows. For each test case, the raw score for it is the number of constraints which are satisfied by the returned permutation, divided by the total number of constraints. If the return is invalid (i.e. is not a permutation of numbers from 0 to N-1), the score for that test case is 0.

The overall score will be the average of raw scores over all test cases, multiplied by 1,000,000.

Test Case Generation

  • The size of the permutation N is chosen between 10 and 1000, inclusive.
  • The number of constraints is chosen between N and N*(N-1)/4, inclusive.
  • The probability of constraint generated incorrectly W is chosen between 0.1 and 0.3.
  • A random permutation of numbers 0, 1, ..., N-1 q0, q1, ..., qN-1 is generated. The constrains are created based on it. For each constraint two distinct indices I and J which haven't been used previously are chosen randomly. A correct constraint is generated based on the values of numbers qI and qJ (if qI is greater than qJ I and J are swapped). Finally, with probability W I and J are swapped.

Tools

An offline tester is available here. You can use it to test/debug your solution locally. You can also check its source code for exact implementation of test case generation and score calculation. That page also contains links to useful information and sample solutions in several languages.
 

Definition

    
Class:ConstrainedPermutation
Method:permute
Parameters:int, String[]
Returns:int[]
Method signature:int[] permute(int N, String[] constraints)
(be sure your method is public)
    
 

Notes

-The time limit is 10 seconds per test case (this includes only the time spent in your code). The memory limit is 1024 megabytes.
-There is no explicit code size limit. The implicit source code size limit is around 1 MB (it is not advisable to submit codes of size close to that or larger). Once your code is compiled, the binary size should not exceed 1 MB.
-The compilation time limit is 30 seconds. You can find information about compilers that we use and compilation options here.
-There are 10 example test cases and 100 full submission (provisional) test cases. There will be 500 test cases in the final testing.
-The match is unrated.
 

Examples

0)
    
seed = 1
N = 10
K = 14
Incorrect constraint probability = 0.2553452771879665
Constraints:
7 4
8 2
8 5
1 9
6 1
2 7
3 9
0 9
8 3
9 5
7 5
8 9
0 6
8 6
1)
    
seed = 2
N = 30
K = 108
Incorrect constraint probability = 0.23112787015918956
Constraints:
2 8
0 20
26 7
24 0
11 18
0 29
27 11
18 19
18 27
19 10
23 18
1 20
16 9
6 28
25 11
7 21
17 13
3 21
4 10
11 7
29 24
6 23
24 14
27 16
23 22
21 4
11 28
13 27
4 1
23 29
12 28
11 14
1 28
20 27
22 0
19 17
16 8
19 2
22 29
9 23
14 27
24 6
16 18
29 28
14 0
0 12
19 20
17 3
13 24
2 25
25 26
29 11
11 26
24 26
3 13
16 17
5 4
7 1
12 9
6 18
19 28
6 4
5 28
14 17
19 11
15 23
15 25
19 9
0 25
16 26
3 9
20 14
24 22
8 23
16 23
20 3
2 3
3 23
7 23
29 20
29 10
16 7
9 4
2 1
0 10
2 6
21 18
5 25
25 16
5 17
24 16
5 18
23 24
23 25
13 15
14 5
17 18
14 25
3 24
19 23
14 26
15 14
19 12
7 3
25 1
16 4
12 27
0 17
2)
    
seed = 3
N = 1000
K = 203510
3)
    
seed = 4
N = 761
K = 81502
4)
    
seed = 5
N = 852
K = 124835
5)
    
seed = 6
N = 586
K = 5014
6)
    
seed = 7
N = 506
K = 37496
7)
    
seed = 8
N = 289
K = 17489
8)
    
seed = 9
N = 164
K = 2608
9)
    
seed = 10
N = 620
K = 80648

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.