### hiddentesla's blog

By hiddentesla, history, 8 years ago,

hello!, about a while back, i came across a problem called "building fences", link: https://open.kattis.com/problems/fence2, back then i cant solve it, and yesterday i remembered about that problem and attemp to solve it again, but still, i could not solve it. im thinking about binary searching the length of the log, to find the the highest log length (ill denote it L) that we can make, but then i noticed that if the log length is divisible by L, the number of cuts to get the logs to size L is log_length/L -1, and if its not divisible by L, the number is log_length/L. so while that binary search may return the largest L, it may not be the minimum cut, right?

so can anyone give me some hints on this problem? could this just be a simple problem and i have ben looking at it the wrong way?

• +2

 » 8 years ago, # |   0 up...
 » 8 years ago, # |   0 still cant solve this
 » 8 years ago, # |   0 up, its ben a week, still cant do it
 » 8 years ago, # |   0 up, 3 weeks and still no idea
 » 8 years ago, # |   +6 Same problem. Any hints ?
 » 8 years ago, # |   +16 Accepted :DLook your approach is correct. You have to just maximize the length, the cuts will automatically be minimized.I will leave the proof for you to try first.If you are still having problems, we will discuss again.P.S — Thanks for such a nice problem
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 i did try to prove this, this problem is from 3 weeks ago, but failed...edit: got it now, and its accepted
•  » » 7 years ago, # ^ |   0 I had encountered the same problem two days ago and I used a same approach of maximizing the length of the fence using binary search. It is very easy to evaluate whether a given length L can be achieved using the given poles or not. My problem is associated with determining the minimum cuts after finding the maximum L. I tried to follow an approach where I cut the poles that are multiples of L first before cutting the remaining poles. I used a heuristic to check whether an integer length of a pole (len) is a multiple of a possibly real number L by checking whether L*(len/L)=L or not. I tried this approach in multiple test cases and it seems to get the correct answer. For ex. creating a fence of 3 poles having 4 sticks 1, 2, 3, 4 can be done in one cut (cuts 4 in half).My approach is getting wrong answer. It would be great if any help can be provided about a tricky test case or a problem with my approach.
•  » » » 7 years ago, # ^ |   0 Got it accepted now.I missed this condition "Also, the parts of the poles that are not used for the posts must not be longer than the ones used for the posts." which simplifies the problem a lot. This condition invalidates the example I had in the previous comment as now the output of this case would be 2 in stead of 1.
•  » » » » 7 years ago, # ^ |   0 Can you please explain the output 2 for your example. if 4 is cut in half both its part will be used, so the answer is still 1 instead of 2. And if you can explain how the condition "Also, the parts of the poles that are not used for the posts must not be longer than the ones used for the posts." simplifies the problem that would be great. Because for me it makes the problem a lot more harder.
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 The condition "Also, the parts of the poles that are not used for the posts must not be longer than the ones used for the posts" makes it impossible to have an output of 1. As if you cut four into two sticks of lengths 2 then now you have: 1, 2, 2, 2, 3 but you cannot leave a post longer than the ones used in the posts (3) so you need to cut 3 as well to 1 and 2. Hence, why the correct answer should be two.
 » 7 years ago, # |   -6 HELLO... IT'S ME, I WAS WONDERING ABOUT YOU