SUBPRNJL - EDITORIAL

binary-search
easy
march19
partial-sums
segment-tree
subprnjl
taran_1407

#61

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.

#62

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


#63

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


#64

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.


#65

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.


#66

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 ?


#67

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


#68

And btw I hope u know that all problems gets 100 points regardless of difficulty and it’s only setter who gets different amount of payment on basis of difficulty… I don’t see any point that u should have any problem… And the O(n^3) soln passes which shows it’s an easy problem


#69

It can be solved by simple sum query Segment tree also and if you don’t even know segment tree then I don’t think you are a competitive programmer yet… It’s very popular tree… You should learn it by now then… And even if u don’t know it… It’s still solvable without it…


#70

Chef and soccer has 1/8 times submission than this problem and it was categorised as easy medium… So what difficulty do you expect for this one ? Same ? Or medium ?


#71

Well I know about segment tree. But for this problem I solved using BIT but after the contest though.
https://www.codechef.com/viewsolution/23587323

One thing I can agree since the constraint is weak it can be solved without any tree. But editorial does not say about it clearly.


#72

Okay :slight_smile: @prmondal
That’s great…


#73

If anyone found difficult solving the problem using the trees…then you can view my solution :slight_smile:

link : https://www.codechef.com/viewsolution/23538302

import bisect as heep
from sys import stdin, stdout
def take_input():
n,k=map(int,stdin.readline().split())
return n,k
def take_input_list():
x=[int(x) for x in stdin.readline().split()]
return x
def main():
n,k=take_input()
a=list(take_input_list())
x=[]
ans=0
b=[]
i=0
while i<n:
x=[0]*(2001)
j=i
b=[]
while j<n:
heep.insort(b,a[j])
x[a[j]]+=1
if x[x[b[(k-1)//((k+(j-i+1)-1)//(j-i+1))]]]>0:
ans+=1
j+=1
i+=1
return ans
for _ in range(int(input())):
if name == “main”:
result=main()
stdout.write(str(result))
print()


#74

My very complex solution which uses Trie :stuck_out_tongue:

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


#75

haha…it’s very complex to understand …but yeah… it’s a good practice to use Data structures instead of using builtin libraries


#76

In the question i found that the Kth element will alaways be the largest in the subarray.


#77

Hi, just a small doubt in tester’s solution: Why LEAFOFFSET is set to 2047? I tried to submit the same solution with different offsets(say 2031, 2046) and got WA but same code passed with 2047 as offset.

Thanks :slight_smile:


#78

please explain the use of OFFSET in tester’s solution ?