Добрый день!
Только что закончился этап Открытого Кубка.
Давайте поделимся решениями.
Интересуют B,G,F.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Name |
---|
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
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)
I guess only remaining are H, I and J. Any thoughts?
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.
You can find analysis here.
need upsolving ...
You may upsolve at Yandex.contest — it works well even while problems have not been added to ejudge upsolving.
how can I register there?