Happy segments | Hackerearth april circuits

editorial
, , ,
10

Hi Rashmi,
here is my submission code

11

You should check out my submission.
I am efficiently using two pointers do that I don’t have to run a loop from l to r for every query.
https://www.hackerearth.com/submission/40966009/

12

I can see a lazy segment tree approach. First input the data, and store all the numbers in a vector<vector<int>> occurrence;, such that occurrence[i][j] gives the index of the jth occurrence of i.

Make a lazy segment tree with all values 0, that allows range addition/subtraction updates and element queries. If the value in the segment tree is not 0, then it’s not a happy segment. The value represents how many values in m don’t like this r.

Then for each value i in m add 1 to the range from the 1st occurrence of i to just before the h_ith value, and from the h_i+1th value to the end. These are the ranges you are not allowed because i won’t have a correct value. sort the queries by l. For every query, if you have to move l forward, undo the last change we made with the value at l, and do the same update. Lets say that update was from ath occurrence to the bth occurrence, and from the cth occurrence to n, then our new update will be from a+1th occurrence to the b+1th occurrence and the c+1th occurrence to n. To check whether it’s a happy segment, just check the element at the index r.

6 Likes
13

I too tried with Mo’s but got TLE(only 9 points), I used a single pointer to check the number of numbers having frequency not equal to the required frequency. Where should I optimize my code still? Link to my solution Link .

14

Hey thanks for the help

15

Try changing block size to 1500

16

same result :neutral_face:

17

thanks thats what i was looking for

18

Hey, I understood till the part you said add 1 in range [1:h’ith -1] and [h’ith + 1:n] for every m.

Can you elaborate the part of answering queries after sorting queries by l, what exactly do i need to update while answering each query?

1 Like
19

Yeah i got it,

Its like consider an element was x at cuurent index.
then, while moving forward I need to update the valid range for the element at this index.

Thanks a lot @everule1 for sharing the approach.

2 Likes
20

It was quite difficult to explain, because a large part of this question is just implementation.

1 Like
21

Here is my submission. I have added comments explaining every step.

1 Like
22

I think there exists a much simpler solution using last and previous indices,2 segment trees and offline processing:

Edit : Segment trees are Min. Max. segment trees

1 Like
23

do you have any resource so that i can get to know about MO’s algo
plz help

24

this is my submission
my approach is almost similar to u
but i m getting tle
can u plz tell me why it is getting tle

25

Finally, I was able to write the AC code with this approach Here.

It took me a lot of debugging, but it was a good problem for implementation.

2 Likes
26

@pksingh290
Prerequisite - - YouTube
MO’s Algo - - YouTube
Practice Problem - - YouTube

27

I’ve walked through the code @mkitkat . But still I’m getting TLE for my Mo’s solution.
Can you have a look and lemme know of any optimisation which can help reduce the time further Submission (41325957) for Happy segments | HackerEarth

28

Can you elaborate what last and previous are here? And please brief about what approach you used?

29

What are doing in loop starting at line 164 in your code?