Cooling pies problem help

I am trying my hands on problem “Cooling Pies” sectioned under Easy Problems. I have devised an algorithm which I believe is correct. Here are the provided test cases.
2
3
10 30 20
30 10 20
5
9 7 16 4 8
8 3 14 10 10

Now, according to me, If I sort pies weights and rack weight limits in decreasing order, then only those pies can not be cooled whose weight is greater than the first element in the rack weight array, as first element in the rack weight array would be maximum and thus, chef can not use any rack to cool a pie having weight greater than it.

After sorting,

16 9 8 7 4 (pie weights)

14 10 10 8 3 (rack limits)

Now, Since, There is only one pie whose weight is greater than first element of rack limits, it can not be cooled. However, this logic didn’t served and I was responded with wrong answer.

Modifying just a bit in that algo, Now I count only pies whose weight is either less than or equal to first element of rack limits, but still I am being responded in wrong answer.

Please have a look at my code and tell me my mistake.

# include <stdio.h>

# define BUFFER 32678

static char input[BUFFER];
static int pieWt[32];
static int rack[32];

int byteRead = BUFFER;

int readInt()
{
	while(byteRead < BUFFER && input[byteRead] < '0')
	byteRead++;
	
	if(byteRead == BUFFER)
	{
		fread(input, sizeof(char), BUFFER, stdin);
		byteRead = 0;
		
		while(byteRead < BUFFER && input[byteRead] < '0')
		byteRead++;
	}
	
	int num =0;
	
	while(byteRead < BUFFER && input[byteRead] >= '0')
	{
		num = num*10 + (input[byteRead++]-'0');
	}
	
	if(byteRead == BUFFER)
	{
		fread(input, sizeof(char), BUFFER, stdin);
		byteRead = 0;
	
		while(byteRead < BUFFER && input[byteRead] >='0')
		{
			num = num*10 +( input[byteRead++] - '0');
		}
	}
	
	return num;
}

void bubbleSort(int*arr, int max)
{
	int i, j, count=0, temp;
	
	for(i=1;i<=max;i++)
	{
		count = 0;
		for(j=1; j<max;j++)
		{
			if(arr[j] < arr[j+1])
			{
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
				
				count++;
			}
		}
		
		if(count==0)
		break;
	}
}

int main()
{
	int cases, pies, i, count=0;
	
	cases = readInt();
	
	while(cases>0)
	{
		count=0;
		pies = readInt();
		
		for(i=1; i<=pies; i++)
		{
			pieWt[i] = readInt();
		}
		
		bubbleSort(pieWt, pies);
		
		for(i=1; i<= pies; i++)
		{
			rack[i] = readInt();
		}
		
		bubbleSort(rack, pies);	
		
		for(i=1; i<=pies;i++)
		{
			if(pieWt[i]<=rack[1])
			count++;
		}
			
		printf("%d\n", count);
		
			
		cases--;
	}
	
	return 0;
}

I have another query, as I am writing readInt() function over and over again in each of the problems, I have a very strong feeling that instead of providing fast I/O, readInt() slows down my program ? Is it true because scanf() can replace readInt() in this context ?

1 Like

There’s a problem with your logic

Okay let me show you using a example

No of pies = 4

Pies : 16,10,9,8

Racks : 14,4,3,2

your logic will give 3 won’t it?
but the answer is 1 because once 10 is placed in 14 rack no other pies can find a suitable rack.

Its because you are only comparing the pies with biggest rack, but once that rack is occupied with a pie you need to check the second biggest rack, then third…and so on.

You can keep a variable MARKER initialized to 1 and increment it every time you enter the if condition

int marker=1;
for(i=1; i<=pies;i++)
{
   if(pieWt[i]<=rack[marker])
   {
      marker++;
      count++;
    }
}

I submitted your code with the mentioned change and it was accepted here

And scanf() is as effective here because input is not very large

Cheers

1 Like

I had figured out this shortcoming in my logic on the next day on my own. Still, Thanks for considering and your efforts.

No problem :slight_smile:

NOTE: in my opinion, it would be nice if you count++ inversely. assume weight is X, and limit is Y func respectively. we have(or reach) our desired count++ when Y’s element is bigger than or equal to X’s particular element. and in that condition we count++. otherwise, we just pass onto Y’s next element, till we meet the condition.

//