Chef and Strange Matrix

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;
}``````

Try this :

2 2 3

1 1

1 1

1 1

-1

1

but you are getting

-2

1

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

Hope it Helps !!

1 Like

Why compiler is giving wrong answer, may i get the testcase for which it failed…

@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.

Thanks for this. But it is still giving WA.

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

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

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 .

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