So I tried solving the puzzle in C++ using breadth first search algorithm. I get only a 40% as I use an Adjacency Matrix to store the graph, But creating a Matrix with 2000+ rows and columns is giving a time out error, Can someone give me another efficient way of representing a graph in C++ and also how to access it?

I did the puzzle in javascript (which is far slower than C++). My graph is a just an object poiting on other object. In C++, youāll have something like this i believe :

```
class Node {
// Some code here
// ...
Node** nodes; // You can also use a vector<Node*>
}
```

In javascript this structure works fast enought. So thereās no reason it canāt work in C++.

Maybe BFS is not the best algorithm.

So thats a pointer to multiple nodes(classes) or a structure?

Thatās a class containing an array of pointers to the same class. I canāt really say more than this.

My algo runs in 50ms on test 8 the structure is just everyone carrying a list to itsā connections (C++). Your probably much better off with the lists than that adjacency matrix. Your looking through a huge row/line instead of iterating through a couple of elements in the list.

In general representing the graph with lists is going to be alot better for sparse graphs (graphs where each element is connected to a few people). For dense graphs (graphs where everyone is connected to almost everyone) adjacency and lists will be similar with maybe a small advantage to the adjacency because itās lower level.

Iām trying the puzzle in JavaScript and, for the life of me, cannot solve the large set problems (8 and 9). I am currently constructing an object of objects with the node number and then two values called ālinks,ā which stores all nodes to which this node is connected, and āvisited,ā which is either true or false.

I have optimized the hell out of my for loops, so Iām assuming it has something to do with the way I am constructing my graph. Any tips on optimizations? Please? PLEASE?!

You donāt have to guess. You can take the time your algorithm uses to construct the graph. And then you can probably see that itās not the problem.

I tried it myself. Iām also using javascript. At the top of your program:

```
var start = new Date().getTime();
```

Everytime you want an output:

```
printErr("time: "+(new Date().getTime()-start)+"ms");
```

In problem eight my graph is ready after 70ms. My algorithm needs another 20ms to find the solution.

I know where my problem lies. My graph is ready in 27ms, but when I need to go through it and reset all numbers āvisited: falseā, that takes 30ms per go, and I need to reset it after every number. Do you know of a way to reset an object to its original state in a way that takes <1ms?

Do I understand that right? All nodes in your graph have `visited===false`

. Then after you run your algorithm for one number, all nodes have `visited===true`

. Then you reset `visited`

on all nodes to `false`

and continue with the next number.

If thatās the case you donāt have to reset `visited`

at all. Before you run your algorithm create another variable `var visitedThisTurn = true;`

. Instead of checking `visited===true`

in your algorithm you check `visited===visitedThisTurn`

. Then you can switch the value you use for comparison with `visitedThisTurn=!visitedThisTurn;`

instead of resetting all nodes.

HAHAA! Awesome idea! Thanks a lot!

Dammit!

Your solution worked like a charm. It cut my times by over half, but with tree travel times of about 3ms per number, that still times out.

Iām assuming that my solution, of having the numbers have a property called āvisitedā is not the way I am supposed to do it.

I believe you are only thinking about the implementation of your algorithm but instead, you should be thinking about your algorithm.

You probably canāt solve the large problems with a naive algorithm.

I wouldnāt describe my algorithm as naive (by the way, thanks for teaching me the term ānaive algorithmā), but there must be something wrong with it. Iām trying something new. Thanks again for the help.

Here is some perspective. The timeout is ~5000ms. Testcase 8 has ~35000 nodes. Testcase 9 has ~50000 nodes. The validation testcases might have more.

Take an algorithm with time complexity O(n). That means it touches every node only once. In testcase 9 that leaves 0.1ms per node.

Your algorithm sounds like it has a time complexity O(nĀ²). For every node, it has to touch every other node. In testcase 9 that leaves only 0.000002ms per node.

Iām getting slowly out of ideas.

I first tried a a really ābrutalā way (list of nodes, BFS starting from each node, the result is the smallest BFS). It might not come as a surprise, but I timed out on several test cases.

I tried to take another approache: building a graph (I based it on this tutorial: https://msdn.microsoft.com/en-US/library/ms379574(v=vs.80).aspx ) and removing every node with only one edge until the graph is empty. This did not really helped: I time out on test 8 and 9 only by creating the graph. Any idea on how to optimize it?

Thanks

Bruteforce it, bruteforce this one too, BRUTEFORCE EVERYTHING !

You can bruteforce with a BFS starting from each node. This is how i do and i do it in javascript (so itās slow ā¦). But you have to optimize a little your code. Store what you can to avoid calculating the same thing twice.

You can store the nodes from which the BFS should start.

What do you mean with Store? Does the fact that I time out only by creating a graph, without even starting to search means this strategy is wrong in C#?