## 10912 - Simple Minded Hashing

Moderator: Board moderators

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:
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
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:
argggh... yes... got several WA and TLE because of my stupid DP implementation thx asif_rahman0

JC1
New poster
Posts: 4
Joined: Thu Jul 20, 2006 11:02 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
Contact:

### Re: 10912 - Simple Minded Hashing

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

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

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

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

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

Got it. Thanks.