i_am_eating_wa_and_tle's blog

How to learn Divide and Conquer strategy??????
By i_am_eating_wa_and_tle, history, 8 years ago, In English

In the Editorial "Divide by Zero and Codeforces Round #399 (Div. 1+2, combined)" the problem setter said PROBLEM B can be solved easily by using DIVIDE AND CONQUER strategy. How to learn this strategy????

  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
8 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Just play a lot.

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

Usually in the problems of divide and conquer you should divide the problem into several similar and disjoint parts, can be in two equal parts, and find an interesting property in the middle so that you can continue reducing the problem, or joining these parts to have a final result, i.e. if you build a convex hull with a divide and conquer approach, you would first think about dividing it in half, and you suppose you can build the major convex hull with the two parts, then The serious question is: how would you do to join them?, there is a form with complexity O(n),

thus obtaining an O(nlgn) algorithm, since time is T(n) = 2*T () + O(n), but I will not end this. Instead if I want find the square root of x, then I can search: "The greatest number v such that v * v <= x", so if I analyze in the middle of the interval [0, x], v = , then this may be my answer or it can be  < , in the first case I continue whit interval [0, ()] and otherwise in the interval [(), x], so I just look at O(log(n)) intervals. The execution time is T(x) = T() + 1, then T(x) = O(log(x)).

In the problem B, you divide the problem of the interval [1, 2k - 1] where k is the most significant bit plus 1, i.e if n = 8, then k = 4. In the intervals [1, 2k - 1 - 1] and [2k - 1 + 1, 2k - 1] and I verify in the point {2k - 1}, where it should be the first bit of n, and add this if is in the range [l, r] and continue...

My English is not the best, I hope it has been understood.

my submission: http://codeforces.net/contest/768/submission/24854078

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

    of course, if you analize the interval [a, b] and is disjoint to interval [l, r], then return, this it is very important to complexity...

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

Thanks for your comments. Now I have realized how to deal with that.

→ Reply