khatribiru's blog

By khatribiru, history, 16 months ago, In English,

This Blog is Just the List of Problems for Dynamic Programming Optimizations.Before start read This blog.

1.Knuth Optimization

Read This article before solving Knuth optimization problems.

Problem 1 Problem 2 Problem 3 ( C ) Problem 4 Problem 5 Problem 6

2. Divide and Conquer Optimization

Read This article before solving Divide and Conquer Optimization problems

Problem 1 Problem 2 Problem 3 Problem 4 Problem 5 Problem 6 Problem 7 Problem 8 Problem 9 Problem 10 Problem 11

3. Convex Hull Trick Technique(CHT)

Read This article before solving problem based on CHT.

Problem 1 Problem 2 Problem 3 Problem 4 Problem 5 Problem 6 Problem 7 Problem 8 Problem 9 Problem 10 Problem 11

Note:- Some problems from Divide and conquer optimization section can also be solved using CHT.

Please, share your knowledge and links on the topic.

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

»
16 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Link to Problem 1 and Problem 4 on Divide and Conquer Opt point to the same problem

»
16 months ago, # |
  Vote: I like it +4 Vote: I do not like it

two more problems for CHT :

377E , 91E

»
16 months ago, # |
  Vote: I like it +8 Vote: I do not like it

I think in Divide and Conquer Optimization article there was written dp[i−1][j]+C[k][j] i think it should be
dp[i−1][k]+C[k][j]?

  • »
    »
    16 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Yes You are correct. The fifth line of first paragraph there should be dp[i−1][k]+C[k][j].

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Another one: Ciel and Gondolas

»
16 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Nice Collections , Liked it.

»
16 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Thanks a lot bro . Was searching for something like this . :)

»
7 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Another problem that can be solved using D&C: ARC 067 problem F

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Where can we submit solutions to the above problems from Russian Camp.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

One more problem of Divide and Conquer

http://codeforces.com/problemset/problem/834/D

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

There is also a very cool technique to optimize DP. I have seen it in a Radewoosh comment here and in a recent CSAcademy contest here.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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