LUNCH 63 SPOOL wrong answer on brute force approach

Hello,

I’m trying for a couple of days to solve this problem (SPOOL Problem - CodeChef ) with a basic approach (btw I was expecting to obtain a TLE but only WA which makes me think that either I’m doing something very wrong):

  • keep an array of depths (guarded the array with 0) to simulate the overflow of the pool
  • for every query of type 2 just return the depth from previous array
  • for every query of type 1 do the following
    1. compute the segment [start, end] that has same depth as the query point
    1. if both depth[start] & depth[end] > depth[queryPoint] fill recursively on start and end with v/2
    1. elseif depth[start] or depth[end] > depth[queryPoint] and other head of segment is lower then fill that point start or end with v
    1. elseif both depths are lower than queryPoint - try to fill that point up to the closest depth and then repeat the process with the rest of volume.

Code is here.
https://www.codechef.com/viewsolution/19954290

I’ve compared my solutions with the ones passing the tests and I couldn’t find tests that have different output (different in comments of more than 1e-6)

I found the issue by myself - it’s wrong to fill recursively with v/2 because you can over-spill from first recursion into the second one (at least in the way i implemented it)
You need to spill smaller amounts in order to avoid this until you have none left.
Testacase:

1
6 6
3 2 1 2 1 2
1 3 4
2 1
2 2
2 3
2 4
2 5
2 6

Correct output:
1.50000000000000
1.50000000000000
1.00000000000000
1.00000000000000
1.00000000000000
1.00000000000000

My Wrong output
1.25000000000000
1.25000000000000
1.00000000000000
1.00000000000000
1.00000000000000
1.50000000000000

Link to submission with accepted solution:
https://www.codechef.com/viewsolution/19956792