WEIRD2 - EDITORIAL

amortization
data-structure
easy
ltime65
order-statistic
taran_1407
weird2

#3

OMG I also used the setters approach without knowing! Its a lot of fun when you realize you did it in setters method :). Thank you for editorial taran!


#4

this is my code that pass all test cases.however when i use unordered_map it gives wrong answer.suggest some
test case where it fails.

link to my solution:
https://www.codechef.com/viewsolution/21247254


#5

“”"
Now we need to count the number of positions in Suffix [j,N−1] for which A[j]≤F*
“”"

Cannot this be done in a simple way like this instead of using order Statistic Tree?

Just maintain a set (cpp STL) of all elements from j to N-1 .for knowing the number of positions or which A[j]≤F* just use upperbound on that set.

when we want for i-1 just add ith element to that set and use upperbound again.
This takes logn time for each i .


#6

I think there are weak test cases because n^2 approach is working for 100 points . just make array of all different numbers then use two loops for checking all i and j .
here is my solution . .
https://www.codechef.com/viewsolution/21256684


#7

@motif
Lazy tester that what I can say.
If I were in place of tester, this counter tc would have been the first tc which I would have included. :frowning:
From past seven rated contest I’m seeing complains about weak tc :frowning:

P.S. - Posting as the separate answer instead of the comment. Hoping @admin will see this.


#8

Yep you are right , this should be the first counter test case because if this problem can be solved in n^2,then the problem is a cakewalk and the whole story of this editorial ( that sort the array , f* , O(n) , observation etc…) makes no sense ,I hope that next time @admin will take care of this.


#9

I prefer short python solutions. XD


#10

Well, we need to answer queries of type KQUERY, whichever method you may apply.


#11

HERE is my solution.
which is O(n+10^6)
Seems to be same as setter… but this is not O(n*log(n))
Still confused about time complexity… can anyone help ?


#12

reader functions and huge templates and assert statements annoys a lot in checking solutions :frowning:


#13

I agree. So many random defines hinder readibility >_<


#14

@l_returns hacked your soln. Check Hacked Soln.

TC is hard coded instead of reading. Takes 1.5 sec and TL is 1 sec.


#15

Your complexity is omega(T*1e6) but inner loop is not executed many times so it passed.


#16

Such a difference doesnt really matter @aryanc403 …XD


#17

I failed to understand setter soln. So link of your well-commented soln, please. xD


#18

Her (or his…?) profile doesnt show any submission XD


#19

This reminds me of that moment … :stuck_out_tongue:


#20

In the ordered map, all tuples are ordered by key, while in unordered, they can appear in any order, making your solution incorrect, when an unordered map is used.


#21

As usual. I know this profile just logs in to post such comments at my editorials.

Just stop it!!


#22

Setter seems to be having same solution @aryanc403 XD…