Блог пользователя LeBronJamez

Solution to IOI 2014 Rail
Автор LeBronJamez, история, 9 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +16
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        9 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

        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)

        → Ответить
        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

          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 !

          → Ответить