Блог пользователя khatribiru

Автор khatribiru, история, 8 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +199
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

two more problems for CHT :

377E , 91E

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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]?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Another one: Ciel and Gondolas

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Nice Collections , Liked it.

»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

One more problem of Divide and Conquer

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Fresh problem. Can be solved with CHT.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thanks

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

From Codechef Long Challenge July19 Can be solved using CHT