One 32-Bit Variable Solution to Contest 363 Div. 2 Problem C:

Revision en2, by Noble_Mushtak, 2016-07-20 04:28:22

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.

Tags #363 (div. 2) c, dynamic programming, greedy, memory manipulation

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Noble_Mushtak 2016-07-20 04:28:22 133
en1 English Noble_Mushtak 2016-07-19 21:36:57 1155 Initial revision (published)