Magic Ranking (MGCRNK)

general
,
1

hey this was the code i wrote when contest was on, 2day i saw the tutorial can’t figure out where my algo gets different… getting WA here please help

 #include<iostream>
    #include<math.h>
    using namespace std;
    
    main(){
        int T;
        scanf("%d",&T);
        while (T--){
            int N;
            scanf("%d",&N);
            int matrix[N+1][N+1];
            
            for (int j=0; j<=N; j++){
                matrix[0][j]=-1000000;
                matrix[j][0]=-1100000;
            }
            
            for (int i=1; i<=N; i++){
                for (int j=1; j<=N; j++){
                    scanf("%d",&matrix[i][j]);
                    if (i>1 || j>1) matrix[i][j]=matrix[i][j] + max(matrix[i-1][j], matrix[i][j-1]); 
                }
            }
            float x= matrix[N][N]/float(2*N - 3);
            cout.precision(6);
            if (x>=0) cout<<fixed<<x<<endl;
            else cout<<"Bad Judges\n";
        }
    }
2

Why are you checking i > 1 and j > 1 .

In case it is a boundary point two options are not available for taking max but one option still needs to be considered and value updated accordingly .
You have initialized very low negative values to 0th row and 0th column which is Okay but you need to remove the check for i > 1 and j > 1 for it to be effective .
Regards
Vineet Paliwal .

3

Hello @charchit,

In addition to the issue Vineet pointed out, I see you are using float…

I would recommend you to use double whenever it’s possible, as double allows more control when it comes to precision formatting, as it was the case in this problem…

Also, you can check my solution to this problem (I was the setter), where I use a slightly different approach than the one used on the editorial…

//constructs DP solution
int max_score(int*** array, int N)
{
	int D[N][N];
    D[0][0] = (*array)[0][0];
    
    for(int i = 1; i < N; ++i)
		D[i][0] = D[i-1][0]+(*array)[i][0];
		
    for(int i = 1; i < N; ++i)
		D[0][i] = D[0][i-1]+(*array)[0][i];
		
    for(int i = 1; i < N; ++i)
	{
		for(int j = 1; j < N; ++j)
		{
			D[i][j] = max(D[i-1][j], D[i][j-1]) + (*array)[i][j];
		}
    }
    return D[N-1][N-1];
}

The idea I use, takes advantage of the fact that on the 1st column and 1st row, you can only move down or to the right, so, the values of the sums are easy to compute for these two particular cases…

Then, once these 2 cases are handled, in the nested for loop, one can generate all the answers as:

D[i][j] = max(D[i-1][j], D[i][j-1]) + (*array)[i][j];

without having to worry about setting some values to -inf, as both “bounds” are already defined after the computations for 1st row and column are done…

Hope I could help,

Bruno

1 Like
4

cool!! use double instead of float… that was all!!
thanks loads indeed u did helped :slight_smile:

1 Like
5

Hi vineet,
but the check does no harm, I got the correct answer anyway using double instead of float. but its needed when i=j=1
yeah but it indeed is a useless instruction that slows down the algo

6

That’s why we all are here for :smiley: