10564 - Paths through the Hourglass

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

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

Post by Larry » Mon Oct 06, 2003 10:54 pm

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

Post by Per » Mon Oct 06, 2003 11:01 pm

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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Tue Oct 07, 2003 12:00 am

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:

Post by turuthok » Tue Oct 07, 2003 2:57 am

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:

Post by turuthok » Tue Oct 07, 2003 3:00 am

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:

Post by Larry » Tue Oct 07, 2003 7:22 am

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:

Post by Larry » Tue Oct 07, 2003 7:44 am

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

Post by BiK » Wed Oct 08, 2003 7:51 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:

Post by Larry » Wed Oct 08, 2003 9:35 pm

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

Post by Per » Wed Oct 08, 2003 9:59 pm

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

Post by BiK » Thu Oct 09, 2003 10:31 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

Post by Per » Fri Oct 10, 2003 1:03 am

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?

Post by jpfarias » Sun Oct 12, 2003 3:11 pm

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:

Post by Larry » Tue Oct 14, 2003 9:10 pm

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:

Post by jpfarias » Wed Oct 15, 2003 12:13 am

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

Maybe an example should clarify my mind ;-]

Thanks,

JP.

Post Reply

Return to “Volume 105 (10500-10599)”