Hi, can anyone help with this task http://www.spoj.com/problems/METEORS/ . First i thought about binary search and segment tree with lazy propagation but that wouldn't work. Can anyone give me hole perspective to this problem? Thanks.
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
6 дней
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
6 дней
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 156 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 24.11.2024 15:25:53 (k2).
Десктопная версия, переключиться на мобильную.
При поддержке
Solution for yet another Div2 A.
Ok, but you want the sum of a group of numbers to become X.
Wow! I thought I've seen this problem before, but it has been an easier one. I'm sorry :p
Is O(N * sqrt(N)) solution ok for you?
Yes, but how did you get sqrt(N)?
Of course there should be M somewhere, but since N ~ M I wrote it in that way.
Ok, but how did you get sqrt?
Let's divide our queries into O(sqrt(N)) groups. We can process all the queries from a single group in O(N) time. When we do it, we can check whether a particular group is filled now. If it does, then let's run all these updates from the last group and get the precise time when it got filled. We can do it point-by point, since every point will be affected by O(sqrt(N)) segments.
This got accepted with two times margin on main, but got TLE on SPOJ :(
Thanks very much. :-D
Something got TLE on SPOJ? That is unbelievable :P! (I got TLEs for optimal complexities algorithms in 3 out of 5 problems I submitted on SPOJ :P)
Their new cluster is ok, but those problems that are checked on the old one are sometimes hard to make them pass.
Btw, it's pretty strange that there is 35 sec TL on some tests on main, while maximum TL on SPOJ is 15 sec.
Got accepted on SPOJ O(N * sqrt(N))
Code
Think about doing binary searches parallel.
That is a really great problem. In Poland parallel binary searching is abbreviated as "Meteors" since that task appeared on finals :P. I was really proud that I have solved it on a contest, but even though I got 70 pts — beware of long long overflow :D.
By the way, if you don't like SPOJ, here is that task on a much better site :P http://main.edu.pl/en/archive/oi/18/met
Can you recommend some good editorial for parallel binary searching? It also would be great if you explain this technique on "Meteors" problem. Thanks in advance.
In binary searching you need to be able to answer questions of form "Is answer greater than x?", so that in log n questions we can find answer. In that problem we need to find values a_1, ..., a_n and trick is that we can answer all of the questions of form "Is a_i greater than x_i?", where x_i are chosen by us, simulating all of the rains just once (pretty easy how to do this). So it suffices to do log n of simulations in order to find all answers.
Sorry to bring up this old thread, but has anyone got an AC using segment tree? here is my implementation of parallel binary search : http://ideone.com/7l4nSx which gets TLE on SPOJ
Edit : NVM, got AC with BIT.