Teads Sponsored Puzzle

Puzzles
#1

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?

Teads Problem
#2

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++.

#3

Maybe BFS is not the best algorithm.

#4

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

#5

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

#6

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

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

#8

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:

#9

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.

#10

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?

#11

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

HAHAA! Awesome idea! Thanks a lot!

#13

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.

#14

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.

#15

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.

#16

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

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

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

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

#20

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