1
\$\begingroup\$

I'm stuck on a problem involving the Gale-Ryser Theorem. The problem's input gives me the row-wise sum of an hv-convex binary matrix(n*m).

e.g. I get {4,3,2,2,1} in the input. It's the row wise sum of the following matrix:

    1 1 1 1
    1 1 1 0
    1 1 0 0
    1 1 0 0
    1 0 0 0

To solve the problem, I have to find the row-wise sum of it's transpose.

i.e. I need to calculate {5,4,2,1}

1 1 1 1 1
1 1 1 1 0
1 1 0 0 0
1 0 0 0 0

Can it be achieved in less than O(n*m)?


I got the answer here.

\$\endgroup\$
  • 3
    \$\begingroup\$ This might be more appropriate on cs.stackexchange.com, and you have already posted there. They'll ask you what you have already tried before giving hints to it. \$\endgroup\$ – jimmy23013 Jun 1 at 11:24
  • 3
    \$\begingroup\$ This could probably still be somewhat salvageable as a challenge. Trivial for golfing languages but solutions in "real" languages could be interesting. \$\endgroup\$ – Shaggy Jun 1 at 22:28