Mine quite straightforward realization works about 1 sec. and uses almost 60 megabytes of memory. Please, give an idea how to solve it more quickly...

Edited by author 17.03.2010 14:10

Struggled with WA2/WA4 for a lot of submits. Tricks are tracking min-length and even then getting least possible value can be tricky. My solution is DP(900*8100)*9 to get minimal length. Then greedy BACKtracking from higher to lower using least possible digit (so you get as many '1' as possible, then as many '2' and so on) over edges that follow minimal length path. As for memory - two arrays of uint8_t. That's 14Mb. You can also sacrifice backtracking array, and perform it on the fly during generating output, would be bigger runtime, but half the memory.