hackercupai/hackercup huggingface dataset:
For each seating section \(i\), we can compute 4 quantities:

1. **At least** \(\text{max}(0, X_i - S_i)\) customers must be added to it
2. **At most** \(\text{max}(0, (X_i + Y_i) - S_i)\) customers may be added to it
3. **At least** \(\text{max}(0, S_i - (X_i + Y_i))\) customers must be removed from it
4. **At most** \(\text{max}(0, S_i - X_i)\) customers may be removed from it

Note that no section will require customers to both be added and removed from it (quantities 1 and 3 cannot both be positive).

Let \(Q_i\) be the sum of the \(i\)th quantity described above across all \(N\) seating sections. We can compute \(Q_{1..4}\) in \(O(N)\) time. If \(Q_1\) (the minimum total number of customers who must be added to sections) is greater than \(Q_4\) (the maximum total number of customers who may be removed from sections), then the output must be \(-1\). The same applies if \(Q_3 > Q_2\).

Otherwise, we can observe that it's always possible to relocate customers such that all of the sections' requirements are satisfied, and in particular to do so using only \(\text{max}(Q_1, Q_3)\) relocations (it cannot possibly take fewer). In particular, we can begin by relocating \(\text{min}(Q_1, Q_3)\) customers from sections which must have customers removed into ones which must have customers added. After that, there may either be remaining sections requiring more customers or ones requiring fewer customers, which can be addressed with another \(\text{max}(Q_1, Q_3) - \text{min}(Q_1, Q_3)\) relocations.