10912 - Simple Minded Hashing

[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.

[little joey]

So how many strings of length, say 100 can you make that have sum, say 5000? That's the answer!

[mamun]

Can anybody explain the dynamic relation here? I think it is a dynamic problem.

[Martin Macko]

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]

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]

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?

[Emilio]

Yeah!

[Martin Macko]

Do you mean the string "aaaaabbbbbbcccccc" is not strictly ascending?

Is "a" strictly lower then "a"?

[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

[Martin Macko]

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.

[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

[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.

[asif_rahman0]

thnx

[jan_holmes]

I still do not understand about the recurrence relation for this problem. Is it 3-d array ?

[asif_rahman0]

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)