WA in MAXEP December Long 18 using Egg dropping puzzle approach (Resolved)

general
, ,
1

I am using egg dropping puzzle approach to solve MAXEP problem.

I am not getting why I am getting WA . Here is my code : solution link.

N can be max 150000 & c (cost) can be max 150.
So according to egg dropping puzzle solution constraint (k*(k+1))/2 <= (N=150000), k can be max 548.

And for this approach panel can be broken only 2 times (why because first time panel will break it means we get segment [l,u] where u-l+1<=548 after that we will traverse left to right in segment [l,u] so after second time we will get exact answer we will print and exit).

So total cost = 548 + 2*150 = 848 in worst case.

According to my solution , we will always get answer x according to given constraints.

I am not sure why it is giving WA for few test cases.

Edit:

Resolved :

In my solution, main culprit was this statement u=u+k-1;

So I have updated to this u=min(n,u+k-1) and maintaining previous state here is my working solution

2

It appears that you’ve missed some corner cases. (Like maybe after discovering the first breakage, you are accidentally skipping over corner elements for the linear search.)

Here’s the modified code which clears the first sub task. (Sadly, no changes to your code though). I confirmed using asserts that you are missing corner cases in linear search).

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

I also used the same concept during the contest but rather than calculating the bigger limit (548), I calculated the limit of each n independently.

Here’s my approach

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

Feel free to comment if you are stuck anywhere.

3

@masood786 I think you are using square root decomposition solution. I have found issue in solution I have updated it. This problem is very interesting because this problem can be solved by multiple approaches like square root decomposition, egg dropping puzzle, modified function/golden ratio, etc.

4

Don’t they co-incide in the case of egg dropping puzzle with 2 eggs? (atleast that’s what I think). I mean, you are calculating k by solving the quadratic equation which would result in k being roughly equal to sqrt(n).

I’m basically applying the egg dropping puzzle to the given input rather than n==150000*