tag:blogger.com,1999:blog-29632375.post5246847713765299733..comments2024-06-25T13:05:10.432-07:00Comments on vexorian's blog: Google Codejam round 2 - yay!Unknownnoreply@blogger.comBlogger2125tag:blogger.com,1999:blog-29632375.post-88734456110237858152012-10-10T18:54:31.688-07:002012-10-10T18:54:31.688-07:00que buen analisis el que le haces a estos problema...que buen analisis el que le haces a estos problemas del codeJam que nunca la pone facil...saludoscarlos ariasnoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-29764514578726967292012-05-28T12:36:24.897-07:002012-05-28T12:36:24.897-07:00Just read the analysis and noticed that A allows y...Just read the analysis and noticed that A allows you to go backwards. Yet my solutions don't go backwards. It is not a important fact for A-small, because the f(i,j) function can be turned into a graph easily. But for A-large it matters.<br /><br />Well, just need to proof that going backwards is never going to improve your chances to reach the best vine:<br /><br />Imagine you are in vine i, and that you can go backwards and then return to increase the length of the i-th vine. If that is possible, then there is another vine k, that is reachable from vine i (with its current length) and that allows you to reach i at a larger length. But if k can be reached backwards from i, then there should be a path that allows you to directly go from 0 to k with a length as large or larger than needed. Ok... the proof goes like that.<br /><br />I was really lucky for not noticing that the statement allows you to go backwards :)vexoriannoreply@blogger.com