Petr's blog

A link/cut week
By Petr, 10 years ago, In English

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

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

»
10 years ago, # |
  Vote: I like it +33 Vote: I do not like it
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.

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +54 Vote: I do not like it

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

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

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

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

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

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

      ""thinking >> coding" TopCoder rule." — hehe, funny, good one :))

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

    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.

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

      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.

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

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

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

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

    → Reply