11236 - Grocery store

[sunny]

Getting WA again & again.

Can anyone tell me exactly how many solutions are there in total?

My program prints only 907 solutions which i think is less than the actual number of solutions.

[Robert Gerbicz]

Getting WA again & again.

Can anyone tell me exactly how many solutions are there in total?

My program prints only 907 solutions which i think is less than the actual number of solutions.

Finally I've solved this problem.
The number of the solutions is 949.

[sunny]

finally,got AC.

I missed 42 solutions because i didnt check the solutions where the numbers can be equal.

[pvncad]

Any hint please ?

[sunny]

try to derive a O(n^3) solution from the equation: a+b+c+d=a*b*c*d

[pvncad]

here is my code, i am getting only 667 solutions

Code: Select all

int main () {
   long long a, b, c;
     
for (a = 1 ; 4 * a <= 2000; a ++)
     for (b = a ; a + 3 * b <= 2000; b ++)
           for (c = b ; a + b + 2 * c <= 2000; c ++)
          {
                 long long p = (1.0 * a * b * c);
                 long long s = (0.0 + a + b + c);

                if (p <= 1000000) continue;
            
               long long d = (1000000 * s) / (p - 1000000);

               if ( d >= c && ( s +d ) <= 2000) {
                    double a1 = a/100.0;
                    double b1 = b/100.0;
                    double c1 = c/100.0;
                    double d1 = d/100.0;

                   double s1 = a1 + b1 + c1 + d1;    
                   double p1 = a1 * b1 * c1 * d1;
         
                   if (s1 == p1) {
                        printf("%0.2lf %0.2lf %0.2lf %0.2lf\n", a/100.0, b/100.0, c/100.0, d/100.0);
	          }
           }
}
}

[sunny]

i think precision issue.
change this line : if(s1==p1)

to,

Code: Select all

if(fabs(s1-p1)<1e-9) 

or,

Code: Select all

if ((a+b+c+d)*1000000==a*b*c*d)

[sclo]

how is O(n^3) going to pass the time limit?

[ayeshapakhi]

>>sclo

here it is not exactly 2000^3
optimization is possible because a<=b<=c<=d.
and (a+b+c+d) <= 2000

[Piklu_sust]

O(n^3) certainly get Time Limit Exceed. But not much time to crash a PC.
After running and print the solution you will see that:
Maximum value for a, b, c is 125, 592, 884.
So, the complexity of the algorithm reduces in O(max(a)*max(b)*max(c)).
Now, This will pass the TLE. Other, There is huge pruning in the loop that can make decision for finding a solution or not.