### lama_codes's blog

By lama_codes, history, 5 years ago, ,

Hi, Can anybody help me to figure out how to apply binary search for the problem 231C - To Add or Not to Add.

• 0

 » 5 years ago, # |   0 Why not to read editorial?
•  » » 5 years ago, # ^ |   0 Referring to editorial was my first destination but ,I can't clearly get the idea. So if you could help me out , it'd be great.
•  » » » 5 years ago, # ^ |   +5 Well. First part — second number in answer should be a number from initial array. It's explained good enough there. So, we need to check all the numbers from array and calculate, how many operations of "+1" we need to use — the first number for our answer depends on that. That's true, as much operations we use — so much equal numbers we can obtain. Consider the following forward algo: first, we take a[i-1] and apply "+1" to it until a[i-1]==a[i], then go to a[i-2] and so on: we apply more operations — we get more numbers. Hence, first part of answer is monotonic function, which depends on number of applied operations. And we can use binary search here. Let cnt be that number of operations... And then — last part of editorial as it is. Is it better now?
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 clear thinking. I think lama_codes will solve it.
•  » » » » » 5 years ago, # ^ |   0 Thanks for the support radical! :P
 » 4 years ago, # |   -14 my family was searching for a form a few weeks ago and was informed of an online service that has 6,000,000 forms . If others are looking for it as well , here's a http://pdf.ac/1YepwQ.