Teads Sponsored Puzzle

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. :slight_smile:

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.

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.

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