Monk in the Grass Fields - HackerEarth (Sorting)

Problem link: https://www.hackerearth.com/code-monk-sorting/algorithm/monk-in-the-grass-fields/

My code: https://www.hackerearth.com/submission/2962880/

My logic:

  1. Find sum of elements in each row and store in an array called rowsum.

  2. Find sum of elements in each column and store in an array called colsum.

  3. Sort rowsum and colsum

  4. Choose the row sum or column sum with the least value. Let’s say it’s a row which has the least value. Increase that particular row sum by n, and increment all colsum values by 1. Can happen vice versa.

  5. Sort. Repeat.

Might not be the most efficient, but it seems to be wrong as such. I don’t really get the idea described in the editorial in the problem link either. So could someone please clarify why my logic is wrong and in what angle I should approach the problem instead (just a hint)?

1 Like

You need to rethink about your fourth step. Partiicularly the part “Increase that particular row sum by n”.

When you do so, there might be a possibility that the “rowsum” is no longer sorted.

For this, you need to implement Min-Priority-Queue or the “Min-Heap” which is able to do following operations quite efficiently:

  1. Report the Minimum element in the list.
  2. Remove the Minimum element of the list.
  3. Increase an element “k” with key.

All this is done by maintaining the Min-Heap property at all times. If you have implemented Heap-Sort you probably know about this data structure.

2 Likes

Here is a counterexample to your approach :

1
3 2
4 2 1
2 1 4
1 5 6

Correct answer is 14, but your code gives 15 as output.

Check my approach:
https://www.hackerearth.com/submission/3584510/

2 Likes

@ishan_nitj giving 14 as output

Yes, rowsum will no longer be sorted after increasing it by n. That’s why I said sort rowsum and colsum every iteration. But then, it gives WA, not TLE. Is the logic erroneous, or have I committed a minor error in the implementation?

1 Like