10081 - Tight Words

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

Moderator: Board moderators

Chameleon
New poster
Posts: 4
Joined: Thu Jun 20, 2002 4:54 pm

10081 - Tight Words

Post by Chameleon » Thu Jun 20, 2002 4:56 pm

I have written code for 10081, but the judge doesn't like it.
Any ideas?

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

Post by 10153EN » Thu Jun 20, 2002 7:27 pm

Any more information? e.g. what's the judge's reply?

and what's your algorithm in solving it?

Chameleon
New poster
Posts: 4
Joined: Thu Jun 20, 2002 4:54 pm

Post by Chameleon » Thu Jun 20, 2002 7:31 pm

"Incorrect output".

I was using a recursive way that counted the number of ways to generate the word, and then for efficiency converted to iterative.

Result = Tight words / Total words

where total words = (k+1)^n

I had to put in some tricks to overcome overflow... perhaps that is the problem.

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Fri Jun 21, 2002 4:10 pm

While counting the number of tight words and total words use double if not I think you could get integer overflow.

Master
Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
Location: St. Johns, Canada
Contact:

10081 - What the problem states and how can I solve it?

Post by Master » Wed Feb 25, 2004 10:57 am

Would you pls tell me what the problem states and How can I solve it? :roll:
If you know then Pls tell me....

Thanks in advance
M H Rasel
Cuet Old Sailor

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

confusing

Post by sohel » Wed Feb 25, 2004 11:54 am

This problem is hard to understand if you read it only once, but if you read it 3-4 times then you will probably get the hang of it.

consider the second case in the sample:
2 5

here k is 2 and n is 5.

you can form 3^5 numbers.... ( allowed digits are 0,1,2 and of length 5).

Of these 3^5 numbers, the numbers whose adjacent digits do not differ by one are tight words (numbers).
Just output the percentage.

Hint: Use DP as manual genertions will exceed Mem limit && time limit.

Hope it helps.
:wink:

Digit
New poster
Posts: 5
Joined: Sat Jan 15, 2005 7:06 pm

10081 (Tight Words) - Wrong Answer

Post by Digit » Tue Feb 08, 2005 3:25 pm

I'm trying to solve 10081, Tight words, but I'm getting WA all the time.

Can anybody give me the number of tight words for input '9 100' ?

I know that this is not asked, but this is part of the solution.
My program says 1069966138. Is this correct?

Or maybe someone has some input/output for testing?

Thanks.

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Tue Feb 08, 2005 4:36 pm

Here are some tests.
Input

Code: Select all

0 8
5 10
2 20
2 30
2 40
2 50
2 60
2 70
9 13
Output

Code: Select all

100.00000
0.09657
1.56615
0.17839
0.02032
0.00231
0.00026
0.00003
0.00012
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

jagadish
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

10081 - Tight Words

Post by jagadish » Tue Aug 02, 2005 2:44 pm

How do u acheive precision for this problem ? I used double and got quite different results for the above case :

Code: Select all

100.00000
0.09657
1.56615
0.17839
0.02032
0.00231
0.00026
0.00003
0.00003
for 9 100 i get 0.00000 ..
if u can think of it .. u can do it in software.

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Re: How to solve problem 10081?

Post by chunyi81 » Thu Aug 04, 2005 3:28 pm

I was trying to solve this problem but could not figure out how to use DP here. Here is what I observed: For a string of length i ending with digit j, then the second last digit will be j - 1, j or j + 1 if 1 <= j <= k - 2, 0 or 1 if j = 0, and k - 2 or k - 1 if j = k - 1. At first I thought of using memoization(using a lookup table), after trying to work out the recursion tree to calculate the number of tight words for a small example, say the first test data in the sample input: 2 5. The lookup table would become too big because there are too many places in the recursion tree where the same value is calculated more than once.
Can anyone give me a hint how to use DP for this problem? Thanks.

jagadish
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

Re: How to solve problem 10081?

Post by jagadish » Thu Aug 04, 2005 8:16 pm

Got AC despite some lossy precision..
chunyi81 wrote: For a string of length i ending with digit j, then the second last digit will be j - 1, j or j + 1 if 1 <= j <= k - 2, 0 or 1 if j = 0, and k - 2 or k - 1 if j = k - 1.
formally that would look like :
f(n,t) = f(n-1,t-1)+f(n-1,t)+f(n-1,t+1)
take advantage of the fact that f(n) needs only f(n-1)
if u can think of it .. u can do it in software.

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Fri Aug 05, 2005 9:51 am

Thanks jagadish for the recurrence equation you posted. I figured out how to solve this problem using DP.

migichen
New poster
Posts: 2
Joined: Fri Mar 17, 2006 5:28 am

Re: 10081 - Tight Words

Post by migichen » Fri Mar 17, 2006 6:12 am

jagadish wrote:How do u acheive precision for this problem ? I used double and got quite different results for the above case :

Code: Select all

100.00000
0.09657
1.56615
0.17839
0.02032
0.00231
0.00026
0.00003
0.00003
for 9 100 i get 0.00000 ..
My program which got AC has the same result :)

Alberto
New poster
Posts: 4
Joined: Fri May 20, 2005 5:15 pm
Location: La Paz - Bolivia
Contact:

Re: 10081 - Tight words

Post by Alberto » Thu May 15, 2008 6:41 pm

for k=9 and n=100
the number of tight words:
tights = 100512267936480837475180750161082113997249340218
And the number of possible words:
possibles = (k+1)^n = 10^100
Then
% = 100.0*(tights/possibles)
% = 0.00000

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 10081 - Tight words

Post by Mukit Chowdhury » Sun Aug 31, 2014 12:40 pm

Astonished to see, for computing 10^100 pow() can be used !!!! Would anybody please tell me, what is the actual range of returned value of pow() in C++ ??? It'll really help.... :)
Thanks in advance... :)

Post Reply

Return to “Volume 100 (10000-10099)”