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

A link/cut week
Автор Petr, 10 лет назад, По-английски

http://petr-mitrichev.blogspot.com/2014/09/this-week-in-competitive-programming.html

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

»
10 лет назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится
In this particular problem sqrt-decomposition means splitting all queries into blocks of sqrt(n), and shrinking the tree to only contain interesting vertices for each block of queries.

I finally understand why sqrt-decomposition works in this problem.

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

I think TopCoder will be ruined with those data structure problems :(

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

    Can't believe what I saw when I opened 1000 . ... Anyway back to 2200... Thank to Link Cut Tree !!

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

    In general you are right, but this very problem satisfies "thinking >> coding" TopCoder rule.

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

    those data structure problems

    There haven't been that many, though. And this one is not a DS problem, because there's a simple fast code that doesn't require any DS.

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

      It is not that way of think things. Yes, it do have simple fast code doesn't require and DS, but also it have a Ctrl+C Ctrl+V solution which involve no thinking. This is the part I dislike.

      Actually,just speaking of data structure problem, I might be one of the best competitor, but this is not because how smart I am, simply because I am a representative Chinese OI competitor which trains REALLY A LOT of them. I can code a LCT under 10 minutes when I was young(well, 1 or 2 years ago when I am still in High school).

      But why I hate them? Algorithm Contest is a place where you can have fun when use your brain, Ctrl+C Ctrl+V is not that fun.

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

        Umm... I might be too radical, (If TopCoder is full of DS problem I think I can easily get a rating of 3600, just joking ...)

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

    So you can start writing problems for TC to save it, I mean, non-DS problems. :)

    → Ответить