ZCO 2016 discussion

general
41

I have the same solution and this should work as the overall complexity turns out to be N^2 log N which works well under the time limit for max test.

Edit: The binary search might cause problems as that adds a extra log N factor. I just used a array to check whether an element existed or not, making it constant time lookup.

42

I hope it doesn’t cause any problems! But, it will take 8-9 iterations for the worst case, so shouldn’t be such a big addition to the complexity, right?

43

i did the same. but foolishly set all the elements of dp array to 1, which could have been done efficiently as well. so time was n*max(a[i]). though it gave 100, will it succeed?

44

I did the same thing. Passed for me for 100.

1 Like
45

We will just have to wait and watch, I guess :stuck_out_tongue: To my knowledge, yes it should give a tle

46

Wow pretests passed for you on O(N^3)?

47

N^2 log N will obviously pass :3

48

O(10^8) should pass.
BTW, logn could have been reduced by storing the index in an array, since all the elements were unique.

2 Likes
49

Try running your code on input of N = 2500, A = {1, 2, 3, …, 2500}. If your code works under 1 second, then you should be fine.

50

Those are like, 2.5*10^7 ops, it should work if your DP was O(n^2) @anupam_datta and @nishantha

51

It ran within a second! :smiley:

But I feel I made a few mistakes, like not setting temp to 0 or 1 at the end of each j loop.

EDIT: The temp thing doesn’t make any difference.

52

I believe that’s not the worst case @sampritipanda

Something like 1, 4, 9, 16… where the answer is not high, will probably be the worst case… Mine takes more than 1 sec for that…

Btw, what were the constraints on length? 1 <= l <= 10^5 right?

53

@nibnalin 2.5*10^8

54

@nibnalin and @anupam_datta I so wish it was 2.5*10^7 xD

55

Length is 0 <= l <= 10^5. What was the exact test case where your codes takes more than 1 second?

56

Sorry for typo. I knew its 2.5*10^8, but it should work I guess, because one codeforces and ideone, it takes 0.6 seconds or so, to run. Hence if you guys had O(n^2) algorithm, and they keep the TL even 1 sec, it has huge chance of passing. Cheer up, otherwise you could personally request them this. :slight_smile:

57

What? what? How did you get time for such heavy duty local testing of your code? And whats your expected score? did your computer work fine at the Delhi centre??

1 Like
58

Sorry but it means you’re program gives wrong answer for some case(s).
Yes, it means 0.

59

Yep, I was pretty surprised. I don’t expect it will pass once they test on larger inputs though.

60

So you’re expecting 100 now? Or did you optimise for O(n^2) ?