Hi, I am Konijntje, staff of solved.ac.

We will hold 2024 KSA Automata Winter Contest · Arena #22. The problems are prepared by Automata, an algorithmic problem-solving research group of Korea Science Academy of KAIST. (solved.ac arena page / acmicpc.net contest page).

(huge thanks to wizardrabbit for making this banner)

Contest Information

• Time: https://www.timeanddate.com/worldclock/fixedtime.html?msg=2024+KSA+Automata+Winter+Contest&iso=20240224T1900&p1=235&ah=5, 300 minutes
• No. of Problems: 11, 100 points each = 1100 points total
• The questions are sorted in order of difficulty expected by the jury.
• Statements are available in both English and Korean.
• Every problem has partial points.
• At least one of the problems will be interactive.
• There may be some problems related to mathematics.
• Penalties are calculated based on (the time you spent to gain the highest score in the contest). The time is measured in minutes from the start of the contest.
• The scoreboard will freeze 90 minutes before the contest ends.
• There are bonus time/memory limits for some languages. Check here for details.
• Editorial will be posted after the contest ends.

Please refer to the following guide for registering for the Arena contest: — https://help.solved.ac/en/arena/getting-started/link-account

This contest is a solved.ac Arena contest. The following terms apply to an Arena contest.

• Your performance in the Arena will change your arena rating if you register on the solved.ac Arena page.
• Registrations are open until 5 minutes before the contest starts. You can cancel registration anytime before the contest begins.
• You can participate in the Arena without registering. In this case, your rating will not change.
• Please note that your rating will change even if you don't make a submission in the arena if you're registered.

Participants ranked 1st through 31st will receive a mobile voucher that can be used in Korea.

Also, 11 special prizes with hidden conditions are prepared. We deliver them internationally!

Participants get a solved.ac badge if they score 100 points or more, and a solved.ac background if they score 202.4 points or more.

(The above information may change depending on the situation of the staff.)

Problems have been prepared by: aaronkim00, flakepowders, hwpark12, mickeyjung, MoonlightWarrior, sooahn07, and zamong_juice.

We would like to thank everyone who made this contest possible:

• ai4youej, alex0211, 15631164, annyeong1, BoYangKu, chromate00, Eunha, FD..LH..lloyJ, gs20036, kiwiyou, kookeudas, naeby, parkky, shiftpsh, utilforever, wizardrabbit, and Wonsei for testing,
• utilforever for generously sponsoring our contest,
• Baekjoon Online Judge and solved.ac for great platforms.

We look forward to your participation. Thank you!

Hi, I am Konijntje, staff of solved.ac.

We will hold SciOI 2023 Open Contest · Arena #16 (solved.ac arena page / acmicpc.net contest page).

Contest Information

• Contest time: December 30th, 13:00 — 18:00 (UTC+9, 5 Hours)
  • You may refer to the following link: https://www.timeanddate.com/wo...
• Problems and points: 10 problems × 100 points = total 1000 points
• Problem Type: Interactive and two-step problems may exist.
• Difficulty: The problems are divided into sections A, B, and C. Inside a section, the problems are sorted in increasing order of difficulty (expected by the jury). Additionally, problems A-1 and A-2 are the easiest two problems in the contest.
• Statements: Both available in Korean and English.
• Penalty: Will be determined based on the timestamp of your latest update to your highest score. No additional penalties will be applied for incorrect submissions.
• Scoreboard Freeze: Does not exist.
• Time limit scaling: There are handicaps for some languages. For additional information, please check: https://help.acmicpc.net/language/info
• Editorial: Will be released after the contest ends.

Arena Information

• This contest is a solved.ac arena contest. (Arena #16)
• If you want your arena rating to change, register for the arena at https://solved.ac/arena before the contest. Registration is open up to five minutes before the contest and can be canceled up until the start of the competition.
  • Be aware that your rating will change even if you do not submit any code in the arena.
• If you don't want your arena rating to change, you may participate in the contest without arena registration.

Prize Information

• solved.ac prizes (exclusive for solved.ac linked accounts)

  • solved.ac badge: Given to participants with 100 points or higher score
  • solved.ac background: Given to participants with 200 points or higher score

• Ranking Awards (These are vouchers that can be used in Korea.)

  • First Prize (1st — 3rd place): BBQ Golden Olive Chicken + Coke Voucher (BBQ Chicken)
  • Second Prize (4th — 10th place): Thigh Burger Combo Voucher (Mom's Touch)
  • Third Prize (11th — 15th place): Baskin Robbins Single Regular Ice Cream Voucher (Baskin Robbins)

• Special Awards

  • Special Awards (5 people): Subway 10,000 KRW Voucher (Subway)
  • The conditions for special awards are revealed after the contest ends.

Please refer to the following guide for registering in the Arena contest:

• https://help.solved.ac/en/arena/getting-started/link-account

We look forward to your participation. Thank you!

Hi, I am Konijntje, staff of solved.ac.

We will hold an onsite Grand Arena event in the Republic of Korea. If you've previously participated in the Arena contests and willing to visit Korea in February, we welcome you!

This on-site competition requires participants to attend the competition site to participate physically. If you cannot participate in the on-site competition, please apply during the application period for this competition's mirror contest(solved.ac Grand Arena #4), which will be open after the application for participation in this competition has closed.

Please refer to the following guide for registering in the Arena contest:

• https://help.solved.ac/en/arena/getting-started/link-account

Sponsored by NEXON Korea Corporation, Chris 'utilforever' Ohk

English statements are provided in the onsite contest, but please understand that the competition and side events will be conducted mainly in the Korean language.

Please carefully check the information below before registration.

Onsite Overview

• February 3, 2024 (Saturday)
• All That Mind Mullae — 2nd Floor, 55 Mullae-ro, Yeongdeungpo-gu, Seoul, Republic of Korea (Kakao Map, Google Maps)
• Participants must bring their own computing devices, such as laptops.
• The competition will take place from 13:00 to 16:00 KST.
• Participants must complete registration by 11:30 and attend the entire event, which ends at 18:00*.
• Lunch and snacks will be provided.
• Internet searches and personal reference materials are allowed, but communication with other participants is prohibited.

* Leaving early may result in disadvantages for attending future offline events organized by Solved Company.

Registration Deadline

December 30, 2023, 11:59 PM (UTC+9, KST)

Divisions

Although not currently indicated on the registration page, the competition will be held in the following two divisions:

• Division 1 (Arena rating of TBD – X)
• Division 2 (Arena rating of ? – TBD)

Participants in each division of this competition do not overlap**.

Once the list of participants is finalized, divisions will be assigned based on their ratings. However, participants with the following records will be exceptionally placed in Division 1:

• Participants who have placed 1st, 2nd, or 3rd in previous Grand Arenas
• Past winners of Arenas

** In mirror contests, the rating range may overlap.

Selection

Due to limited capacity at the venue, if more than 100 participants apply, selection will be based on the following criteria, in order:

1. Participants with 1st, 2nd, or 3rd place records in previous Grand Arenas
2. Past Arena winners
3. Applicants with the top $$$A$$$ Arena ratings
4. Applicants with the most Arena participation^†, randomly selected among those with equal participation for $$$B$$$
5. Applicants in the top $$$X$$$% of Arena ratings, selected by most Arena participation^† for $$$C$$$, randomly among those with equal participation
6. Applicants in the top $$$Y$$$% of Arena ratings, selected by most Arena participation^† for $$$D$$$, randomly among those with equal participation
7. Applicants in the top $$$Z$$$% of Arena ratings, selected by most Arena participation^† for $$$E$$$, randomly among those with equal participation
8. Applicants selected based on arbitrary criteria set by Solved or sponsors for $$$F$$$
9. Remaining applicants, randomly selected weighted by Arena participation^†

$$$A$$$, $$$B$$$, $$$C$$$, $$$D$$$, $$$E$$$, $$$F$$$, $$$X$$$, $$$Y$$$, $$$Z$$$ will be announced after registration closes and vary based on total participation. ($$$A \le 10$$$; $$$C + D + E \ge 50$$$; $$$F < 10$$$; $$$X < Y < Z$$$)

^† Only participation in Arenas A10 – A16 held after October 24, 2023, is considered. Participation includes organizing, problemsetting, reviewing, participating as a jury in the contest, and attending Arenas which is not rated for the participant. Instances of registration without submission in a competition are not counted.

Souvenirs and Prizes

Souvenirs and prizes will be awarded to onsite participants based on their competition performance. Details on souvenirs and prizes will be announced later.

Souvenirs

• Blue Archive collaboration sweatshirt
• MapleStory collaboration sticker set
• Arena keycap set (OEM layout, five pieces)
• Arena eco bag, notebook, and pen set
• Arena acrylic tier keyring
• Random MapleStory merchandise

Prizes

• Grand Prize (1 per division, 2 total), iPad Air^‡
• First Prize (2 per division, 4 total), AirPods Pro^‡
• Second Prize (4 per division, 8 total), CHERRY MX BOARD 3.0S^‡
• Third Prize (8 per division, 16 total), Logitech G304 LIGHTSPEED^‡
• Additional special prizes are available

^‡ Solved will cover any taxes and fees associated with prize collection.

Rating Reflection

This competition will affect Arena ratings. After the onsite and mirror events' conclusion (solved.ac Grand Arena #4), the scoreboards for each division will be merged, and ratings will be updated accordingly.

Hi, I am Konijntje, staff of solved.ac. It's been a while!

We will hold solved.ac Grand Arena Round 3. (Division 1 / Division 2)

• Time: https://www.timeanddate.com/worldclock/fixedtime.html?iso=20231126T14&p1=235&ah=3, 180 minutes
• Problems:
  • Division 1: 7-8, in ICPC format
  • Division 2: 7-8, in ICPC format
• Difficulty:
  • Division 1: Problems A and B are the first and second easiest problems expected by the jury. The order will be random except for problems A and B.
  • Division 2: Problems are sorted ascending by the difficulty expected by the jury.
• Penalty: 20 minutes; The scoreboard will freeze 30 minutes before the contest ends. Compilation errors do not count toward penalties.
• Scoreboard: ICPC style. The contestant with more solves is ranked in a higher place. If two contestants have the same number of solves, the contestant with the small amount of the sum of penalties over all accepted problems is ranked in a higher place.
• Time and memory: There is a handicap for some languages.
• Rated range:
  • Division 1: Everyone. (Unrated — X)
  • Division 2: Unrated — S+.
  • For participants in overlapping rating ranges, you can register to the division of your choice. Note that Division 1 problems will be harder than that of Division 2 and are expecting participants whose performances in previous Arenas are at least SS.

Previous problems in the Arena contest can be viewed here:

• https://www.acmicpc.net/category/859

This contest is a solved.ac Arena contest. The following terms apply to an Arena contest.

• Your performance in the Arena will change your arena rating if you register on the solved.ac Arena page.
• Registrations are open until 5 minutes before the contest starts. You can cancel registration anytime before the contest begins.
• You can participate in the Arena without registering. In this case, your rating will not change.
• Please note that your rating will change even if you don't make a submission in the arena if you're registered.

Additionally, the following terms apply for Arena with separate divisions.

• Baekjoon Online Judge does not limit you from making submissions to other divisions while in contest. Make sure if you are making submissions to your registered division.
• If there are problems that overlap with other divisions (including Easy/Hard versions, etc.), for the overlapping problems, you must not make submissions to the same problem in other divisions until you get the correct answer to the problem in which division you are registered in. In case of violation, the rating will be calculated as if no problems have been solved in this Arena.

Among the participants registered in the Arena, the top 3 on the scoreboard and 3 randomly selected participants will receive a metal badge commemorating their participation in the Arena as a small souvenir.

Please refer to the following guide for registering in the Arena contest:

• https://help.solved.ac/en/arena/getting-started/link-account

We look forward to your participation. Thank you!

Hi, I am Konijntje, staff of solved.ac.

We will hold 2023 KSA Automata Summer Contest · Arena #4. The problems are prepared by Automata, algorithmic problem solving research group of Korea Science Academy of KAIST.

• Time: https://www.timeanddate.com/worldclock/fixedtime.html?iso=20230818T1930&p1=235&ah=4&am=30 270 minutes
• No. of Problems: 10, 100 points each = 1000 points total
• The questions are sorted in order of difficulty expected by the jury.
• Statements are available in both English and Korean.
• Every problem has partial points.
• The scoreboard will freeze 60 minutes before the contest ends.
• There are bonus time/memory limits for some languages. Check here for details.
• Editorial will be posted after the contest ends.

Please refer to the following guide for registering in the Arena contest:

• https://help.solved.ac/en/arena/getting-started/link-account

This contest is a solved.ac Arena contest. The following terms apply to an Arena contest.

• Your performance in the Arena will change your arena rating if you register on the solved.ac Arena page.
• Registrations are open until 5 minutes before the contest starts. You can cancel registration anytime before the contest begins.
• You can participate in the Arena without registering. In this case, your rating will not change.
• Please note that your rating will change even if you don't make a submission in the arena if you're registered.

Participants ranked 1st through 31st will receive a mobile voucher that can be used in Korea.

However, 8 special prizes with hidden conditions are prepared. Also, among the participants registered in the Arena, 3 randomly selected participants will receive a metal badge commemorating their participation in the Arena as a small souvenir. We deliver them internationally!

Participants get a solved.ac badge if they score 100 points or more, and a solved.ac background if they score 202.3 points or more.

Problems have been prepared by: flakepowders, juneekim7, mickeyjung, and zamong_juice.

We would like to thank everyone that makes this contest possible:

• ai4youej, chromate00, cologne1723, DELTARUNE, Eunha, FD..LH..lloyJ, gs20036, jaime_spat, kiwiyou, leo020630, parkky, petamingks, shiftpsh, sl1slq96, utilforever, and yongwoods for testing the problems and making it much better.
• BaaaaaaaaaaaaaaarkingDog, bennyk0406, jaime_spat, parkky, and utilforever for sponsoring our contest.
• Baekjoon Online Judge and solved.ac for great platforms.

We look forward to your participation. Thank you!

UPD: Editorial

Hi, I am Konijntje, staff of solved.ac.

We will hold solved.ac Grand Arena Round 2.

• Time: https://www.timeanddate.com/worldclock/fixedtime.html?iso=20230813T14&p1=235&ah=3, 180 minutes
• Problems: 9, in ICPC format
• Difficulty: Problems A and B are the first and second easiest problems expected by the jury. The order will be random except for problems A and B. All problems' difficulty will be between Bronze and Diamond by the solved.ac scale.
• Penalty: 20 minutes; The scoreboard will freeze 30 minutes before the contest ends. Compilation errors do not count toward penalties.
• Scoreboard: ICPC style. The contestant with more solves is ranked in a higher place. If two contestants have the same number of solves, the contestant with the small amount of the sum of penalties over all accepted problems is ranked in a higher place.
• Time and memory: There is a handicap for some languages.
• Rated range: Unrated — SS+.

Previous problems in the Arena contest can be viewed here:

• https://www.acmicpc.net/category/detail/3635

This contest is a solved.ac Arena contest. The following terms apply to an Arena contest.

• Your performance in the Arena will change your arena rating if you register on the solved.ac Arena page.
• Registrations are open until 5 minutes before the contest starts. You can cancel registration anytime before the contest begins.
• You can participate in the Arena without registering. In this case, your rating will not change.
• Please note that your rating will change even if you don't make a submission in the arena if you're registered.

Among the participants registered in the Arena, the top 3 on the scoreboard and 3 randomly selected participants will receive a metal badge commemorating their participation in the Arena as a small souvenir.

Please refer to the following guide for registering in the Arena contest:

• https://help.solved.ac/en/arena/getting-started/link-account

We look forward to your participation. Thank you!

Hi, I am Konijntje, staff of the Korean programming site -- solved.ac.

We will hold solved.ac Grand Arena Round 1.

• Time: https://www.timeanddate.com/worldclock/fixedtime.html?iso=20230806T14&p1=235&ah=3, 180 minutes
• Problems: 9, in ICPC format
• Difficulty: Problems A and B are the first and second easiest problems expected by the jury. The order will be random except for problems A and B. All problems' difficulty will be between Bronze and Diamond by the solved.ac scale.
• Penalty: 20 minutes; The scoreboard will freeze 30 minutes before the contest ends. Compilation errors do not count toward penalties.
• Scoreboard: ICPC style. The contestant with more solves is ranked in a higher place. If two contestants have the same number of solves, the contestant with the small amount of the sum of penalties over all accepted problems is ranked in a higher place.
• Time and memory: There is a handicap for some languages.
• Rated range: Unrated — SS+.

This contest is a solved.ac Arena contest. The following terms apply to an Arena contest.

• Your performance in the Arena will change your arena rating if you register on the solved.ac Arena page.
• Registrations are open until 5 minutes before the contest starts. You can cancel registration anytime before the contest begins.
• You can participate in the Arena without registering. In this case, your rating will not change.
• Please note that your rating will change even if you don't make a submission in the arena if you're registered.

Among the participants registered in the Arena, the top 3 on the scoreboard and 3 randomly selected participants will receive a metal badge commemorating their participation in the Arena as a small souvenir.

Please refer to the following guide for registering in the Arena contest:

• https://help.solved.ac/en/arena/getting-started/link-account

We look forward to your participation. Thank you!

UPD: Editorial: https://solved.ac/en/arena/1/editorial

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 Konijntje, 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);
	}
}