Page 1 of 2
10912 - Simple Minded Hashing
Posted: Wed Oct 12, 2005 6:00 pm
by mamun
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.
Posted: Wed Oct 12, 2005 6:14 pm
by little joey
So how many strings of length, say 100 can you make that have sum, say 5000? That's the answer!
Posted: Fri Nov 11, 2005 1:40 pm
by mamun
Can anybody explain the dynamic relation here? I think it is a dynamic problem.
Posted: Sat Dec 10, 2005 9:29 pm
by Martin Macko
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
Posted: Sat Dec 10, 2005 9:30 pm
by Martin Macko
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
Posted: Sun Jan 01, 2006 6:02 am
by ImLazy
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?
Posted: Sun Jan 01, 2006 6:26 am
by Emilio
Yeah!
Posted: Sat May 20, 2006 11:30 pm
by Martin Macko
ImLazy wrote:Do you mean the string "aaaaabbbbbbcccccc" is not strictly ascending?
Is "a" strictly lower then "a"?
Posted: Wed Aug 30, 2006 2:58 am
by Jemerson
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
Thanx in advance
Posted: Wed Aug 30, 2006 8:54 am
by Martin Macko
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 0 ≤ l, 0 ≤ s and 'a' ≤ c ≤ 'z'.
After stating the trivial cases of the recurence, it may help you to find a DP solution.
Posted: Thu Aug 31, 2006 1:27 pm
by asif_rahman0
please check my input/output:
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
Posted: Thu Aug 31, 2006 3:16 pm
by mf
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.
Posted: Thu Aug 31, 2006 4:24 pm
by asif_rahman0
thnx
Posted: Sun Jun 24, 2007 7:39 pm
by jan_holmes
I still do not understand about the recurrence relation for this problem. Is it 3-d array ?
Posted: Sun Jun 24, 2007 8:52 pm
by asif_rahman0
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)