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:
-
Find sum of elements in each row and store in an array called rowsum.
-
Find sum of elements in each column and store in an array called colsum.
-
Sort rowsum and colsum
-
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.
-
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:
- Report the Minimum element in the list.
- Remove the Minimum element of the list.
- 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