Happy segments | Hackerearth april circuits

editorial
, , ,
1

i need a good solution to this problem… the editorial in hackerearth wasn’t good for me…
the question link is below…

please provide a good explanation of concept… i really need to know how to solve these type of questions…in which there are very large queries…
what i thought was of using unoredered map but that gave me TLE… :frowning:
PLEASE HELP ASAP…
THANK YOU

3 Likes
2

I solved using MO’s algorithm and I think test cases were weak because my solu will get a TLE in strong test case.
I am too looking for an explanation using Segment tree or BIT or any other technique.

1 Like
3

Why do you think MO’s should give TLE? I passed it using MO only.

4

Can you share your code?

5

can you give the link to your solution ? I barely got AC with 1.9s with Mo’s

6

can you give the link to your solution ? I barely got AC with 1.9s with Mo’s

7

Here it is Submission (40973320) for Happy segments | HackerEarth

8

Here is solution Submission (40973320) for Happy segments | HackerEarth
walk through it you will get the reason for tle

9

Hey can you help me with segment tree or BIT logic for this. Thanks

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