WA in Carvans

carvans

#1

Here’s the link http://www.codechef.com/problems/CARVANS
#include<stdio.h>
int main()
{
int t, c[100], n, d, ctr, i, j;

    scanf("%d", &t);
while (t--)
{
	ctr = 1;
	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d", &c*);
	for (i = 0, j = 1; j < n; i++, j++)
	{
		d = c* - c[j];
		if (d >= 0)
			ctr++;
		else
			continue;

	}
	printf("%d

", ctr);

}
return 0;

}


#2

When the max. speed of the car is more than the previous one then it should not be counted and the speed of the car should be changed to the speed equal to the speed of the previous one.(i.e. you need to update the speed of the car before processing the next car.)
So you should do this:-
for (i = 0, j = 1; j < n; i++, j++)
{
    d = c* - c[j];
    if (d >= 0)
        ctr++;
    else
    {
        c[j]=c*;
    }
}
Note: You have defined the array of size 100 but this will not be sufficient according to given constraint so define the array of size 10000 as specified in the constraints.


#3

your problem :

Consider your solution against input test case

5

4 5 1 2 3

here is the required situation :

4 4 1 1 1

Your solution neglects the fact that expected speed of carvan is due to the domino effect of all the succeeding carvans and not just the one next to it.

Correction

Instead of

            for (i = 0, j = 1; j < n; i++, j++)
            {
                d = c* - c[j];
                if (d >= 0)
                    ctr++;
                else
                    continue;

            }

USE this:

                for (i = 0, j = 1; j < n; i++, j++)
                {
                    d = c* - c[j];
                    if (d >= 0)
                        ctr++;
                    else
                        c[j]=c*;

                }

Lemme know if it still gives WA.


#4

Refer to my solution here:-
http://www.codechef.com/viewsolution/4047622