topovik's blog

Divide and Conquer optimization
By topovik, history, 4 years ago, In English

Hi for everyone.

At this blog I want to offer you some tasks on D&C optimization.

About this algorithm you can learn here.

When you can use this and other DP optimizations you can learn at this blog.

Some tasks on D&C optimization.

834D - The Bakery

673E - Levels and Regions

321E - Ciel and Gondolas

868F - Yet Another Minimization Problem

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

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

I think that it is quite hard to solve 321E with D&C Optimization because the runtime is multiplied by 2. I tried several times and barely passed the time limit. I think there are very fast solutions to this problem but I am not sure if they used D&C optimization.

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

    Author solve uses D&C optmization, so you can read this here

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

      Well, the runtime is now multiplied by 2 due to change in servers. So I am not sure if the author's solution can pass so easily this time.

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

        How do you solve it without this optimization? I had to do some dumb input reading tricks to get AC.

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

Did you solve these tasks? These will be useful after you solve tasks and can tell about idea of these tasks

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

https://codeforces.net/contest/1175/problem/G this task can't be solved using D&C optimization (Um_nik wrote it during the contest and get WA). Yes, here can be used D&C but it is another approach.

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

Auto comment: topic has been updated by topovik (previous revision, new revision, compare).

→ Reply