send_nodes's blog

What is an offline solution?
By send_nodes, history, 9 years ago, In English

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

  • Vote: I like it
  • +14
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it +46 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can we proccess queries with update in offline mode?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can u elaborate it a little or provide a usefull link?

        → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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.

      → Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply