Teads Sponsored Puzzle

Puzzles
#62

I did it with PHP, 5 seconds on test 8, timeout on test 9.
Translated it to Javascript, 200ms on test 8.
Got to stay out of slow languages.

#63

Your algorithm is too slow, anyway.

#64

Yeah, but what I mean is that a valid solution, even not the fastest, fails on a language and not another.
I retested it, and I made in my last message, it was 91ms on test8 and 200ms on test 9.
The speed ratio is 50:1.
Iā€™m just gonna rephrase that to just keep an eye out for the language used on this one with big datasets.

#65

The trick with high level languages is to use memoization (in Python functools.lru_cache) as suggested in the briefing. First sorting the nodes by connection number may also give you more useful cached results at the start.
I use DFS. This isnā€™t a problem, because every branch has to be searched.

#66

BFS for me.

#67

Damn genius!

#68

I dit it with php too, 400ms on test 8, 600ms on test 9.

#69

Thanks for this idea !!!

I used this approach in my code (didnā€™t read the tutorial, it was really straightforward to implement).
With this and a graph structure based on a Node class, the algorithm validates the case nĀ°9 in 330ms. (very far from the timeout of 5000ms based on chr-m post) (in Python 3)

#70

Thanks for that.
I havenā€™t thought that the initialization may be the issue here until I read this and started to measure the time needed for the different parts.

In my case a Hash in Ruby did the trick to fasten the computation.

#71

Thanks for the idea of removing edges.
This combined with optimizing the initialization of the graph was the way to go :slight_smile:

#72

Submitted a solve for a couple of times. First time for 80%, second time on 70%.
Then rebuilt it witth a recursion and stopping on a branches with a growing broadcast time. Starting from a most connected man and moving into direction of longest branch to find an shorter broadcast time.
Now all the interactive tests pass very fast, but all validation tests fail. Is it possible that it is a bug.

#73

A bug in your code, of course. :wink:

1 Like
#74

Thanks! This code you posted above helped me a lot.

#75

hi everyone !

first sorry for my english ^^

i want some informations for the teads problem ā€œfind the node to start information propagation ,with a minimum costā€.

I encountred two problem with test 1 and the test 2.

test 1 : link : [[0, 1], [1, 2], [2, 3], [2, 4]]
expected solution : node 2 for a cost of 2
my solution : node 1 for a cost of 2

there is the same cost, but considering my solution wrong :confused:

test 2 : link : [[0, 1], [1, 2], [1, 4], [2, 3], [4, 5], [4, 6]]
expected solution : node 2 for a cost of 3
my solution : node 1 for a cost of 2

there is best solution then expect and also considering wrong :confused:

I cant upload images, so you can draw the graph and see by your self.

some one have explanation or i miss something ?

#76

Your output is meant to be the cost, not the node number.

#77

ohh godā€¦-__-, now its work, thanks you very much.

#78

I was thinking the same, but i had written it down. From 1 to 0 you got 5 steps and from 15 to 2 you got five steps. It is correct.

#79

Hello everyone, Iā€™ve been working on the Teads puzzle for a long time now with a solution that works for validators 1,2,3,3,4,5,6,10 but as for the others I have some problems!!!I have not the time, Iā€™m on python. My program consists of:
1- detect the elements that have the most links to analyze as a priority
2- repeat each element until they belong to a duo and add the duo of the element in the list (yes it works)
I would like to know if he has any other way than to analyze everything and if Iā€™m off on the wrong track.

#80

The Teads sponsored puzzle will be removed from the platform at the end of the week by agreement with the sponsor. Iā€™m sorry for those who are currently working on it.