11571 - Simple Equations - Extreme!!

All about problems in Volume 115. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

11571 - Simple Equations - Extreme!!

Post by tryit1 » Sat Dec 27, 2008 10:47 pm

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
New poster
Posts: 20
Joined: Mon Oct 20, 2008 6:26 am

Re: 11571 Simple Equations - Extreme!!

Post by SerailHydra » Sun Dec 28, 2008 2:26 am

Thank you so much.

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

Re: 11571 Simple Equations - Extreme!!

Post by Articuno » Sun Dec 28, 2008 11:16 pm

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.
May be tomorrow is a better day............ :)

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 11571 Simple Equations - Extreme!!

Post by Jan » Mon Dec 29, 2008 8:58 pm

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.
Ami ekhono shopno dekhi...
HomePage

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Re: 11571 - Simple Equations - Extreme!!

Post by Robert Gerbicz » Tue Dec 30, 2008 1:26 am

Jan wrote: 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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 11571 - Simple Equations - Extreme!!

Post by Jan » Tue Dec 30, 2008 1:31 am

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.
Ami ekhono shopno dekhi...
HomePage

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Re: 11571 - Simple Equations - Extreme!!

Post by Robert Gerbicz » Tue Dec 30, 2008 2:45 am

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
New poster
Posts: 20
Joined: Mon Oct 20, 2008 6:26 am

Re: 11571 - Simple Equations - Extreme!!

Post by SerailHydra » Tue Dec 30, 2008 3:36 am

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.

User avatar
tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

Re: 11571 - Simple Equations - Extreme!!

Post by tryit1 » Tue Dec 30, 2008 8:27 am

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 11571 - Simple Equations - Extreme!!

Post by Jan » Tue Dec 30, 2008 12:17 pm

Thanks Robert Gerbicz and, tryit1. Got accepted. Just handled the overflow carefully :).
Ami ekhono shopno dekhi...
HomePage

peterkwan
New poster
Posts: 16
Joined: Sun Oct 28, 2007 1:54 pm

Re: 11571 - Simple Equations - Extreme!!

Post by peterkwan » Thu Jan 01, 2009 11:56 am

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.

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Re: 11571 - Simple Equations - Extreme!!

Post by Sedefcho » Mon Feb 16, 2009 1:06 am

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
New poster
Posts: 2
Joined: Sun Oct 11, 2009 8:25 pm
Location: Bangladesh

Re: 102

Post by munzuruleee » Sun Oct 11, 2009 9:15 pm

thank i get my fault .

munzuruleee
New poster
Posts: 2
Joined: Sun Oct 11, 2009 8:25 pm
Location: Bangladesh

Re: 102

Post by munzuruleee » Sun Oct 11, 2009 9:36 pm

which come first

GCB or CGB

aia
New poster
Posts: 5
Joined: Wed Dec 02, 2009 12:01 am

102

Post by aia » Fri Jan 08, 2010 2:54 am

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 ;
}

Post Reply

Return to “Volume 115 (11500-11599)”