https://www.codingame.com/training/easy/plague-jr
Send your feedback or ask for help here!
Created by @JBM,validated by @Zorg1,@bbb000bbbyyy and @b0n5a1.
If you have any issues, feel free to ping them.
I feel like it should be specified that infection starts at square X.
For precision sake.
I agree. The description should emphasize more that the coder will have to select the best starting pad for the infection. The first rod does not necessarily indicate the best pads.
I’d tend to disagree.
The statement already specifies “Assuming optimal choice for the initial Disease injection”.
I have no idea how anyone could assume infection starts on the first rod, especially with the sentence “You’ll infect one of the pads”. How would you even choose which pad to start with, since the rod links two of them?
Doesn’t the example make it rather clear that infection should begin on pad 1, not 0?
2 Likes
I’m confused as to how to choose the best node to start from. Right now i’m going through all of the pads and checking how many turns it would take to infect all other pads, is there a faster way to do this? I manage to get success on the test cases but the donut validation test runs just a bit to long and times out so i only get 80%.
EDIT: nvm figured out a more efficent way.
Im also stuck on the donut case, keep timing out. Could you give me a hint how you made this more efficient?
This thread can give you some ideas: https://www.codingame.com/forum/t/teads-sponsored-puzzle/918/14
It is from a similar puzzle that has been withdrawn.
1 Like
Guys! There’s no need to find any first node. Tip: every undirected tree has a diameter.
2 Likes
The best way to go about this is to just choose a pad to be selected check its turns to complete, check its neighbors n change the selection to the neighbor with the least turns to complete, repeat until your at the focal point for selected. This way you dont check all pads
1 Like
Did somebody completed it in Python3? I’m practicing that language and implemented (I think) the very same algorithm as in C++. In C++ I got 100% in the validation, but only 80% with python, because Donut Case always fails. I’ve spent a lot of time on it, but I can’t see the reason. It’s not time out, because I measured it with Test Cases, and even Python find the solutions in some ms. Conditions are the same in both languages. Calculations also. Thanks for any hint.
How does finding the diameter help me solve this problem? As far as I can tell that gets me the longest path through the graph and im looking for a vertex in the graph that provides the shortest path. The problem im having is a simpler way then looking at all vertexes looking for the shortest path to find the one vertex to start from. The diameter whould do the opposit.
Diameter: biggest distance between two nodes in a tree. Divide it by 2 and you get the radius. You don’t need to tell which node is in the center. It’s enough if you tell that within the radius you can reach from that node all the other nodes. Radius = solution to this problem.
@E_pur_si_muove In Python, you might need to extend the recursion limit if you’re using a recursive approach.
import sys
sys.setrecursionlimit(2000)
Thank you very much! Now my solution passes all validation tests. 
Seriously, I don’t know how to solve this puzzle fast enough. I tried Floyd-Warshall and repeated Dijkstra, but they can only pass the two first tests and got me a timeout for the other tests…
Can somebody give me some tip ?
There is no distance, Dijkstra is not useful here.
Think different. 
I did it ! \o/ Thanks !
I’ve been spending my days on it for a week, I couldn’t take it anymore! T.T
1 Like
I likewise found it a bit confusing. “Assuming” usually refers to something that you don’t have to mess with, something that is a given. This requires calculating, determining, or finding the optimal choice, not just “assuming” it.
Well… it is a given. You’re given the network structure, and it depends on the network structure only.
You can’t mess with it either.
You’re not told its value, so you might have to compute it on your own if you want to use it, but it’s not a part of the expected answer, so there’s really no reason for the statement to hold your hand that much.
Sorry for stupid question, but I only start to study programming. So, can You help me, where I can read about this theme. I can’t effective search because it’s too new for me.
Thanks!