InuyamaAoi's blog

By InuyamaAoi, history, 7 weeks ago, In English,

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

(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?

Read more »

 
 
 
 
  • Vote: I like it
  • +11
  • Vote: I do not like it

By InuyamaAoi, history, 3 months ago, In English,

If you clicked my profile, you can know that my e-mail account registered in Codeforces is iDOLM@STER.life, 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 sakura@kyouko.moe, equally configured with idolm@ster.life 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 iDOLM@STER.life. (You can use RFC822 standard anyway)

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

Read more »

 
 
 
 
  • Vote: I like it
  • +89
  • Vote: I do not like it

By InuyamaAoi, history, 6 months ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it
  • +31
  • Vote: I do not like it

By InuyamaAoi, history, 15 months ago, In English,

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?

Read more »

 
 
 
 
  • Vote: I like it
  • +161
  • Vote: I do not like it

By InuyamaAoi, history, 16 months ago, In English,

Thanks in advance.

Read more »

 
 
 
 
  • Vote: I like it
  • -22
  • Vote: I do not like it

By InuyamaAoi, history, 3 years ago, In English,

Hello, I am Paohu, 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

Read more »

 
 
 
 
  • Vote: I like it
  • +28
  • Vote: I do not like it

By InuyamaAoi, history, 4 years ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it
  • +35
  • Vote: I do not like it