rahulpadhy's blog

By rahulpadhy, history, 8 years ago, In English

I have been trying out this two-pointers question for a very long time. http://www.spoj.com/problems/KOIREP/ But I haven't been able to implement it. I referred to the following Topcoder thread : http://apps.topcoder.com/forums/;jsessionid=85746DDEA3A3E514D06E169F530987BD?module=Thread&threadID=760646&start=0&mc=5#1598832

But my main problem is that I haven't been able to implement it. Can anyone please help me with this 1 ?

  • Vote: I like it
  • +6
  • Vote: I do not like it

| Write comment?
»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Here is my accepted code — http://ideone.com/BEm6BL. You said you have read the solution so just a few notes. I am using something like two-pointers, maybe N-pointers this time. Initially, I sort every row from the matrix and I store all numbers sorted in another array. Then I initialize the pointers so that they point to the first element of each row. The one that points to the minimum element will be the current minimum and we will try to maximize it for a fixed maximum. We can loop over the additional array with the sorted numbers to fix the current maximum. Then we find the pointer which points to the minimum element and try to increase it while it's not greater than the fixed maximum.