where is QCHEF editorial?

general
,
1

where is QCHEF editorial?

4 Likes
2

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

3

MO’s algorithm i think

4

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
5

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:

6

solved using segment tree.

2 Likes
7

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

1 Like
8

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?

9

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

10

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
11

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
12

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

13

editorial is out !!!

14

editorial out

15

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

1 Like
16

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

17

here is the link for the editorial

18

pre-requisites :
sqrt decomposition, preprocessing