You are not logged in. Please login at www.codechef.com to post your questions!

×

[closed] What is offline query?

While trying to solve http://www.spoj.com/problems/DQUERY/en/, I came across an offline solution. It sorted the queries before hand and solved it. Can anyone help me understand the approach? How can storing the queries beforehand solve the problem?

asked 23 Sep '15, 08:32

dragonemperor's gravatar image

3★dragonemperor
89321134
accept rate: 10%

closed 27 Sep '15, 13:29

The question has been closed for the following reason "The question is answered, right answer was accepted" by dragonemperor 27 Sep '15, 13:29


EDIT: Here is a video editorial on Mo's algorithm. It uses offline query processing with SPOJ - DQUERY problem as a working example.
Mo's Algorithm - DQUERY

This problem belongs to the class of problems:

1) Here is a set of elements to be queried.

2) Here are the queries.

3) Mamu! Give me red. :-P

An offline algorithm allows us to manipulate the data to be queried, before any answer is printed. This is usually only possible when the queries do not update the original element set. So we have the option of completing step 1, and doing some processing on the elements. This processing should enable us to answer any subsequent query very efficiently.

Then we go to step 2, where we print the pre-computed answers or use the processing after step 1 to get the answers quickly. Finally, print each answer.

As an example, try to find the number of inversions for any given range (l,r) in an array where 1<=l<=r<=n. Then try to do this for k queries. You will find the offline solution to be efficient.

Also, note how the processing after step 1 is similar to preprocessing is general questions (Finding primary numbers from 1 to n before checking for primality, etc...)

link

answered 23 Sep '15, 09:10

gkcs's gravatar image

4★gkcs
2.6k11127
accept rate: 9%

edited 16 Mar '17, 10:13

Thank you. This helps. But I failed to solve my first offline query problem. I have posted that as another query. Can you take a look at that please?

(23 Sep '15, 11:40) dragonemperor3★

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×69

question asked: 23 Sep '15, 08:32

question was seen: 2,594 times

last updated: 16 Mar '17, 10:13