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⁵ nodes and there are M ≤ 10⁵ 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⁵ 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⁶ rows and M ≤ 10⁶ columns. There are C ≤ 25000 carrots. Input provides you x_i, y_i and v_i, which denotes row number of the ith carrot, column number of the ith carrot and taste value of the ith 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⁵ with size N ≤ 10⁵. There are M ≤ 10⁵ 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⁵ 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..