There are $$$N$$$ glasses placed in a row (numbered from $$$1$$$ to $$$N$$$). The $$$i$$$-th glass has:
- a total volume of $$$V_i$$$ liters,
- currently contains $$$W_i$$$ liters of water.
A glass is called good if
and bad otherwise.
Bending Operation
You may perform up to $$$K$$$ non‑intersecting merge operations. In each operation you select a contiguous segment of glasses $$$[l, r]$$$ (with $$$1 \le l \lt r \le N$$$) and merge them into one new glass whose:
- volume is
- water amount is
Segments $$$[l_1,r_1]$$$ and $$$[l_2,r_2]$$$ are non‑intersecting if
Goal
Determine whether it is possible—by choosing some $$$K$$$ non‑intersecting segments (where $$$0 \le K \le N$$$) and merging each—to end up with strictly more good glasses than bad glasses.
- If yes, print:
Yes K l_1 r_1 l_2 r_2 ⋮ l_K r_K
where each $$$[l_i, r_i]$$$ is a chosen segment. * Otherwise, print:
No
Input
- The first line contains a single integer $$$T$$$ ($$$1 \le T \le 100$$$) — the number of test cases.
- Each test case consists of:
- An integer $$$N$$$ $$$\bigl(1 \le N \le 10^5\bigr)$$$ — the number of glasses.
- A line of $$$N$$$ integers $$$V_1, V_2, \ldots, V_N$$$ $$$\bigl(1 \le V_i \le 10^9\bigr)$$$ — the volume of each glass.
- A line of $$$N$$$ integers $$$W_1, W_2, \ldots, W_N$$$ $$$\bigl(0 \le W_i \le V_i \le 10^9\bigr)$$$ — the current water in each glass.
It is guaranteed that $$$\sum N \le 2\times10^5$$$ over all test cases.
Output
For each test case:
- If no sequence of merges yields strictly more good glasses than bad, print No.
- Otherwise, print Yes, the integer $$$K$$$, and then $$$K$$$ lines each containing two integers $$$l_i$$$ and $$$r_i$$$ $$$(1 \le l_i \lt r_i \le N)$$$, representing your chosen non‑intersecting segments.
You may output any valid solution.
Example
Input
2
4
6 4 8 10
4 1 6 1
3
4 4 5
1 2 3
Output
Yes
1
2 3
No
My Solution :
The basic idea was :
1) to merge the consecutive negatives and gain something like + — + — ....
2) if #positives == #negatives, we try to merge a + — pair with sum > 0
3) if #negatives — #positives == 1, we try to merge the first + — pair and last + — pair with sum > 0.
I cant understand why this solution doesnt work. And it would be really helpful if someone points out a solution/editorial to this problem as well.
In your idea, for 2) why don't you consider merging a + with a prefix of the next — and the remaining suffix with the next +?
I am sorry but i didn't understand your idea. But do you think number 2 can cause any problem?
You are only considering a group of consecutive negatives paired up with a neighboring positive. Why not split up this group of negatives into a prefix and suffix, let's say the first 3 negatives pair up with the positive on the left of the group, and the remaining (something — 3) negatives pair up with the positive on the right of the group. It's just the first thing that came to my mind when reading your algorithm.
Example:
1
5
8 8 8 8 100
7 2 2 7 1
Here the initial groups are + — + — right? But merging both pairs (2, 8) to a single positive (7, 8) doesn't work, since 7 + 2 + 2 = 11, but the sum of volumes is 24. However, splitting the negatives in the middle and having (9, 16) twice leads to 2 positives and 1 negative (the last horrible pair being the only negative), as desired. Incorrectly, your code outputted "No" for this test case.
Really appreciate your effort for pointing out the error.
Transform the problem's statement as follows:
Let $$$A_i = 2W_i - V_i$$$. Then an interval $$$[l,r]$$$ is considered good if and only if $$$\sum_{i=l}^r A_i \gt 0$$$.
Let $$$B_i = \sum_{j=1}^i A_j$$$, especially $$$B_0 = 0$$$. We need to find a subsequence $$$c$$$ of $$${0, 1,2,3,\ldots,n}$$$ satisfying $$$0=c_0 \lt c_1 \lt c_2 \lt \cdots \lt c_k = n$$$, such that $$$\sum_{i=1}^k ([B_{c_i} \gt B_{c_{i-1}}] - [B_{c_i} \leq B_{c_{i-1}}]) \gt 0$$$, where the notation $$$[condition]$$$ evaluates to 1 when $$$condition$$$ is true and 0 otherwise.
Consider dynamic programming: Let $$$f_i$$$ represent the maximum value of $$$\sum_{j=1}^k ([B_{c_j} \gt B_{c_{j-1}}] - [B_{c_j} \leq B_{c_{j-1}}])$$$ under the optimal strategy given $$$c_k = i$$$. The transition involves enumerating $$$c_{k-1}$$$:
Using a segment tree to maintain this transition achieves $$$O(n \log n)$$$ complexity.
Ultra boring problem. Zero applicability may as well sit down and spend 100 hours writing the digits of PI.