Problem Statement |
| | There are a number of nodes placed at lattice points on a grid. You need to design a network that connects them. You may install new nodes on lattice points, and you may run network cable between any two nodes.
You have two goals in the design of your network. First, you want to minimize the cost of the network you build. That means not installing too many new nodes or running too much cable. Second, you want to make the network fault tolerant. Each node that you install as well as the original nodes, and each unit of cable that you run has some probability of failing.
The inputs x and y will specify the locations of the nodes that must be connected. The input cost will specify how much it will cost if there is a failure that prevents some of the original nodes from communicating. The jth integer in element i of cost will specify the cost incurred if node/cable failures prevents nodes i and j from communicating. The input p represents the probability that a node will fail. The input q respresents the probability that one unit of cable will fail (thus, the probability that a length L cable will fail is 1-(1-q)L). Cable costs 1 per unit length, while nodeCost gives the cost of adding a new node.
Your network design will be judged based on it's expected cost: the sum of the cost of the nodes and cable installed, plus the expected cost resulting from network failures. You should return a String[] where each element specifies either a new node, or a connection between two nodes. If you are installing a new node, the element of the String should specify its coordinates formatted as "x y". If you are installing cable, the element should be formatted as "x1 y1 x2 y2", indicating cable from (x1,y1) to (x2,y2). You may install new nodes in at most 30 unique new locations, and your returned String[] may have at most 1000 elements. If your return is invalid in any way (bad formatting, cables not ending at nodes, etc.), you will be judged as if you returned {} -- you will pay the cost of all communications failing. If you cause a runtime error or exceed the time limit (of 20 seconds) you will also be judged in this way.
The inputs will be randomly generated. All random numbers will be generated uniformly and independently. All ranges are inclusive. First, the number of nodes, N, will be chosen between 5 and 20. Each node will be placed on a unique random lattice point with x and y coordinates between 0 and 99. p and q will be between 0.0 and 0.01. The cost between each pair of nodes will be an integer between 0 and 100,000. nodeCost will be between 10 and 100.
To compute the probability that two nodes can communicate, a monte carlo method will be employed. The random failure process will be simulated 1,000,000 times and the expected cost of the failures will be approximated by the average of these trials.
Your score for each test case will simply be your expected cost as computed by the monte carlo method. Your overall score will simply be 100000 minus the average of your scores on the individual cases. If your score is less than 0, it will be changed to 0. |
| |
Definition |
| | | Class: | GraphBuilder | | Method: | build | | Parameters: | int[], int[], double, double, int, String[] | | Returns: | String[] | | Method signature: | String[] build(int[] x, int[] y, double p, double q, int nodeCost, String[] costs) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | You may run multiple cables between the same two nodes. |
| - | You may install multiple nodes at the same lattice point. If you do, they will be connected to each other by default (and of course this connection cannot fail, having length 0). Furthermore, as long as at least one of the multiple nodes at a point does not fail, all cables terminating at that point will be able to communicate through that point. In other words, installing two nodes at a point is equivalent to installing one node at that point that has a probability of failing of p2. |
| - | The original nodes act just like the ones you may add, with the same failure rate as other nodes. |
| - | If one of the original nodes fails, then clearly it will not be able to communicate with any of the other nodes. This is unavoidable, and thus this cost is not counted against you. |
| - | To keep the simulation times down, java.util.Random will be used for random number generation. |
| - | costs will be symmetric and its diagonal entries will be 0. |
| - | The cost of a cable between two points will be the Euclidean distance between those points. |
| - | Cables may cross, and may pass over nodes without being incident to them. For example, a node at (1,1) does not have any effect on a cable from (0,0) to (2,2). |
| - | The memory limit is 64MB. |
| - | Your return should be single-space delimited without leading or trailing spaces. |
| - | The 30 new unique node location limit means that you may create as many nodes as you want in up to 30 new locations. The locations of the nodes given to you do not count against this limit. |
| |
Examples |
| 0) | |
| | | Returns:
"x = {6, 48, 17, 92, 32, 53}
y = {78, 69, 63, 62, 10, 37}
p = 0.004100808114922016
q = 0.0020771484130971706
nodeCost = 17
costs =
0 95194 25379 48473 75678 39722
95194 0 49336 1729 76360 96659
25379 49336 0 16847 19035 30327
48473 1729 16847 0 54422 94630
75678 76360 19035 54422 0 34098
39722 96659 30327 94630 34098 0 " | One simple strategy would be to place a single node at (50,50) and then connect each of the original nodes to it. However, this is very prone to failure. One way to reduce the risk of failure is to have redundant nodes and edges. If we add two nodes at (50,50), and add 4 cables from every computer to (50,50), we will reduce the risk considerably. Now, there will be a functioning node at (50,50) with probability 1 - p2, and each node will have a functioning cable to (50,50) with pretty high probability.
The cost of the nodes and cables with this strategy is 864.5 and the expected cost from failures is about 74, for a total cost of roughly 939. |
|
|
| 1) | |
| | | Returns:
"x = {19, 68, 34, 67, 47, 35, 30, 58, 66}
y = {47, 94, 14, 99, 99, 53, 24, 19, 98}
p = 0.009014476240300544
q = 0.004968225934308908
nodeCost = 31
costs =
0 91362 16908 94139 90780 74980 58776 68432 12961
91362 0 42371 69340 73967 41612 75504 1122 79824
16908 42371 0 26023 8107 78814 9306 60845 44772
94139 69340 26023 0 62344 4468 34904 40340 52441
90780 73967 8107 62344 0 2675 7898 86637 70758
74980 41612 78814 4468 2675 0 56628 65273 94046
58776 75504 9306 34904 7898 56628 0 54764 11262
68432 1122 60845 40340 86637 65273 54764 0 91519
12961 79824 44772 52441 70758 94046 11262 91519 0 " | |
|
| 2) | |
| | | Returns:
"x = {29, 69, 42, 46, 95, 72, 93, 1, 9}
y = {33, 89, 44, 95, 75, 5, 68, 88, 34}
p = 0.00811194812081668
q = 0.00534613102433974
nodeCost = 19
costs =
0 91710 26818 47023 62803 201 26321 43902 69137
91710 0 27276 25856 1954 77473 63667 90034 93532
26818 27276 0 75046 33704 90756 13079 32444 61138
47023 25856 75046 0 82148 12866 98485 86568 83739
62803 1954 33704 82148 0 44777 75993 38130 11574
201 77473 90756 12866 44777 0 95959 65328 2423
26321 63667 13079 98485 75993 95959 0 24480 29330
43902 90034 32444 86568 38130 65328 24480 0 40488
69137 93532 61138 83739 11574 2423 29330 40488 0 " | |
|
| 3) | |
| | | Returns:
"x = {64, 51, 58, 42, 88}
y = {75, 95, 45, 65, 96}
p = 0.0040731303630733165
q = 0.0013070565365267284
nodeCost = 55
costs =
0 13927 7998 42420 57221
13927 0 3176 92108 94332
7998 3176 0 70383 16346
42420 92108 70383 0 52311
57221 94332 16346 52311 0 " | |
|
| 4) | |
| | | Returns:
"x = {44, 8, 96, 17, 12, 22, 43, 40, 36, 62, 99, 19, 97, 87, 87, 8}
y = {32, 42, 90, 43, 36, 2, 71, 10, 6, 43, 13, 16, 69, 77, 1, 44}
p = 0.0016942263381844326
q = 0.003814951307056981
nodeCost = 91
costs =
0 77669 65398 43088 71887 12439 81519 21556 19523 58242 63192 20445 19681 52511 82820 7224
77669 0 85952 13838 29342 78256 31831 45959 8151 67026 20196 76116 83809 54635 4011 43020
65398 85952 0 35761 17702 82358 25360 17420 5792 41513 83982 61359 66083 26928 86775 26943
43088 13838 35761 0 35729 36433 27150 45651 57224 52420 86476 56070 57659 74556 72981 15669
71887 29342 17702 35729 0 91173 82855 18454 8250 2430 20641 6656 52647 61889 2068 82851
12439 78256 82358 36433 91173 0 2324 66826 30278 73358 245 73734 9016 25617 29616 23372
81519 31831 25360 27150 82855 2324 0 17920 13750 55476 75191 79110 26125 25264 76076 13602
21556 45959 17420 45651 18454 66826 17920 0 31454 48183 29439 38870 85360 31125 40906 68780
19523 8151 5792 57224 8250 30278 13750 31454 0 98482 56835 58689 34467 70294 16824 18871
58242 67026 41513 52420 2430 73358 55476 48183 98482 0 71174 3710 95894 16615 75165 20514
63192 20196 83982 86476 20641 245 75191 29439 56835 71174 0 48763 43067 8333 48449 32499
20445 76116 61359 56070 6656 73734 79110 38870 58689 3710 48763 0 81429 10294 9957 20285
19681 83809 66083 57659 52647 9016 26125 85360 34467 95894 43067 81429 0 53857 29478 31645
52511 54635 26928 74556 61889 25617 25264 31125 70294 16615 8333 10294 53857 0 2518 1973
82820 4011 86775 72981 2068 29616 76076 40906 16824 75165 48449 9957 29478 2518 0 16617
7224 43020 26943 15669 82851 23372 13602 68780 18871 20514 32499 20285 31645 1973 16617 0 " | |
|
| 5) | |
| | | Returns:
"x = {3, 15, 22, 49, 39, 60, 82, 66, 50}
y = {48, 63, 64, 87, 11, 63, 3, 0, 11}
p = 0.008264446916240231
q = 0.007788336306338746
nodeCost = 92
costs =
0 77967 51877 27131 80229 31822 74540 46540 12912
77967 0 66155 16155 8034 35808 22795 60135 11773
51877 66155 0 56078 90246 77516 35786 64769 85614
27131 16155 56078 0 49291 93171 69545 4903 86022
80229 8034 90246 49291 0 40058 43650 40456 82616
31822 35808 77516 93171 40058 0 16614 25592 33985
74540 22795 35786 69545 43650 16614 0 60560 18621
46540 60135 64769 4903 40456 25592 60560 0 51704
12912 11773 85614 86022 82616 33985 18621 51704 0 " | |
|
| 6) | |
| | | Returns:
"x = {7, 57, 11, 80, 55, 92}
y = {72, 41, 31, 74, 47, 27}
p = 0.006583582796657616
q = 0.006224951045415638
nodeCost = 96
costs =
0 99469 40545 36911 89709 39339
99469 0 70083 25060 82569 91026
40545 70083 0 48313 90775 28948
36911 25060 48313 0 19095 8917
89709 82569 90775 19095 0 10560
39339 91026 28948 8917 10560 0 " | |
|
| 7) | |
| | | Returns:
"x = {75, 66, 2, 91, 30, 67, 66, 7, 43, 74, 72, 33, 2, 57}
y = {27, 28, 93, 98, 22, 44, 80, 85, 97, 69, 46, 26, 91, 57}
p = 0.005119199353456559
q = 0.00233858613264591
nodeCost = 79
costs =
0 73318 23837 13038 48840 44716 51384 45139 605 78222 2383 25761 58234 93207
73318 0 24708 93061 78532 63220 28310 17893 12286 42328 78832 86212 76052 71079
23837 24708 0 80561 98642 19790 21705 93011 9697 17833 46922 22582 508 82797
13038 93061 80561 0 9509 84335 91762 51204 84954 53870 4306 34086 35528 12956
48840 78532 98642 9509 0 15124 90317 14283 64762 90430 80507 90203 95766 53457
44716 63220 19790 84335 15124 0 41504 54854 2471 12175 14678 78092 9080 44902
51384 28310 21705 91762 90317 41504 0 14884 28467 52053 81362 810 37463 38426
45139 17893 93011 51204 14283 54854 14884 0 61643 19029 69225 11994 53928 80220
605 12286 9697 84954 64762 2471 28467 61643 0 8673 69183 37395 16015 41185
78222 42328 17833 53870 90430 12175 52053 19029 8673 0 17901 20715 67703 53976
2383 78832 46922 4306 80507 14678 81362 69225 69183 17901 0 6495 56554 24308
25761 86212 22582 34086 90203 78092 810 11994 37395 20715 6495 0 41860 64687
58234 76052 508 35528 95766 9080 37463 53928 16015 67703 56554 41860 0 33033
93207 71079 82797 12956 53457 44902 38426 80220 41185 53976 24308 64687 33033 0 " | |
|
| 8) | |
| | | Returns:
"x = {59, 23, 32, 5, 38, 48, 13, 75, 53, 23, 86, 84, 1, 18, 98, 70, 87, 88, 19}
y = {72, 20, 23, 61, 0, 8, 85, 69, 72, 39, 84, 30, 10, 4, 75, 92, 12, 14, 47}
p = 0.00724697587422273
q = 3.594426926882632E-4
nodeCost = 33
costs =
0 76020 48775 52436 62850 46095 47662 68187 91453 82801 8970 12962 30917 10106 37961 20056 62292 21270 95897
76020 0 86067 21391 5614 84665 64134 24348 34702 95666 50482 30637 77441 89051 90787 54627 41232 67377 31079
48775 86067 0 41241 74226 98781 79751 82602 15650 35707 25502 21453 74002 96942 43165 21290 24956 86115 63628
52436 21391 41241 0 88338 52168 75847 53303 85202 56379 32395 23044 44457 69283 95190 82928 10532 91660 68295
62850 5614 74226 88338 0 84058 9930 48040 96374 90608 60713 22399 37078 75985 11315 79268 30410 95581 98603
46095 84665 98781 52168 84058 0 60896 15736 15828 87583 41779 92443 18468 85657 23163 48104 13422 25329 90558
47662 64134 79751 75847 9930 60896 0 10727 9094 74371 22272 82033 3294 89505 91943 16788 41995 21340 11509
68187 24348 82602 53303 48040 15736 10727 0 8592 456 94418 21096 5065 62864 10863 47783 16906 98426 28435
91453 34702 15650 85202 96374 15828 9094 8592 0 63107 82280 31573 27340 31877 19045 53187 53799 60741 957
82801 95666 35707 56379 90608 87583 74371 456 63107 0 3885 91855 65689 75931 36036 28946 76106 59341 97765
8970 50482 25502 32395 60713 41779 22272 94418 82280 3885 0 23210 58146 74625 62642 25771 61349 95272 28346
12962 30637 21453 23044 22399 92443 82033 21096 31573 91855 23210 0 53240 53844 80656 82869 55348 10227 14790
30917 77441 74002 44457 37078 18468 3294 5065 27340 65689 58146 53240 0 37344 7988 3042 16894 46929 95645
10106 89051 96942 69283 75985 85657 89505 62864 31877 75931 74625 53844 37344 0 82015 54558 60990 47323 72894
37961 90787 43165 95190 11315 23163 91943 10863 19045 36036 62642 80656 7988 82015 0 81404 85568 85386 14113
20056 54627 21290 82928 79268 48104 16788 47783 53187 28946 25771 82869 3042 54558 81404 0 24853 90567 4630
62292 41232 24956 10532 30410 13422 41995 16906 53799 76106 61349 55348 16894 60990 85568 24853 0 18497 22310
21270 67377 86115 91660 95581 25329 21340 98426 60741 59341 95272 10227 46929 47323 85386 90567 18497 0 42999
95897 31079 63628 68295 98603 90558 11509 28435 957 97765 28346 14790 95645 72894 14113 4630 22310 42999 0 " | |
|
| 9) | |
| | | Returns:
"x = {98, 13, 32, 71, 81, 57, 33, 71, 2, 62, 33, 36, 60, 25, 0, 39, 74, 63}
y = {46, 50, 98, 99, 10, 53, 52, 56, 69, 97, 66, 31, 67, 71, 18, 56, 70, 74}
p = 0.008420372767857684
q = 0.008580875521429242
nodeCost = 91
costs =
0 1938 17938 89667 34256 82565 76861 83631 61892 65080 62667 48473 38836 79925 72355 90465 52833 54901
1938 0 22624 34739 91459 44177 81269 65812 39621 80560 52651 58100 86157 71183 54465 23620 17618 81501
17938 22624 0 27863 83372 21630 37387 780 97936 86937 22607 10729 40242 63071 11432 15028 31509 87055
89667 34739 27863 0 17581 31996 78747 44222 75622 36459 50317 85008 34504 54641 88035 96912 20273 60262
34256 91459 83372 17581 0 60058 40919 80829 32569 81029 72780 13806 92055 84812 3872 25057 45768 14713
82565 44177 21630 31996 60058 0 15596 68456 97168 95864 23942 88530 39566 46800 96425 63799 78716 70750
76861 81269 37387 78747 40919 15596 0 37241 75619 98363 34941 78223 51753 13622 76679 20763 71354 73555
83631 65812 780 44222 80829 68456 37241 0 61949 92386 83844 30854 73186 93073 9520 12627 33074 83611
61892 39621 97936 75622 32569 97168 75619 61949 0 63787 16190 70021 61037 38069 47231 36845 75340 59116
65080 80560 86937 36459 81029 95864 98363 92386 63787 0 84618 4772 94828 77198 34802 77159 76000 86054
62667 52651 22607 50317 72780 23942 34941 83844 16190 84618 0 60963 96085 29839 34144 70568 68331 50930
48473 58100 10729 85008 13806 88530 78223 30854 70021 4772 60963 0 47190 96335 36845 3227 7848 79810
38836 86157 40242 34504 92055 39566 51753 73186 61037 94828 96085 47190 0 33086 88326 94790 59320 56625
79925 71183 63071 54641 84812 46800 13622 93073 38069 77198 29839 96335 33086 0 75347 34727 73380 20289
72355 54465 11432 88035 3872 96425 76679 9520 47231 34802 34144 36845 88326 75347 0 33177 47237 83013
90465 23620 15028 96912 25057 63799 20763 12627 36845 77159 70568 3227 94790 34727 33177 0 69708 31363
52833 17618 31509 20273 45768 78716 71354 33074 75340 76000 68331 7848 59320 73380 47237 69708 0 73260
54901 81501 87055 60262 14713 70750 73555 83611 59116 86054 50930 79810 56625 20289 83013 31363 73260 0 " | |
|