11082 - Matrix Decompressing

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Post by Mohammad Mahmudur Rahman »

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. 8)
You should never take more than you give in the circle of life.

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Re: any backtrack solution..

Post by Cho »

sohel wrote:I also solved this problem using MAX-FLOW.

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..????
Found a greedy approach to the problem. No max-flow, no backtracking. :)

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

greeeeedy....

Post by sohel »

GREEDY .... ????
WOW!

Can u ...... :D

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard »

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
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Location: Canada
Contact:

Post by kmhasan »

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:
You can assume that there is at least one solution for each of the given encodings.
In anycase, I haven't got anything against the solution based on max-flow. You can try whichever approach you want. I haven't done anything special in the problem to prevent people from using max-flow. The special judge for this problem isn't intelligent enough to classify solutions based on their approaches :(

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho »

I construct the matrix row by row. For each row, I allocate the values in such a way that the column sum will be 'neutralized'.

Take the sample as example, the initail column sums are 10 10 27 11. Then I will construct row 1 such that the sums become 9 9 20 10 for the remained rows.

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

Post by Nazmul Quader Zinnuree »

Hello Cho,

I have sent my code to you by PM. Coz, your approach seems to be like mine. Would you plz check my code, why I'm getting WA.

Thanks.

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho »

Nazmul Quader Zinnuree wrote:I have sent my code to you by PM. Coz, your approach seems to be like mine. Would you plz check my code, why I'm getting WA.
As mentioned in an earlier post, it's really easy to generate some random input for this problem to test for yourself.
I code, therefore I am.

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego »

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.
If only I had as much free time as I did in college...

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko »

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)
Last edited by Darko on Tue Sep 12, 2006 5:47 pm, edited 1 time in total.

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego »

Ah. That explains the wrong answers. Thanks.
If only I had as much free time as I did in college...

fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:

How to convert the constraint into maxflow?

Post by fh »

How to convert the constraint into maxflow?

this is the initialization step i did:
set flow[j] = 1 for all i in [0,R-1] and j in [0,C-1]
set flow[source] = C for all i in [0,R-1]
set flow[j][sink] = R for all j in [0,C-1]

But then how to run the Ford-Fulkerson 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://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:

I realized it now

Post by fh »

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

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Post by baodog »

Nevermind... bug fixed.

Post Reply

Return to “Volume 110 (11000-11099)”