10912 - Simple Minded Hashing
Moderator: Board moderators
-
- Experienced poster
- Posts: 136
- Joined: Fri Apr 15, 2005 3:47 pm
- Location: Singapore
- Contact:
-
- Experienced poster
- Posts: 209
- Joined: Sun Jan 16, 2005 6:22 pm
-
- Experienced poster
- Posts: 136
- Joined: Fri Apr 15, 2005 3:47 pm
- Location: Singapore
- Contact:
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

Thanks,
Joao
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:
Output:

Try these
Input:
Code: Select all
13 170
8 100
26 351
16 200
5 2
23 323
14 156
12 12
0 0
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
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
-
- Learning poster
- Posts: 98
- Joined: Fri Aug 17, 2012 9:23 pm
- Location: Dhaka
- Contact:
Re: 10912 - Simple Minded Hashing
My accepted code also gives output like your code... @YousufYousuf 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
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.
-
- 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
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!
Re: 10912 - Simple Minded Hashing
Got it. Thanks.