# HackerRank | Roads and Libraries | Getting wrong answer in some test cases • ### 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 - 1,city -1] = 1;
adjacentMatrix[city - 1,city - 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);

long m = Convert.ToInt64(nmC_libC_road);

long c_lib = Convert.ToInt64(nmC_libC_road);

long c_road = Convert.ToInt64(nmC_libC_road);

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, city] = 1;
adjacentMatrix[city, city] = 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);

long m = Convert.ToInt64(nmC_libC_road);

long c_lib = Convert.ToInt64(nmC_libC_road);

long c_road = Convert.ToInt64(nmC_libC_road);

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 Saturday, August 24, 2019 2:31 PM
• Edited by 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, city] = 1;
adjacentMatrix[city, city] = 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);

long m = Convert.ToInt64(nmC_libC_road);

long c_lib = Convert.ToInt64(nmC_libC_road);

long c_road = Convert.ToInt64(nmC_libC_road);

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 Saturday, August 24, 2019 2:31 PM
• Edited by Saturday, August 24, 2019 2:35 PM ADDING CODE!
Saturday, August 24, 2019 2:31 PM