scorpion's blog

By scorpion, 10 years ago,

Добрый день!

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

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

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

Разбор

• +19

 » 10 years ago, # | ← Rev. 2 →   +21 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
 » 10 years ago, # | ← Rev. 2 →   0 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)
 » 10 years ago, # |   0 I guess only remaining are H, I and J. Any thoughts?
•  » » 10 years ago, # ^ |   0 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.
•  » » 10 years ago, # ^ |   +34 You can find analysis here.
 » 10 years ago, # |   +3 need upsolving ...
•  » » 10 years ago, # ^ |   0 You may upsolve at Yandex.contest — it works well even while problems have not been added to ejudge upsolving.
•  » » » 10 years ago, # ^ |   0 how can I register there?