Happy Days

The bridge from Island 1 to Island 2  is same bridge that is from island 2 to island 1 ...... or there are 2 distinct bridges ..??

It's the same ..

There is only one bridge between two islands. If there were two, the answer would be 8 (4 pairs of islands not connected by favorites * 2 bridges for each pair = total number of bridges that could be left alone i.e. 8)

are we assured that the answer will fit in long long? Or is that information intendedly not given?

is it legal to use the code library of someone else??? with proper acknowledgement of the author of that code library.

I think judge should explicitly say if the given matrix is symmatric.

Please mention if the answer will fit in 64 bit integer. The number of JAVA submissions indicate that 64 bit is not enough. Plz clarify!

On submitting my solution, the judge says " :( internal error occured in our system " .... is this a problem with my program or the judge?

On submitting my solution, the judge says " :( internal error occured in our system " .... is this a problem with my program or the judge?

@NAMIT .D. SHETTY

It's actually a part of a problem for you to derive if the answer will fit into any standard datatype

"Internal error occured in our system" is the problem of the judge. You should just resubmit I assume.

seems the internal error issue is fixed.....

@Ivan - thnx 4 the reply :)

I am getting TLE, but on my pc i have tested my code with 5 test cases of 30 nodes complete graph, its runs <2 sec :| , i dont know what to do ............

anyone plz explain how the answer is four...with proper path

@Satyarth:

you can remove any three of the remaining 4 unfavorite edges and the resulting graph will be a tree. So, the answer is four.

Are the bridges bidirectional?

Can someone give me a input file to be tested? Judge says my answer is wrong, but there's no way for me to check it without a good test file. :-(

Codechef, can you please show an input of more than one test case?

That is against the rules of the content; please do not ask people to break the rules.

"Of course, if the favorite bridges themselves don't satisfy the happiness condition Johnny will not be happy for even single day."

I am not exactly sure what that is saying. Is it saying that if you need to remove a favorite bridge in order to make a new path, it will not make him happy?

yes. It is saying that if it is always necessary to remove atleast 1 bridge from favorite bridges then he will never be happy.

I learnt Java to solve this problem!

This is my first Java Program , not long but coding long time , LOL.

HAPPY made me UNHAPPY for 2 days. :|

@Team Cyclone

Am an atheist but i do not do blasphemy.

Myabe you have no respect for a coding competetion and all, but if others are doing it why dont you refrain from ruining the 'fun' of it by posting solutions.

And try to be a bit rational, by open source and by saying competetions should be 'team work' you are basically saying that 22 players should shoot goal in the same goal post for 1st half and other goal post in second half by working as a 'team'.

can the graph be disconnected? If it is what is the happy days count?

"Every day Johnny removes some bridges so that there is only one way from any island to any other."

Does it mean there is always one way from any island to any other or if islands are connected they must be connected with a single path???

There must be exactly one way between each pair of islands, not 'at most one'.

phew... 20 submissions.. so many TLEs so many wrongs.. but finally it works.. feels great... :)

1---2----------3--------5

|            |

5

in this graph  2 3 5 makes a cycle

is answer is 2 or 3 for happy day.

The example shown not at all clarifies the problem. The matrix shows all the islands are interconnected.

And the output shown is just the number of unfavourite bridges.

So can somone plz explain with a better example.

is the graph is complete graph

mean every island is connected to every island?

No, the problem statement does not say the graph has to be a complete graph.

Please give, atleast one more test case.

i tried to use principle of inclusion exclusion... but somehow ended up with WA everytime. Could someone please tell me whats the flaw in my argument?

Let F be the set of favorite edges. For every set S subseteq F, define N(S) as the number of spanning trees in G that preserve at least the edges in S.

We need the number of spanning trees that preserve exactly all edges in F.I used PIE for this calculation. Is this method right?

Now that the contest is over, can anyone explain the problem with a better test case?

@vivek.. red this http://en.wikipedia.org/wiki/Kirchhoff's_theorem

but the given problem is not a direct application of this theorem since you always have to select some paticular edges.

to solve this problem you first remove all the edges which are NOT favourite, then the remaining set of nodes can be considered as a forest.(If this does not reduce to a forest then ans will be zero) Now consider every tree as a single node  (total no.of new nodes will be n-p)  and no.of edges between two nodes will be equal to the no. of connections between their corresponding trees.

Now finally you have a new multi graph, no. of spanning trees of which you can find using kirchoff theorem.

sorry for spelling mistakes. :)

@mcsharma thanks ....

yes i got that... but whats wrong with the principle of inclusion exclusion? sorry i didnt define it correctly above.... here is what i intended to:

Let F be the set of favorite edges. For every set S subset of  F, define N(S) as the number of spanning trees in G that dont preserve at least the edges in S.

N(S) is computable using kirchoffs theorem.

Now we need the number of spanning trees that dont miss any edge, call it n.

Then, by Inclusion Exclusion , n = N(phi) - N(subset of F having 1 element) + N(subset of F having 2 elements) - ...

Is this wrong? I tried it for simple cases (eg complete graphs with 0/1 edge fixed etc. ,) it works

@vivek: That should be n = N(phi) - sum of N(S) over all subsets S of F having 1 element + sum of N(S) over all subsets S of F having 2 elements -...

Equivalently, n = sum of N(S)(-1)^|S|, over all subsets S of F.

yes thats what i mean in the last post.... sorry if it wasnt clear .... so that means it was an implementation mistake or something similar :(

Yes, it could be anything. An easy logical mistake to make would be to forget that N(S)=0 if G-S is disconnected.