[Community Puzzle] Plague, Jr


#21

Considering the puzzle tags, I suggest you look into the basics of graph theory


#22

Hi,
please don’t give the solution, you’re hint was very good and let people search.
Thank you


#23

Hello all,
I tried this puzzle in C and passed all the tests, but 0% when I submitted my code.
I went into the contribution section and hit the ‘test in IDE’ button to run both tests and validators: I pass them all.
I don’t have this with any other puzzle, so far.
Anyone knows this, please?
Thank you


#24

IDE tests are run in debug mode and validators in release mode. We’re assuming you have a memory issue.


#25

You may be right, thank you.
I use ad-aware browser no more supported with hundreds of tabs, and my computer is on for days. Despite, memory usage is 55% and swap usage 30%, and still I can submit my code for other puzzles. Anyway, I’ll switch it off and try again later, I’ll let you know if it continues.
Thank you


#26

An accurate description is not “holding your hand”. The other puzzles on CodinGame, for the most part, have clear, accurate descriptions. “Assuming” an ideal starting point is not as clear as, for example, “Out of all possible starting points…”


#27

LOL :rofl:
I spend enough time correcting them to have a fair idea of the general level.

In any case, thank you for writing out your rewording suggestions. I don’t wish to merge it in the statement, but they’ll certainly help someone by being here.


#28

In other words, you prefer to keep a less accurate description even when you see that more than one person has to come here to clarify.


#29

“Less accurate” is merely your opinion, I’m afraid. You might share it with 3 people in this thread, but it was fine for myself, all three independent moderators who approved it, and the 130 other CodinGamers who solved it. The arguments you used in your debating here, for now, have only comforted me in my opinion.

Let it be clear that I do think it’s less clear. And that’s the point.


#30

My solution is essentially just performing a BFS on each of the nodes to find the one that requires the smallest depth to traverse them all. With BFS, you should most likely be using the deque from the collections package so that you can push and pop from opposite ends of the queue in an efficient manner (it’s a doubly linked list).

Another trick is to keep track of the smallest depth found thus far, and short-circuit any “trials” that reach that depth because you know they won’t be any shorter and can thus continue to another node to start from without fully simulating a longer infection.

Essentially:

  • Keep track of current min
  • For each node:
    • Simulate infection with BFS
    • While simulating, if infection nights >= current min, stop
    • Otherwise, current min = infection nights
  • Tada

#31

This puzzle reminded me of the Teads sponsored medium training puzzle that I solved 2 months ago. While I don’t find that puzzle on the site anymore, I have the saved the code.
Interestingly it tests/validates to 80% without any modification at Plague Jr test, but with “advanced case” I find graph diameter of “10” vs the expected answer of 13.
Now I am stuck: I don’t find the real difference between the two puzzle problems and I don’t understand why 13 is the answer to this case (though I admit I did not draw the graph of 999 vertices).
Any hint from experts?


#32

The Teads puzzle disappeared (was a sponsored one).
So JBM made a completely new puzzle without any reference to possibly existing ones :smiley:
I would guess, that your solution to the original Teads had a bug not covered by the given testcases back then.


#33

Hey I’m completly stuck … solved all cases but the advanced one. I’m finding a solution in only 5 nights instead of 13… what am I doing wrong ? I’m using a tree diameter method.


#34

Why can’t I use networkx ? It complains with ModuleNotFoundError: No module named ‘networkx’

Isn’t it pretty standard ?


#35

@thanos.a Your question is not specific to this puzzle and you should mention the language when asking such a question (Python). The available libs are listed in the FAQ. networkx is not particularly “standard” and solving puzzles by calling libs that do all the job to the rescue is arguably not very interesting.


#36

Thanks a lot for the suggestions and the link.


#37

Thank you - recursion limit was stumping me