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#?
That’s what I did in Java and it works fine. I don’t think you need to build the graph that way, keep things to what you need, no more.
You can see it like: A graph is just nodes that are linked to other nodes.
How can you do that and easily add and especially remove a node? Using this strategy, when you remove a leaf (i.e. node with only one edge), you do not want to check every node of the graph to see if it’s linked to the node you remove. What you want is: okay, I will remove this node, so for every node it is linked (and I already know who they are), I’ll remove the link.
If you timeout just by creating the graph, you are doing it so wrong. C# is clearly fast enough to do that so you may have a problem.
Yeah, I think I am doing it wrong. I timeout by creating the graph only on the 2 biggest tests: 8 and 9. My previous brute force solution failed 7, 8 and 9, So there is “some kind” of optimisation. But it is wrong somehow
Can you just show how you create your graph ? Don’t post the full code (it’s forbidden), just the creation of the graph.
hi magus,
Thanks. In my main, I do:
class Solution
{
static void Main(string[] args)
{
Graph<int> personGraph = new Graph<int>();
int n = int.Parse(Console.ReadLine()); // the number of adjacency relations
for (int i = 0; i < n; i++)
{
string[] inputs = Console.ReadLine().Split(' ');
int xi = int.Parse(inputs[0]); // the ID of a person which is adjacent to yi
int yi = int.Parse(inputs[1]); // the ID of a person which is adjacent to xi
personGraph.AddEdge(xi, yi, 0);
}
{...}
}
}
My graph class (with only the relevant 2 Method visible):
public class Graph<T> //: IEnumerable<T>
{
private NodeList<T> nodeSet;
public Graph() : this(null) {}
public Graph(NodeList<T> nodeSet)
{...}
public void AddNode(GraphNode<T> node)
{
// adds a node to the graph
nodeSet.Add(node);
}
public void AddNode(T value)
{...}
public void AddEdge(T fromVal, T toVal, int cost)
{
GraphNode<T> from = nodeSet.FindByValue(fromVal) as GraphNode<T>;
if (from == null)
{
from = new GraphNode<T>(fromVal);
nodeSet.Add(from);
}
GraphNode<T> to = nodeSet.FindByValue(toVal) as GraphNode<T>;
if (to == null)
{
to = new GraphNode<T>(toVal);
nodeSet.Add(to);
}
from.Neighbors.Add(to);
from.Costs.Add(cost);
to.Neighbors.Add(from);
to.Costs.Add(cost);
}
public bool Contains(T value)
{
return nodeSet.FindByValue(value) != null;
}
public bool Remove(T value)
{...}
public int RemoveExernalNodes()
{...}
public NodeList<T> Nodes
{...}
public int Count
{...}
}
I could simplify my whole graph structure to has it less general (in the current construct, I have a Node class which encapsulates my node data and its neighbours as a NodeList. The NodeList derives from a Collection of Node and a GrpahNode class which inherits from Node to handl directed edges and weight (not needed here, I try to remove them but it did not show mnuch improvement).
Ok i understand why you are so slow. FindByValue is slow. Because it will search into the whole set the find your element (actually it will not browse the whole set because it is optimized, but it’s slow, anyway).
Maybe i’ll do some error because i’m not an expert at C#, but this is what i do:
First of all, read the input to know how many nodes you will need. Let’s call this value N. Don’t forget to store inputs in a List or an array.
You only need one class, this one:
public class Node {
private int id;
private List<Node> nodes;
// Constructors, methods, bla bla bla
}
Now, you just have to create an array of Node: Node[] nodes = new Node[N]; And don’t forget to initialize all your nodes
for (int i = 0; i < N; i++) {
nodes[i] = new Node(i + 1); // Node id in the input start at 1, not 0
}
To create your graph, re-read the inputs to add edges like this:
nodes[xi - 1].getNodes().add(nodes[yi - 1]);
nodes[yi - 1].getNodes().add(nodes[xi - 1]);
You have your graph.
Sounds “easy enough”. I did not know of the performance drawback of “FindByValue”. Thanks for the hint. I shall give uit a try 
Nice thanks for the tip, I think I’ve the same issue with Java. I’m having timeouts for tests 8 and 9.
For test 7 which is the largest I pass, debug tells me:
Duration for init: 57
Duration for compute: 1
Duration for checkCurrentBestNodeBalanced: 0
Total duration: 58
This is ridiculous to spend 99% in the init part (graph construction). I guess indexOf in Java is as slow as FindByValue in C#. I’ll give it a new try and change some lists for some arrays.