10564 - Paths through the Hourglass

[Larry]

Can someone post some critical input? I tried tons and tons of cases by hand and it works..

[Per]

Not very critical, but anyway:

Code: Select all

6 60
3 5 1 7 0 9
2 6 9 7 4
0 5 3 9
3 7 6
6 8
5
1 7
4 1 5
2 6 4 5
4 2 1 7 4
3 1 6 8 8 5

Answer:

Code: Select all

34
1 RRRLRRRRRR

Perhaps slightly more interesting: for an hourglass with n = 20, s = 39, consisting only of ones, the answer is

Code: Select all

274877906944
0 RRRRRRRRRRRRRRRRRRRLLLLLLLLLLLLLLLLLLL

[Larry]

Thanks.. I was naive enough to use int for some reason, so I fixed the 20, 39 case, but still WA.. =( any cases that are very sensitive to which case to display first?

(Mine works for your first case too..)

[turuthok]

Larry, what if 20 and 39 ... with all zeroes instead of all ones.

I know I failed this one but passed the all ones (I think).

-turuthok-

[turuthok]

Larry, sorry about my typo ... mine failed 20 0 will all zeroes ...

-turuthok-

[Larry]

Still got the same thing.. hrmmm.. I also tried it with 9's and 351, and still the same thing..

My basic algorithm is basically recursion + caching, with saving the first path, since I do them in lexo order, should be okay..

[Larry]

Okay, I fixed it. I was outputting the last item on the path incorrectly. Thanks everybody.

[BiK]

Hi Larry,

my algorithm is also using recursion and hashing. I calculate the sums of the paths in the lower part of the Hourglass and store them using STL's map. As a key I use the sum along the path and with it I associate the number of paths with that sum and the first path I found (since I also enumerate the paths in lexicorder).

In the second part of the algorithm I enumerate the paths in the upper part of the Hourglass and try to complement the sum along the path with a sum from the map.

My program outputs correct results for all input I tested but the OJ says TLE. Help me to speed up the program. I think that this is the idea of the solution.

[Larry]

Mine ran in .25, and i basically use the same thing. My guess is that STL is that slow, since I did it in C. I cache on cell and sum, since sum can be at most ~360, so ya.. hope that's enough.. =)

[Per]

It's not STL per se which causes the TLE, but rather the use of maps.

There is no need whatsoever to use a balanced search tree (i.e. a map) for this problem, you're better of with a vector. maps have a lot worse constant factor than vectors.

[BiK]

I don't know for what reason I decided to use a map. I could index a vector or even an array instead. Now everything is OK (I also found some bugs in my program).

However I didn't know that the map is organized as a balanced search tree. I thought that a hash table is used. So my intention was to use the map exactly as a hash table. So is it true that actually there is no container in STL which I could use as a hash table? Of course SGI provides the hashmap class with their implementation of STL but it is not included in the standard. So the OJ denies it.

[Per]

I've used the hashmap class in several of my solutions (though the last time was a while ago). Have you really tried this, or do you assume it just because it's not part of the standard? Because in that case, there must have been some change of compiler and/or flags.

But to answer your question: no, in STL by the book, there is currently no container which is guaranteed to work like a hash table (in terms of complexity).

[jpfarias]

Can anyone explain me how to solve this one?

I'm thinking on it a lot and I yet could not find a way to solve it... May be you can give me some tips on how to solve this one...

Thanks,

JP.

[Larry]

I used memoization on grid position and the sum.

[jpfarias]

Can you explain better? I didn't understand what you mean...

Maybe an example should clarify my mind ;-]

Thanks,

JP.