## 10564 - Paths through the Hourglass

Moderator: Board moderators

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

### 10564 - Paths through the Hourglass

Can someone post some critical input? I tried tons and tons of cases by hand and it works..
Last edited by Larry on Tue Oct 14, 2003 9:09 pm, edited 1 time in total.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
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``````

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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
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
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:
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-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:
Larry, sorry about my typo ... mine failed 20 0 will all zeroes ...

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Okay, I fixed it. I was outputting the last item on the path incorrectly. Thanks everybody.

BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm
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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
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
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm
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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
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
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

### How to?

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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
I used memoization on grid position and the sum.

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:
Can you explain better? I didn't understand what you mean...

Maybe an example should clarify my mind ;-]

Thanks,

JP.