October Long - SHTARR

Hi,

Can someone please suggest me some test cases for my solution for SHTARR.I tried random cases with some AC solution but I get all my results same.

If anyone wants I can share my test case generator with them :slight_smile:

Thanks!

I believe the trouble is with your lower bound function. In query function, you need two indices, it and it2 which (as i understand) are storing index of element greater than r and l respectively.

For it2 variable, you ought to find the index lower than or equal to r while for it variable, you ought to find the index where element is lower than l.

While ur solution will work in many cases, it might fail (as i believe it did) for cases where the block contains l, other than the start block.

Your code will work well for N<=1000 because in this case, only your start function would be called.

I don’t believe anyone here would be able to actually provide test cases except problem setter/tester because the test case your code will fail are test cases with N>1000.

Hope this helps :slight_smile:

Hey, @taran_1407 the indices it & it2 are actually supposed to store indices with element just greater than or equal to l or r respectively.If you wish you can just have a look at the quick explanation of editorial.

And I even can’t verify a test case with n>1000 but for the sake of this we can just generate random test cases with n=10 and let the BS(block Size) to be around 2 or 3(anything less than 10).I think it would generate same situation as it would for BS=1000 & n>1000.

But, I have tried all cases with BS less than 10 & n=10 and n=10e6 and BS=1000 I have find all my test cases to match with AC Solution :frowning:

The bug is below, whenever you are ready…

Click to view

You just forgot a +1 :stuck_out_tongue:
In the query function it should be l = (it!=sz) ? block[id][it]+1 : block[id][sz-1]+1

1 Like

I myself have posted an editorial on this problem using sqrt decomposition approach which you may refer, alongwith my solution from following link…

https://discuss.codechef.com/questions/114542/unofficial-editorials-october-long-challenge-part-3

PS: Do tell me what’s the error in your code if u find it. I’m interested :slight_smile:

By the way, @anushi I have found the failing test case for you solution id 15886711

Run this test case whith BS = 5

1

12 1

2 5 6 7 2 6 8 8 11 12 10 12

? 4 6 13

Correct answer is 4 while your code gives 5.

Enjoy Debugging :smiley:

Feel free to ask anything…

@meooow why did you spoil the fun of debugging. As i believe, you ought to give her a chance to debug her code. She only asked for test cases where her code was failing. It would have helped her learn to debug…
I knew the bug in code, but i didn’t reveal it for this reason…

Not accusing or anything… Just expressed my view…

Yes I think you are right, she did just ask for test cases. I am making it hidden, she can see it if she wants.

@anushi the above hidden comment has the bug of your code, view it after giving your code a try…

By the way, thanks @meooow for that :slight_smile:

No problem, I get it :slight_smile:

1 Like

@taran_1407 The whole purpose of using that hide content feature (so that she has to click to see) is to give her a chance to debug. And its better to allow her/him/whatever to see the answer if he/she/XYZ gets frustrated with debugging. So, yes, its all cool I guess :slight_smile: :slight_smile:

agreed @vijju123