Combinatorics Homework
Contest: Educational Codeforces Round 114 (Rated for Div. 2)
Difficulty rating: 1100
Tags: combinatorics, greedy, math

You are given four integer values $$$a$$$, $$$b$$$, $$$c$$$ and $$$m$$$.

Check if there exists a string that contains:

- $$$a$$$ letters 'A';
- $$$b$$$ letters 'B';
- $$$c$$$ letters 'C';
- no other letters;
- exactly $$$m$$$ pairs of adjacent equal letters (exactly $$$m$$$ such positions $$$i$$$ that the $$$i$$$-th letter is equal to the $$$(i+1)$$$-th one).

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.

Each of the next $$$t$$$ lines contains the description of the testcase — four integers $$$a$$$, $$$b$$$, $$$c$$$ and $$$m$$$ ($$$1 \le a, b, c \le 10^8$$$; $$$0 \le m \le 10^8$$$).

Output format:
For each testcase print "YES" if there exists a string that satisfies all the requirements. Print "NO" if there are no such strings.

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES will all be recognized as positive answer).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first testcase strings "ABCAB" or "BCABA" satisfy the requirements. There exist other possible strings.

In the second testcase there's no way to put adjacent equal letters if there's no letter that appears at least twice.

In the third testcase string "CABBCC" satisfies the requirements. There exist other possible strings.

Example input:
3
2 2 1 0
1 1 1 1
1 2 3 2

Example output:
YES
NO
YES

Editorial:
Let's start with a simple assumption. For some fixed values $$$a, b, c$$$, the values of $$$m$$$ that the answers exist for, make up a range. So there's the smallest possible number of adjacent equal pairs one can construct and the largest one — everything in-between exists as well.
The largest number is simple — put all A's, then all B's, then all C's. So this value is $$$(a - 1) + (b - 1) + (c - 1)$$$.
The smallest number is trickier. Let's instead investigate when it's equal to $$$0$$$. WLOG, assume $$$a \le b \le c$$$. Imagine the following construction. There are $$$c$$$ letters C which separate blocks of letters A and B. There are $$$c-1$$$ ($$$c+1$$$ if you consider the ones to the sides of all letters C, but we want the smallest value, so we shouldn't consider them) such blocks, thus it's possible that each block contains no more than one letter A and no more than one letter B. So letters A and B will never produce adjacent pairs.
If there are empty blocks, then there are adjacent letters C. So the condition to still have no empty blocks is to have at least $$$c-1$$$ letters A and B in total. If $$$c - 1 > a + b$$$, then any extra letter C can only be put adjacent to another letter C, thus producing an extra pair (at least one extra pair, but since we are examining the lower bound, we can always do exactly one). That means that the lower bound is $$$c - 1 - (a + b)$$$.
Now for the proof of the fact that every value in-between is also achievable. Since we have a construction for $$$m = 0$$$, let's try modifying it. Let's reduce the test to $$$m = 0$$$ the following way. While $$$m > 0$$$, decrease the count of the letter that appears the most by $$$1$$$ and decrease $$$m$$$ by $$$1$$$. Now build the string for $$$m = 0$$$ with the reduced values. After that put the letters back, placing them next to the last occurrence of the same letter (there is at least one occurrence of each letter, the proof is trivial). That increases $$$m$$$ by $$$1$$$ and the count of this letter by $$$1$$$. Thus, we'll return to the initial test.
Overall complexity: $$$O(1)$$$ per testcase.