hiddentesla's blog

stuck on the problem building fences
By hiddentesla, history, 8 years ago, In English

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?

  • Vote: I like it
  • +2
  • Vote: I do not like it

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

up...

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

still cant solve this

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

up, its ben a week, still cant do it

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

up, 3 weeks and still no idea

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

Same problem. Any hints ?

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

Accepted :D

Look 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

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    i did try to prove this, this problem is from 3 weeks ago, but failed...

    edit: got it now, and its accepted

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

    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.

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

      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.

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

        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.

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          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.

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

HELLO... IT'S ME, I WAS WONDERING ABOUT YOU

→ Reply