11082  Matrix Decompressing
Moderator: Board moderators

 Experienced poster
 Posts: 154
 Joined: Sat Apr 17, 2004 9:34 am
 Location: EEE, BUET
Actually I was stunned to know that the judge solution was written using backtracking, too. But, in fact this is a variant of the assignment problem which has 2 solutions as far as I know. One is the classical flow solution & the other one is a backtracking solution which continously prunes the searchspace by readjusting upper & lower bound of the result at each step . If possible take a look at chapter 9 of the book "Fundamentals of Algorithmics" by Gilles Brassard & Paul Bratley. You'll find a example of the assignment problem with constrains in one dimension. The use of upper & lower bound makes a drammatic reduction of the searchspace. In the problem 11082 you actually have constrains on both rows & columns i.e. two dimensional constrains. They can be effectively used to reduce the run time. Still I would say that, I'm not sure if it is absolutely impossible to create a dataset which will cause the backtracking solution to get TLE & why one should use that instead of the cool flow solution.
You should never take more than you give in the circle of life.
Re: any backtrack solution..
Found a greedy approach to the problem. No maxflow, no backtracking.sohel wrote:I also solved this problem using MAXFLOW.
But I'd like to know whether any backtracking solution exists for this problem.
I heard that the judge solution was implemented using backtrack...
Isn't (20 x 20 ) matrix too much for a backtrack approach..????
Hello Cho.
I have found Greedy aproach too,but my algorithm is macking matrix with numbers not in range 0..20 and I can't change my algorithm too work vor 0..20.
Give some hint please.
Thanks.
Eduard
I have found Greedy aproach too,but my algorithm is macking matrix with numbers not in range 0..20 and I can't change my algorithm too work vor 0..20.
Give some hint please.
Thanks.
Eduard
someone who like to solve informatic problems.
http://acm.uva.es/cgibin/OnlineJudge?AuthorInfo:29650
http://acm.uva.es/cgibin/OnlineJudge?AuthorInfo:29650
To say that the judge solution is implemented in backtracking is only half true. I tested my solution with plenty of randomly generated test cases. If backtracking with pruning based on updating the constraints let you through, I'd consider you lucky. I had to do a bit more than that. I ordered the next states based on my heuristics  that did the trick.
The reason that any backtracking solution (with pruning and heuristics) have a good chance to pass is that the problem says:
The reason that any backtracking solution (with pruning and heuristics) have a good chance to pass is that the problem says:
In anycase, I haven't got anything against the solution based on maxflow. You can try whichever approach you want. I haven't done anything special in the problem to prevent people from using maxflow. The special judge for this problem isn't intelligent enough to classify solutions based on their approachesYou can assume that there is at least one solution for each of the given encodings.
K M Hasan
http://www.cs.umanitoba.ca/~kmhasan/
http://www.cs.umanitoba.ca/~kmhasan/

 New poster
 Posts: 42
 Joined: Sun Jul 31, 2005 2:07 am
 Location: SUST. Bangladesh
 Contact:

 A great helper
 Posts: 281
 Joined: Tue Sep 10, 2002 5:14 am
 Location: Mountain View, CA, USA
 Contact:
Does anyone else think that the sample output for this problem is completely wrong? How does the last row of either of the two examples add up to 58?!
Also, the dimensions of the matrices in the judge's input are much larger than 20x20. My assert() fails.
Also, the dimensions of the matrices in the judge's input are much larger than 20x20. My assert() fails.
If only I had as much free time as I did in college...
That is a "cumulative" sum (yet another case of "let's make it unneccessarily complicated").
So, 58 will be the sum of all elements (that's why it is the same for rows and columns).
(btw, whatever I do to that page, I can't make the image appear in the blank area  it is always above the text)
So, 58 will be the sum of all elements (that's why it is the same for rows and columns).
(btw, whatever I do to that page, I can't make the image appear in the blank area  it is always above the text)
Last edited by Darko on Tue Sep 12, 2006 5:47 pm, edited 1 time in total.
How to convert the constraint into maxflow?
How to convert the constraint into maxflow?
this is the initialization step i did:
set flow[j] = 1 for all i in [0,R1] and j in [0,C1]
set flow[source] = C for all i in [0,R1]
set flow[j][sink] = R for all j in [0,C1]
But then how to run the FordFulkerson method on this graph?
How can I find the augmented path to maximize the flow?
Can anyone explain on this?
this is the initialization step i did:
set flow[j] = 1 for all i in [0,R1] and j in [0,C1]
set flow[source] = C for all i in [0,R1]
set flow[j][sink] = R for all j in [0,C1]
But then how to run the FordFulkerson method on this graph?
How can I find the augmented path to maximize the flow?
Can anyone explain on this?
Visit my script to hunt UVA problem here:
http://felixhalim.net/uva/hunting/

Felix Halim
http://felixhalim.net/uva/hunting/

Felix Halim
I realized it now
nevermind, i realized how to convert it now.
Visit my script to hunt UVA problem here:
http://felixhalim.net/uva/hunting/

Felix Halim
http://felixhalim.net/uva/hunting/

Felix Halim