I proposed a problem called “Problem C – Omar the Bus Driver” which was on Scorify platform, and I would like to share its solution in this post. I am not that happy about it because the problem statement was ambiguous, and some cases were not consistent even if they will not change the output. I checked this point after the requests in clarifications because some contestants used assert to check it.

The case that was not consistent was :

3 1 8

3 0 0

So the number of nodes is 3 and the only edge connects a node with index 3 and a node with index 0 which is NOT consistent to the problem statement. And I am sorry about it.

And the hero was my friend Omar Salim Moussa. So, this problem was a gift for him.

I am sorry 😦

I apologize for all the contestants who tried this problem and find it ambiguous. I know some contestants spent a lot of time trying to solve it. I deeply apologize specifically to Pythonista, Pinky and the Brain, Koding4Khobz teams.  The problem can be seen for the first time as traveling salesman problem. I hope I corrected this ambiguity in the clarifications. And I hope it did not affect the overall standing. I took it very seriously, but these things happen. And I am really sorry about it. I hope it will not be repeated next time. It is the first time I write a problem for a contest, but I am not taking it as an excuse.

Problem Statement:

Omar is a bus driver in a famous traveling Moroccan company. Omar travels once per day, and he visits daily N cities. He has a serious problem because he does not know if the initial volume of Gasoline is enough to visit the N cities. Your task is to help Omar to know if he can traverse all the N cities with the minimum cost so that he can know if the initial volume of gasoline is enough to do so.

Input:
The input consists of several test cases. Each test case starts with a line with three non-negative integers, 1 ≤ N ≤ 20000, and 0 ≤ M ≤ 30000, and 1 ≤ G ≤ 30000, separated by a single space, where N is the numbers of cities and M is the number of roads, and G the initial volume of Gasoline. Cities are numbered from 0 to N−1. Then follow M lines, each line consisting of three (space-separated) integers u, v and g indicating that there is a road between u and v such that if the bus traverses this road, it will consume g liters of Gasoline where 0 ≤ g ≤ 20000. Roads are undirected.
Input will be terminated by a line containing -1 -1 -1, this line should not be processed.

Output:
For every test case, if there is no solution, then output the word “NULL” (without quotes) on a line of its own. If Omar can visit all the cities with G liters of Gasoline, output “POSSIBLE” (without quotes). Otherwise, If he cannot, output “IMPOSSIBLE” (without quotes).
Sample Input:
4 4 20
0 1 1
1 2 2
1 3 3
2 3 0
2 1 90
0 1 100
3 0
-1 -1 -1

Sample Output:
POSSIBLE
IMPOSSIBLE
NULL

Clarifications during the contest:

1/ You should connect all the nodes with the minimum cost.

2/ You do not need to repeat the calculation of an edge if you already traversed it.

Idea:

The idea of the problem is to calculate the minimum spanning tree and compare its value with the initial amount of gasoline. So, if mst <= g, print “POSSIBLE”. If mst > g, print “IMPOSSIBLE”. If the mst = 0  because the driver cannot go anywhere or the graph is not connected output “NULL”.

Time Complexity:

In my implementation, I used Kruskal’s algorithm to find the minimum spanning tree, so the time complexity is O(E log V)

A Solution in C++:

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s