Subprnjl - editorial

general
, , , , , ,
41

Yup I got. I used treap.

42

I think the test cases were weak. O(N^3) solutions also got accepted. Check this one.
Link

43

nice editorial!

44


post it here… don’t ask for free karma points…

45

That’s kind of excuse. Sorry. Ordered statistics tree is not something beginner wants to know at first. I hope easy problems are actually easy to solve for beginners. Otherwise it seems that the platform discriminates the participants since this problem looks easier for experienced participants.

46

Worth mentioning that the BS solution can be sped up substantially by initializing M to the previously found B_x. Amazingly, I still could not get this to pass TL in python :frowning:

47

@admin: How a solution gets complete AC when it takes 3.74 sec for some test cases and written in Java? What is the time limit for this problem for JAVA?

48

Can you explain it please?

49

Thanks a lot!

50

<3 for O(T*n^3)

1 Like
51

Look what I found while checking some solutions.

  1. https://www.codechef.com/viewsolution/23432969
  2. https://www.codechef.com/viewsolution/23491310
  3. https://www.codechef.com/viewsolution/23500523
  4. https://www.codechef.com/viewsolution/23483846
  5. https://www.codechef.com/viewsolution/23429480
  6. https://www.codechef.com/viewsolution/23427050
    All same code. Mass cheating going on here.
52

java and python are slow languages that’s why codechef and all OJs provide time multipliers for them. for java its x2, and for python its x5

53

I know they are slower but its not mentioned anywhere in the problem. Isn’t it?

54

Solution of Another Solution mentioned in Editorial.

Just Instead of Two heaps I maintained one Max Heap and one Array. I got AC in 0.58 seconds.

https://www.codechef.com/viewsolution/23590325

55 
That's kind of excuse. Sorry.

Dont be, lul. Neither I owe you any explanation nor do you. Its anyways my own opinion and not the setter/admins.

Ordered statistics tree is not something beginner wants to know at first.

Thats a very subjective thing. I can argue the same for other data structures like heap, segment tree, set etc. and say they should not be given as “Beginners will want a easy problem which they can solve.”

looks easier for experienced participants.

Which is alright lol.

Lastly, if everyone solves easy problem means they are learning nothing. Personally against that.

56

Hmm that all mean we shouldn’t have any category in Practice section like Easy, Medium, etc! Something related to segment tree or BIT shouldn’t be in easy in that case.

57

I passed the testcases using a persistent segment tree to know the value of the kth element in a range [l,r]. Each query takes log2(N), so passes all the testcases in N * N * log2(N). Nice question if you want to learn different methods to find the kth element in range [l,r] in different complexities. I referred Merge Sort Tree, Order Statistics Tree, and an old Codeforces blog. Beautiful problem :smiley:

58

I used the Persistence segment tree for finding kth smallest element. Is this is what the editorial is talking about?

59

Hello @prmondal the test cases were weak and you can even solve this question with any tree and hence it’s an easy question… Okay fine ?

60

Here is an sample soln https://www.codechef.com/viewsolution/23473452