Noble_Mushtak's blog

By Noble_Mushtak, history, 8 years ago, In English

After the contest, I read other people's solution to Vacations and people kept using big dynamic programming arrays on Div. 2 Problem C, which confused me, so I decided to show all of you that this was unnecessary by solving this problem using only one uint_32 variable in C. Using bit fields in a struct, we can get this down to only three bytes.

The intuition behind this solution is that you only need to keep track of what is possible from the day before and if nothing is possible, then you have to rest this day and everything will be possible the next day. I think it's kind of a greedy algorithm because unlike the DP algorithms, which seemed to take into account solutions where we rest early in order to do something the next day, this algorithm does something on every day when it can and rests only when it finds that it needs to. I do this because whether or not we rest early or the day after when we have to is irrelevant: We still end up resting one day, so the answer is the same. Thus, no dynamic programming is necessary and we only need to keep track of one answer at every point.

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

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

Yes, you are right about memory usage, but I think a DP solution is more easy to code and think like it. I don't like the DP algorithms the first time too, but now I see more problems easy using DP and DP optimizations( Knuths , CH trick, and so on). Anyway, congratulations... you solved the problem. (Sorry for my poor English)

  • »
    »
    8 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    I am definitely not as experienced with dynamic programming as I am with greedy algorithms, so this is a good point! Usually, with these kinds of problems, I sometimes get stuck, but with this problem, once I realized that whether or not you rest earlier or later doesn't matter, I stopped thinking about the problem and immediately coded up a short solution so I could start hacking.

    Also, what is the CH trick? I have never heard of either of these algorithms, but I found something on Quora about Knuth, but I couldn't find anything about CH (unless by CH, you meant "convex hull"). Can you please link me to an article about it so I can learn about this? Thank you so much!

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      Several DP problems also have a greedy solution. I was good finding those solutions, but they take me a lot of time. Now with DP approach I solved several problems more quickly. I think you must choose your approach for each problem. About the CH, i leart it here . I hope it helps you. Happy Coding! (One more time... Sorry for my poor English)

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      You can find a good tutorial about convex hull optimization here: http://wcipeg.com/wiki/Convex_hull_trick

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

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

(The update was adding the solution with a struct that was only three bytes.)