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.
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
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:
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.
Well yeah with arrays for init on case 7 it’s now much better:
Duration for init: 37
Duration for compute: 1
Duration for checkCurrentBestNodeBalanced: 0
Total duration: 39
For the largest one (9):
Duration for init: 219
Duration for compute: 7
Duration for checkCurrentBestNodeBalanced: 0
Total duration: 226
No idea if it’s good or not, but my algo (which is NOT the leaf cutting discussed in this thread) looks not that bad for execution time…
By the way, funny I had not realized earlier the number of nodes is just number of link +1, whatever the way they’re linked…
Yeah, it worked \o/. You were right, from the moment I stopped “searching” it went all smoother. The c# stopwatch tells me a duration of approximately 80ms to compute the right result for the test 9
Hello, I need some information for the Teads Sponsored Puzzle.I use C. I passed the first 7 cases but when it’s about the 8th, I get an error while initializing my adjacency matrix. Then and I tested that initialization for several values of n -number of nodes-, for values of n above 6000 I get an segmentation fault. Does someone has an explanations for that?
Salut, j’ai besoin d’information concernant le Teads Sponsored Puzzle. J’utilise le langage C. Mon programme fonctionne pour les 7 premiers tests mais au huitième j’ai une erreur juste à l’initialisation de ma matrice d’adjacence. J’ai alors tester avec plusieurs valeur du paramètre n (le nombre d’arêtes), et pour les valeurs supérieures ou égale à 6000 j’ai une erreur de segmentation. Quelqu’un aurait une explication?
I see, I didn’t think that too big matrix could lead to a segmentation fault. I guess I’ll be obliged to use adjacency lists instead of adjacency matrix
There has to be a more elegant way to do this, but this was my solution:
I did this using two main processes: an outer process that picks nodes to test, and an inner process that broadcasts the message and counts relays. In both of the processes I maintain lists of nodes that have already been tested or relayed, so that I don’t end up re-testing/re-counting nodes.
For the outer process:
I started with the node with the highest number of neighbors as the first node.
Run the inner process (see below), and store the number of relays as the starting “minimum relays”
Then:
Run the inner process for each of the neighbors of that node, keeping track of the number of relays for each.
If any of those nodes are lower than the current minimum relays, the lowest of those becomes the source node for the next set of nodes to test.
Repeat until all viable nodes have been tested
By doing this, you’re targeting each test at a better node, narrowing down the list each time.
For the inner process:
I created two loops: one that loops through a “current nodes” list, and one that adds nodes to a “next nodes” list, based on each of the “current nodes.”
For each iteration through the complete “current nodes” list, I increment a relay counter.
If at any time the relay counter becomes greater than the current “minimum relays”, I break out of the process.
At the end of the loop, the “next nodes” list becomes the “current nodes” list.
I solved the puzzle with a different method, however I’d just like to point out that the 10th test expects a wrong value: 5 instead of 4
(This just happens in testing, while submitting the code there’s no issue)
Happy coding!
I am having a little problem on this puzzle : My algorithm succeeds on cases 1 to 6, and in case 10.
However, it finds incorrect values (too small) on cases 7, 8 and 9. Because of the size of the last 3 datasets, it is hard to figure out what went wrong. Is there an easy way to see the tree on a “graphical” way so that i can understand at what point the algorithm fails ?
Thanks!
Bonjour à tous !
J’ai un petit problème sur cet exercice : Mon algorithme fonctionne correctement sur les cas 1 à 6 et sur le 10, mais trouve des valeurs incorrectes (trop petites) sur les cas 7, 8 et 9. Vu la taille des jeux de données, j’ai du mal à trouver le problème. Est-ce qu’il existe un moyen pratique de voir les graphes de manière plus “visuelle” pour que je puisse voir à quel moment mon algorithme plante ?
