Editorial of “Problem C – Omar the Bus Driver” in CodeIT 2017

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.

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.

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:

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.


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++:

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