10912 - Simple Minded Hashing

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10912 - Simple Minded Hashing

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

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

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
Location: Bangladesh
Contact:

Post by mamun »

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)

Post 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 :wink:

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post 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 :oops:

ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post 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?
I stay home. Don't call me out.

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

Post by Emilio »

Yeah!

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko »

ImLazy wrote:Do you mean the string "aaaaabbbbbbcccccc" is not strictly ascending?
Is "a" strictly lower then "a"? :wink:

Jemerson
Learning poster
Posts: 59
Joined: Mon Feb 02, 2004 11:19 pm
Contact:

Post 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
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)

Post 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 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

Post 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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

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

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

Post by asif_rahman0 »

thnx

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Post by jan_holmes »

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

Post 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)

Post Reply

Return to “Volume 109 (10900-10999)”