scorpion's blog

Opencup, GP of Central Europe
By scorpion, 10 years ago, In Russian

Добрый день!

Только что закончился этап Открытого Кубка.

Давайте поделимся решениями.

Интересуют B,G,F.

Разбор

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

»
10 years ago, # |
← Rev. 2   Vote: I like it +21 Vote: I do not like it

G: You need some preprocessed array. prevMin, nextMin, prevMax, nextMax. prevMin[i] = j, if j is maximum among such indices that number[i] => number[j]. Similarly others.

Now for each index i, consider the span: (prevMin[i], nextMin[i]) (exclusive range), and find the right most maximum in the range: (prevMin[i], i] and left most maximum in the range: [i, nextMin[i]). These two are possible candidate for maximum and minimum. Say one of these indices is j. Then your answer can be: intersection of: (prevMin[i], nextMin[i]) and (prevMax[j], nextMax[j]).

Take the best among these candidates

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

In div.2 I tried to solve O (or N in my pdf problem set). About Hacktris. How did you solved it? I tried slow variant — O(W*H), but have a mistake at 27 testcase. Can't find my mistake — http://ideone.com/W6eUNZ (Perl)

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

I guess only remaining are H, I and J. Any thoughts?

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

    J. Let's choose some root. For each speleologist, let's compute the highest node in the tree which he can reach on his path (LCA + binary ascent, or how is it called in English). These nodes should form a chain, otherwise the answer is "NIE". Let's take the lowest node from the chain and check it (2 LCA per speleologist). If all the checks pass, we know the answer otherwise the answer is "NIE".

    So, we have 3 LCA and 1 binary ascent per speleologist, which fits in TL if implemented carefully.

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

    You can find analysis here.

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

need upsolving ...

→ Reply