Problem Statement |
| | A random walk in a directed graph starts at some node in the graph and then follows one of that node's outgoing edges uniformly at random. The process is then repeated from the next node and so on. If a graph consists of a single strongly connected component, then a random walk will eventually visit every node in the graph. In this problem, your program will make a random walk of a graph. However, you will only be able to observe the in and out degrees of the vertices that you visit. Your task is to make as short a random walk as possible such that you have visited every node in the graph.
You should write two methods: init and walk. The init method will be called first with a single integer argument: the number of vertices in the graph. Subsequent calls will be made to the walk method and will give a sequences of in and out degree observations. Both of these methods should return an integer between 0 and one million, inclusive, indicating the number of steps your program wants to move at once. So, if you want to take 10 steps in the first iteration, your init method should return 10. Then, you will be given 10 degree observations in the next call to the walk method.
You are allowed to observe at most 10 sequences of degrees (walk will be called at most 10 times). Each time it will be given a int[] with 2 elements per observations. Element 2*i and 2*i+1 will given the in and out degrees of the ith observation, respectively. If you ever return 0, it will be assumed that you are done and want to make no further observations.
Scoring will be based on two factors: the number of nodes that you visit before quiting, and the total number of observations you make. In the best case, you will stop as soon as you hit the last unvisited node, in which case you will get 100 points. If you don't visit all the nodes, you will lose half your points for each unvisited nodes, so your score will be 100*0.5unvisited. If you visit all the nodes and make some additional observations, your score will be 100-(percent extra observations)/3 (with a minimum of 0). For example, if you visited all but 2 nodes, you would get 25 points. If you visisted the last node on observation 100, but you made a total of 130 observations, you would receive 90 points (having made 30% extra observations). Your total score will simply be the sum of your individual scores.
The graphs will be generated via a very simple model. First, the number of nodes will be selected between 10 and 100, inclusive, with size K chosen with probability proportional to 1/K. Then, a probability, p is chosen between 0 and 10/K. For each potential edge (u,v) (where u does not equal v), that edge is added with probability p. If the generated graph has a single strongly connected component, it is kept, otherwise, p and all the edges are regenerated (the size is kept), and the process is repeated until a graph with a single strong component is generated. |
| |
Definition |
| | | Class: | RandomWalking | | Method: | init | | Parameters: | int | | Returns: | int | | Method signature: | int init(int nodes) | | | | Method: | walk | | Parameters: | int[] | | Returns: | int | | Method signature: | int walk(int[] seq) | | (be sure your methods are public) |
|
| |
|
| |
Notes |
| - | You will have a total of 20 seconds execution time (not 20 seconds per sequence). |
| - | The memory limit is 64 MB. |
| - | There are 100 test cases. |
| - | Graphs are given as adjacency lists. For instance, in example 0, there are edges from node 0 to nodes 1, 2 and 9. |
| - | The return from the 10th call to walk is ignored (treated as if it is 0). |
| - | The calls to walk form a single continuous random walk. In other words, concatenating all of the inputs to the walk methods gives a continuous walk. |
| |
Examples |
| 0) | |
| | | Returns:
"0: 1 2 9
1: 0 4 5 6 7
2: 3 8 9
3: 2 5 9
4: 0 2 3 6 7 8
5: 8
6: 3 4 5 7 9
7: 1 4 6 8 9
8: 1 3 7
9: 0 1 2 5 7
" | |
|
| 1) | |
| | | Returns:
"0: 4 5 7 8 9
1: 0 3 4 5 6 7 8 9
2: 0 1 3 4 5 6 7 9
3: 0 1 2 4 5 6 7 8 9
4: 1 3 5 6 8 9
5: 0 1 2 3 4 6 7 8 9
6: 1 2 3 4 7 8 9
7: 0 1 2 3 5 6 8 9
8: 1 2 3 4 5 7 9
9: 0 2 3 4 6 8
" | |
|
| 2) | |
| | | Returns:
"0: 19 28 41 43 45 46 48
1: 4 11 15 17 19 25 26 34 39 40 44 47
2: 3 9 12 16 31 34 40 43 46
3: 2 5 13 16 25 28 30 32 35 38 40 44
4: 6 14 18 22 31 35 47
5: 2 4 14 16 20 26 27 37
6: 0 5 12 14 16 21 25 27 33 36 37 44 47
7: 0 31 32 36 37 43 44
8: 0 10 17 23 27 29 31 32 33 35 37 40 45 47
9: 2 3 10 11 14 15 16 32 38 48
10: 6 8 12 23 37 44 48
11: 8 9 10 17 19 20 34 48
12: 1 2 13 20 22 30 31 33 39 41 45
13: 1 6 9 19 33 36 41 45
14: 6 20 22 25 31 37 41 43 49
15: 3 8 9 21 24 33 39
16: 6 12 22 23 24 26 27 29 36 38 39 44
17: 5 9 13 21 23 24 27 34 39 42 43 45 49
18: 9 10 14 20 22 24 25 26 29 31 32 35 44
19: 12 16 20 22 23 25 28 34 35 46
20: 0 1 2 3 7 11 18 21 25 27 44 45 49
21: 3 4 7 9 10 14 23 28 33 37 42 48 49
22: 1 7 12 19 21 26 30 40 43 44
23: 0 3 4 5 8 9 11 14 27 30 38 41 43 45 49
24: 5 6 8 11 15 16 23 30 32 34 35 36 37 42
25: 0 8 16 18 19 31 33 34 46
26: 0 11 13 27 33 35 40 45 49
27: 7 11 21 23 38 39 40
28: 0 7 8 9 24 27 30 31 33 41 44
29: 6 7 9 12 18 19 26 30 32 34 38 41 47
30: 1 4 7 14 18 22 23 26 29 31 32 44 45 47
31: 0 4 11 14 18 22 29 30 37 45
32: 9 13 17 20 21 24 26 28 29 30 35 42
33: 6 8 9 14 16 21 22 24 25 28 30 37 40 42 45 47
34: 7 21 29 36 43
35: 11 15 18 41 43 46
36: 9 25 28 48
37: 0 7 10 18 28 38 42
38: 3 4 12 13 15 17 18 23 27 35
39: 1 19 35 37 47
40: 9 16 18 29 38 42
41: 2 3 15 16 17 22 25 32 36 37 40 42 45
42: 2 9 15 16 23 28 30 34
43: 0 8 22 23 27 29 33 37 45 46
44: 2 18 30 42 47 48
45: 0 8 12 26 32 34 40
46: 7 9 18 23 24 25 30 33 36 37 40
47: 11 12 13 14 19 29 36 44 48
48: 15 23 25 33 38
49: 12 18 22 25 26 42 43
" | |
|
| 3) | |
| | | Returns:
"0: 1 6 7 10 11 14 17 18 19 20 24 25
1: 0 2 3 4 6 7 8 17 23 25
2: 0 3 4 5 6 11 16 19 21 24
3: 0 2 10 13 14 15 16 18 20 23
4: 0 3 10 13 14 15 18 20 21 22 23 25
5: 6 8 11 12 14 15 16 17
6: 0 3 5 8 9 10 11 12 16 19 20 22 23
7: 1 17 18 20 23
8: 1 4 5 7 12 13 15 17 20 22
9: 1 4 5 6 8 11 12 17 19 21 22
10: 1 5 7 9 11 14 16 18 19
11: 0 4 6 9 10 18 21 24
12: 2 3 5 7 8 9 10 11 17 19 20
13: 1 7 8 9 12 22 24
14: 1 4 7 8 9 16 17 21
15: 1 7 10 12 16 18 19 22
16: 1 13 14 15 21 22
17: 0 2 4 14 15 18
18: 0 3 4 12 16 17 19 22 23 24
19: 0 1 4 7 8 9 10 11 12 20 21 22 24
20: 2 3 4 5 6 7 9 10 12 13 16 17 19 22 24 25
21: 0 1 6 7 8 9 14 20 25
22: 3 4 5 6 7 10 11 17
23: 2 4 5 6 8 12 16 18 20 24 25
24: 0 9 11 13 14 17 18 25
25: 0 1 6 7 9 15 21 23 24
" | |
|
| 4) | |
| | | Returns:
"0: 1 2 3 4 5 6 7 8 9 10
1: 0 2 4 5 8 10
2: 0 3 4 5 6 7 8 10
3: 0 1 2 4 5 6 7 8 10
4: 0 1 2 3 6 7 8 10
5: 0 1 2 3 6 8 9 10
6: 0 1 2 3 4 7 8 9 10
7: 0 1 2 3 4 8 9 10
8: 1 3 4 6 7 9 10
9: 0 1 2 3 4 5 7 8 10
10: 0 1 2 3 5 8 9
" | |
|
| 5) | |
| | | Returns:
"0: 5 22 25 28 63
1: 13 24 26 43 58 61
2: 5 9 14 17 20 23 26 40 50
3: 9 27 35 37 38 49 54 57
4: 29 44 45 62
5: 9 44 48 62 63
6: 9 18 31 43 46 61 65
7: 0 12 19 25 34 39
8: 9 17 21 44 53 62 63
9: 0 3 5 17 27 44 53
10: 7 16 24 37 38 56 67
11: 3 4 13 15 32 50 64
12: 1 7 14 20 28 29 30 32 52 59 60 65
13: 2 4 34 44 51 57
14: 8 23 28 36 53 54 55 62 63 65
15: 1 6 27 30 48 55 57
16: 2 10 26 47 53 61 66
17: 5 8 11 24 30 41 42 50 59
18: 0 6 11 33 35 44 52 59 68
19: 6 41 49 55
20: 18 25 36 39 48 58
21: 1 4 19 27 30 35 43 47 48
22: 11 15 32 41 58 62 66
23: 5 17 18 20 21 34 35 43
24: 0 5 37 50 51 61 62 63
25: 7 15 21 36
26: 8 10 20 36 41 43 56
27: 3 12 14 34 38 51 55 59 63 64 66
28: 3 15 26 49 56
29: 2 9 22 35 41 44 46 49 59 63
30: 28 32 40 41
31: 5 9 27 49 52 55 56
32: 2 5 33 41 55 57 59 63
33: 26 38 51 63 66
34: 14 41 42
35: 7 10 28 31 57 67
36: 2 13 19 50
37: 6 13 14 41 47 49 54 60 63
38: 6 22 39
39: 9 13 16 22 48 58
40: 8 25 28 47 59
41: 0 8 18 25 38 46 53 60 61 62
42: 13 18 33 39 56 60 65
43: 2 5 13 14 27 34 57
44: 8 11 17 25 27 37
45: 16 36 38 48 50 56 59 64 65
46: 1 3 8 14 16 19 24 50 64
47: 14 25 32 40 60 67
48: 3 10 18 32 35 50 56 61
49: 8 20 25 29 43 54
50: 12 13 14 16 31 33 34 47 49 57 58 61
51: 24 36 46 61 62
52: 33 35 38 41 44 48 64
53: 5 12 13 24 28 40
54: 3 22 34 42 45 65
55: 1 9 10 15 16 31 36 38 61 67
56: 4 6 9 32 38 54 59 67
57: 5 13 16 23 24 25 29 35 36 41 46 54 65
58: 13 18 23 26 33 34 57 60 61
59: 0 4 14 19 35 37 42 47 54 65
60: 8 18 21 24 53 66
61: 0 3 11 13 19 22 51 62
62: 4 8 20 28 48 49 50 54
63: 2 3 28 35 39 51 52 53 64 68
64: 13 21 36 46 55
65: 3 6 14 29 36 43 50 55
66: 19 20 25 54 55 56 59
67: 3 5 7 17 19 22 48 54 59
68: 2 8 20 23 31 48
" | |
|
| 6) | |
| | | Returns:
"0: 1 19 24 32
1: 7 13 20 27
2: 3 5 29
3: 6 16 28 29 30
4: 6
5: 11 14 16 17 22 31
6: 1 2 8 31
7: 29 30
8: 4 10 12 19
9: 15 22
10: 0 12 13 18 29
11: 2 7 17 20
12: 11 13 20 27 29
13: 3 5 6 11 23
14: 21 25 27 28
15: 11 24 25 31
16: 1 29
17: 5 9 28
18: 1 6 29
19: 5 6 24 26
20: 0 5 12 17 30 31
21: 14 20 30
22: 1 15 19 20 26 30
23: 6 8 13 26 28
24: 0 13 14 16 20
25: 3 23 31
26: 14 20 23 24
27: 3 15 20 23 30
28: 1 10 12 22 29 31
29: 9 18 28 31 32
30: 27
31: 5 16 24 30
32: 26 28 30 31
" | |
|
| 7) | |
| | | Returns:
"0: 3 4 7 10 11 13 15
1: 2 3 5 8 9 13 17
2: 4 5 8 9 17
3: 6 9 12
4: 3 5 6 10 11 13 15 17
5: 0 2 3 6 7 11 13 16
6: 1 2 3 4 8 10 11 13 14 15 17
7: 0 1 2 3 9 12 13 15 16
8: 0 5 7 14
9: 0 3 5 6 7 8 10 13 17
10: 0 1 2 3 5 6 8 14 15 16
11: 0 1 4 12 16 17
12: 1 2 3 5 6 9 11
13: 3 5 7 8 14 15 16 17
14: 2 3 4 7 11 12 13 16
15: 1 2 4 6 7 8 10 12 13
16: 0 5 6 8 10 12 13 14
17: 2 5 7 8 13
" | |
|
| 8) | |
| | | Returns:
"0: 1 2 5 6 7 9 10 11
1: 4 6 10
2: 5 6 8 10
3: 4 5 7 9
4: 5 7 8 9 11
5: 0 1 3 7 9 10
6: 2 3 4 5 8 11
7: 1 4 6 9 10
8: 4 6 9 11
9: 2 8 11
10: 0 1 2 3 6 8
11: 6
" | |
|
| 9) | |
| | | Returns:
"0: 1 7 12 13 18 19 38 45
1: 5 6 12 14 21 26 31 35 38 43 44
2: 4 5 6 16 17 27 33 36 43
3: 7 8 9 16 23 28 29 30 46
4: 3 7 17 23 28 31 32 35 36 37 38 39 46
5: 1 4 13 14 15 17 18 31 33 41
6: 2 7 14 15 18 29 30 34 38 42 44
7: 2 10 11 12 16 18 19 35 45
8: 16 18 19 28 38 47
9: 3 18 21 37 38 39 41 46
10: 0 3 5 7 9 19 23 27 29 33 34 38
11: 5 20 22 36 38 39 41
12: 4 10 16 17 26 33 37
13: 1 3 6 7 11 21 22 25 26 30 31 32 34 36 37 44
14: 1 5 7 8 12 16 18 30 31 32 40 41 42
15: 2 10 14 20 25 35 40
16: 8 12 14 15 20 21 25 26 35 36
17: 2 12 14 15 20 26 28 29 32
18: 5 8 9 13 14 17 19 23 26 27 38
19: 7 16 17 28 29 35 36 39 40 42 45
20: 1 6 9 12 13 27 29 33 39 47
21: 15 23 26 33 41 44
22: 10 12 21 32 35 36 39 41 42 45
23: 0 4 7 10 24 28 32 36 38 41 47
24: 6 8 10 12 14 16 18 21 29 32 33 39 41
25: 0 9 16 21 24 27 36 37 38
26: 2 10 14 16 17 22 33 34 37 43 45
27: 4 10 11 18 23 28 34 35 36 39 41 43
28: 8 9 13 15 22 24 25 26 30 35 40
29: 5 9 24 26 31 33 46
30: 7 9 13 17 21 41
31: 4 9 14 15 23 24 40
32: 5 9 10 11 16 17 18 24 37 40 41 43
33: 2 6 7 16 21 25 39 42 44 46
34: 1 2 5 8 10 11 14 20 28 32 35 40 46
35: 1 10 13 15 16 24 40 41
36: 3 8 10 14 15 17 26 30 40 41 45 46
37: 1 4 17 22 23 25 26 28 29 39 43
38: 2 5 23 24 27 28 31 45
39: 1 3 7 16 17 34 41 46
40: 1 14 20 24 29 33 38 44
41: 2 6 12 23 31 34 40 42 47
42: 1 2 12 15 29 30 38 39 47
43: 9 12 31 38
44: 3 5 7 10 20 35 36 37 40 46
45: 1 4 6 17 21 23 25 30 31 34 40 42 46
46: 4 5 7 11 13 23 29 31 34 41
47: 4 8 9 14 17 21 32 36 38 44 45
" | |
|
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.