carlosmederos's blog

I need help with this problem(binary search)
By carlosmederos, history, 8 years ago, In English

Hello guys, I tried resolve this problem: Good kg of Flauta Bread, using binary search but I not had luck, please if somebody know how to resolve this problem, help me, please, thanks in regards link in online judge — Caribbean Online Judge: http://coj.uci.cu/24h/problem.xhtml?pid=3382

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please!!! help me!!!!

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello,

I must assume you speak Spanish, so do I, so if you still have any doubts private-message me and I'll reply.

First, you should convert the pyramid into something easier to handle, that is, an array. The i-th element of the array will represent the number of unitary triangles in the i-th row of the pyramid. So it should look like this 1,3,5,..., 2L-1. (you don't really need to fill an actual array, just have the idea in mind). After that, we are to split it into K contiguous subsections.

Let's say the smallest sum of a subsection is C. Then you start taking elements from the start of the array greedily until you reach C. There you found your first subsection. Repeat until all the array has been considered. Only consider subsections having sum >= C. If you have some spare triangles you can think of them as belonging in the biggest subsection. If the number of subsections is greater than or equal to K, then C is feasible. This is because we can keep on 'merging' the biggest subsections until we have just K, without adding any extra triangles to the smallest one. Finally, binary-search on C to find the answer. You know that the answer should be at least 1 and at most L^2. Then if C is feasible, so is C' for all C' < C.

In the video (Spanish) provided by LaFuckinGioconda you can see the solution above better explained.

→ Reply