Chef and Strange Matrix

general
,
1

What’s wrong with the following code?

http://www.codechef.com/viewsolution/3900513

It is giving me WA.

#include <stdio.h>
int main()
{
    long long int n, m, p, i, j, total_cost, cost;
    scanf( "%lld %lld %lld", &n, &m, &p );
    long long int ar[n][m];
    for( i = 1; i <= n; ++i ){
    for( j = 1; j <= m; ++j ){
        ar[i][j] = j;
    }
    }
    while( p-- ){
    scanf( "%lld %lld", &i, &j );
    ar[i][j] += 1;
    }
    /*
    printf("\n");
    for( i = 1; i <= n; ++i ){
    for( j = 1; j <= m; ++j ){
        printf("%d ", ar[i][j]);
    }
    printf("\n");
    }
    printf("\n");
    */
    if( n == 1 && m == 1 ){
    printf( "0\n" );
    return 0;
    }
    if( m == 1 ){
    for( i = 1; i <= n; ++i ){
        printf( "0\n" );
    }
    return 0;
    }

    for( i = 1; i <= n; ++i ){
    total_cost = 0, cost = 0;
        for( j = m; j >= 2; --j ){
        cost = ar[i][j] - ar[i][j - 1];
        if( cost < 0 ){
	    printf( "-1\n" );
	    break;
        }
        total_cost += cost;
    }
    if( cost >= 0 ){
        printf( "%lld\n", total_cost );
    }
    }
    return 0;
}
2

Try this :

2 2 3

1 1

1 1

1 1

Answer should be

-1

1

but you are getting

-2

1

instead of checking cost==-1 you should check cost < 0

Hope it Helps !!

1 Like
3

Thanks for this. But it is still giving WA.

4

You should also change the condition cost!=-1 to cost >= 0 , if it still giving WA can you share the new code .

5

Please check this http://www.codechef.com/viewsolution/3868911
Why compiler is giving wrong answer, may i get the testcase for which it failed…

6

Yes, of-course I did that. But it is still gave me WA. Edited the code.

7

@tapasweni Your code includes nested loop in terms of n and m. Will your code work for large values like 10^5? I don’t think so… Your code is giving WA probably because it os failing on some small test file otherwise in my opinion, it will give TLE.

Please correct me if I am wrong. :slight_smile:

8

The problem is that you have used dynamic array and it is creating problem . Due to this it gives unpreditable output .Answer is wrong even for the sample test case . https://ideone.com/xTMp9i .

9

Also your solution is O(n*m) i.e. O(10^10) , so even if you remove WA it will give TLE .