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.

1 Like

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.

4 Likes

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.

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.

1 Like

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

2 Likes

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.

1 Like

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#?