||Yeah, you are amazing - and so modest with it. Would you like to be my hero? ;)
Sorry to derail your thread sumantbhardvaj, I couldn't resist.
||Not that amazing, I didn't remember it at all. I just remembered having made a little mental breakthrough in solving it during the match in which it was used, and figured that since I remembered getting it right, my rating probably went up. Then I went and looked at my rating graph and started checking the matches where I went up recently, and I found it.
Well, one of two conditions exist, in the case that there are multiple ways to multiply all the matrices, the reason there are multiple ways is that there's a potential "cycle" somewhere (although there may even be multiple cycles, but that's not so important in the end). Because of that, we can rotate the order to maximize the size of the matrix, which will start with the largest thing in M and end with the largest thing in N (and that M and N will be equal).
The tricky part here is figuring out if there is such a condition, and doing that has two parts:
Can the numbers in M match up with the numbers in N? How many numbers x are there such that there are a different number of x's in M and N? There is definitely no answer if there is more than one number that occurs more in M than N or more than one number that occurs more in N than M (or if there is two more of that number in M than N or vice versa).
If they can match up, is there a way to reach every matrix from every matrix? If you think of the input as a graph (where each M[i], N[i] pair is a directed edge), the answer is basically yes if the entire graph is strongly connected. You'll notice that the M's and N's match up in example 3, but the graph isn't strongly connected - it has two separate strongly connected components, therefore there's no way of putting them together.
After that, there is only one way to set up an order if there was a spare element in M and N that isn't matched in the other. The answer in this case is the product of those spare elements (example 1 does this). If M and N matched up perfectly, then we can pick any number to be both the beginning and end, so we pick the largest one, and the square of the largest element in M/N is our answer (see example 0 or 4).
A better description from the standpoint of graph theory as well as why it works can be found in the editorial for that match.
||ya .. that was the name of the Question---"OrderDoesMAtter". Its quite amazing that u remember the name !
I solved that problem by applying Brute force techniques to find all sorts of methods to multiply the metrices and then choose the best one which gave the answer.
But that program was exceeding the time limit...(as it should)
U suggested that when there is more than one way to mulitiply the matrices ,then the answer is simply the square of the largest no in M and N . ( if i did not get it wrong.)
But how will that work , can u just be more elaborate !!!
I mean, is it necessary that if we start with the matrix having the highest value in N , we will always end at the matrix having largest value in M ???
||Well, I have solved that problem - I think you're talking about OrderDoesMatter, the div 1 500 from SRM 298. I'm not sure there's a good way to do a depth first or breadth first search on this one, but someone can correct me if I'm wrong. To me, there were a few parts to this problem:
1. Figure out if there is going to be any way to multiply all the matrices together (take a step back and think about it if it's not obvoius - the solution to this part is both easier and harder than it may look at first).
2. If there is, figure out if I have a choice about the order - if there's only one way to order them, then the answer should be simple. Otherwise, the answer is a different kind of simple, because it will be the square of the largest element in M and N.
||I don't hv words to thank u.....
That was a serious mistake i was committing (of marking nodes after dequeing and not at the time of enqueing).I made the necesssary changes and it worked miraculously...
(But i was tempted to do it like that by that article,I think then there is some serious problems with that pseudo code mentioned there..)
Any way ,
I have a fresh problem for u though !!!
I had come across a question on topcoder which was regarding multiplication of matrices.I do not remember which SRM !!
The question said that we would be given a set of Matrices and we hv to multiply them in such a manner that the end matrix has maximum no. of elements...
To procede, we will form a 2 dim array and form a graph with the interlinked matrices.and then apply BFS or DFS....
I think u would hv solved that question as well ...
Can u suggest how DFS/BFS could be implemented on the resulted graph of interlinked matrices?
||Looking at your practice room code, it looks like you're using a BFS, not a DFS. That's fine, that's how I did, but just to get the terminology right :-)
The thing that seems to be the problem is that you should mark spots as visited when you add them to the queue (instead of when you dequeue them), and you shouldn't add new things to the queue that have already been visited, otherwise you'll add lots of the same thing to the queue and it can get rather large.
||lemme tell at the outset..
i am new to the topcoder.
I read the article by written gladius and found it very helpful....
I tried the same problem (SRM 156 Division 1, 900) whose algorithm has been explained clearly in the article (using DFS).
I followed the pseudo code described in the article.
But upon system testing , my java code is giving the error :
java.lang.OutOfMemoryError : Memory heap space.
How can i fix it ??
Do the algo need to be more efficient or there is any fault on my part..
may be gladius himself or somebody else suggest soemthing !!!
(do not suggest to use -Xmx -Xms, i cannot use it on topcoder)