I've seen "offline solution" a lot on codeforces. What does it mean? Is it a solution that precomputes answers?
№ | Пользователь | Рейтинг |
---|---|---|
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 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
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 | 151 |
I've seen "offline solution" a lot on codeforces. What does it mean? Is it a solution that precomputes answers?
Название |
---|
If the problem involve processing queries then there are online solutions and offline solution
online means that your solution can process each query before reading the the queries that come after it
offline means that your solution reads all queries then process them , probably you sort the queries in some order so that you can process them faster
Can we proccess queries with update in offline mode?
not in general but there are methods with sqrt decomposition of queries that allow you to solve the problem "semi offline"
Can u elaborate it a little or provide a usefull link?
Yes, sure. Just make sure you don't change the order. A simple example is performing coordinate compression on all values after reading the queries and then processing them in the same order with the compressed values.
You may want to read this to know more about where offline algorithms can be used, and how!