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

Автор Petr, 10 лет назад, По-английски
  • Проголосовать: нравится
  • +85
  • Проголосовать: не нравится

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

What is your thought on last problem(25 pts). Was it easier(on your perspective) than the 25pts problem(second last) you have tried to solve?

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

    I didn't know how to solve it during the round, and solving it requires coming up with a non-trivial hypothesis (that the only operation we need to do with regard to the canals is to take some prefix, level it, then join with our region) and either proving or trusting it. This hypothesis did not even occur to me, so I was quite far from solving it. I think this problem is conceptually much harder than the fourth one.

    • »
      »
      »
      10 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks and wish you better luck next time. And one more question, well using C++ over java would have solved your solution in time? For example Rockethon problem F which was really difficult to optimize it in java. UPD- Rubanenko asked the similar question

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

    My view is that the last two problems have similar difficulty levels, but he had to make a choice of which problem to think about (it doesn't do you any good attacking multiple problems at once), so he didn't think a lot about the last one. It's not something you see instantly, but after doing some cases by hand you eventually come to the prefix conclusion. (I'm operating under the assumption that if I could see it, then Petr would see it too).

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

Why haven't you chosen C++ rather than Java when you were not sure about the speed of your solution?

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

    Well, initially I was quite certain it would pass, but the solution turned out a bit more complicated and thus slower. Also, I'm coding much much slower in C++ and thus might not have finished the problem in time. And finally, I'm not certain that C++ would help here — the slow operation is long division (needed to multiply two longs with "cap"), and that's probably implemented simiarly in C++ or Java. Maybe using a 64-bit compiler would help more actually :)

    • »
      »
      »
      10 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      By the way, what do you do in order to make Java run as fast as possible locally?

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

        Not much. I create 3 threads, but that's about it. In fact, I'm making it run slower by using Cojac to catch integer overflows :)

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

          In fact, I'm making it run slower by using Cojac to catch integer overflows :)

          You are looking as Michael Schumacher fastening seat belt :)