Sub-Sequence Count

array
optimal
subsequence

#1

Can any one please help me with this problem, i am not able to get to an optimal solution.


#2

first sort the array and then use sliding window to find the subarrays which satisfy the above condition and in the end add “n” to the answer because each element individually is also satisfying the condition.


#3

how will the sliding window be useful in this case as we need to check all subsequences with different lengths.


#4

this is a live problem from ODESSA HACKATHON 2020, on hackerearth.

https://www.hackerearth.com/challenges/competitive/odessa-hackathon-2019/?utm_source=satellite&utm_campaign=odessa-hackathon-2019&utm_medium=link&rem-web=1


#5

I had given the contest yesterday and i thought its over now and there will be no editorial so that’s why i aksed it here.


#6

There is no point in CHEATING!!! a question of a 3 hr contest on a discussion platform. I was not able to get to optimal solution that’s why i asked it here Just to learn.


#7

I can Totally understand your situation. (And may be i should say a sorry too☺)

But, the contest is currently live. If, the solution is discussed, then that is going to help others during live content, which i think, should not be the case.

please, allow the contest to end. :slight_smile:

End date : 18th May’19


#8

Yeah you are right if contest is live then we shouldn’t discuss it ,we can discuss it after 18 and if you were able to solve the problems then we can discuss it.:+1::+1:


#9

This is the wrong solution.


#10

I read the question. Figured out the correct simple approach in under a minute. Will discuss it when contest ends :slight_smile:


#11

Well i tried this and luckily it got accepted :slightly_smiling_face: well would love to see your approach and also please do discuss rest two questions if someone had solved them they two were also really great question.


#12

Ok,ok,sorry,I get it. When you said ‘sort the array’,I assumed the solution is WA…then realized that its ok to sort as guys are only talking about the first and last element.
Sorry :slight_smile:


#13

No issues man :wink: can you help me out with this problem like how to approach it that would be great if you do so
and here goes the link to the problem


see if you get this.


#15

Ok,I’ve solved it. :slight_smile: Its such a nice problem. I’ll write its editorial on Codechef discuss :slight_smile:


#16

3rd question I didn’t see. 2nd one is a basic-trie problem :slight_smile:


#17

I understood the sorting part, but after that the straightforward thing to do is binary search, may I know how/what did you do with sliding window after the contest? Thanks! :slight_smile:


#18

To all…
Please don’t discuss before it ends…


#19

Yup,now,as usual, after getting all nice info about the problem, @l_returns will secretly enter that contest with his tools and weapon and destroy the competition. Beware Guyzz!!:joy: :joy:


#20

:joy::joy::joy: share krte hi Kyo ho details


#21

now the competition is over now can some one help us out with the problem sub sequence count