khatribiru's blog

Dynamic Programming Optimizations ( Problems )
By khatribiru, history, 8 years 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

Comments Comments (23)
| Write comment?
»
8 years 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

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

two more problems for CHT :

377E , 91E

→ Reply
»
8 years 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]?

→ Reply
  • »
    »
    8 years 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].

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

Another one: Ciel and Gondolas

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

Nice Collections , Liked it.

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

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

→ Reply
»
7 years 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

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

One more problem of Divide and Conquer

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

→ Reply
»
7 years 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.

→ Reply
»
7 years 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).

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

Fresh problem. Can be solved with CHT.

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

Thanks

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

From Codechef Long Challenge July19 Can be solved using CHT

→ Reply