You are not logged in. Please login at www.codechef.com to post your questions!

×

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

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

asked 30 Dec '18, 19:07

gannu_raj's gravatar image

2★gannu_raj
1
accept rate: 0%

edited 30 Dec '18, 23:32


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.

link

answered 30 Dec '18, 22:53

masood786's gravatar image

4★masood786
1063
accept rate: 13%

edited 30 Dec '18, 23:09

@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.

(30 Dec '18, 23:31) gannu_raj2★

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*

(30 Dec '18, 23:38) masood7864★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×164
×152
×19

question asked: 30 Dec '18, 19:07

question was seen: 109 times

last updated: 30 Dec '18, 23:41