| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
Hi,
Can someone please explain the approach for the following problem :
Problem Link : https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ff08/0000000000386d5c
There's an editorial blog as well, but am not quite able to understand the solution. Editorial Link : https://codeforces.net/blog/entry/80040
Haven't been able to find the solution. Can someone please help?
Have you tried reading the official editorial(aka analysis)?
Hey!
Am sorry, is there an official editorial as well? I couldn't find it anywhere. Can you please share the link to it?
P.S. Nvm, found it. It's right there. I will check it out.
Hi,
I don't seem to get it. I guess there are solutions without using cartesian tree. I tried reading some codes and get the idea, but not able to understand the approach exactly. Can someone please help?
The approach is binary search + RMQ.
I'll just give some hints. Before going to the K-th room, you'll open the (K-1)the door.
If you start at room C, then before opening the door X (assuming it is on the right of C) you must open all the doors between C and X, and you also must open all the doors on the left of C with strength less than the max of all doors between C and X.
Use this along with RMQ to find the number of doors that must be opened before opening an arbitrary door X. Now use this to binary search the (K-1)th door.
I did this using a sparsetable and the solution complexity was $$$O(N log^2 N)$$$. You can see my code from the ranklist for reference.
Might help: https://codeforces.net/blog/entry/80040#comment-662229