- Problem Link: https://cses.fi/problemset/task/2402
- I have solved this problem using component merging ideas. complexity: $$$O(Nlog^2(N))$$$
- Numbers belonging to the same component are assigned in the same stack.
- One observation I could see was, that if I am able to do an output operation, it's always optimal to output the number as early, without delaying the output operation.
- Another observation, we could maintain currently active numbers, and if any new number $$$X$$$ is added, we could make a component for all numbers < $$$X$$$
- I felt happy to solve this problem on my own, as it had only 73 correct submissions till now.
- I am curious to know if there exists a simpler approach (any mind-blowing observation/ lower complexity) to solve this.
→ Pay attention
→ Streams
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Dec/22/2024 17:33:44 (i1).
Desktop version, switch to mobile version.
Supported by
Another way to think of the problem is think of the range for how long each number has to be be in some stack. Then problem turns into you have set of ranges where you create edge between two ranges if they partially intersect, bipartite color this graph. It is a standard problem, you can look at solutions to JOISC port facility.
nice, i did something similar
How did you add the edges??...Won't it get n^2 or is there any better way