Petr's blog

Fox Weeks
By Petr, 9 years ago, In English

http://petr-mitrichev.blogspot.com/2015/03/this-week-in-competitive-programming_7.html

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

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

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?

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

    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.

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

      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

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

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

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

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

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

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

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

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

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

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

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

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

          You are looking as Michael Schumacher fastening seat belt :)

          → Reply