ikbal's blog

Turkish Team Selection Contest Day1 — Day2 Problems
By ikbal, 10 years ago, In English

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 ≤ 105 nodes and there are M ≤ 105 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.105 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 ≤ ai ≤ 50 and also .

DAY 2

Problem 1

There is a grid with N ≤ 106 rows and M ≤ 106 columns. There are C ≤ 25000 carrots. Input provides you xi, yi and vi, 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 ai ≤ 105 with size N ≤ 105. There are M ≤ 105 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 ≤ 105 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..

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

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

link to problems ?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      Are the in online judges in Turkey?

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +21 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              10 years ago, # ^ |
                Vote: I like it +4 Vote: I do not like it

              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.

              → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        I will see what i can do...

        → Reply
»
10 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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?

  1. (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.

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      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:

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

1st and 2nd both LCT problems?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What is "LCT"?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      link-cut tree

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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!

          → Reply
»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    ikbal

    EMINAYAR

    enesoncu

    KayacanV

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      Congratz :P

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it

        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.

        → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

    Problems are in the same order.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

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

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        I'm the 5th! :P

        → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem 1 — Day 2: "Our rabbit can jump K steps down or K steps right". I think it should be "and" in stead of "or" in this sentence, right?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    It should be or. There is a mistake in formal explanation. I will fix it.

    → Reply
»
10 years ago, # |
  Vote: I like it +20 Vote: I do not like 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?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +31 Vote: I do not like it

      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 ?

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +15 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          Nezzar'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.

          → Reply
»
10 years ago, # |
← Rev. 5   Vote: I like it +7 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

Is it O(N * sqrt(N) * log(N)) ?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Yes it is. And works under 0.5 seconds.

    → Reply