tag:blogger.com,1999:blog-29632375.post1687045670662775562..comments2024-06-25T13:05:10.432-07:00Comments on vexorian's blog: SRM 596: Lack of speed will kill youUnknownnoreply@blogger.comBlogger1125tag:blogger.com,1999:blog-29632375.post-49428464665648332292013-11-02T11:25:39.543-07:002013-11-02T11:25:39.543-07:00Hi! Here is my greedy solution for 250, together w...Hi! Here is my greedy solution for 250, together with a short explanation.<br /><br /><br />At first, let's think about a single number only. What is the best strategy for it? Well, when we have 2 different sequences S1 and S2 of increments and doubling, then if they are of the same length, the better one is the one with more doublings. This is because doubling takes as much as an increment, and may help with other numbers as well.<br /><br /><br />Let's also notice, that it is impossible, to have 2 sequences S1 and S2 which lead us to a specific number, where in S1 we have more doublings then in S2 and the length of S1 is more then S2. This is because an increment can not increase a number by more then doubling, so S2 has to have at least as many increments as S1 + the difference in doublings.<br /><br /><br />From the above 2 observations, we have that the best way is to choose for each number a sequence, which is the shortest and with the maximum number of doublings (among the shortest sequences). Such sequences will have maximum number of doublings at once.<br /><br /><br /><br />After we choose the best sequence for each number, the result is the sum of all increments plus the maximum number of doubling in any sequence. This is an easy observation because of how the doublings are possible to perform so that each number is doubled only the number that is specified.<br /><br /><br /><br />How to find the best sequence for a number? This can be done by Dynamic Programming: For each number n from 1 to 1000, just update the best solution for n+1 and 2*n.Mikinoreply@blogger.com