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

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

11082 - Matrix Decompressing

Post by Nazmul Quader Zinnuree »

Someone give me some I/O, plz

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf »

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 :(

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

Post by Mohammad Mahmudur Rahman »

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

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

Post by Nazmul Quader Zinnuree »

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:

Post by mf »

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

Post by FAQ »

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.

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

Post by Mohammad Mahmudur Rahman »

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

Post by FAQ »

I sent you a PM

rammestain
New poster
Posts: 18
Joined: Fri Apr 21, 2006 11:34 am

Post by rammestain »

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
Location: buet, dhaka, bangladesh

Post by ayon »

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

Post by SRX »

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 :D
studying @ ntu csie

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon »

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
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

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
Location: buet, dhaka, bangladesh

Post by ayon »

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

Post by sohel »

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

Post Reply

Return to “Volume 110 (11000-11099)”