10450 - World Cup Noise

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

Moderator: Board moderators

bery olivier
Learning poster
Posts: 90
Joined: Sat Feb 15, 2003 1:39 am
Location: Paris, France
Contact:

10450 - World Cup Noise

Post by bery olivier » Sat Feb 15, 2003 1:58 am

Hi !

I tried to solve "world cup noise" 4 times but I only got Time Limit Exeeded and WA. :cry:
I know it seem to be an easy problem. But I really don't understand why I can't manage to get Acc.
Is that anybody could give me a heap of sample input/outpout



Thanks.
______________________
--- Theocrite le Newbee ---
Last edited by bery olivier on Sat Feb 15, 2003 3:16 pm, edited 1 time in total.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Sat Feb 15, 2003 12:13 pm

How about I give you a recurrence?
T(n) = T(n-1) + T(n-2)

This fits in long long..

bery olivier
Learning poster
Posts: 90
Joined: Sat Feb 15, 2003 1:39 am
Location: Paris, France
Contact:

Post by bery olivier » Sat Feb 15, 2003 5:11 pm

Larry wrote:How about I give you a recurrence?
T(n) = T(n-1) + T(n-2)

This fits in long long..
I finally got Acc :D . But I think long long isn't enough for the 5 last numbers. I had to cheat a little to succed.
Thanks a lot larry.


_________________
Theocrite le Newbee

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Sat Feb 15, 2003 8:33 pm

Well, Fib is ~ 1.6^n (or so, don't remember off my head), which is smaller than 2^n, and the max input is only 51... so long long worked perfectly for me..

bery olivier
Learning poster
Posts: 90
Joined: Sat Feb 15, 2003 1:39 am
Location: Paris, France
Contact:

Post by bery olivier » Sun Feb 16, 2003 12:18 am

Well anyway, the first time I sent my source I got WA. Then I print the 4 last numbers ( if(51) printf("XXX"); I know it's not really beautiful, but it was accepted. I'll try to improve it) and it worked perfectly. I don't know what's the matter. Maybe something wrong whit my compiler or something else.
Not AC yet Image AC at last Image

zsepi
Learning poster
Posts: 51
Joined: Thu Sep 26, 2002 7:43 pm
Location: Easton, PA, USA

why fibonacci?

Post by zsepi » Sun Feb 16, 2003 4:00 am

hei,
I spent some time on the problem and I just couldn't figure out how to solve it, but after looking at this thread, it seems that it is using the fibonacci numbers - could someone explain me why or just recommend some book/website? thanx a lot.
Dealing with failure is easy: Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.

magicalan
New poster
Posts: 3
Joined: Wed Jan 29, 2003 1:52 pm
Location: Hong Kong

Post by magicalan » Sun Feb 16, 2003 5:06 am

code : array [1..50] of longint;
zeros : longint;

when n = 1
there are only two possibilities '1' and '0'
for n = 2 we try to add '0' and '1' after them
(code[1] = 2 , zeros = 1(one number end with zero))

for number end with '1' , we can add '0' only
for '0' , we can add both '0' and '1'

so '10' , '01' , '00' ( total number = zeros * 2 + ones = 3
new zeros = code[1])

.........


we come up with the code

zeros:= 1;
code[1]:=2;

for i:=2 to 50 do begin
code := code[i-1] + zeros;
{code:= code[i-1] - zeros + zeros *2}
zeros := code[i-1];
end;

and I discover that zeros is code[i-2] when it is added.

so ------- >

code[1]:=1;
code[2]:=3;

for i:=3 to 50 do
code:=code[i-1] + code[i-2];
ALAN LEE

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Sun Feb 16, 2003 9:43 am

Base Case:

T(1) = 2 (0) and (1)

T(2) = T( 1 ) ( This is adding a '1' to each of the string ) plus 1 ( Adding a '0' to the (1) string ) = 3

T(3) = T(2) (Again, adding '1' to each of the string) plus T(1) (This is the number of occurences where the last digit is not zero.

and so on...

I learnt this in my combinatorics class, and I took that a few years ago, so maybe someone can explain this better..

zsepi
Learning poster
Posts: 51
Joined: Thu Sep 26, 2002 7:43 pm
Location: Easton, PA, USA

Post by zsepi » Sun Feb 16, 2003 9:01 pm

thanx a lot guys,
I guess I'll just borrow a combinatorics book from someone and read through that - I'm just a freshman and combinatorics is next semester for me....

thanx again!
Dealing with failure is easy: Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.

Sajid
Learning poster
Posts: 94
Joined: Sat Oct 05, 2002 5:34 pm
Location: CS - AIUB, Dhaka, Bangladesh.
Contact:

Using DP

Post by Sajid » Fri Feb 21, 2003 7:13 am

Hello, guys...

Why dont u use Dynamic Programming Algorithm for this problem. I think, it'll take less Time Complexity.

Best of LUCK.. c ya... :D

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Fri Feb 21, 2003 9:24 am

In many cases recurence is involvwe with DP. I think, that of of this guys talking about recurences using it (with me too). If not - TLE must occur :))) because computing >25 number in this problem is very time-consuming ...

Dominik Michniewski
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

User avatar
Moni
Experienced poster
Posts: 202
Joined: Fri Mar 22, 2002 2:00 am
Location: Chittagong. CSE - CUET
Contact:

Post by Moni » Fri Mar 07, 2003 4:39 am

But just tell me how did you all came across to this algorithm? From Knuth's book? or Observing the pattarn? How you have figured it out that it has some relation with the "Fibonacci Sequence"???
ImageWe are all in a circular way, no advances, only moving and moving!

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok » Fri Mar 07, 2003 8:14 am

Hello Moni, ... I hope this can explain a little bit on why it is related to Fibonacci sequence, ...

We all know from problem-statement that we finally reduce the problem to finding the number of all binary-strings of length n that don't have consecutive ones.

Let f(n) = number of binary-strings of length n that don't have consecutive ones.

We can split f(n) by two smaller functions:
-> f0(n) -> finds the number of strings that start with '0'.
-> f1(n) -> finds the number of strings that start with '1'.

Let's consider f1(n) ... If the string starts with '1', clearly the next digit has to be '0'. So, the strings are fixed to "10????..."
Starting from s[2] until s[n-1], the values are chosen so there is no consecutive ones. That means it is the same as calculating f(n-2) ...

f0(n) is even simpler. Since it starts with '0' ... the next digit can be either '0' or '1' ... So, the strings are only fixed to this pattern "0????..." and the rest should be chosen in such a way so that no consecutive ones are found. It's the same as calculating f(n-1).

Finally, we can see right away that f(n) = f(n-2) + f(n-1) ... which is Fibonacci sequence.

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

10450

Post by Red Scorpion » Mon Apr 14, 2003 11:24 am

Hi,
I always got WA.

Is my output right?

Input:
9
0
2
10
9
13
50
51
47
49

Output:
0
3
81
60
175
10151
10777
8420
9550

Thanks.

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok » Mon Apr 14, 2003 11:31 am

RedScorpion, ... 51 is not a valid input ...

Here's the output of my solution (excluding 51):

Code: Select all

Scenario #1:
0

Scenario #2:
3

Scenario #3:
144

Scenario #4:
89

Scenario #5:
610

Scenario #6:
32951280099

Scenario #7:
7778742049

Scenario #8:
20365011074
-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

Post Reply

Return to “Volume 104 (10400-10499)”