It is my favorite moment of year in CodeForces.

Recently, I am solving old Educational Codeforces problem and found this problem, 600D — Area of Two Circles' Intersection. This problem seems quite simple. Description simply says, calculate area of intersection of two area. This problem could be given as one excercise of 10th grade students' math class. What spice it up is real number and its error.

Solution of this problem is (when $$$r_1$$$ = $$$r_2$$$ = $$$R$$$ and $$$D = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$$$)

$$$2R^2(\theta - \sin(\theta)\cos(\theta))$$$ where $$$\theta$$$ is given as $$$\cos^{-1}\left(\frac{D}{2R}\right)$$$.

Which seems quite simple, but you always have to aware of that minus. If there is minus in your formula, you should always be aware of it.

So, when does the error occur? Real error of $$$A-B$$$ occurs when $$$A$$$ and $$$B$$$ is close enough than $$$A$$$ or $$$B$$$. So, If $$$\frac{\theta-\sin(\theta)}{\theta} \sim O(\theta^2)$$$ is close enough to 0, than error will likely be happen. And they are close enough when $$$\theta$$$ is close to 0. Machine Epsilon of long double is $$$10^{-19}$$$. So if $$$\theta \sim 10^{-9}$$$, there likely will be real error.

Let's calculate how $$$\theta$$$ could be small. Let's rewrite $$$D = \sqrt{4R^2-v}$$$ and $$$\theta = cos^{-1}\left(\frac{\sqrt{4R^2-v}}{2R}\right) = \sin^{-1}\left(\frac{\sqrt{v}}{2R}\right) \sim \frac{\sqrt{v}}{2R}$$$. We can choose $$$v$$$ freely, so $$$\theta$$$ could be as small as $$$10^{-9}$$$. But in this case, answer is not large enough to make absolute error large.

To make absolute error large, $$$2R^2(\theta - \sin(\theta)\cos(\theta)) \sim 10^{-6}$$$, $$$10^{18} \times \theta^3 \sim 10^{-6}$$$ which is $$$\theta \sim 10^{-8}$$$. So, By having $$$v$$$ larger than $$$\sim 100 = (10^9 \times 10^{-8})^2$$$ we can exploit.

By using these strategy, We can carefully choose $$$v = 566$$$, $$$v = 6039$$$, and $$$R = 6 \times 10^8$$$ where $$$4R^2-v$$$ is representible as sum of two squares and exploit epsilon of $$$\cos^-1$$$ and $$$\sin$$$ calculation as possible as can. Here are the data:

Input
0 0 600000000
935404269 751677360 600000000

Output
0.00013036020766994

Input
0 0 600000000
976586705 697336653 600000000

Output
0.00000374043529189

Where output is calculated with mpmath library, with 300 digits precision. Most of solutions submitted and accepted failed to answer this.

If there are anything wrong or overly complex part, please write down into comment.

Edvard, please check this issue and solution, and if you can do an action such as changing eps, publish exact model solution, adding data above, and so on, please do so.

Recently, I felt lack of knowledge and techniques for solving various number of cases, probability and expected number problems.

I did not managed to solve a lot of problems including

• Dstorv,
• Gem Island,
• Do I wanna know,
• Solitaire, and
• BBQ Hard.

(For the first three problems, I did not managed to solve problem in contest. And, I think it led to unsatisfying results.)

I really want to be good at this kind of problems, so could anyone give sufficient number of problems, or materials (including book) to improve my skill?

If you clicked my profile, you can know that my e-mail account registered in Codeforces is [email protected], which is both valid(according to RFC822) and quite exotic. (I personally like that term where I got response from SPOJ Forum, when I said that their system cannot my valid e-mail address.)

You might feel some anime addict bought a strange e-mail address, and yes it is.

I think that some of system do not see this as valid e-mail address, most of reason is that life contains 4 character, which makes lots of inconvenience situation to me.

For example, my university mail system is configured to receive mail only matching regex /^[0-9a-zA-Z]([-_\.]?[0-9a-zA-Z])*@[0-9a-zA-Z]([-_\.]?[0-9a-zA-Z])*\.[a-zA-Z]{2,3}$/i, which cannot accept e-mail address containing + character, life domain, and so on.

I think I cannot receive an e-mail including Codeforces. My another email account [email protected], equally configured with [email protected] can receive mail. I did not noticed it quite long, but once I tried to log in polygon, it says me to check e-mail inbox, and I cannot receive an e-mail. (Sure, I checked a spam mail box)

I just want to ask Codeforces to check this issue, and if you are developing e-mail-related system, just want you to think a little about weird anime addict using exotic e-mail address using [email protected]. (You can use RFC822 standard anyway)

UPD: I think issue in codeforces was fixed. Thanks in advance.

Certificate of https://polygon.codeforces.com expired 5 minutes ago,

Is this problem for only myself (such as MITM attack), or it is just expired as my browser told?

MikeMirzayanov

I participated ACM-ICPC World Finals in 2017 and 2018, and I am trying to coach people who are willing to compete ACM-ICPC.

As a participant and educator, I always wondered that "Why there are no syllabus in ACM-ICPC?" IOI has their syllabus. It changes from year to year, but it is least guideline that how can you ready for the competition. For example, 'non-trivial calculations on floating point numbers, manipluating precision errors' is excluded in IOI, so I did not practiced about real precision error deeply (but did in ACM-ICPC, since some problem requires it). Actually handling real numbers in computer is complicated, same recursion formula can earn different result, etc,. You can think about following problem: "Determine whether for integer a, b, c, d." Double precision cannot help you when each number is 5 digit.

Which area you should concentrate on practicing ACM-ICPC or other programming contests? Even well-known part in programming contest is not covered by undergraduate (at least school where I am, Computation Geometry, Graph Theory is for Master's degree.) and some is not covered by even graduate education. You might know about impartial game and Sprague-Grundy theorem about impartial game. Game theory is one of topic for Senior and Graduate student in departure of Mathematics, and the class did not handle about impartial game.

Moreover, do we really have to know about Physics (Newton's laws of motion, Optics, etc,.) while programming? You do when you have to write some simulation program for physics lab or class but really in participating ACM-ICPC or other programming contest? Does it really help us for testing competitive programming skills?

Actually, I am writing this because I am writing a book titled "Mathematics for programming contest." and I have no idea about which area should I write about. I am considering even writing about Matroid theory and Generating function.

I hope programming contest concentrate on algorithmic thinking, not prior knowledge of harsh area. So I have a question. Why there are no syllabus in ACM-ICPC?

Thanks in advance.

Hello, I am TheQueenOfHatred, one of scientific committee of APIO 2016.

We have Open Contest after all official competition ends.

From now on, APIO 2016 Open Contest Registration is available until UTC+0 14:00:00 May 8.

I hope you to take part in if you are available.

Official Site

Open Contest Registration Form

I chose Splay tree as my Balanced Binary Search Tree if I have to implement it.

There are few reasons.

1. It always give amortized O(lg n) time complexity. This is reason why I'm not using treap or skip list. But I think skip list is meaningful than only usage for BBST.

2. It is easy to remember. Unlike other balanced binary tree, such as Red-black tree or AVL tree or 2-3 tree, it has same logic for searching, finding and deleting. Also, Making node as root is straight-forward.

I have implemented Red-black tree once with guidebook in IOI training camp. It took long. (maybe 2h?) But I implemented Splay tree with only 1h in my first implementation. I only saw wikipedia once to implement it just before I started to code.

My code is following.

Its major part is Splay and It is very simple! Anything other is same with just BST.

Maybe implementation of Erase is easier than other BST.

#include<cstdio>
#include<cstdlib>
struct Node{
	Node *l;
	Node *r;
	Node *p;
	int v;
};
Node *root;
void rightRotate(Node *P)
{
	Node *T=P->l;
	Node *B=T->r;
	Node *D=P->p;
	if(D)
	{
		if(D->r==P) D->r=T;
		else D->l=T;
	}
	if(B)
		B->p=P;
	T->p=D;
	T->r=P;
	
	P->p=T;
	P->l=B;
}
void leftRotate(Node *P)
{
	Node *T=P->r;
	Node *B=T->l;
	Node *D=P->p;
	if(D)
	{
		if(D->r==P) D->r=T;
		else D->l=T;
	}
	if(B)
		B->p=P;
	T->p=D;
	T->l=P;
	
	P->p=T;
	P->r=B;
}

void Splay(Node *T)
{
	while(true)
	{
		Node *p=T->p;
		if(!p) break;
		Node *pp=p->p;
		if(!pp)//Zig
		{
			if(p->l==T)
				rightRotate(p);
			else
				leftRotate(p);
			break;
		}
		if(pp->l==p)
		{
			if(p->l==T)
			{//ZigZig
				rightRotate(pp);
				rightRotate(p);
			}
			else
			{//ZigZag
				leftRotate(p);
				rightRotate(pp);
			}
		}
		else
		{
			if(p->l==T)
			{//ZigZag
				rightRotate(p);
				leftRotate(pp);
			}
			else
			{//ZigZig
				leftRotate(pp);
				leftRotate(p);
			}
		}
	}
	root=T;
}
void Insert(int v)
{
	if(!root)
	{
		root=(Node *)malloc(sizeof(Node));
		root->l=NULL;
		root->r=NULL;
		root->p=NULL;
		root->v=v;
		return;
	}
	Node *P=root;
	while(true)
	{
		if(P->v==v) break; // not multiset
		if(v < (P->v) )
		{
			if(P->l) P=P->l;
			else
			{
				P->l=(Node *)malloc(sizeof(Node));
				P->l->p=P;
				P->l->r=NULL;
				P->l->l=NULL;
				P->l->v=v;
				P=P->l;
				break;
			}
		}
		else
		{
			if(P->r) P=P->r;
			else
			{
				P->r=(Node *)malloc(sizeof(Node));
				P->r->p=P;
				P->r->r=NULL;
				P->r->l=NULL;
				P->r->v=v;
				P=P->r;
				break;
			}
		}
	}
	Splay(P);
}
void Inorder(Node *R)
{
	if(!R) return;
	Inorder(R->l);
	printf("v: %d ",R->v);
	if(R->l) printf("l: %d ",R->l->v);
	if(R->r) printf("r: %d ",R->r->v);
	puts("");
	Inorder(R->r);
}
Node* Find(int v)
{
	if(!root) return NULL;
	Node *P=root;
	while(P)
	{
		if(P->v==v)
			break;
		if(v<(P->v))
		{
			if(P->l)
				P=P->l;
			else
				break;
		}
		else
		{
			if(P->r)
				P=P->r;
			else
				break;
		}
	}
	Splay(P);
	if(P->v==v) return P;
	else return NULL;
}
bool Erase(int v)
{
	Node *N=Find(v);
	if(!N) return false;
	Splay(N); //check once more;
	Node *P=N->l;
	if(!P)
	{
		root=N->r;
		root->p=NULL;
		free(N);
		return true;
	}
	while(P->r) P=P->r;
	if(N->r)
	{
		P->r=N->r;
		N->r->p=P;
	}
	root=N->l;
	root->p=NULL;
	free(N);
	return true;
}
int main()
{
	while(true)
	{
		int t;
		scanf("%d",&t);
		if(t!=0 && t!=-1) Insert(t);
		else if(t==0)
		{
			scanf("%d",&t);
			if(!Find(t))
				printf("Couldn't Find %d!\n",t);
			else
				printf("Found %d!\n",t);
		}
		else
		{
			scanf("%d",&t);
			if(Erase(t))
				printf("Deleted %d!\n",t);
			else
				printf("Couldn't Find %d!\n",t);
		}
		if(root) printf("root: %d\n",root->v);
		Inorder(root);
	}
}