OJ Board

Someone give me some I/O, plz

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

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.

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.

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

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

Yes, it is (source -> sum of rows) : (rows -> columns) : (sum of columns -> sink). Btw, what did you set as (rows->columns) capacity value?

I sent you a PM

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

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

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

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

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.

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

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