11082 - Matrix Decompressing

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

[Cho]

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]

GREEDY .... ????
WOW!

Can u ......

[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

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

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]

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]

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.

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

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

[Abednego]

Ah. That explains the wrong answers. Thanks.

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

[fh]

nevermind, i realized how to convert it now.

[baodog]

Nevermind... bug fixed.