OnurYildiz's blog

compete in IOI 2013
By OnurYildiz, 11 years ago, In English

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

  • Vote: I like it
  • +16
  • Vote: I do not like it

»
11 years ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

The judge is compiling my submissions over 60 minutes. Is it just a problem with me?

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 2   Vote: I like it +4 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    sometimes the diameter of the tree is in a pre-existing compenet

    How do you answer this case:

    1 2 10
2 3 10
4 5 1
L=1
    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Connect 4 or 5 with 2, and the answer is 20. Maybe is something wrong in my code, but my time expired...

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 3   Vote: I like it +3 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          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 ).

          → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I only used STL structures. This is not a task focused on data structures, but on algorithms.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply