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 » Wed Oct 12, 2005 6:00 pm

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.

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

Post by little joey » Wed Oct 12, 2005 6:14 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
Location: Bangladesh
Contact:

Post by mamun » Fri Nov 11, 2005 1:40 pm

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

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

Post by Martin Macko » Sat Dec 10, 2005 9:29 pm

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:

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

Post by Martin Macko » Sat Dec 10, 2005 9:30 pm

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:

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

Post by ImLazy » Sun Jan 01, 2006 6:02 am

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 » Sun Jan 01, 2006 6:26 am

Yeah!

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

Post by Martin Macko » Sat May 20, 2006 11:30 pm

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

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

Post by Jemerson » Wed Aug 30, 2006 2:58 am

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!

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

Post by Martin Macko » Wed Aug 30, 2006 8:54 am

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 » Thu Aug 31, 2006 1:27 pm

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 » Thu Aug 31, 2006 3:16 pm

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 » Thu Aug 31, 2006 4:24 pm

thnx

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

Post by jan_holmes » Sun Jun 24, 2007 7:39 pm

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 » Sun Jun 24, 2007 8:52 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)

Post Reply

Return to “Volume 109 (10900-10999)”