VINMAZE - Editorial

editorial
1

VINMAZE

Contest
Practice

Author: ltc_groverkss, sigma_g
Tester: multiple, see announcement
Editorialist: sigma_g

DIFFICULTY:

HARD

PREREQUISITES:

Djikstra in undirected graphs

PROBLEM

Determine for each edge in the given graph if it lies in at least one shortest path from 1 to n.

Buggy code plain text

Pastebin

QUICK EXPLANATION

Spoiler

There is a TLE in the buggy solution because the Djikstra call does not use a visited array. You can cause the adjacency matrix loop to run too many times, and cause TLE.

EXPLANATION

Step 1

There is a TLE in the buggy solution.

Step 2

When performing Dijkstra with priority queue, we need to maintain a boolean visited array to make sure we don’t revisit nodes that have been previously visited. The buggy solution does not have such a visited array.

Step 3

Without a visited array, if a node is pushed into the queue twice, it will visit all its neighbours twice. Similarly, if a node is pushed ten times, it will visit all its neighbours ten times. Can we exploit this to create TLE?

Step 4

We can create a graph structure that has a pivot node with 9e4 neighbors. And if we can get this pivot node inside the queue roughly 1e4 times, there’ll be a total of 9e8 iterations (of the for (auto neigh : adj[node]) loop), which will certainly TLE. Can you come up with such a graph structure?

Step 5

VINMAZE_test_case
VINMAZE_test_case1242×455 69.8 KB

SOLUTIONS:

C++14 generator 
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n = 5e5, w = 1e9;
    // there are 1e4 nodes in the middle of first node and pivot node
    int pivot = 1 + 1e4 + 1;
    int inter = 2;
    int weighttoput = 1e9;
    int m = (1e4 - 1) * 2 + (n - pivot);

    cout << n << " " << m << endl;
    
    // such that each node i with less weight in turn has a higher weight
    // towards pivot
    for (int i = 2; i <= 1e4; i++) {
        cout << "1 " << inter << " " << i << endl;
        cout << inter << " " << pivot << " " << weighttoput << endl;
        weighttoput -= 10;
        inter++;
    }

    // now connect edges from pivot to remaining nodes
    int remainingnode = pivot + 1;
    while (remainingnode <= n) {
        cout << pivot << " " << remainingnode << " " << w << endl;
        remainingnode++;
    }

    return 0;
}

EXTRA INFO

Actually, in the given buggy code, there was another issue.

Second bug

Line 55 had a long long overflow in case of disconnected components. We did not realize this earlier, midway through the contest we had to update the checker. Fortunately, less than 10 submissions were affected, and we fixed the issue in contest.

Hack case

This was an unintended bug, we allowed it to pass nonetheless. Any submission with more than two components would pass.