Teads.TV

Initially I’ve solved the problem using graph Data Structure, and finding the leaf node (or) last neighbour from each node, and given the minimum of all nodes value, but it fails because of Time.

So i have modified to use Matrix and after long time, it reduced to or came similar to All Path Shortest Path. But it gives me less value than actual result. Fails from Test case 4 (also processing Time Out For Testcase 5).

What am i missing? or any clues?

Try to use existing thread even if it’s in another language, because moving your topic provoke bugs in the order of the post like above.

And english is the main language here, french is just tolerated, don’t hesitate to put stuff in english even in french topic :wink:

Because one of the tests declares a large amount of edges (~52K) using an adjacency list to represent the graph is much better than the adjacency matrix as you will get an OutOfMemory exception with the matrix.

The algorithm is quite simple, all you need is iteratively playing with leaf edges (or nodes)

Adjacency list also fails for test cases as its taking too much time, and thats why i went for matrix as optimization. I’ve used python, with objects. does that causes overhead in running time?

My solution is in Java and if adjacency lists didn’t work for you in Python then it’s either an issue with your algorithm or in the way how large data sets are handled/accessed in Python.
If I were to store the 52K nodes in an adjacency matrix using one byte for each node then, unless using a sparse matrix structure, I would need ~2.5GB of heap.

Anyway, it was just a recommendation - feel free to use any approach that works for you.

Hi I am using python too, but I am using a dictionary to implement the adjacency list, so if I am given the next edges:
1 2
1 3
2 4
2 6
4 5
I would have the next dictionary:
{1:[2,3], 2:[4,6], 3:[1], 4:[5], 5:[4], 6:[2]}

Update: yes I missed some children in 2 and 4, it is like you wrote:
{1:[2,3], 2:[1,4,6], 3:[1], 4:[2,5], 5:[4], 6:[2]}

is it optimal or there is a better implementation? I having problems to pass the last test.

It depends on how you are coding the solution, but your idea of dict is good.

Because the graph is not oriented there seems to be a bug in your implementation. The list should look like:
{1:[2,3], 2:[1,4,6], 3:[1], 4:[2,5], 5:[4], 6:[2]}

Hey there,

Can anyone tell me, if there is at least one 100% solution submitted using Dart as programming language?

Is A* the for this puzzle to much as an algorithm and should I try with another one?

Thanks in advance!

Are you sure that A* (or Dijkstra) is the good idea?

I’ve only managed to get 7/10 and I would really like to get 100% so if you had any advice that would be great! My algorithm requires going through all the values twice and I think that could be what’s slowing me down. Is it possible to reduce this?

Also I’m storing the connections using 2 lists (so list1[x] and list2[x] have a connection). Should I switch to a dictionary? Is that more efficient?

I’m using Python.

Well, now that you’re asking, seems to be kind of an overkill here…

Get the following execution times:

1: 21ms
2: 16ms
3: 30ms
4: 64ms
5: 200ms
6: 1897ms
7-9: timeout
10: wrong result

Guess I have to try sth different :wave:

You should both read again this thread. :wink:

1 Like

Did it, guess @int33h said it all :smile:

two bugs on submit:

  1. submit page formatting is puny
  2. a lot of “company not found” error messages

@bvs23bkv33 me too…

Hi @bvs23bkv33, @ronlobo,

Except for the page formatting which can have issues at times (not always, that’s the trick…), we are not able to reproduce the “company not found” errors.

Could you send a screenshot and scenario at coders@codigname.com? (Browser?, are you logged-in when submitting?, when does the error occur?).

Thanks for reporting the issue,

@XorMode seems to happen in latest Chrome, see attached screenshot.

Hmm, tried to upload the screenshot as .png, yielded ‘Sorry, there was an error with your upload…’.

2 seems to happen, when refreshing the session or opening the laptop after standby?

Using the external editor Chrome plugin when submitting.

Hope that helps to replicate it :ship:

Hey @nicolas_patrois,

Now I rewrote it with the following results:

1: 19ms
2: 17ms
3: 20ms
4: 26ms
5: 37ms
6: 50ms
7: 70ms
8: 209ms
9: 276ms
10: 21ms

Much better than the first approach, every test works, but…

On validation, test 6 fails :heavy_multiplication_x:

So, your implementation is faulty. :wink:
Which test is the sixth?

1 Like