10912 - Simple Minded Hashing

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

Moderator: Board moderators

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Post by jan_holmes » Sun Jun 24, 2007 9:06 pm

length is the current length, right ? and what is level ? Thx

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by asif_rahman0 » Sun Jun 24, 2007 9:14 pm

jan_holmes wrote:length is the current length, right ?
ya
....and what is level ? Thx
level means length here, also.

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Post by jan_holmes » Sun Jun 24, 2007 9:41 pm

argggh... yes... got several WA and TLE because of my stupid DP implementation :oops: thx asif_rahman0 :D

JC1
New poster
Posts: 4
Joined: Thu Jul 20, 2006 11:02 pm

Post by JC1 » Wed Aug 15, 2007 4:26 pm

I've got AC a couple of times, but I'm not happy with my time. First I tried recursion with memoization for 3.6 seconds. Then I filled an array directly, using DP, and it took 4 seconds to get AC. Even worse. :( Maybe I'm doing unecessary calculations. Could somebody give me some help on this? I may post some code here if necessary.

Thanks,
Joao

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Location: Bangladesh
Contact:

Re: 10912 - Simple Minded Hashing

Post by Imti » Fri Sep 02, 2011 5:11 pm

Even My O(n^3) solution was giving TLE and was really irritated with this...at last I found memset() is too slow for this problem..manual assigning gives me accepted...
:)
Try these
Input:

Code: Select all

13 170
8 100
26 351
16 200
5 2
23 323
14 156
12 12
0 0
Output:

Code: Select all

Case 1: 201413
Case 2: 61890
Case 3: 1
Case 4: 157236
Case 5: 0
Case 6: 104
Case 7: 194788
Case 8: 0

Yousuf
New poster
Posts: 13
Joined: Thu Jun 09, 2011 8:22 am

Re: 10912 - Simple Minded Hashing

Post by Yousuf » Wed Sep 26, 2012 7:43 pm

My Accepted Code gives this Output

Code: Select all

Case 1: 201413
Case 2: 30945
Case 3: 1
Case 4: 78618
Case 5: 0
Case 6: 52
Case 7: 48697
Case 8: 0

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 10912 - Simple Minded Hashing

Post by Mukit Chowdhury » Tue Oct 01, 2013 10:41 pm

Yousuf wrote:My Accepted Code gives this Output

Code: Select all

Case 1: 201413
Case 2: 30945
Case 3: 1
Case 4: 78618
Case 5: 0
Case 6: 52
Case 7: 48697
Case 8: 0
My accepted code also gives output like your code... @Yousuf

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

Re: 10912 - Simple Minded Hashing

Post by jddantes » Mon Dec 22, 2014 3:49 pm

Removed after AC
Last edited by jddantes on Thu Dec 25, 2014 12:55 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10912 - Simple Minded Hashing

Post by brianfry713 » Tue Dec 23, 2014 11:59 pm

On my machine your code is throwing a RE on line 32:
arr[j][k] += arr[j - 1][x];
When i = 1, j = 2, k = 4, x = 3
Check input and AC output for thousands of problems on uDebug!

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

Re: 10912 - Simple Minded Hashing

Post by jddantes » Thu Dec 25, 2014 12:53 pm

Got it. Thanks.

Post Reply

Return to “Volume 109 (10900-10999)”