LeBronJamez's blog

Solution to IOI 2014 Rail
By LeBronJamez, history, 9 years ago, In English

Hi, can anyone share a solution to IOI 2014 Rail? I checked the official solution (http://www.ioinformatics.org/locations/ioi14/contest/day1/rail/rail-solution.pdf), but it does not specify how to handle each case, it only mentions them.

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

»
9 years ago, # |
  Vote: I like it -17 Vote: I do not like it

http://www.ioinformatics.org/locations/ioi14/contest/day1/rail/rail-solution.pdf

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

    That's the link I posted. As you can see, it doesn't explain in detail how to handle each case...

    → Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Why downvotes ? It's true that the official solution isn't explained in lots of details.

The only other link I can give you is Bruce Merry's blog. It is pretty cool, but you'll need to be concentrated because he also doesn't give lots of details (though he explains everything you need).

If you're completely stuck, you can PM me and I'll send you an AC code.

But try to do it by yourself first :D

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

    Thanks for the response!

    I have already seen Bruce Merry's post, but I stumbled upon his first observation:

    1. d(X, Y) < d(X, 0): these are reached directly from station X and of type C, so we can locate them exactly. (where X is the station closest to 0)

    Say we have for example the following railway (0)CCCCCCCCD(X)D(Y). d(X, Y) < d(X, 0), but Y is of type D, and cannot be reached directly from X.

    Is there anything i am missing here?

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

      Actually, you don't have d(X, Y) < d(X, 0). In your case, d(X, Y) = d(X, 0) + d(0, Y) > d(X, 0)

      Did you understand well how the distances are defined ?

      These aren't the physical distances but rather the railway distances.

      So, here, d(0, Y) < d(X, Y) while X and Y are adjacent on your scheme.

      Read the statement again, I think you misunderstood it.

      EDIT: this is actually false, check my other message :-)

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

        I don't think the formula d(X,  Y)  =  d(X,  0)  +  d(0,  Y) is correct in this case. I mean, If you want to go from Y to X, you don't have to move to point 0 to turn, there are other C stations closer to Y:

        (0)CCCCCCCC(Z)D(X)D(Y) d(X, Y) = d(X, Z) + d(Z, Y)

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

          You are completely right :D

          I answered without reading my code and I had forgotten this.

          I think that bmerry is wrong for that point. In fact, I didn't get AC the first time I submitted, and it was because I processed wrongly these railways.

          So, well done, you understood the question perfectly ^^

          Anyway, I marked these points as "left" and I used them like the other points at the left of X (so, strangely, I consider your Y as a "left" station !)

          Then, the technique explained by bmerry works well (checking if C are at the right place or not), so you should use it, and you should get a wonderful 100 / 100 !

          → Reply