The team selection contest for IOI 2015 happened on the last weekend. It is an IOI style contest. There are two days and each day has 3 problems for 5 hours. Here are the short statements of the problems:

**UPD**: I have added problems of the second day too.

### DAY 1

#### Problem 1

There is a rooted tree with *N* ≤ 10^{5} nodes and there are *M* ≤ 10^{5} queries. Initially, all the nodes have the value 0. There are two types of queries. First one gives you two nodes *a* and *b*. For every node lying on the path from *a* to *b* you need to increase all values of the nodes in its subtree. Notice that you might have increased one of the node's value several times. The Second one gives two nodes *a* and *b* as well, and asks you to calculate the sum of subtrees of all the nodes lying on the path from *a* to *b*. You need to print the answers for second queries at modulo 10009.

#### Problem 2

There are *Q* ≤ 2.10^{5} queries. Each of them is in one of the following formats: "PUSH *x*, *v*", "POP *x*". There is an empty tree in the beginning. "PUSH *x*, *v*" means add a new node to the tree with the last unused id(which is the number of PUSH'es so far plus one), and make its parent *x*, v denotes the value of the node. "POP *x*" means delete the node with id *x* from the tree. Every POP operation guarantees that *x* has no parent at the time of the operation. For each PUSH operation, you need to calculate the minimum value of the *x*'s parents.

#### Problem 3

There are *N* ≤ 50 sticks. You need to create a square by choosing a subset of them.

Each of them has a lenght 1 ≤ *a* _{ i} ≤ 50 and also .

### DAY 2

#### Problem 1

There is a grid with *N* ≤ 10^{6} rows and *M* ≤ 10^{6} columns. There are *C* ≤ 25000 carrots. Input provides you *x* _{ i}, *y* _{ i} and *v* _{ i}, which denotes row number of the *i* th carrot, column number of the *i* th carrot and taste value of the *i* th carrot. You are helping a rabbit to travel in the grid. There is an integer *K* given in the input. Our rabbit can jump *K* steps down or *K* steps right. The weird thing is if he jumps out of the grid he returns to the grid from the opposite side.

More formally if rabbit is on ( *x*, *y*) then he can go to (( *x* + *K*) mod *N*, *y*) or ( *x*, ( *y* + *K*) mod *M*). Our rabbit can not jump more than *T* times. In the beginning, you will put the rabbit into any cell. And rabbit will travel in the grid freely. The problem asks you to calculate the maximum possible difference between highest value and lowest value of taste that our rabbit has eaten during the travel.

#### Problem 2 (Time limit for this problem was 5 seconds.)

There is a sequence of integers *a* _{ i} ≤ 10^{5} with size *N* ≤ 10^{5}. There are *M* ≤ 10^{5} queries. Each query gives to you two integers *L* and *R*, after then asks you to calculate the maximum value of the interval that belongs to [*L*, *R*].

More formally you will choose *l* and *r* where *L* ≤ *l* ≤ *r* ≤ *R*. Value of the interval [*l*, *r*] can be calculated with this pseudo code :

```
res = a[l]
last = a[l]
for i = l + 1 to r:
if(last > a[i])
for j = a[i] to last - 1:
res = res ^ j;
else
for j = last + 1 to a[i]
res = res ^ j.
last = a[i]
```

"^" denotes xor. Res equals to the value of the [*l*, *r*] after the process.

#### Problem 3

There is a tree with *N* ≤ 10^{5} nodes and there are *K* ≤ 10 good digits. The problem asks you to calculate number of pairs of nodes that the distance between them consist of only good digits.

PS. First problem from the first day is one of my favorites. I would like to see your thoughts about problems as well. Feel free to ask any questions..

link to problems ?

Unfortunately, there is no online judge that you can submit your solutions.

Are the in online judges in Turkey?

I do not know what I suppose to understand from this sentence of yours.

Do you have site like codeforces.ru,topcoder.com, acm.timus.ru ..?

As far as I know, we only have one online judge, which only contains Turkish translations to problems in other sites like USACO Training Gateway and problems from past (inter)national contests such as COCI, IOI.

That online judge is not that common in Turkey nowadays. We have another online judge that only the students on Summer and Winter Training Camps can use. So, it is not nationwide like bilgisayarolimpiyati.com.

Just get the test data (or make your own) and put it in Gym.

I will see what i can do...

Did you have full feedback during the contest? (IOI-style)

Yes we had.

Hello,

I don't really understand Problem 2. Can you please clarify? Firstly, it seems that you start with a tree with single node of id 1 instead of an empty tree? Otherwise how does the first push operation work?

Secondly, is my understanding of the operations correct?

(PUSH, x, v). Suppose this is the (k-1)th push operation. Add node k to the tree and set node x as the parent of node k. Make the value of node k to be v.

(POP, x). Remove node x. We know that x has no parents.

If this is correct, it seems to be that we will have a tree (or forest), and so every node has a single parent?

I think it would make a lot more sense for POP to guarantee x has no children, not "x has no parents."

I dont agree with you. If pop guarantees that deleted node has no children it becomes much more easy.

As i wrote above pop operation just guarantees that node is one of the roots:

First push operation guarantees that x is equal to -1. We will have a forest due to pop operations.

What were the time limits? (Looking at problem 3)

2 seconds 256 MB

1st and 2nd both LCT problems?

What is "LCT"?

link-cut tree

I do not know how to solve the first problem with link cut tree. But the second one is obvious, though I would not use it instead of a simple solution with a sparse table.

Yeah, I guess you are right, I didn't read the first problem carefully. Can you explain how to solve the second one using sparse table? Thank you!

So who are in the Turkish IOI Team this year? :)

ikbal

EMINAYAR

enesoncu

KayacanV

Congratz :P

ikbal why didn't you go last year were not you in top 4 ?!

Yes, I was not. Though last year, I could not even participate in team selection contest(which is third stage) because I could not passed the first stage which is happening on paper.

PS. I made kind of virtual contest of previous year's team selection contest at the same time it was official happened and end up with 6'th place a year ago. So it was not just first stage's fault.

How many points did you get (for each problem)?

Well, if you are interested in here are the full results

Problems are in the same order.

That 2 point difference between 4th and 5th :-O

Yeah, that's a quite sad story. It is quite odd that there are just 11/600 points between 4th and 7th too.

I'm the 5th! :P

day1 problem 3, as I understand, stick is 1xa[i] dimension. Are we allowed to use a[i]x1 as well?

You just need to choose 4 subsets and each of them needs to have same sum.

Problem 1 — Day 2: "Our rabbit can jump K steps down

orK steps right". I think it should be "and" in stead of "or" in this sentence, right?It should be or. There is a mistake in formal explanation. I will fix it.

First problem from the first day is one of my favorites, too. :D Are there any solutions better than O(N*sqrt(N)) for that problem?

I think it can be done in O(N*lg(N)) using Heavy Light Decomposition.

UPD : O(N*lg(N)*lg(N))so in this case when N <= 10^5 O(N*lg(N)*lg(N)) = O (N*sqrt(N))Wait, what? O(N*log(N)) ? Even if you apply Heavy Light Decomposition to this problem, how can you update or answer the queries with adjacent indexes in O(1)? We cannot even do that for simple Heavy Light problems. Or in the case you wanted to say O(N*log(N)*log(N)), can you please explain your idea in detail ?

Ups you are right,I wanted to write O(N*log(N)*log(N)) thank you.

So how can it be done in O(N*sqrt(N)) ?

I_know_nothing's approach is correct but the solution is not that simple since the constant of the complexity O(N*sqrt(N)) is very large and the implementation is not very simple.

Day 1 Q 1: Split the quiries into sqrt(Q) blocks so we will get a O(sqrt(Q)) version tree to solve. Rebuild data after this block.

Q2: 2^k parent with lgnlgn per query

What is the complexity of your Day 2 Problem 2 code?

Is it

O(N*sqrt(N) *log(N)) ?Yes it is. And works under 0.5 seconds.