Teads.TV

Feedback & Bugs
#63

And I have a solution! When pushing stuff onto my tree dict, I had some code to get around the fact that I might not yet have initialised a list:

    if u not in tree.keys():
        tree[u] = [v]
    else:
        tree[u].append(v)

Apparently, this part of the job is enormously faster if I use setdefault.

#64

what language is this? in c++ map operator [] initialises key if not present

#65

It’s Python. I’m quite enjoying learning it, but it does have its quirks.

#66

You could try if u not in tree as well, it should bring the same result, but skip the generation of a list of all keys.

Or, asking for forgiveness instead of permission:

try:
    tree[u].append(v)
except:
    tree[u] = [v]
#67

Thanks for the suggestions! Both of those are masses quicker than generating tree.keys(). In particular, I did not know that u in tree is equivalent to u in tree.keys() nor that generating tree.keys() was quite so slow. Asking for forgiveness instead of permission is a nice way to think about that other alternative.

The if u not in tree approach works as quickly as tree.setdefault(u, []).append[v], while the try: ... except: ... approach is just a smidge slower.

#68

Ok, noone answered my question, but fortunately I found out myself.
Test 10 gives you a graph with 13 connections. If they start indexing vertices from 0, 13 would be the highest index, because a tree has v-1 edges. In the test, there are some 0 rank vertices, and the maximal index is 15.
First, I handled it with increasing the size of my array of sets, avoiding overindexing. (Its size were 16, not 14).
Im sure, that in validation test they indexed a vertex to 199999 or INT_MAX even, causing huge memory leak because of the size of reprezentation.
My final solution finds the unconnected vertices, and using these indices it renames the unnecessary high indices. In a tree with 13 connections my vertices are always in 0-13 range. 100% finally.

#70

@ronlobo: Thanks for the node deletion idea ^^ My graph exploration algorithm in C++ was stuck at 80% (can’t pass tests 8 & 9) and doing this leaf-cut to the graph before sending it to my algorithm worked perfectly :slight_smile:

1 Like
#71

Looks like some tests are missing for an accurate validation. My algorithm shouldn’t work in all cases, but I sent it “just to see” and I got 100%.
Indeed, I only calculate the distance between the first leaf I find (leaf1) and the most distant leaf from leaf1 (leaf2).
However, another leaf could be further from leaf2 than leaf1, but it never happens in the validation tests.

For example, my algorithm returns 3 at this custom test case:

11
0 1
1 2
2 3
1 4
4 5
5 6
6 7
7 8
4 9
9 10

But the real answer should be 4, and I still get 100%.
Hope this was clear enough. Thanks

1 Like
#72

Any bash user here? I have finished all other medium games with bash, but failed at case 8&9. I can not process over 15000 links in time. Both my graph store solution got similar efficiency. Any hope for bash?

solution1:
let “node[xi200000+(pos[xi]++)]=yi"
let "node[yi200000+(pos[yi]++)]=xi”

solution2:
node[$xi]="${node[$xi]}"" “$yi
node[$yi]=”${node[$yi]}"" "$yi

BTW: I use a different algorithm to get the result:
1, from one node, use BFS to get the farthest node
2. from this node, use BFS again to get the farthest node, the number of cycles is the longest distance in the map
3. result=longest_distance/2

I think it should work in a non-directed acrylic graph, am I correct?

#73

Which one is the “existing thread”? There are 3 general thread (including this one) and none linked from the challenge page as official :eyeglasses:

I was wondering as it is the next one I wished to solve, but I have some rouble identifyong by which end should I take the problem (literally speaking) :sweat_smile:

#74

Hi, i have a problem with this puzzle, in ide i pass the 10 test but in validation i don’t pass the 10’th. Can someone give some information about this validation to know what i am doing bad? Ty.

#75

Oddly, I got a problem with test 2 that I dont understand …

Test is following :
6
0 1
1 2
1 4
2 3
4 5
4 6

so we have the nearest node to all others is (from my point of view) the #1 which is at distance 2 from all other nodes … but the answer of the test is allegedly 2 which is at distance 3 from node 5 and 6 … I dont understand in which world 3 in lesser than 2.

Thanks :stuck_out_tongue:

#76

From the problem description:
Output
The minimal amount of steps required to completely propagate the advertisement.

From your post:
“1 which is at distance 2 from all other nodes … but the answer of the test is allegedly 2”

See your mistake? :grin:

#77

Yup … misread the output :blush:

thx

#78

Hello

I solved this problem 2 years ago in Java, and try to do it again in Python (that i’m learning) with the same algorithm (cut the leafs).
But i’ve a performance issue (as a lot of people), tests 8 and 9 are too slow.
Can someone looking at my code please ?

Thank you

EDIT : by using sets in place of lists the performances are far better and all tests pass

#79

Has anybody managed to do 100% with Javascript?

#80

After spending a day on this I finally reached 100% with Javascript yeah.