11082 - Matrix Decompressing

Moderator: Board moderators

New poster
Posts: 42
Joined: Sun Jul 31, 2005 2:07 am
Contact:

11082 - Matrix Decompressing

Someone give me some I/O, plz

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Shame on you! You can so easily make I/O yourself! Generate random matrices, sum their rows and columns, and you get your input. Checking if the output is correct is a trivial coding exercise, too.

And it seems like there's now something wrong with online judge on this problem, my accepted solution from the contest gets WA

Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET
I think you are right. I didn't take part in the contest cause I participated in the real-time contest held with this problemset last month. But I solved this problem during the real-time. And now, amazingly the simple Ford-Fulkerson code with that very idea is getting WA.
You should never take more than you give in the circle of life.

New poster
Posts: 42
Joined: Sun Jul 31, 2005 2:07 am
Contact:
Shame on you! You can so easily make I/O yourself! Generate random matrices, sum their rows and columns, and you get your input. Checking if the output is correct is a trivial coding exercise, too.
Ok, I'm sorry. I knew that. But what to do when all my attempts seems right to me, but not to the judge? There are various reasons why paople wants help.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
But what to do when all my attempts seems right to me, but not to the judge?
Let the admins/problemsetters know about it, for example, by posting in 'Bugs & Suggestions' forum (I've just did it.)

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm
graph looks like sum_rows - rows - colums - sum_columns, is right?
I still WA :'(
Last edited by FAQ on Sun Sep 03, 2006 4:25 am, edited 1 time in total.

Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET
Yes, it is (source -> sum of rows) : (rows -> columns) : (sum of columns -> sink). Btw, what did you set as (rows->columns) capacity value?
You should never take more than you give in the circle of life.

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm
I sent you a PM

rammestain
New poster
Posts: 18
Joined: Fri Apr 21, 2006 11:34 am
Is this reverese of max flow? I am not familiar with max flow very much, please help me doing this problem

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
matrix entry range [1,20], so i assign capacity 20 to each edge joining row and column, but how to tackle the lower part, if i run simple ford-fulkerson, any matrix entry could be 0, but i have to take care about it, please help me
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan
ayon wrote:matrix entry range [1,20], so i assign capacity 20 to each edge joining row and column, but how to tackle the lower part, if i run simple ford-fulkerson, any matrix entry could be 0, but i have to take care about it, please help me
ayon wrote:matrix entry range [1,20], so i assign capacity 20 to each edge joining row and column, but how to tackle the lower part, if i run simple ford-fulkerson, any matrix entry could be 0, but i have to take care about it, please help me
First , thanks to Mohammad Mahmudur Rahman and FAQ .

I never have a thought that turn this probelm into a graph probelm

hi , ayon .
actually you can turn the "1" as 0+1
that is all
studying @ ntu csie

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
solved the problem. i flowed 1 unit through all row -> column edge before running ford-fulkerson
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
ayon wrote:solved the problem. i flowed 1 unit through all row -> column edge before running ford-fulkerson
you can also subtract C from each row sum, and R from each column sum.

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
sclo wrote:you can also subtract C from each row sum, and R from each column sum.
ya i did exactly that, and assigned capacity 19 to each row->column, both have the same meaning
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

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

any backtrack solution..

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..????