10341 - Solve It

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

Moderator: Board moderators

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Fri Feb 24, 2006 12:07 am

It's usually called 'binary search' or 'bisection'.
There's nothing wrong with the algorithm; maybe you have problems with precision.

Read this thread: http://online-judge.uva.es/board/viewtopic.php?t=1058

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Fri Feb 24, 2006 7:31 pm

I used Newton's method to solve it, but would like if someone could point out why it didn't work until I used Jan's approach.

I was getting all the correct outputs for the inputs posted in this thread, but until I switched to first checking that f(0) and f(1) are of a different sign, I was getting WAs (I did handle NaN and Infinity, well, I thought I did).

My question would actually be: How do you know that there is no zero if both f(1) and f(0) are on the same side of the x-axis? I guess it is true in this case, but I couldn't tell by just looking at the function. Do you just chance it and see if it works?

(EDIT: I just played around with gnuplot a bit, it seems that the fact that coefficients are integers has something to do with it, but I still am not 100% sure)

(EDIT(2): sin(x)+cos(x)-tan(x)+x*x-1 has two zeros on [0,1]. It probably doesn't mean anything, because q is supposed to be negative, but still)

Thanks,

Darko

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Fri Feb 24, 2006 9:05 pm

How do you know that there is no zero if both f(1) and f(0) are on the same side of the x-axis?
The function is continuous and differentiable on [0,1]. Just take its derivative, and you'll see that f'(x) <= 0 for all x in [0,1], and for given restrictions on values of p,q,...,u. That means f(x) is non-increasing on [0,1].

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Fri Feb 24, 2006 10:12 pm

Sigh, I feel so stupid. I missed the restrictions at first (Started it last night around 2am), so I just got confused more and more. (I realized that some are only non-positive and some are only non-negative after my 2nd edit - long after my AC, now when I look at the code, I've never even seen the "integer" part, I'm parsing doubles) :oops:

Thanks, mf.

Just one more thing - if you have time: In your experience, what would be the limiting factors to using Newton's method? This is only the 2nd time I used it and I am really fascinated by it (for this problem it gets correct answers in 5 iterations).

Darko

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Sat Mar 18, 2006 1:07 am

Thank You for your reply!
Exactly! It was just precision error and I didn't consider the case when all coefficients are zero :D

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Tue May 23, 2006 8:53 am

Hi fellows!

I got AC 10341 - "Solve It" with bisection, but would like to consider it in terms of Newton-Raphson method. This is to be my first Newton-Raphson :), so I need your help.
This is my code:
(here I get initial approximation of the root by bisection(not that with this bisection only it got AC), - if in 10 iterations the root wasn't found, then begin N-R )
Please help - why this gets WA?

Code: Select all

#include<stdio.h>
#include<math.h>
#define Epsilon 0.00000001
#define oo 21

int p,q,r,s,t,u;

double F(double x){
	/*F(1)<=F(x)<=F(0) for each x: 0<=x<=1*/
	return p/exp(x)+r*cos(x);
}
double G(double x){
	/*G(0)<=G(x)<=G(1) for each x: 0<=x<=1*/
	return q*sin(x)+s*tan(x)+t*x*x-u;
}
/*the equation itself*/
double H(double x){
	return(p/exp(x)+r*cos(x)+q*sin(x)+s*tan(x)+t*x*x+u);
}
/*derivative of the above*/
double dH(double x){
	double f=cos(x);
	return (-p/exp(x)-r*sin(x)+q*f+s/(f*f)+2*t*x);
}
	
int main()
{
	int counter;
	double up,down,f,g;
	double x,y;
#ifndef ONLINE_JUDGE
	freopen("10341.in","r",stdin);
#endif
	while(scanf("%d %d %d %d %d %d",&p,&q,&r,&s,&t,&u)!=EOF)
	{
		if(p==0 && q==0 && r==0 && s==0 && t==0 && u==0)
		{
			printf("No solution\n");
			continue;
		}
		
		q=-q;
		s=-s;
		t=-t;
		if(F(1)>G(1)||F(0)<G(0))
		{
			printf("No solution\n");
			continue;
		}

		up=1.0;
		down=0.0;
		counter=10;
		while(up-down>Epsilon)
		{
			x=(up+down)/2;
            f=F(x);
			g=G(x);
			if(f<g)
				up=x;
			else if(f>g)
				down=x;
			else
				break;
			if(--counter==0)
				break;
		}
		
		if(fabs(F(x)-G(x))<Epsilon){
			printf("%.4lf\n",x);
			continue;
		}

		q=-q;
		s=-s;
		t=-t;
		
		y=x;
		while(fabs((x=y-H(y)/dH(y))-y)>Epsilon)
			y=x;		
		printf("%.4lf\n",x);		
	}
	return 0;
}
Last edited by serur on Tue May 23, 2006 1:57 pm, edited 1 time in total.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Tue May 23, 2006 10:44 am

First of all, code tags can really help :)

Anyway - why do you treat all 0's that way? Now when I think about it, you can pick any x, but someone posted their solution with 0.0000 as answer (just checked, mine does that too).

Took me a while to make it work, but it ended up being my Java solution in C :(

First I check if H(0) and H(1) are of different signs (if not, there is no zero) and then if zeros are maybe at 0.0 or 1.0. Then I do Newton's. I start with x=0.5.

To answer my own question - you can always make a guess for x_0 and then check if it was a good one. After a few iterations, if it is good, it will converge. Meaning - the difference between two elements will be < EPS (like your check - be careful if you pick a bad x_0). If that difference is >EPS, pick another x_0 and try again. That worked for me in 10631.

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Tue May 23, 2006 2:00 pm

Thank you Darko.

I'll see now...
As to 00000 - I really think there is no such input, for my AC code with bisection treated the case in the above way.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Tue May 23, 2006 3:02 pm

Hello again, Darko!
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Tue May 23, 2006 4:55 pm

You are right, there is no need to check around 0 and 1, I probably had that there first then added other stuff later.

Thanks, this actually helped me to figure out what Newton's actually does. I just redid it in Java checking only if it converges and if it does, if it is in [0,1]. For some reason I can't do it in C. Well, "some reason" might be that I don't really know C that well. I was just hoping that by doing it I would improve the time (now that my Java time is gone)

subzero
New poster
Posts: 26
Joined: Mon Aug 15, 2005 5:21 am

Re: 10341 - Solve It

Post by subzero » Tue Sep 02, 2008 10:06 pm

Hi, how are you??

I'm trying this problem but still getting WA... :(
I'm using Newton's Raphson method, I have tryed each test input in this topic and the output is ok...

any ideas?, thanks

Code: Select all

#include <cstdio>
#include <cmath>
#include <iostream>
#define E 2.7182818284590452353602874713526624977572470937
#define EPS 1e-12

using namespace std;

double p,q,r,s,t,u;

double func(double x){
	return p/pow(E,x) + q*sin(x) + r*cos(x) + s*tan(x) + t*x*x + u;
}
double dfunc(double x){
	double se=1.0/cos(x);
	se*=se;
	return -p/pow(E,x) + q*cos(x) - r*sin(x) + s*se + t*2*x;
}
int main() {
	#ifndef ONLINE_JUDGE
	freopen("10341.in","r",stdin);
	#endif
	double s1,s2,x;
	int i;
	while(scanf("%lf %lf %lf %lf %lf %lf",&p,&q,&r,&s,&t,&u)==6) {
		s1=func(0.0);
		s2=func(1.0);
		
		if ((s1>EPS && s2>EPS) || (s1<EPS && s2<EPS))
			printf("No solution\n");
		else {
			x=0.5;
			for (i=0;i<10;i++){
				x=x-func(x)/dfunc(x);
			}
			printf("%.4lf\n",x);
		}
	}
	return 0;
}
There is no knowledge that is no power.

anondo_iut
New poster
Posts: 3
Joined: Sun Sep 07, 2008 6:25 pm

Re: 10341 - Solve It

Post by anondo_iut » Thu Oct 30, 2008 9:25 pm

hi, everyone.
i've solved it using newton-rhapson method;
can anyone plz tell me why the TLE??? :cry:
i am sure there is an infinity loop.but where????
thanks.

Code: Select all

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
	double p,q,qq,r,s,t,u,d,er,rr,ex,x,x1,fx,ffx;
	freopen("1.txt","r",stdin);
	while(scanf("%lf %lf %lf %lf %lf %lf",&p,&qq,&r,&s,&t,&u)==6){
		x=.5;
		if(p==0&&qq==0&&r==0&&s==0&&t==0&&u==0){
			printf("No solution\n");
			continue;
		}
		while(1){	
			er=x;
			ex=exp(-x);
			fx=p*ex+qq*sin(x)+r*cos(x)+s*tan(x)+t*x*x+u;
			d=1/cos(x);
			ffx=-1*p*ex+qq*cos(x)-r*sin(x)+s*d*d+2*t*x;
			if(ffx==0)x+=.01;/*if the denominator is zero i am simply changing it. it is a quadratic equation, so at best two such denominator can come.so it'll not slow down the algorithm much.*/
			else{
				rr=x1=x-(fx/ffx);
				x=x1;
				er=fabs(er);
				rr=fabs(rr);
				q=fabs(er-rr);
				if(q<=.00001)break;
			}
		}
		if(x1<0||x1>1)printf("No solution\n");
		else printf("%.4lf\n",x1);
	}
	return 0;
}

hdtp
New poster
Posts: 1
Joined: Thu Sep 24, 2009 12:47 pm

Re: 10341 - Solve It

Post by hdtp » Thu Sep 24, 2009 6:17 pm

Hello,I get WA many times.
But I really don't know what's wrong in this code.
I think it should be a stupid mistake, but I can't find it....
help me if you can,thank you~

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

//p*e-x + q*sin(x) + r*cos(x) + s*tan(x) + t*x2 + u = 0

int p,q,r,s,t,u;//input parameter

bool in();
double caculate(double x);

int main(){
double lower_bound;
double upper_bound;
double mid;
int count=1;
char input;
int solution;

//freopen("in","r",stdin);
//freopen("out","w",stdout);
while(in()){
lower_bound=0;
upper_bound=1;
mid=(lower_bound+upper_bound)/2;
solution=2;

scanf("%c",&input);

while((upper_bound-lower_bound)>0.00000001){
if(caculate(lower_bound)==0){
solution=1;
break;
}
else if(caculate(mid)==0){
solution=2;
break;
}
else if(caculate(upper_bound)==0){
solution=3;
break;
}
else if(caculate(lower_bound)*caculate(upper_bound)>0){
solution=0;
break;
}
else if(caculate(mid)*caculate(lower_bound)<0){
upper_bound=mid;
}
else if(caculate(mid)*caculate(upper_bound)<0){
lower_bound=mid;
}

mid=(lower_bound+upper_bound)/2;
}
if(count>1)
printf("\n");
switch (solution){
case 0:
printf("No solution");
break;
case 1:
printf("%.4lf",lower_bound);
break;
case 2:
printf("%.4lf",mid);
break;
case 3:
printf("%.4lf",upper_bound);
break;
default:
printf("%.4lf",mid);
break;
}
count++;
}

return 0;
}

bool in(){
if(scanf("%d%d%d%d%d%d",&p,&q,&r,&s,&t,&u)!=6){
return false;
}
else
return true;
}

double caculate(double x){
double result;
result=p*exp(-x)+q*sin(x)+r*cos(x)+s*tan(x)+t*pow(x,2)+u;
return result;
}

Azad Salam
New poster
Posts: 7
Joined: Fri Sep 18, 2009 5:15 pm
Location: Dhaka
Contact:

Re: 10341 - Solve It

Post by Azad Salam » Sat May 01, 2010 7:28 am

Pls someone help me.getting tons of WA :(
here goes my code

Code: Select all

#include <stdio.h>
#include <math.h>
#include <iostream>

#define EPS 1e-4
int p,q,r,s,t,u;
double x,val,low,high,med,val_low,a,b,val_hig;

double calcul(double x)
{
	return (p / exp(x) + q * sin(x) + r*cos(x) + s*tan(x) + t*x*x +u);
}
using namespace std;


int main()
{
	while(scanf("%d%d%d%d%d%d",&p,&q,&r,&s,&t,&u)==6)
	{
		a=calcul(0.0000);
		b=calcul(1.0000);

		if((a > EPS && b > EPS) || (a < -EPS && b < -EPS) )
			printf("No solution\n");

		else if(fabs(a) < EPS)
			printf("0.0000\n");

		else if(fabs(b) < EPS)
			printf("1.0000\n");

		
		else if(p == 0 && q == 0 && r == 0 && s == 0 && t == 0 && u == 0)
		{
			printf("0.0000\n");
		}

		else
		{

			for(low=0,high=.005;high<=1.0000-EPS;low+=.005,high+=.005)
			{
				val_low=calcul(low);
				val_hig=calcul(high);
				if((val_low<-EPS && val_hig > EPS)||(val_low>EPS && val_hig < -EPS))
					break;
			}
			x=0.0000;
			for(;low<=high-EPS;)
			{
				med= (high+low)/2;
				val=calcul(med);
				val_low=calcul(low);
				val_hig=calcul(high);
				if((val < -EPS && val_hig > EPS) ||( val > EPS && val_hig < -EPS))
					low=med;
				else if((val < -EPS && val_low > EPS) ||(val > EPS && val_low < -EPS))
					high=med;
				else
				{
					x=med;
					break;
				}
					
			}
			
			printf("%.4lf\n",x);	
		}
	}
	return 0;
	
}

Thanks in advance

Marheari
New poster
Posts: 1
Joined: Thu Mar 24, 2011 4:58 pm
Location: United States
Contact:

online-judge.uva.es &bull; Post a reply

Post by Marheari » Tue Mar 29, 2011 1:45 am

Hi fellows! I got AC 10341 - "Solve It" with bisection, but would like to consider it in terms of Newton-Raphson method. This is to be my first Newton-Raphson , so I need your help. This is my code: (here I get initial approximation of the root by bisection(not that with this bisection only it got AC), - if in 10 iterations the root wasn't found, then begin N-R ) Please help - why this gets WA? Code: Select all#include<stdio.h>#include<math.h>#define Epsilon 0.00000001#define oo 21int p,q,r,s,t,u;double F&#40;double x&#41;&#123;&nbsp; &nbsp;/*F&#40;1&#41;<=F&#40;x&#41;<=F&#40;0&#41; for each x: 0<=x<=1*/&nbsp; &nbsp;return p/exp&#40;x&#41;+r*cos&#40;x&#41;;&#125;double G&#40;double x&#41;&#123;&nbsp; &nbsp;/*G&#40;0&#41;<=G&#40;x&#41;<=G&#40;1&#41; for each x: 0<=x<=1*/&nbsp; &nbsp;return q*sin&#40;x&#41;+s*tan&#40;x&#41;+t*x*x-u;&#125;/*the equation itself*/double H&#40;double x&#41;&#123;&nbsp; &nbsp;return&#40;p/exp&#40;x&#41;+r*cos&#40;x&#41;+q*sin&#40;x&#41;+s*tan&#40;x&#41;+t*x*x+u&#41;;&#125;/*derivative of the above*/double dH&#40;double x&#41;&#123;&nbsp; &nbsp;double f=cos&#40;x&#41;;&nbsp; &nbsp;return &#40;-p/exp&#40;x&#41;-r*sin&#40;x&#41;+q*f+s/&#40;f*f&#41;+2*t*x&#41;;&#125;&nbsp; &nbsp;int main&#40;&#41;&#123;&nbsp; &nbsp;int counter;&nbsp; &nbsp;double up,down,f,g;&nbsp; &nbsp;double x,y;#ifndef ONLINE_JUDGE&nbsp; &nbsp;freopen&#40;"10341.in","r",stdin&#41;;#endif&nbsp; &nbsp;while&#40;scanf&#40;"%d %d %d %d %d %d",&p,&q,&r,&s,&t,&u&#41;!=EOF&#41;&nbsp; &nbsp;&#123;&nbsp; &nbsp;&nbsp; &nbsp;if&#40;p==0 && q==0 && r==0 && s==0 && t==0 && u==0&#41;&nbsp; &nbsp;&nbsp; &nbsp;&#123;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;printf&#40;"No solution\n"&#41;;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;continue;&nbsp; &nbsp;&nbsp; &nbsp;&#125;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;q=-q;&nbsp; &nbsp;&nbsp; &nbsp;s=-s;&nbsp; &nbsp;&nbsp; &nbsp;t=-t;&nbsp; &nbsp;&nbsp; &nbsp;if&#40;F&#40;1&#41;>G&#40;1&#41;||F&#40;0&#41;<G&#40;0&#41;&#41;&nbsp; &nbsp;&nbsp; &nbsp;&#123;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;printf&#40;"No solution\n"&#41;;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;continue;&nbsp; &nbsp;&nbsp; &nbsp;&#125;&nbsp; &nbsp;&nbsp; &nbsp;up=1.0;&nbsp; &nbsp;&nbsp; &nbsp;down=0.0;&nbsp; &nbsp;&nbsp; &nbsp;counter=10;&nbsp; &nbsp;&nbsp; &nbsp;while&#40;up-down>Epsilon&#41;&nbsp; &nbsp;&nbsp; &nbsp;&#123;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;x=&#40;up+down&#41;/2;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; f=F&#40;x&#41;;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;g=G&#40;x&#41;;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;if&#40;f<g&#41;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;up=x;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;else if&#40;f>g&#41;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;down=x;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;else&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;break;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;if&#40;--counter==0&#41;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;break;&nbsp; &nbsp;&nbsp; &nbsp;&#125;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;if&#40;fabs&#40;F&#40;x&#41;-G&#40;x&#41;&#41;<Epsilon&#41;&#123;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;printf&#40;"%.4lf\n",x&#41;;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;continue;&nbsp; &nbsp;&nbsp; &nbsp;&#125;&nbsp; &nbsp;&nbsp; &nbsp;q=-q;&nbsp; &nbsp;&nbsp; &nbsp;s=-s;&nbsp; &nbsp;&nbsp; &nbsp;t=-t;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;y=x;&nbsp; &nbsp;&nbsp; &nbsp;while&#40;fabs&#40;&#40;x=y-H&#40;y&#41;/dH&#40;y&#41;&#41;-y&#41;>Epsilon&#41;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;y=x;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;printf&#40;"%.4lf\n",x&#41;;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;&#125;&nbsp; &nbsp;return 0;&#125;

Post Reply

Return to “Volume 103 (10300-10399)”