Help with Paintings problem !!

general
, , ,
1

Hey,
I was trying to solve the Paintings problem. I implemented the pseudo-code that was mentioned in the algorithm. I am new to this greedy approach, which makes it even hard to find where the problem lies. I am getting WA in spite it being correct for various test cases i’ve tried. I am attaching the code here.

#include<stdio.h>
#define min(a,b) a<b?a:b
int main()
{
    long long int N,M;
    int H;
    scanf("%lld %lld %d",&N,&M,&H);
    long long int toPaint = N*M;
    long long int ans =0;
    long long int canPaint;
    long long int T[H];
    unsigned long long int C[H]; int i;
    for(i=0;i<H;i++)
    {
        scanf("%lld %lld",&T[i],&C[i]);
    }
    for(i=0;i<H;i++)
    {
        canPaint = min(toPaint,T[i]);
        ans += canPaint *C[i];
        toPaint -=canPaint;
        //printf("%lld %d\n",T[i],C[i]);
    }
    if(toPaint >0)
        printf("Impossible\n");
    else
        printf("%lld",ans);
    return 0;
}

Any suggestion would be of great help !! :slight_smile:

2

Greedy approach simply means that at each step you select the option that is best at the moment.
In this problem, aim is to minimise the total cost of painting. So, obviously we will paint only the required number of cells and not more than that. The greedy approach here is that we start painting from the floor which has the minimum painting cost and then continue painting the floors in the increasing order of their costs. So the key thing missing in your solution is that you are not sorting the floors in increasing order of their costs i.e. according to array C[]. 2nd thing is that your program is not printing newline after printing the answer. Hope this helps :slight_smile:

EDIT: I saw your solution. Looks like you have already realised that you need sorting. But the sorting technique you are using is too slow for the input of size 10^12 hence it is TLE. Try using better algorithm like quick sort and you should get correct answer :slight_smile:

EDIT2:Sorry, you need to sort H numbers and not N numbers. So you sort 10^5 numbers at most which is possible for quicksort to do in given timelimit

3

It won’t be the only problem… Doing whatever with 1012 items leads to TLE, even O(n) approach, it’s just too many…

4

Oh sorry, you have to sort 10^5 numbers not 10^12. Since there are H layers and H <= 10^5. Quick sort will be fast enough for 10^5

5

Thanks for explaining and checking the solution too. I am leaning quick sort to implement in this too. Btw, can you tell me the name of sorting technique i have used in the solution. It’s the only one that i know of as of now. :slight_smile:

6

You have used selection sort. Glad to have helped :slight_smile:

7

Would using the qsort() function be of any help? I know i have to shift the corresponding places in the T[] array as well.

8

Sorry, I didn’t understand this. Which function are you refering?

9

My approach was to declare T[] and C[] globally. And in quick sort function compare only C[] but change corresponding values in T[] as well as C[].

10

Yes, but i did something like this qsort(C,H,sizeof(int),compare) and in the compare function I checked if the values in the C array was in increasing order or not. Something like this return (*(long long int *)a - *(long long int *)b);.

But what i couldn’t understand was how to swap the respective places in the T[] array as well.

Hope this is clear now :slight_smile:

11

Sorry, I still don’t understand your implementation. Why would you need to check whether C is sorted? Anyway, if the only problem is to swap valuesof T, you can simply perform same operations you are performing on C

12

I was able to get AC :slight_smile: I used a structure to hold the values of C and T. Although, it is a bit slow and heavy on the memory.

13

Oh great. I’m glad you got AC :slight_smile:

BTW, I had no idea that C standard library has built in qsort() function! I got to know about it because of your AC solution :stuck_out_tongue: So thank you :slight_smile: