## 10912 - Simple Minded Hashing

Moderator: Board moderators

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Contact:

### 10912 - Simple Minded Hashing

I don't understand the problem clearly. The problem says
You have to consider strings that have only lowercase letters in strictly ascending order.
Again
Each case consists of 2 integers L and S. (0 < L, S < 10000). (L is string length)
Isn't it contradictory? How can length be more than 26 when the the letters are in strictly ascending order?
Clarify plz.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
So how many strings of length, say 100 can you make that have sum, say 5000? That's the answer!

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Contact:
Can anybody explain the dynamic relation here? I think it is a dynamic problem.

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
Anonymous wrote:
little joey wrote:So how many strings of length, say 100 can you make that have sum, say 5000? That's the answer!
how many? none...
so all string length of more than 26 should give answer 0. am i correct?
yep

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
mamun wrote:Can anybody explain the dynamic relation here? I think it is a dynamic problem.
What do you mean by "dynamic problem"? I don't understand

ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China
Do you mean you give the answer "0" for every L > 26 or S > 351 ( 1+2+3+4...+26)?
Do you mean the string "aaaaabbbbbbcccccc" is not strictly ascending?
I stay home. Don't call me out.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain
Yeah!

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
ImLazy wrote:Do you mean the string "aaaaabbbbbbcccccc" is not strictly ascending?
Is "a" strictly lower then "a"?

Jemerson
Learning poster
Posts: 59
Joined: Mon Feb 02, 2004 11:19 pm
Contact:
repeating mamun question: can anyone please explain me how to apply dynamic programming in this problem, i just cant find the relation and got too many TLE already

UFCG Brazil - Computer Science graduate student
http://acm.uva.es/problemset/usersnew.php?user=54806 ... and going up!

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
Jemerson wrote:repeating mamun question: can anyone please explain me how to apply dynamic programming in this problem, i just cant find the relation and got too many TLE already
Denote f(l,s,c) the number of strictly increasing strings of length l ending with c, which sum is s. You can easily prove that:
• f(l+1, s+c, c) = 'a' ≤ d < c f(l, s, d), where 0l, 0s and 'a' ≤ c ≤ 'z'.
After stating the trivial cases of the recurence, it may help you to find a DP solution.

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

Code: Select all

``````3 9
11 29
2 9
1 0
0 1
1 10
3 10
77 151
26 3
17 121
18 171
6 91
7 35
3 35
4 11
4 19
7 65
3 11
17 161
6 23
4 33
4 67
2 19
3 44
4 51
100 100
100 92
8 65
8 67
1 26
2 26
3 26
4 26
5 26
0 0
``````
Output:

Code: Select all

``````Case 1: 2
Case 2: 0
Case 3: 4
Case 4: 0
Case 5: 0
Case 6: 1
Case 7: 4
Case 8: 0
Case 9: 0
Case 10: 0
Case 11: 1
Case 12: 0
Case 13: 6
Case 14: 52
Case 15: 1
Case 16: 10
Case 17: 46
Case 18: 4
Case 19: 10
Case 20: 2
Case 21: 67
Case 22: 0
Case 23: 9
Case 24: 46
Case 25: 66
Case 26: 0
Case 27: 0
Case 28: 80
Case 29: 72
Case 30: 1
Case 31: 12
Case 32: 36
Case 33: 35
Case 35: 14
``````
Is it OK?

bye
rabbi
------------------------------------------------
http://www.third-eye-creative.com

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
My accepted program produces this output:

Code: Select all

``````Case 1: 3
Case 2: 0
Case 3: 4
Case 4: 0
Case 5: 0
Case 6: 1
Case 7: 4
Case 8: 0
Case 9: 0
Case 10: 0
Case 11: 1
Case 12: 4605
Case 13: 15
Case 14: 73
Case 15: 1
Case 16: 18
Case 17: 3729
Case 18: 5
Case 19: 22
Case 20: 2
Case 21: 149
Case 22: 280
Case 23: 9
Case 24: 76
Case 25: 398
Case 26: 0
Case 27: 0
Case 28: 1972
Case 29: 2611
Case 30: 1
Case 31: 12
Case 32: 44
Case 33: 64
Case 34: 37
``````
4th and 5th test cases in your input are invalid -- L and S must be both greater than zero.

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

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:
I still do not understand about the recurrence relation for this problem. Is it 3-d array ?

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm
jan_holmes wrote:I still do not understand about the recurrence relation for this problem. Is it 3-d array ?
Yes.

Code: Select all

``````function(char_index,length/level,sum)
``````