Блог пользователя send_nodes

Автор send_nodes, история, 9 лет назад, По-английски

I've seen "offline solution" a lot on codeforces. What does it mean? Is it a solution that precomputes answers?

  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +46 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can we proccess queries with update in offline mode?

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      not in general but there are methods with sqrt decomposition of queries that allow you to solve the problem "semi offline"

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      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.

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

You may want to read this to know more about where offline algorithms can be used, and how!