tn757's blog

Clarification about the recent Div 2 B problem
By tn757, history, 21 month(s) ago, In English

Sorry for the question post, but I've spent 2 hours on the recent Div 2 B (1786B - Cake Assembly Line) and it seems I just don't understand the problem statement. Correct solutions to the test case:

1

3 3 1

3 10 25

7 23 27

return "NO," but according to my interpretation, it should be "YES". The dispenser at position 7 gives chocolate to the cakes at position 3 and 10, and the dispensers at position 23 and position 27 give chocolate to the cake at position 25. Also correct solutions don't seem to consider at all the case where one dispenser covers two cakes and two dispensers cover one cake. Is it mentioned somewhere in the problem statement this won't happen?

Could someone point out the flaw in my logic/interpretation? Thank you!

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

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

There is no way how dispenser at position 7 gives chocolate to cakes at position 3 and 10. If you shift the position of 1st dispenser to 3 then its coverage would (3 - 1, 3 + 1) => (2, 4). It can only cover 3 not 10, and so for other cases.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Doesn't the cake at position 3 span from [0, 6] and the cake at position 10 span from [7, 13]? So if the dispenser is center at position 7, it should cover [6, 8] which is within both intervals?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      cakes: ㅤㅤ (0, 6) (7, 13) (22, 28)
      Dispenser : (6, 8) (22, 24) (26, 28)

      the space between 6 to 7 from 1st and 2nd cake is being filled with chocolate where the problem says no chocolate should be wasted.

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Thanks for the help, I realized my error.

        → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

"Determine if it's possible to shift the conveyor so that each cake has some chocolate on it, and there is no chocolate outside the cakes."

One dispenser cannot cover two cakes since $$$a_i+w < a_{i+1}-w$$$ for all $$$i$$$, which means that there must be a gap between the cakes and since there must be no chocolate outside the cakes this won't be possible.

Two dispensers can technically cover one cake, but since there are an equal number of dispensers and cakes, there won't be enough dispensers to cover the rest of the cakes.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Can't side-by-side cakes allow a dispenser to cover 2 cakes? If the width of cakes were 2, and there were cakes at positions 3 and 8, then the intervals [1, 5] and [6, 10] are covered. 3+2 < 8-2

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually, I am wrong. The interval [1,5] ends at 5.0 and the interval [6, 10] begins at 6.0. So there is a gap at 5.1 to 5.9. Thank you!

    → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
  • No, the dispensers at position 7 gives chocolate at position 6, 7, 8 as h=1.
  • You have to shift the conveyor (aka shift the cakes), not the dispensers.
  • In additional, as the constraints: h <= w, a[i] + w < a[i+1] - w, b[i] + h < b[i+1] - h, there can't be one dispenser covers two cakes or two dispensers cover one cake.
→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Thanks, I overlooked that even if there is a cake that ends at position 5.0 and a cake that begins at position 6.0, there is still a gap because positoins 5.1 — 5.9 are empty. I wrongly assumed they would be contiguous.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

This is why you should always clarify when u are unsure about something. I wasn't sure whether the same dispenser can put chocolate on two cakes so I simply asked.

→ Reply