SAT2020's blog

Problem J (Platform Placing) from NAQ 2023
By SAT2020, history, 21 month(s) ago, In English

Hi Everyone!

I hope you're all having a great day!

Last week, I participated in NAQ 2023. After the contest, I've been trying to upsolve Problem J (Platform Placing), but I keep getting WA on test case 6.

Here is a link to my code.

And here is a high-level summary of my code (problemB()):

  1. Read the input. Add (1e18) and (-1e18) to the set of platforms to represent extra space for the first and last platforms.

  2. Sort the array.

  3. Iterate through and expand the current platform as much as possible.

  4. Add the length to our result and record the increased size of the platform.

This is similar to the greedy approach that the contest authors offer, but for some reason, it continues to fail! If anyone could help me out with what is going wrong here, it would be very appreciated.

Thanks!

Simon

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

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

Auto comment: topic has been updated by SAT2020 (previous revision, new revision, compare).

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

Auto comment: topic has been updated by SAT2020 (previous revision, new revision, compare).

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

Why are front and back defined differently?

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

    Front = distance to the next platform. Back = distance to the previous platform.

    I subtract s/2.0 from the front to ensure that there is enough space for the next platform.

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

When the answer is large you output it in scientific notation because you're printing double, multiply everything by 2 and use long long instead.

→ Reply