CareerCup

Very interesting problem.

Here's my solution with O(N*M*log(N+M)).

I want to sort all the numbers, and make the path from smallest to largest.Each time we just need to make sure that the current number can be added to the path without violating the rule(using right and down moves).

When it comes to traversing a gride using right and down moves, it's usually useful to think about the problem as traversing the gride layer by layer that layers are secondary diagnols.

When we traverse the layers (secondary diagnols), following condition always should be true.
For two cells (x1,y1) , (x2,y2) in the path: if (x1+y1)<(x2+y2) then x1<=x2 && y1<=y2.
it means, for two cells in path, the one which lies on the lower layer should be on the left-bottom of the second one. (which is obvious).

Now, we can use a set(or sorted array) for having visited layers.Each time we just have to make sure that the current number can hold the above condition true,i.e, for its two immediate layers (above and down) the condition is true.

Time Complexity:
Iterate over all number(N*M) and each time a binary search(lower_bound) on the set.
Totaly: O(N*M*log(N+M))

#include <bits/stdc++.h>

using namespace std;


vector<int> findPath(vector< vector<int> > arr)
{
	int N=arr.size(),M=arr[0].size();

	//first num, second: position,(x,y)
	vector< pair<int, pair<int,int> > > nums; 


	for (int i=0;i<N;i++)
		for (int j=0;j<M;j++){
			if ((i==0 && j==0) || (i==N-1 && j==M-1))
				continue;
			nums.push_back({arr[i][j],{i,j}});
		}

	sort(nums.begin(),nums.end());

	//first: diagonal's number, second: position,(x,y)
	set< pair<int, pair<int,int> > > st;

	//up-left
	st.insert( {0,{0,0}});

	//bottom-right
	st.insert({M+N-2,{N-1,M-1}});

	//M+N-1 is number of all secondary diagonals
	for (int i=0;i<nums.size() && st.size()<(M+N-1);i++){
		int x=nums[i].second.first;
		int y=nums[i].second.second;
		int d=x+y;// current item diganol's number

		auto it=st.lower_bound({d,{0,0}});

		if (it->first == d) continue;
		int x1=(it->second).first;
		int y1=(it->second).second;
		if (x>x1 || y>y1) continue;

		it--;
		x1=(it->second).first;
		y1=(it->second).second;
		if (x<x1 || y<y1) continue;

		st.insert({d,{x,y}});
	}

	vector<int> path;
	for (auto it=st.begin();it!=st.end();it++){
		int x = (it->second).first;
		int y=(it->second).second;

		path.push_back(arr[x][y]);
	}

	return path;
}

int main()
{
	int N,M;
	cin >> N >> M ;
	vector< vector<int> > V;
	V.resize(N);
	for (int i=0;i<N;i++){
		V[i].resize(M);
		for (int j=0;j<M;j++)
			cin >> V[i][j];
	}

	vector<int> path=findPath(V);
	for (int i=0;i<path.size();i++)
		cout <<  path[i] << " " ;
	cout << endl;

	return 0;
}

use DP.
Say matrix is

4 2 5
3 1 6
8 9 7

transform this to

4 24 245
34 124 2456
348 1249 12479

each cell is dependent on cell left and cell up. and each cell has the sorted path so far.

public void mostBeautifuPath (int [][] matrix){
	  	int r = matrix.length ;
	  	int c = matrix[0].length ;
	  	int [] dp = new int [r * c] ;
	  	for (int i = 1 ; i < c ;++i ) {	  		
	  		dp[id (0 , i, c)] = id (0 , i - 1, c) ; 
	  	}
	  	for (int i = 1 ; i < r ; ++i) {
	  		dp[id (i , 0, c)] = id (i - 1 , 0, c) ;
	  	}
		for (int i = 1 ; i < r ; ++i) {
		  for (int j = 1 ; j < c ; ++j ) {
			  if (matrix[i - 1][j] <= matrix[i][j - 1]) {
				  dp[id(i , j , c)] = id (i - 1, j, c);				  
			  } else {
				  dp[id(i , j , c)] = id (i, j - 1, c);
			  }
		  }
		}		
		int i = dp.length - 1 ;		
		List<Integer> rst = new ArrayList<> ();
	    int [] start = coordinator (dp.length - 1, c) ;
	    rst.add(matrix[start[0]][start[1]]) ;
		while (i > 0 ) {
			i = dp[i] ;
			int [] pre = coordinator (i, c) ;
			rst.add(matrix[pre[0]][pre[1]]) ;
		}		
		Collections.sort(rst); 
		
		for (int v : rst) {
			System.out.print(v + " ");
		}
		System.out.println();
	}
	
	public int id (int x, int y, int c){
		return x * c + y ;
	}
	
	public int [] coordinator (int id, int c){
		return new int [] {id / c , id % c } ;
	}