Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Petr's blog

By Petr, 7 years ago, In English
 
 
 
 
  • Vote: I like it
  • +65
  • Vote: I do not like it

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

»
7 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 :(

  • »
    »
    7 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 !!

  • »
    »
    7 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.

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

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

  • »
    »
    7 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.

    • »
      »
      »
      7 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.

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

  • »
    »
    7 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. :)