11082 - Matrix Decompressing

[Nazmul Quader Zinnuree]

Someone give me some I/O, plz

[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]

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.

[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]

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]

graph looks like sum_rows - rows - colums - sum_columns, is right?
I still WA :'(

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

[FAQ]

I sent you a PM

[rammestain]

Is this reverese of max flow? I am not familiar with max flow very much, please help me doing this problem

[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

[SRX]

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

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

[ayon]

solved the problem. i flowed 1 unit through all row -> column edge before running ford-fulkerson

[sclo]

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]

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

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