none
HackerRank | Roads and Libraries | Getting wrong answer in some test cases RRS feed

  • Question

  • My approach:

    According to the problem we have to minimize the cost to repair the lib and the roads. So what I did was if the cost of repairing the lib is <= cost of repairing the roads then I just simply return (numberOfCities  * costOfRepairingLib). Otherwise I count the no of connected components and the no of roads to be repaired then I calculated the cost and return it.

    And I'm unable to pass 4, 5, 6, 8, 9 and 10 test cases and the test cases are so huge that I can't even debug. Please see where I did the mistake.

    The logic feels fine to me but its failing for large test cases even I change every data type to long. I'm really stuck on this.

    class Solution {
    
        // Complete the roadsAndLibraries function below.
        static long roadsAndLibraries(long n, long c_lib, long c_road, long[][] cities) {
            if(c_lib <= c_road || c_road == 0)
                return c_lib * n;
    
            long[,] adjacentMatrix = new long[n, n];
            Stack<long> stack = new Stack<long>();
            Dictionary<long, bool> notVisited = new Dictionary<long, bool>();
            Dictionary<long, bool> visited = new Dictionary<long, bool>();
    
            for(long i = 1; i <= n; i++){
                notVisited[i] = false;
            }
    
            foreach(var city in cities){
                adjacentMatrix[city[0] - 1,city[1] -1] = 1;
                adjacentMatrix[city[1] - 1,city[0] - 1] = 1;
            }
    
            long noOfCycles = 0;
            long noOfRoads = 0;
    
            while(notVisited.Count > 0){
                stack.Push(notVisited.ElementAt(0).Key);
                visited.Add(stack.Peek(), true);
                notVisited.Remove(notVisited.ElementAt(0).Key);
                noOfCycles++;
                while(stack.Count > 0){
                    long top = stack.Pop();
                    for(long i = 0; i < n; i++){
                        if(adjacentMatrix[top - 1, i] == 1 && !visited.ContainsKey(i + 1)){
                            visited.Add(i + 1, true);
                            noOfRoads++;
                            stack.Push(i + 1);
                            notVisited.Remove(i + 1);
                        }
                    }
                }
            }
    
            return (noOfCycles * c_lib) + (noOfRoads * c_road);
        }
    
        static void Main(string[] args) {
            TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);
    
            long q = Convert.ToInt64(Console.ReadLine());
    
            for (long qItr = 0; qItr < q; qItr++) {
                string[] nmC_libC_road = Console.ReadLine().Split(' ');
    
                long n = Convert.ToInt64(nmC_libC_road[0]);
    
                long m = Convert.ToInt64(nmC_libC_road[1]);
    
                long c_lib = Convert.ToInt64(nmC_libC_road[2]);
    
                long c_road = Convert.ToInt64(nmC_libC_road[3]);
    
                long[][] cities = new long[m][];
    
                for (long i = 0; i < m; i++) {
                    cities[i] = Array.ConvertAll(Console.ReadLine().Split(' '), citiesTemp => Convert.ToInt64(citiesTemp));
                }
    
                long result = roadsAndLibraries(n, c_lib, c_road, cities);
    
                textWriter.WriteLine(result);
            }
    
            textWriter.Flush();
            textWriter.Close();
        }
    }
    

    Friday, August 23, 2019 5:22 AM

Answers

  • So I found out what was going wrong with my code

    My logic was totally correct the thing where I wasn't able to guess what was happening is that HACKERRANK handles OutOfMemoryException badly, they show wrong answer instead of showing that exception. So I changed my code to improve the time complexity.

    So what I did is:

    #1. I removed the two dictionaries (visited and notVisited) and added a visited array instead as the array lookup will be quicker because a dictionary lookup is two operations: calculate the hash of the key to get an index and retrieve the value from an internal array at that index.

    #2. Used adjacency list instead of adjacency matrix.

    CODE:

    class Solution {
    
        // Complete the roadsAndLibraries function below.
        static long roadsAndLibraries(long n, long c_lib, long c_road, long[][] cities) {
            if(c_lib <= c_road || cities.Length == 0)
                return c_lib * n;
                
            long[,] adjacentMatrix = new long[n + 1, n + 1];
            Stack<long> stack = new Stack<long>();
            bool[] visited = new bool[n + 1];
    
            foreach(var city in cities){
                adjacentMatrix[city[0], city[1]] = 1;
                adjacentMatrix[city[1], city[0]] = 1;
            }
    
            // for(int i = 0; i < n + 1; i++){
            //     for(int j = 0; j < n + 1; j++){
            //         Console.Write(adjacentMatrix[i,j]+" ");
            //     }
            //     Console.WriteLine();
            // }
    
            long noOfComponents = 0;
            long noOfEdges = 0;
            
            for(long i = 1; i <= n; i++){
                if(visited[i]){
                    continue;
                }
                stack.Push(i);
                visited[i] = true;
                noOfComponents++;
                while(stack.Count > 0){
                    long top = stack.Pop();
                    for(long j = 0; j <= n; j++){
                        if(!visited[j] && adjacentMatrix[top,j] == 1){
                            stack.Push(j);
                            visited[j] = true;
                            noOfEdges++;
                        }
                    }
                }
            }
    
            // Console.WriteLine(noOfCycles+" "+noOfRoads);
    
            return noOfComponents * c_lib + noOfEdges * c_road;
        }
    
        static void Main(string[] args) {
            TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);
    
            long q = Convert.ToInt64(Console.ReadLine());
    
            for (long qItr = 0; qItr < q; qItr++) {
                string[] nmC_libC_road = Console.ReadLine().Split(' ');
    
                long n = Convert.ToInt64(nmC_libC_road[0]);
    
                long m = Convert.ToInt64(nmC_libC_road[1]);
    
                long c_lib = Convert.ToInt64(nmC_libC_road[2]);
    
                long c_road = Convert.ToInt64(nmC_libC_road[3]);
    
                long[][] cities = new long[m][];
    
                for (long i = 0; i < m; i++) {
                    cities[i] = Array.ConvertAll(Console.ReadLine().Split(' '), citiesTemp => Convert.ToInt64(citiesTemp));
                }
    
                long result = roadsAndLibraries(n, c_lib, c_road, cities);
    
                textWriter.WriteLine(result);
            }
    
            textWriter.Flush();
            textWriter.Close();
        }
    }

    • Marked as answer by FaxMachine Saturday, August 24, 2019 2:31 PM
    • Edited by FaxMachine Saturday, August 24, 2019 2:35 PM ADDING CODE!
    Saturday, August 24, 2019 2:31 PM

All replies

  • Link to the problem: https://www.hackerrank.com/challenges/torque-and-development/problem
    Friday, August 23, 2019 5:23 AM
  • So I found out what was going wrong with my code

    My logic was totally correct the thing where I wasn't able to guess what was happening is that HACKERRANK handles OutOfMemoryException badly, they show wrong answer instead of showing that exception. So I changed my code to improve the time complexity.

    So what I did is:

    #1. I removed the two dictionaries (visited and notVisited) and added a visited array instead as the array lookup will be quicker because a dictionary lookup is two operations: calculate the hash of the key to get an index and retrieve the value from an internal array at that index.

    #2. Used adjacency list instead of adjacency matrix.

    CODE:

    class Solution {
    
        // Complete the roadsAndLibraries function below.
        static long roadsAndLibraries(long n, long c_lib, long c_road, long[][] cities) {
            if(c_lib <= c_road || cities.Length == 0)
                return c_lib * n;
                
            long[,] adjacentMatrix = new long[n + 1, n + 1];
            Stack<long> stack = new Stack<long>();
            bool[] visited = new bool[n + 1];
    
            foreach(var city in cities){
                adjacentMatrix[city[0], city[1]] = 1;
                adjacentMatrix[city[1], city[0]] = 1;
            }
    
            // for(int i = 0; i < n + 1; i++){
            //     for(int j = 0; j < n + 1; j++){
            //         Console.Write(adjacentMatrix[i,j]+" ");
            //     }
            //     Console.WriteLine();
            // }
    
            long noOfComponents = 0;
            long noOfEdges = 0;
            
            for(long i = 1; i <= n; i++){
                if(visited[i]){
                    continue;
                }
                stack.Push(i);
                visited[i] = true;
                noOfComponents++;
                while(stack.Count > 0){
                    long top = stack.Pop();
                    for(long j = 0; j <= n; j++){
                        if(!visited[j] && adjacentMatrix[top,j] == 1){
                            stack.Push(j);
                            visited[j] = true;
                            noOfEdges++;
                        }
                    }
                }
            }
    
            // Console.WriteLine(noOfCycles+" "+noOfRoads);
    
            return noOfComponents * c_lib + noOfEdges * c_road;
        }
    
        static void Main(string[] args) {
            TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);
    
            long q = Convert.ToInt64(Console.ReadLine());
    
            for (long qItr = 0; qItr < q; qItr++) {
                string[] nmC_libC_road = Console.ReadLine().Split(' ');
    
                long n = Convert.ToInt64(nmC_libC_road[0]);
    
                long m = Convert.ToInt64(nmC_libC_road[1]);
    
                long c_lib = Convert.ToInt64(nmC_libC_road[2]);
    
                long c_road = Convert.ToInt64(nmC_libC_road[3]);
    
                long[][] cities = new long[m][];
    
                for (long i = 0; i < m; i++) {
                    cities[i] = Array.ConvertAll(Console.ReadLine().Split(' '), citiesTemp => Convert.ToInt64(citiesTemp));
                }
    
                long result = roadsAndLibraries(n, c_lib, c_road, cities);
    
                textWriter.WriteLine(result);
            }
    
            textWriter.Flush();
            textWriter.Close();
        }
    }

    • Marked as answer by FaxMachine Saturday, August 24, 2019 2:31 PM
    • Edited by FaxMachine Saturday, August 24, 2019 2:35 PM ADDING CODE!
    Saturday, August 24, 2019 2:31 PM