OJ Board

yeah ! you are absolutely right. I was not printing correctly when we have output 1. later on i found the mistake and got AC .why do acm problems have such irrelevant output formats.. i nearly wasted 1 hr for that.

Somebody plz provide me some test case.. I m constantly getting wrong answer for this problem..thanx in advance

I am aquainted with Bit masking concept.. but here in this situation, i could not imagine how bits can be used to mark the reached position ( as mentioned by Adrian )
if we do it by an array we need a 64000 x 100 size of array.. but masking can be done only for integers upto 64.

Can anybody ...

What is the correct approach to this problem .... ? somebody plz suggest.

got ACC

changed it from PRIMS to Kruskal ..

I have got this problem ac long ago.. just forgot to remove code later..

for BFS , Think abt some pruning

I am facing TLE in this problem. I tested my program for your I/O and it gave following output :


2642 2642


ur second I/O is invalid. since weights should be <=450

By the way, what is your algo ?

I used top down approach with memoization to produce all possible sum using n/2 weights with ...

I tried to implement the algorithm mentioned in cormen for finding the second best minimum spanning tree . (along with prims to find minimum spanning tree ) but it is giving wrong answer in 0.029 secs.. :cry: :cry:

some body plz provide me with some test cases or have a look at my code ...

why i m keep on getting TLE in this problem. I hv applied simple BFS.

How can i make this algo efficient ??

well , as u would hv already seen in previous posts that there are two possible strategies...

if A,B,C....Z are time in ascending order ,

then Strategy one: AB+A+YZ+B
Strategy two: AZ+A+AY+A

So u r required to check for both and choose min out of them..

This problem is based upon Matrix Multiplication .
I wrote a top down DP solution to it .which is being timed out. Can't we have top down solution to this problem get accepted ??

Or if there is any mistake in optimization in solution then plz point it out. My code goes as follows.

#include ...

Yeah thanx rio ,

I got the error , Now i m puzzled how can i use Floyd Warshall to find cylces of odd length ?

I mean is it useful to apply FY here. Plz throws some light

earlier I solved this problem using a different approach but this time i tried to use Floyd warshall algorithm to solve it..
Using FY , i tried to find cycles in it of length 3.

ie. if i is connected to j and if i is also connected to k and k is connected to j then its Not Bicolrable.

But my ...

Thanx rio ... on carefully watching at my output .. i found tht i had used capital X instead of small X

code removed after being accepted..