Introduction
The algorithm is very interesting. Julia has to find one of algorithms to work on and make some points. Start from one extra point first, now is 4/29/2017 12:50pm.
Julia wrote a brute force solution and sample test case of "7 people are happy out of 10" is timeout. At least Julia started to write the code and understand the problem now. It is 2:04 pm, almost 60 minutes later.
One of ideas to solve timeout is to use dynamic programming. Need to figure out the recurrence formula next step.
In general, we only need to make sure that at most n - k are not happy, but we do not too much detail.
Coding in the contest
Follow up
After the contest, Julia published her code using recursive solution. Link is here. Score is 0, timeout all the test cases. But it is a great workout for recursive solution.
Julia did think about the dynamic programming in the contest, she tried to build recurrence formula. She almost had the same idea showed in the editorial notes. But she did not write down the detail.
It is a good idea to write down the dynamic programming thinking process, and post the algorithm on the code review later on. It is not hard, for a mathematics major, all Julia has to do is to start to practice again the mathematics analysis. She will figure out what to do next after the contest, how to train herself better.
No comments:
Post a Comment