where is QCHEF editorial?

where is QCHEF editorial?

4 Likes

Can anybody please let me know what were the prerequisites for solving this problem?

MO’s algorithm i think

I guess the editorial will be published soon. I have solved the problem using the SQRT decomposition principle. My complexity was (N* sqrt(N) + Q * sqrt(N) * log (N)). I am wondering if there exists a better approach, that is, is it possible to get rid off the log(N) part? I have tried the Mo’s algorithm also, but that did not work for me.

1 Like

I got rid off the log(N) part easily. Notice that only sqrt(N) parts are really affected … so for each query you want to check the sqrt(N) parts that were affected, and not all of them.

A really vague explanation, but maybe you had a similar idea, so you will get what I mean :stuck_out_tongue:

solved using segment tree.

2 Likes

Can anyone help in understanding why this solution works: link text

1 Like

I thought it can not be solved using segment trees… Can you please explain your approach? Either here or on the editorial page once it is served?

it,s simple O(N) solution that anyone would think first.Key points
use of hashing where index and query number are hashed

I dont understand why people complicate things by attaching heavy names to simple techniques. This question simply requires basic square root decomposition (I prefer this name to MO’s algorithm). my solution works in N*sqrt(N) and is 80 lines only.

http://www.codechef.com/viewplaintext/6475476

2 Likes

isnt the worst case complexity n^2

if input is like

7 6 n

1 2 3 4 4 5 6

1 7

1 7

1 7

all queries are from beginning to end
and only repeting growth is in the middle

1 Like

Yes that is why I am asking how it got AC?

editorial is out !!!

editorial out

Hi All, we apologize for the situation. We will add strong test cases in the practice session.

1 Like

Hey Alankar63, you can find the editorial here: http://discuss.codechef.com/questions/66188/qchef-editorial

here is the link for the editorial

pre-requisites :
sqrt decomposition, preprocessing