11069 - A Graph Problem

[Nemo]

i am ashamed to see so many people have solved this problem but i coudn't understand how to.

is there any constant time formula? or is it a brute force enumeration? (doesn't seem so).

[mf]

There's a simple recurrence, which can let you compute answer in O(n) time.

[Moheeb]

edit

[little joey]

Come on, no spoilers!

[Nemo]

thanks. i sweat it out to find the pattern. surprised to see so simple recurrence. i got AC with precalculation as you said. i don't know how to solve the recurrence. then i could solve it in constant time.

[shanto86]

well... it is not fair to post the recurrence directly. plz who ever did it, delete that. u may give him enough hint but not direct recurrence!

if u have a close look, then u will realize it is fibonacci. but if u want to formulate it there is a big chance to get precission error (i think u know the direct formula for fib series.)

[FAQ]

I wonder how you could find the recurrence (some math proof behind?) or it's just an experience in "looking at an integer sequence"?

[mf]

(Spoiler removed.)

[lonelyone]

how about 6 nodes

what's the subsets of it..

could somebody explain problem for me, thanks a lot

[lonelyone]

n=6

{1,3,5}
{2,5}
{1,4,6}
{2,4,6}
{3,6}

am I right?
but why {1,6} can't be included

[Darko]

for 6:

1 3 5
1 3 6
1 4 6
2 4 6
2 5

{1,6}is not one of them, because you can insert 3 or 4 which are not connected to 1 or 6 - same thing with {3,6}(you can add 1)

[lonelyone]

thanks, I think I realized it

[little joey]

Please guys, remove those posts that give the solution to this problem. The boards are meant to discuss problems, not to give spoilers.
mf: I know you responded to a request for proof, but you should give that in a PM, not publicly on the board.

[okz]

easy problem...
but i want to know what is the provision for terminating the program..??
"The input will be terminated by EOF",i didnt understand what it meant

just write down
while(!EOF){
cin>>xxx;
cout<<xxx;
}


let me got a WA...

[shanto86]

I do like this:

while(scanf("%d",&x)!=EOF)
{
}

i dont know what it is for cin... may be:

while(cin>>x)
{
}

you may check it in your pc. just end your input by ctrl+z. See if your code terminates!