11571 - Simple Equations - Extreme!!

[tryit1]

i used long double to get AC . Lots of precision problems and EPS = 1e-12.

Code: Select all

4
350000055 750000012500000000 92500003000002525
790001541 1827015957846402603 498101288421155771
1 1 4
56 63 33

AC output.
50 50000000 300000005
29 90000679 700000833
No solution.
No solution.


Input 
10
1 9603 19211
1 19008 19021
1 9408 18821
2 9504 19018
1 28215 18835
1 18620 18633
2 18810 18830
1 9215 18435
2 9310 18630

AC output

-97 -1 99
-96 -2 99
-96 -1 98
-96 -1 99
-95 -3 99
-95 -2 98
-95 -2 99
-95 -1 97
-95 -1 98
-95 -1 99

[SerailHydra]

Thank you so much.

[Articuno]

I solved "Simple Equations" using brute force method. That solution will certainly get TLE for this problem. Can anyone give some hints please?
Thanks in advance.

[Jan]

Hint 1: xyz = B. So, if |x| is smaller than |y| and |z|, then |x^3| <= B.
Hint 2: x is a divisor of B.

Btw I haven't got accepted yet. Getting WA. So far, I haven't found any bug. I am not using any floating point arithmetic. For finding square/cubic root I am using binary search.

[Robert Gerbicz]

Btw I haven't got accepted yet. Getting WA. So far, I haven't found any bug. I am not using any floating point arithmetic. For finding square/cubic root I am using binary search.

Couldn't that be an overflow error? Does that code get AC for the easy version?

[Jan]

Yeah, I have got accepted for the easy version. Here is my code...

Code: Select all

Accepted..

I cant find any overflow. If you find anything, please let me know. Thanks in advance.

[Robert Gerbicz]

For large numbers your code sometimes doesn't find the solution. Here are 5 such example:

Code: Select all

5
2387162575 717973329951426968 5698749207640446741
2237352967 4503748340026097400 5003636701648133909
2297417884 3760073721300737960 5277585283697652330
2289936967 3843198163089955800 5244186565713749245
2223913532 3690224662037965920 4946159590427260520

But my AC code returns by:

Code: Select all

-33854 -8884 2387205313
4305 467690 2236880972
15995 102328 2297299561
-41091 -40842 2290018900
-48722 -34056 2223996310

[SerailHydra]

A Hint:
(a + b + c)^2 = a^2 + b^2 + c^2 + 2(xy + yz + zx)

At least my solution uses it. And yes, then the biggest trouble is the precision.

[tryit1]

Jan, you have got overflow problem.

your A^2 -4*B can overshoot 2^31*2^31 .
If your B is negative .

Now you have high as INT_MAX ie 2^31 -1 , so high^2 < 2^62 < 6*10^18 . take high as 1LL<<32 and mid as unsigned long long , i got correct answers for the robert's question.

Anyone care to help me with
http://acm.uva.es/board/viewtopic.php?f ... d04#p99255
?

[Jan]

Thanks Robert Gerbicz and, tryit1. Got accepted. Just handled the overflow carefully .

[peterkwan]

I have tried to tackle this problem but I am getting WA. I have passed the given input in this thread. here is my code:

Code: Select all

#include <iostream>
#include <cmath>
using namespace std;

main() {
  int n;
  long double a, b, c, x, y, z;
  long double p, q, d, u, v, phi, e, e1;

  double pi = acos(-1.0);

  cin >> n;
  for (int i=0; i<n; i++) {
    cin >> a >> b >> c;
    p=(a*a-3*c)/6.0;
    q=(5*a*a*a-9*a*c-54*b)/54.0;
    d=p*p*p/27.0+q*q/4;
  //  cout << "P=" << p << ";Q=" << q << ";D=" << d << endl;
    if (d<0) {
      phi=acos(-1.0*q/2.0/sqrt(fabs(p*p*p)/27.0));
      e1=2*sqrt(fabs(p)/3)*cos(phi/3.0);
      e = e1;

      e1=-2*sqrt(fabs(p)/3)*cos((phi+pi)/3.0);
      if (e > e1)
        e = e1;

      e1=-2*sqrt(fabs(p)/3)*cos((phi-pi)/3.0);
      if (e > e1)
        e = e1;
    }
    else if (d == 0) {
      u = pow((-q/2 + sqrt(d)), (long double)1.0/3.0);
      v = pow((-q/2 - sqrt(d)), (long double)1.0/3.0);
      e1 = u + v;
      e = e1;
      e1 = (u + v) / -2.0;
      if (e > e1)
        e = e1;
    }
    else {
      u = pow((-q/2 + sqrt(d)), (long double)1.0/3.0);
      v = pow((-q/2 - sqrt(d)), (long double)1.0/3.0);
      e = u + v;
    }

    x = e + a / 3.0;
    u = a - x;
    v = b / x;
    y = (u - sqrt(u*u-4*v))/2.0;
    z = (u + sqrt(u*u-4*v))/2.0;
   
 //   cout << endl << "A=" << a << ";B=" << b << ";C=" << c << endl;
 //   cout << "R=" << (x - round(x) + y - round(y) + z - round(z)) << endl;
    if (isnan(y) || isnan(z) || x == y || y == z)
     cout << "No solution." << endl;
    else if (fabs(x - round(x) + y - round(y) + z - round(z)) > pow(10.0,-7.0))
     cout << "No solution." << endl;
    else
      printf("%.0Lf %.0Lf %.0Lf\n", x, y, z);
  }

  return 0;
}

Could somebody give some critical inputs that my code may fail? Thanks.

[Sedefcho]

Some more I/O from an ACC program.

I think the trick in this problem (apart from the precision problems)
is to print 'No solution' even when we have a solution but the roots x,y,z are not
three different integer numbers (maybe most people overlook the 'different' part).

So for example, (1,1,1) is not a solution.
Another example, (1,1,2) is also not a solution.

Code: Select all

5
3 1 3
3000000 1000000000000000000 3000000000000
5700000 3468000000000000000 14810000000000
300006 1000060001100006 30001200017
300006 1000060001100006 30001200014

Code: Select all

No solution.
No solution.
600000 1700000 3400000
No solution.
100001 100002 100003

Hope these notes will be of some use to other
people still trying to solve the problem.

[munzuruleee]

thank i get my fault .

[munzuruleee]

which come first

GCB or CGB

[aia]

Hi
I solved this problem , but it's WA
I don't know why could anyone help me ?
thanks in advance
my code :

Code: Select all

#include<iostream>
#include<string>
#include<fstream>
using namespace std ;
fstream fin("IN.txt");
int main()
{
	int bin1[3] , bin2[3] , bin3[3] ;
	string result ; 
	while(fin>>bin1[0])
	{
		int max = 0 ; 
		int sum=bin1[0] ;
		for(int i=1; i<3 ; i++)
		{
			fin>>bin1[i] ; 
			sum+=bin1[i];
		}
		for(int i=0; i<3 ; i++)
		{
			fin>>bin2[i] ;
			sum+=bin2[i];
		}
		for(int i=0; i<3 ; i++)
		{
			fin>>bin3[i] ;
			sum+=bin3[i];
		}
		for(int i=0 ;i<3 ; i++)
		{
			for(int z=0 ; z<3 ; z++)
			{
				for(int j=0 ; j<3 ; j++)
				{
					if(i!=j && i!=z && j!=z)
					{
						int s = bin1[i]+bin2[j]+bin3[z] ; 
						if(s>max)
						{
							max = s ;
							if(i==0 && j==2 && z==1)
								result = "BCG" ; 
							else if(i==0 && j==1 && z==2)
								result = "BGC" ; 
							else if(i==2 && j==0 && z==1)
								result = "CBG" ; 
							else if(i==2 && j==1 && z==0)
								result = "CGB" ; 
							else if(i==1 && j==0 && z==2)
								result = "GBC" ; 
							else if(i==1 && j==2 && z==0)
								result = "GCB" ; 
						}
					}
				}
			}
		}
		cout<<result<<" "<<sum-max<<endl;
	}
	return 0 ;
}