OnurYildiz's blog

By OnurYildiz, 6 years ago, ,

everyone can compete in IOI 2013 now http://compete.ioi2013.org/

• +16

 » 6 years ago, # | ← Rev. 2 →   +12 The judge is compiling my submissions over 60 minutes. Is it just a problem with me?
•  » » 6 years ago, # ^ |   0 same here.
•  » » 6 years ago, # ^ |   +142 It's simulation of Australian ioi)
 » 6 years ago, # | ← Rev. 2 →   0 I have a execution time out of many tests. I generate a biggest tests and i have no problems on my machine... Is there someone with that problem?
•  » » 6 years ago, # ^ |   +4 This is IOI... there are many test cases aimed on making some solutions with average complexity sufficient but worst case insufficient. It's likely that your solution is one of those — it works fine on random tests, but a specially prepared one might make it TLE.
 » 6 years ago, # |   0 I have found one solution in task dreaming, but it wrongs on 3-4 tests from each subtasks and i cant find my mistake...Solution: From each component i find the middle vertex ( the vertex which is nearest from its farthest vertex ). I think that the optimal answer is when we connect a middle vertexes from each component to middle vertexes from one of two components with most bigger distance. In this case the answer is L + distances from these two components. But if we connect all middle vertexes to other vertex ( not these two with most bigger distance ) — the answer is 2 * L + two components with most bigger distances. Because of we connect the two most bigger components to other vertex and distance increase with L.I cant found what is incorrect in this solution.. Someone have a idea?
•  » » 6 years ago, # ^ |   0 How do you work around a case when you have a path of length 5 and an isolated vertex and all edge weights equal to 1? It's clear that the optimal solution is joining the center of the path and the isolated vertex, yet this has diameter 4, not 3.
•  » » » 6 years ago, # ^ | ← Rev. 3 →   0 I connect an isolated vertex to the center of the path and with a dfs i find the longest distance in graph, which is 5.
•  » » » » 6 years ago, # ^ |   0 Sorry, 5 not 4. But if you're checking the answer after forming the graph, I don't see what's wrong there.Your ideas seem to be correct, as far as I understand. You connect all middle vertices with the one for the tree with the largest distance (not sure if this is what you meant).There might be a bug in your code or you don't check some special case, I don't know.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +4 Do you consider the case when the answer is max(maximum distance from a vertex to another, if those 2 vertexes are in the same connected component)? If you have a tree like this: N = 6 (1-based), M = 4, L = 1, an edge from 1 to 2 with cost 10, an edge from 2 to 3 with cost 10, an edge from 4 to 6 with cost 1, an edge from 4 to 5 with cost 1.If I understand well, you connect these 2 components with an edge from 2 to 4 with cost L = 1. The answer is not 10 (max dist from node 2) + L + 1 (max dist from node 4) = 12. The correct answer is 20, the distance from node 1 to node 3.
•  » » » » » 6 years ago, # ^ |   0 My answer is also 20. I connect 2 and 4 with an edge. After that with dfs i calculate the longest distance. I have written this formulas above to prove that is always better to connect all the middle vertexes with a middle vertex with the max distance.
•  » » 6 years ago, # ^ |   0 sometimes the diameter of the tree is in a pre-existing compenetHow do you answer this case: 1 2 10 2 3 10 4 5 1 L=1 
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 Connect 4 or 5 with 2, and the answer is 20. Maybe is something wrong in my code, but my time expired...
•  » » » » 6 years ago, # ^ | ← Rev. 3 →   +3 ok.I think that the optimal answer is when we connect a middle vertexes from each component to middle vertexes from one of two components with most bigger distance_ __sometimes connecting the centers with the node that has second maximum distance is not optimal , you should connect the centers with the node that has maximum distance
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 I'm connecting with the first maximum, but why the second is not optimal? When you connect all middle-vertexes with second maximum — the first maximum is included also. The smaller maximums are out of the game, because their sum is always smaller than two of the most bigger. I think that the possible answers are always two ( if you connecting two of most bigger distances with L, or you connecting them to other vertex and the answer is increasing with L ).
•  » » » » » » 6 years ago, # ^ |   0 1 2 100 3 4 2 5 6 1 L=5 
•  » » » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 You are right! Thanks for the explanation :)
•  » » » » » » » » 6 years ago, # ^ |   0 The wrong was in my source... Now I have 100 :)
 » 6 years ago, # |   0 What kind of data structure is needed to obtain full score on Problem "Robots" ? I think it shouldn't be too fancy. My solution passed the first 4 subtasks with a time complexity of O(T * (A + B)) using only plain arrays as data structures.
•  » » 6 years ago, # ^ |   0 I only used STL structures. This is not a task focused on data structures, but on algorithms.
•  » » » 6 years ago, # ^ |   0 Thank you. It seems that my 90-point solution is different from the intended 100-point solution for this task and thus can't be improved.