RandomDijkstraDiv2
SRM 791 · 2020-10-16 · by laoriu
Problem Statement
Given is a complete directed graph on N vertices. The vertices are numbered from 0 to N-1. For each pair of distinct vertices u and v, the edge from u to v has a non-negative length dist[u,v].
You are given the edge lengths in the
You wanted to compute the shortest paths from 0 to all other vertices, so you implemented Dijkstra's algorithm. Here is the pseudocode that corresponds to your implementation:
1) S = set of all vertices 2) D[0] = 0 3) for i = 1 to N-1: D[i] = infinity 4) while (S is not empty): 5) find u in S such that D[u] is minimal among all D[i] where i is in S 6) remove u from S 7) for each v in S: 8) if D[v] > D[u] + dist[u,v]: 9) D[v] = D[u] + dist[u,v]
The above pseudocode is an actual correct version of Dijkstra's algorithm. When it terminates, each value D[i] is the length of the shortest path from vertex 0 to vertex i.
Your friend then decided to prank you and edited line 5) in the above code to the following one:
5') select u from S uniformly at random
Calculate and return the probability that the modified algorithm will calculate the entire array D correctly.
Notes
- Your return value will be accepted if it has a relative or an absolute error at most 1e-9.
- Note that the cycle in lines 7-9 of the pseudocode iterates just over all vertices v that are still in the set S (i.e., those that have not been processed yet).
Constraints
- N will be between 1 and 15, inclusive.
- G will have exactly N*N elements.
- Each element of G will be between 0 and 10^6, inclusive.
- For each u, G[u*N+u] will be 0.
4
{ 0, 1, 1000, 1000, 1000, 0, 1, 1000, 1000, 1000, 0, 1, 1000, 1000, 1000, 0 }
Returns: 0.041666666666666664
A graph on 4 vertices. The edges 0 -> 1, 1 -> 2, and 2 -> 3 each have length 1, all other edges have length 1000. You will only get the correct array of distances if you remove the vertices in order 0, 1, 2, 3. That happens with probability (1/4) * (1/3) * (1/2).
4
{ 0, 1, 1, 1, 1, 0, 1000, 1000, 1, 1000, 0, 1000, 1, 1000, 1000, 0 }
Returns: 0.25
In this case the edges between 0 and each other vertex are short and all other edges are long. We will compute the correct array of distances if and only if we process vertex 0 first. That happens with probability 1/4.
15
{0, 1, 2, 3, 2, 3, 2, 2, 3, 2, 2, 3, 1, 2, 3, 1, 0, 1, 2, 2, 3, 3, 1, 2, 3, 2, 1, 1, 3, 3, 2, 2, 0, 1, 3, 2, 3, 3, 2, 3, 2, 3, 3, 1, 1, 3, 1, 1, 0, 1, 2, 3, 2, 3, 3, 2, 1, 3, 1, 3, 2, 1, 2, 3, 0, 2, 3, 2, 3, 2, 1, 3, 2, 2, 3, 3, 1, 2, 2, 3, 0, 2, 3, 3, 1, 3, 1, 3, 1, 2, 2, 2, 3, 3, 1, 2, 0, 1, 3, 3, 1, 1, 2, 3, 3, 3, 2, 2, 2, 1, 3, 2, 0, 3, 3, 3, 2, 3, 3, 2, 1, 3, 1, 1, 2, 2, 3, 1, 0, 2, 1, 1, 1, 1, 3, 3, 2, 3, 2, 1, 2, 2, 1, 3, 0, 2, 1, 2, 1, 2, 1, 1, 1, 3, 3, 2, 1, 2, 3, 2, 0, 3, 1, 3, 1, 1, 1, 3, 2, 3, 1, 3, 1, 3, 1, 2, 0, 1, 1, 2, 1, 3, 2, 1, 3, 3, 3, 1, 3, 3, 2, 3, 0, 1, 3, 2, 2, 3, 1, 1, 2, 2, 2, 2, 3, 2, 3, 1, 0, 3, 1, 2, 3, 2, 1, 2, 3, 3, 1, 2, 3, 2, 3, 1, 0}
Returns: 0.016666666666666666
15
{0, 834931, 347194, 175026, 485031, 23692, 616273, 102956, 703528, 481790, 985345, 482900, 290233, 669025, 571391, 719341, 0, 722653, 963344, 24940, 587411, 198481, 864135, 712613, 300999, 42873, 809296, 276050, 568594, 506130, 402343, 71792, 0, 824177, 114332, 921906, 546165, 743505, 618657, 628011, 500505, 563250, 780490, 829200, 379546, 606561, 326839, 432114, 0, 715975, 939649, 941939, 214822, 767939, 663243, 95888, 984827, 107669, 537282, 848428, 319813, 424757, 999594, 348920, 0, 876864, 377616, 892436, 114085, 855847, 978451, 97707, 896357, 652661, 780115, 446827, 378043, 52686, 366773, 611146, 0, 59220, 970680, 410893, 664732, 846309, 280928, 266691, 220842, 303800, 219370, 487590, 892386, 693448, 860854, 857490, 0, 466874, 980466, 813384, 461848, 332873, 906812, 707259, 57432, 162820, 608475, 503002, 646, 28861, 443279, 908248, 0, 545494, 459149, 643888, 854209, 901659, 270242, 308242, 107487, 317798, 129865, 978739, 177994, 443640, 353010, 521697, 0, 245900, 527807, 597970, 538167, 275882, 328194, 581741, 24188, 963102, 638467, 705766, 915826, 397747, 897407, 958457, 0, 617929, 730632, 623737, 723361, 654322, 962061, 484260, 646952, 585435, 188220, 715685, 735995, 395329, 854056, 44876, 0, 642763, 974243, 190277, 654187, 81719, 508512, 430985, 63199, 235322, 484152, 184456, 975848, 626984, 417222, 4682, 0, 145847, 779351, 76322, 587404, 408015, 792, 403041, 523583, 777894, 477232, 660369, 391329, 766116, 128435, 536082, 0, 107068, 90217, 827850, 440707, 431964, 986672, 933353, 577245, 109328, 893298, 647273, 183324, 947471, 697428, 522785, 0, 460585, 625300, 868906, 98278, 414716, 549997, 530200, 343301, 453592, 785312, 957765, 206196, 331755, 416408, 888941, 0}
Returns: 4.822530864197531E-6
15
{0, 2, 1, 0, 1, 2, 0, 1, 0, 2, 3, 0, 3, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 2, 0, 2, 0, 2, 1, 3, 2, 0, 2, 3, 0, 2, 0, 3, 4, 0, 4, 1, 4, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 2, 0, 2, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 3, 2, 0, 2, 3, 0, 2, 0, 3, 4, 0, 4, 1, 4, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 2, 0, 2, 0, 2, 1, 3, 2, 0, 2, 3, 0, 2, 0, 3, 4, 0, 4, 1, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 3, 2, 0, 2, 3, 0, 2, 0, 3, 4, 0, 4, 1, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 1, 2, 0, 1, 0, 2, 3, 0, 3, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
Returns: 0.06666666666666667
5
{
0, 1000, 1000, 4, 5,
1000, 0, 1000, 1000, 1000,
1000, 2, 0, 1000, 1000,
1000, 1000, 6, 0, 1000,
1000, 7, 1000, 1000, 0
}
Returns: 0.058333333333333334
The exact answer for this test case is 7/120.
Submissions are judged against all 144 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RandomDijkstraDiv2 with a public method double solve(int N, vector<int> G) · 144 test cases · 2 s / 256 MB per case