I used a little bit of dp with previous and next greater element thing. For every index i if I open it to left then water will flow up to index just after previous greater element. So ans at that index was updated by ans[i]=min(ans[i],ans[pge[i]]+1). And if I open it to right then water will flow up to index just before the next greater element, Now I’ll update ans at index (nge[i]-1) by ans[nge[i]-1]=min(ans[nge[i]-1],ans[i-1]+1). At last I printed ans[n]. click here to see my code.
What is wrong with my solution, I am getting TLE, whereas many submission for this problem has similar code as mine and same logic.
(too long for a comment lol)
On case of weak TC, I see some people wanting an @admin response. Not an official response, but I think I know him/her and cookoff-preparations good enough to answer this.
Well, I will kind of defend the setter here. The test cases were not ridiculously weak - its just that the condition of “If maximum is at one of ends of subarray - terminate and return 1” hacked the large TC which was designated as worst case (I assume).
Like, the worst case is similar to worst case of quicksort - I think its very specific. I got 4 TLEs because I missed that good condition and wrote “If size==1, return 1” - so TCs were not weak, its just that this case was perhaps overseen/not expected. And if you consider that the official solution aint divide and conquer, you’d give setter benefit of doubt.
Preparation for cookoff is very hectic. At times there are multiple last moment changes made to adjust problems to a better difficulty. Even in this problem, initially duplicate heights were allowed which was changed later.
Talking about TCs in long now-
Regarding weak TC in long - lets face it, you have 10 days to break them. There are multiple heuristics to break random cases, especially if T=1 per file - this combined with 10 days time you can reverse engineer the test cases to get AC. In these instances, the definition of strong TC is redefined - “If making strong Test cases for a problem is very difficult, or its expected that contestants can use heuristics, make sure they waste a LOT of time there (especially in short contests).” With that in mind, with CPCOMP took you over 5 hours to solve, I guess TCs are ok. Of course, they could have been better, no denying that, I am simply saying that they were not trash.
And lastly, heuristics is also a skill. Like, getting a deterministic solution to every problem is difficult. If you can get a solution which uses randomness of TCs, and prune it to work on specific manual cases, or perhaps if you find various optimizations to make your code work under different conditions/inputs, I feel its good. It requires skills. A gray coder just starting cp cannot do heuristics - you need skills, you need concepts for that. Once you become good to a level, and are given 10 generous days for a problem perhaps you’d make your non deterministic solution pass with little difficulty.
Like, on a lighter note, I had 2 TCs failing (TLE) in CPCOMP for 70 point subtask. And I knew where the problem was. For my algo the scenario where there are no primes was a big bummer. What to do? I was like, ok…lets just simulate it. Pick random elements, compare them, add random edges. For connection of nodes we need < N edges, after that its just making cycles and useless stuff. So I start with Ans=N componenets. What are the chances that, if I randomly put edges by comparing random elements of array, I will miss a key edge which would reduce the answer? Well…quite likely. But perhaps a little over 60%? 30%? (Didnt do maths. Perhaps its some nCr in numerator and denominator).
Anyways, I give that a try, and well, one of the two passes XD. That again gives out a new info - that the passing TC has/might-have some randomness in it while other TC is very craftfully handmade. Perhaps a little more TL allowing me more simulations could have helped me pass that too, but then it was ok. We get new info we see where we can use xD. Eventually passed after a few hours.
The point, heuristics will be there where you get info per test file. If this, was instead like, you only get info about a subtask (and not of individual TCs in it), it will be much tougher. For Cookoff, its just a mishap twice a row. I am sure they’d make sure to try harder to frame stronger TC next time.
3 Likes
I tried divide and conquer and got green tick !
I haven’t used seg-tree for finding max element just a linear traversal. Thats it!
But
@taran_1407 I am asking this to you because you generally use JAVA and it would be helpful if you or somebody can tell me my mistake.
I have doubt why my first solution got RE but second solution passed.
Note : Just see solve() and dnc() function.
I changed global declaration of arr[] in the solution that passed. But any ways na() function always creates and initialises new array and takes input all array elements.
Can somebody tell me what was wrong in first solution ?
Taranpreet very nice editorial. Thanks, keep doing great work.
https://www.codechef.com/viewsolution/21138623
could you tell me what is wrong with my solution i just found the max then after removing the smaller side of th hills i found the nex max and so on getting wrong answer.
2 Likes
for sequence 4 1 9 5 7 3 2
is there consecutive i and i+1 such that both facing opposite direction for optimal solution
I am not sure if its O(n^2). Could you explain it to me?
Your solution is of O(nlog(n)) not O(n^2) . Divide & Conquer
It is divide and conquer but it is not O(n \log n) since the split will not necessarily be at the center. The worst case is O(n^2) similar to quicksort.
1 Like
@vipsharmavip, not everything that divide a segment in two parts is O(nlogn), it’s much similar to quick sort worst case, like splitting can be non-uniform, and I can even construct a case where this is really O(n^2)
Yes, but if u bound depth of recursion to logN, which you can prove is indeed maximal answer u get O(nlogn).
1 Like
@nidzulandz5 - Yes, a greedy solution (taking the bigger part of the remaining landscape each time from the remaining max hill) is less than \log n, so the best solution will be also.
@nidzulandz, can you shed some light on the proof you are talking about, as I still think it is O(N^2) in the worst case, for example consider the case where elements at even indexes (1-indexing), are decreasing and greater than elements at odd-index.
For example : consider this.
1 5 1 4 1 3 1 2 1
1 Like
int N = 1e9, n = 1e5;
for(int i=1;i<n;i+= 2)h[i] = N - i;
for(int i=0;i<n;i+=2)h[i] = 1;
My code takes 9.01s, on this input .
I don’t know why @admin is silent on this.
I used the same approach as said by editorialist with using segment tree for finding max element.
Is my solution O(n*log(n)) in worst case ?
Idk if its is but it seems to be O(n*log(n)).
##HERE is my solution.
I am not sure because I m dividing it in two parts and then applying the recursive algo.
So it is like binary tree… So seems like not O(n*log(n)) in worst case due to recursive calling.
What do you guys think?
1 Like
@pshishod2645 do you really think, @admin is gonna… shout at it? If in the last cook off… there were such nice test cases and no one spoke… out… so its better we make a habit of having weak test cases specially at CookOffs XDD…