November Lunchtime Editorials

editorial
, , , , ,
21

I think your link is broken. Can you please fix it.

22

I’ve fixed it :slight_smile:

23

During contest, I first thought of this solution only. But I thought time complexity will be too much. So as your time complexity is O(TQsqrt(N)log(N)) and let T=2 and N=Q=1e5. So that summation is less than 2e5. Then 2 X 1e5*sqrt(1e5)*log(1e5) comes out to be roughly 1e9. I thought that 1e9 will not work in 4 sec. Nice to see it worked. I coded segment tree during contest to remove sqrt factor and place logN factor. So my solution is O(QNlogNlogN). My solution for segment tree : CodeChef: Practical coding for everyone

1 Like
24

Can you explain how the frequency map is constructed?

25

Replied on your post. :slight_smile: Data types int vs long.

1 Like
26

that multiset idea was really cool :slight_smile:

i have done the same but used sqrt decomposition for handing that(using vectors) but this was really awesome !

thanks for sharing this :slight_smile:

27

@ramini For each block, we use a map maintaining the frequency of all (distinct) elements in that block.

28

we don’t have multiset in java any suggestion for this case

29

@ayush201 You could use a Map and store the count of each element. It should have the same complexity.

1 Like
30

@avi224 u take vector<map<int,int>> why int as constraint of A[i]<=10^9?please explain

31

Hey misha, I edited your answer a little to give some formats (Decent formatting + Decent explanation= Profit :stuck_out_tongue: ). Please have a look in case you find concern. :slight_smile:

2 Likes
32

@vijju123 Oh my god, it’s awesome!! Thanks for your work!)

33

@prince367 The A[i]'s are the keys of the maps. The way data is stored in maps is different. If I insert 10^9 into the map, it goes to the first instead of the 10^9 th position as it would do for arrays.

34

You’re welcome :smiley: :slight_smile:

1 Like
35

@vijju123 please profit by editing mine too :stuck_out_tongue:

1 Like
36

Btw, if you’ll use X-fast trie - Wikipedia you can update your solution theoretically to O(Q sqrt (N log log N)), I don’t how it goes practically, next and previous elements can be found in time O(log log N), but insert/erase in O(log N)

4 Likes
37

Done. Please have a look and verify :slight_smile:

1 Like
38

@bazsi700 - CodeChef: Practical coding for everyone i have implemented similar approach here, but it is timing out can you have a look why?

39

@divyansh_gaba7 The problem is you use std::lower_bound in query, which is O(N) on sets. You should use std::set::lower_bound which runs O(\log{N}), thus replace lower_bound(t[l].begin(),t[l].end(),m) by t[l].lower_bound(m).

I faced the same problem once, and posted a blog about it on CF, where I got explanation for it:

40

Probably the problem is with double precision. However you don’t need to precalculate the division into a double, because you can perform standard division each time which takes floor operation anyways.