1
\$\begingroup\$

I'm trying to solve a problem from HackerRank. I got the correct algorithm, but it seems to be too inefficient. After checking the code with 10 given test cases, 3 cases are good and 7 return a timeout (not wrong).

Problem:

The Ruler of HackerLand believes that every citizen of the country should have access to a library. Unfortunately, HackerLand was hit by a tornado that destroyed all of its libraries and obstructed its roads! As you are the greatest programmer of HackerLand, the ruler wants your help to repair the roads and build some new libraries efficiently.

HackerLand has n cities numbered from 1 to n. The cities are connected by bidirectional roads. A citizen has access to a library if:

  • Their city contains a library.
  • They can travel by road from their city to a city containing a library.

The cost of repairing any road is croad dollars, and the cost to build a library in any city is clib dollars.

You are given q queries, where each query consists of a map of HackerLand and value of clib and croad. For each query, find the minimum cost of making libraries accessible to all the citizens and print it on a new line.

Sample Map:

Input Format

The first line contains a single integer, q, denoting the number of queries. The subsequent lines describe each query in the following format:

The first line contains four space-separated integers describing the respective values of n(the number of cities), m(the number of roads), clib(the cost to build a library), and croad(the cost to repair a road). Each line iof the msubsequent lines contains two space-separated integers, ui and vi, describing a bidirectional road connecting cities uiand vi.

Sample input to console:

1  
8 6 2 1  
1 2    
2 3  
3 1  
1 7  
5 6  
6 8  

Output:

9

With small numbers, the code works well. But with inputs like this:

10   
96295 12709 99058 75153  
78455 13046  
80408 12229  
21285 87954  
29676 9393  
26819 18141  
...........  
...........

I get a timeout from the online test.

Here is my code:

class Program
{

    static void Main(string[] args)
    {
        List<Int64>[] adj;

        Int64 q = Convert.ToInt32(Console.ReadLine()); //Number of queries
        Int64 costLib =0;
        Int64 costStr =0;
        List<Int64> result;

        for (Int64 a0 = 0; a0 < q; a0++)
        {
            string[] tokens_n = Console.ReadLine().Split(' ');
            Int64 n = Convert.ToInt32(tokens_n[0]); //Number of cities
            Int64 m = Convert.ToInt32(tokens_n[1]); //Number of streets
            Int64 x = Convert.ToInt64(tokens_n[2]); //Cost of library
            Int64 y = Convert.ToInt64(tokens_n[3]); //Cost of street

            adj = Graph(n);

            costLib = x;
            costStr = y;

            for (Int64 a1 = 0; a1 < m; a1++)
            {
                string[] tokens_city_1 = Console.ReadLine().Split(' ');
                Int64 city_1 = Convert.ToInt32(tokens_city_1[0]);
                Int64 city_2 = Convert.ToInt32(tokens_city_1[1]);

                AddEdge(city_1-1, city_2-1,adj);
            }

            if (x <= y)
            {
                Console.WriteLine(costLib * n);
            }
            else
            {
                result = DFS(n,adj);
                Console.WriteLine(result[1] * costStr + result[0] * costLib);
            }

        }
    }

    static List<Int64>[] Graph(Int64 v)
    {
        Int64 Vertices = v;
        List<Int64>[] adj = new List<Int64>[v];

        for (Int64 i = 0; i < v; i++)
        {
            adj[i] = new List<Int64>();
        }

        return adj;
    }

    static void AddEdge(Int64 v, Int64 w, List<Int64>[] adj)
    {
        adj[v].Add(w);
    }

    static List<Int64> DFS(Int64 v, List<Int64>[] adj)
    {
        Int64 s = 0;
        Int64 streetCounter = 0;
        Int64 LibraryCounter = 1;
        bool[] visited = new bool[v];
        List<Int64> result = new List<Int64>();

        Stack<Int64> stack = new Stack<Int64>();
        visited[s] = true;
        stack.Push(s);

        while (stack.Count != 0)
        {
            s = stack.Pop();
            foreach (Int64 i in adj[s])
            {
                if (!visited[i])
                {
                    visited[i] = true;
                    stack.Push(i);
                    streetCounter++;
                }
            }

            if (stack.Count == 0)
            {
                for (Int64 ii = 0; ii < v; ii++)
                {
                    if (visited[ii] != true)
                    {
                        stack.Push(ii);
                        LibraryCounter++;
                        streetCounter--;
                        break;
                    }
                }
            }

        }
        result.Add(LibraryCounter);
        result.Add(streetCounter);
        return result;
    }

How should I go about modifying this to improve the speed? Or is there something else wrong with the code? I would appreciate any input.

Note that I cannot create another class in the online IDE.

\$\endgroup\$

migrated from stackoverflow.com Sep 13 '17 at 4:27

This question came from our site for professional and enthusiast programmers.

  • 1
    \$\begingroup\$ have you profiled your code to see whats holding it up? \$\endgroup\$ – Yair Halberstadt Sep 12 '17 at 19:31
  • \$\begingroup\$ The point is that I don't see a way to speed it up and don't know where to get the knowledge to see it. For me the code is fine and it runs fine in Visual Studio, but not online on Hackerrank. \$\endgroup\$ – Julez Sep 12 '17 at 19:37
  • 1
    \$\begingroup\$ Are you sure this is your actual code? It's getting stuck in an infinite loop on the sample input, because you're not marking ii as visited when you do stack.Push(ii). \$\endgroup\$ – Pieter Witvoet Sep 13 '17 at 7:45
  • 1
    \$\begingroup\$ The first thing to notice, is that any 'group' of cities which are connect by roads (but not connected to any others) can be solved independently of any other group: 96295 12709 implies there are at least 80000 independent groups (most of which have no streets, so simply must have a library): simply breaking up the problem will significantly reduce the cost (what is quicker, solving one high-complexity n=10000 problem, or solving 100 high-complexity n=100 problems?) \$\endgroup\$ – VisualMelon Sep 13 '17 at 8:24
  • \$\begingroup\$ @PeterTaylor indeed, and I wouldn't say it is overly clear either; the missing dollar counts appear (from the code) to be specified per-problem (third and fourth params on the second line of input) \$\endgroup\$ – VisualMelon Sep 13 '17 at 8:25
3
\$\begingroup\$

Types

            Int64 n = Convert.ToInt32(tokens_n[0]); //Number of cities

In C# it is more usual to use the type alias long, but that's a matter of style. What makes absolutely no sense, though, is parsing an Int32 and storing it in an Int64 which is never modified. To be honest, I'm surprised to see longs at all: do the constraints which were in the original problem statement imply that they'll be necessary? I am morally certain that the number of cities is not going to exceed the limits of an int.

                Console.WriteLine(result[1] * costStr + result[0] * costLib);

Should result be a Tuple<int, int>?

C# has had the var keyword for some time now. It may make things slightly harder for review without an IDE, but most of the time it makes code more readable by reducing repetition.


Scope

This code reads as though it was written by someone whose preferred language is C (pre-99). Variables should be declared when they're needed, not at the start of the method. The only case in which it's usually necessary to declare a variable without also initialising it is immediately before an if or case when each branch will initialise it. So, for example, in Main the variables adj, costLib, costStr don't need to be outside the loop. (In fact, only one of costLib and x needs to exist at all, because they're just aliases; similarly costStr and y). The variable Vertices in Graph is never read: your IDE is probably giving you a warning about that.


Comments

I don't see a single comment outside the parser. If it's throwaway code, that's fair enough, but it's rather counterproductive to ask for help improving your code and not explain anything about it. What approach are you taking? I can see that there's a DFS, but why? What does the return value of the DFS contain? Why is LibraryCounter initialised to 1?

The lack of comments is very evident in the fact that VisualMelon offered a hint in a comment on this question for something which I think is essentially the very heart of what the code is already doing: but that wasn't obvious from a quick look at the code.

If you write out the basics of your approach and the reasoning behind it, I think you'll find that there's a simpler way of doing it.


Names

Some of the names are so unhelpful that there are comments when they're assigned. Rather than

            Int64 n = Convert.ToInt32(tokens_n[0]); //Number of cities

why not this?

            var numCities = Convert.ToInt32(tokens_n[0]);

Most of the names follow C# capitalisation convention, but not all. Vertices and LibraryCounter are both local variables and should start with a lower-case letter.


High-level data structures

        bool[] visited = new bool[v];

I assume that you're using C# with .Net, whether .Net Standard or .Net Framework. They both have high-level data structures which can make code easier to read and, in many cases, faster. If you flip this round as ISet<long> unvisited then the bulk of DFS can be rewritten as

        ISet<long> unvisited = new HashSet<long>(Enumerable.Range(0, adj.Length));
        Stack<long> stack = new Stack<long>();
        while (unvisited.Any())
        {
            if (!stack.Any())
            {
                // Pick an arbitrary unvisited vertex
                var next = unvisited.First();
                unvisited.Remove(next);
                stack.Push(next);

                // TODO Appropriate manipulation of streetCounter and libraryCounter
            }

            foreach (long i in adj[stack.Pop()])
            {
                if (unvisited.Remove(i))
                {
                    stack.Push(i);
                    streetCounter++;
                }
            }
        }

Correctness

Although maybe some comments would convince me that the code is in fact correct, I'm highly suspicious of the parsing. AddEdge is called once per line of input, and inserts a directed edge. Nothing in the supplied problem statement suggests to me that streets are one-way.

I also find it highly suspicious that in a completely disconnected graph streetCounter is going to end up being negative. If it's counting streets, surely it should be zero in that case?

\$\endgroup\$
  • \$\begingroup\$ Thank you very much for your detailed feedback. I will fix up the code as you suggested. I learned a lot from you. \$\endgroup\$ – Julez Sep 13 '17 at 15:42
2
\$\begingroup\$

The below part is where it is crossing the time limit. As I can see whenever you finish exploring a connected component, you are trying to find the next unvisited vertex to do another DFS. In order to do that, you are starting all the way from index 0 every time which is resulting in \$O(n^2)\$

if (stack.Count == 0)
{
    for (Int64 ii = 0; ii < v; ii++)
    {
        if (visited[ii] != true)
        {
            stack.Push(ii);
            LibraryCounter++;
            streetCounter--;
            break;
        }
    }
}

Instead, if you start ii from the next one of the last visited vertex, the complexity of this particular operation will become \$O(n)\$ instead of \$O(n^2)\$.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.