diego_v1's blog

Overkill?
By diego_v1, 11 years ago, In English

I always suffer from overkill. I mean, using a complex solution in a problem that doesn't require it. It's like killing a fly with a bazooka.

A clear example is the problem "Ladder" (279C). The solution is to check for each element i, the biggest j (j > i) such that the range (i, j] is non-decreasing (call it Inc[i]), and the biggest k (k > i) such that the range (i,k] is non-increasing (call it Dec[i]). Then when a query L,R arrives, just check that Dec[ Inc[L] ] >= R.

Well, I don't usually realize those things (especially on contests, where I don't have too much time to think a better solution), and I end up using more complex things (very frequently segment trees).

For the problem "Ladder" (279C), I used a segment tree that stores for every range [L,R] the number of increasing and decreasing consecutive elements in that range (if a[i] > a[i-1], then a[i] is an increasing element, and if a[i] < a[i-1], then a[i] is a decreasing element). Then, when a query arrives, I use a binary search on that range to search for the rightmost element k such that the range (L,k] has 0 decreasing elements. Then I check the range (k,R], and if it has 0 increasing elements, the range is a ladder, otherwise it isn't. I end up doing in the worst case Q*log(N) range queries in a segment tree, where the problem can be solved in O(N) to make the data, and then answer every query in O(1).

For the problem "Dima and Staircase" (272C), I also used Segment Trees (Yeah, I use them nearly everywhere), when all that was needed were two variables.

Anyway, I was wondering if any of you suffer from the same problem too.

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

»
11 years ago, # |
  Vote: I like it +7 Vote: I do not like it

I used to be an overkiller like you... then I took an arrow in the a knee

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

    I am not going to say I have used a general-graph-match on TCO 1B 1000 ... )

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

It happens with me quite frequently, I used a segment tree for the ladder problem as well. :(

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

It is not a problem which you can deal with it in one day but if you try you can change your mental ability.

→ Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Yeah, I know that feeling. However, codeforces contests often give you the chance to have some overall estimation of the difficulty of a problem. So I could recommend you this:

I know that one always is in a hurry to solve the problem, but I don't think leaving 2 or 3 minutes for pure thinking would be that painful(don't misunderstand this, because I often forget to do that too). If you just think of what is the estimated difficulty of the problem and what solution might exist will help you with these things. At least it helped me...I did the overkill on 272C and was upset with myself that I didn't stop and think for 2-3 minutes. Then I used these tactics for 279C and I was able to think of the simple solution in no time(although I thought of a segment tree initially). As a whole, I think that whatever happens if you are able to solve the problem you should be happy :)

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

Thanks for the replies guys!

Yeah, I usually know that problems A and B are easy, so I try to do the simplest thing, and it always works. I usually overkill problems C/D (specially C). I'm talking about Div 2, obviously.

I'll try to do better thinking from now on :)

→ Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Actually, using hardcore algorithms and data structures is fine. That is, in case you know it well or have it pre-coded. The present tasks in contest programming are made so that just identifying a single algorithm that you need to use is not enough to solve the problem — they often involve more or less of thinking.

Then, it doesn't really matter what you use, or more exactly, if you try an approach that's too complicated, then you just won't get the complexity necessary for solving the task.

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

    I do have segment trees pre-coded, but they always require some modifications, 'cause the information that needs to be on each node is always different.

    If I paste the pre-coded class and tweak it as necessary, it can take as little as 3 or 4 minutes, but if I have to code a segment tree class from scratch (it happens sometimes with special segment trees, like the one used for Lucky Arrays problem), it will take anything from 10 to 20-25 minutes, and that's too much time to spend just coding a class if you're in a contest.

    I have to learn to code simpler and shorter if I want to be able to solve more than 4 problems in Div 2 or 2 problems in Div 1.

    → Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Just overkilled COCI Contest 6 Problem D (BUREK). Used segment tree too. :( I think the next New Year I'll change my handle to overkiller if everything will keep going like this.

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

    Hahahaha! Way to go. Welcome to the group!

    → Reply
»
11 years ago, # |
  Vote: I like it +6 Vote: I do not like it

same here,

I used segment tree to solve http://www.codeforces.com/problemset/problem/272/C

→ Reply