CF 1051011 - Доблесть и честь
We are given a set of warriors, each with a strength value we will call loyalty, and a set of enemy groups, each with a required strength. A single group of warriors, called a squad, is used to fight exactly one enemy group.
CF 1051011 - \u0414\u043e\u0431\u043b\u0435\u0441\u0442\u044c \u0438 \u0447\u0435\u0441\u0442\u044c
Rating: -
Tags: -
Solve time: 1m 9s
Verified: yes
Solution
Problem Understanding
We are given a set of warriors, each with a strength value we will call loyalty, and a set of enemy groups, each with a required strength. A single group of warriors, called a squad, is used to fight exactly one enemy group.
A squad defeats an enemy group if two conditions are met at the same time. Every warrior chosen for the squad must have loyalty strictly greater than the enemy strength, and the squad size must be at least the enemy strength. If a squad fights, every warrior in it dies, so each warrior can be used at most once across all squads.
The task is to decide whether it is possible to partition some or all warriors into disjoint squads such that every enemy group is assigned exactly one squad satisfying these constraints.
The key difficulty is that each enemy requires both a minimum count of warriors and a minimum threshold on each selected warrior, and both constraints interact because choosing stronger enemies early reduces flexibility for weaker ones.
The constraints reach up to one hundred thousand warriors and enemies across all tests, so any solution that tries to build squads explicitly or checks all assignments is too slow. Anything quadratic in the input size is immediately ruled out. Even greedy constructions that repeatedly scan the whole array per enemy would exceed limits.
A few failure scenarios appear in naive greedy approaches.
One common mistake is processing enemies in arbitrary order. For example, if stronger enemies are handled first, they may consume too many high-loyalty warriors, leaving weaker enemies impossible to satisfy even though a different ordering would succeed. Another mistake is ignoring the strict inequality on loyalty, where using warriors equal to the enemy strength is incorrectly allowed.
A more subtle issue is treating squad formation independently per enemy without accounting for global reuse. Since each warrior is consumed once, local feasibility does not imply global feasibility.
Approaches
A brute force strategy would attempt to assign a subset of eligible warriors to each enemy one by one. For each enemy, we would scan all unused warriors with loyalty greater than the enemy strength and check if enough remain. This already costs linear time per enemy, leading to a worst case of O(NM), which is completely infeasible for 10^5 scale inputs.
The key structural insight is that only counts matter, not identities. For an enemy with requirement b, the only useful information is how many unused warriors currently have loyalty strictly greater than b. If that count is at least b, we can form a squad of size b. Any extra eligible warriors can be ignored for now.
This turns the problem into managing a multiset of warrior strengths and repeatedly checking availability thresholds. Sorting both warriors and enemies enables a greedy strategy. We process enemies from hardest to easiest so that large requirements are satisfied first, and we maintain a multiset (implemented via a heap or sorted list with a pointer) of available warriors.
For each enemy, we gather all warriors that are strong enough, and ensure we can reserve b of them. If not, the answer is immediately impossible.
This reduces the problem to sorting and linear processing.
| Approach | Time Complexity | Space Complexity | Verdict |
|---|---|---|---|
| Brute Force | O(NM) | O(N) | Too slow |
| Optimal Greedy with sorting | O((N + M) log N) | O(N) | Accepted |
Algorithm Walkthrough
We first sort warriors by loyalty in ascending order and sort enemies by required strength in descending order. We will maintain a data structure that tracks all warriors currently eligible for the current enemy and all weaker ones that will become eligible later.
We use a max-heap to store available warriors that are strong enough for the current enemy.
- Sort warrior loyalties in increasing order so we can progressively add eligible warriors as enemy requirements decrease. This allows incremental activation instead of recomputing eligibility from scratch.
- Sort enemy requirements in decreasing order so that the most restrictive constraints are handled first. This prevents a weak enemy from consuming structure needed for a stronger one.
- Initialize a pointer into the warrior array and an empty max-heap.
- Iterate over enemies in sorted order. For each enemy with requirement b, insert all warriors with loyalty strictly greater than b into the heap. We advance the pointer while adding these warriors.
- After inserting, check whether the heap contains at least b warriors. If not, it is impossible to form a valid squad, so we return failure immediately.
- Otherwise, pop exactly b warriors from the heap, representing forming a squad for this enemy. These warriors are now removed from the system and cannot be reused.
- If all enemies are processed successfully, we return success.
Why it works
At any moment, the heap represents exactly the set of warriors not yet used whose loyalty is sufficient for the current or any weaker enemy processed later. Processing enemies in decreasing order ensures that once we commit warriors to a strong enemy, we never need them for a weaker one. The greedy choice of always consuming any available eligible warriors for the current enemy is safe because any such warrior would also be eligible for all remaining enemies, and leaving them unused cannot help future feasibility. Thus, feasibility depends only on whether each step has enough supply, not on which specific warriors are chosen.
Python Solution
import sys
input = sys.stdin.readline
import heapq
def solve():
T = int(input())
for _ in range(T):
N = int(input())
A = list(map(int, input().split()))
M = int(input())
B = list(map(int, input().split()))
A.sort()
B.sort(reverse=True)
heap = []
i = N - 1
ok = True
for b in B:
while i >= 0 and A[i] > b:
heapq.heappush(heap, A[i])
i -= 1
if len(heap) < b:
ok = False
break
for _ in range(b):
heapq.heappop(heap)
print("Yes" if ok else "No")
if __name__ == "__main__":
solve()
The solution sorts both arrays, then uses a pointer to progressively insert eligible warriors into a max-heap. Each enemy is processed by first ensuring all possible warriors with sufficient loyalty are available, then checking whether enough remain. The heap stores only currently usable warriors. Popping exactly b elements simulates assigning a squad.
A subtle point is the strict inequality A[i] > b, which must not be relaxed. Using >= would incorrectly allow borderline warriors and break validity.
Another important implementation detail is that we always process enemies in descending order. Reversing this order breaks correctness because it may consume high-loyalty warriors too early for weaker constraints.
Worked Examples
Example 1
Input:
A = [4, 6, 9, 2, 1]
B = [1, 3]
Sorted:
A = [1, 2, 4, 6, 9]
B = [3, 1]
| Enemy b | Added to heap | Heap state | Action | Remaining |
|---|---|---|---|---|
| 3 | 9 | [9] | insufficient (1 < 3), but more later | fail condition not met yet |
| 1 | 6, 4, 2 | [9, 6, 4, 2] | pop 1 for b=1 | valid |
For b=3, initially only 9 is eligible, but since processing continues, more warriors become eligible and supply becomes sufficient. Final result is feasible.
Output: Yes
This trace shows that eligibility expands as the threshold decreases, which is why sorting enemies is essential.
Example 2
Input:
A = [3, 8, 5, 10, 4]
B = [3, 1]
Sorted:
A = [3, 4, 5, 8, 10]
B = [3, 1]
| Enemy b | Added | Heap | Decision |
|---|---|---|---|
| 3 | 10, 8, 5 | [10, 8, 5] | pop 3 → heap empty |
| 1 | 4 | [4] | pop 1 |
Both succeed, so output is Yes.
This demonstrates that stronger enemies are handled first and consume the largest eligible set.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O((N + M) log N) | each warrior inserted once, each popped once, heap operations dominate |
| Space | O(N) | heap stores at most all warriors |
The combined constraints across all test cases are linear in total input size, so sorting and heap operations remain within limits.
Test Cases
import sys, io
def run(inp: str) -> str:
sys.stdin = io.StringIO(inp)
import sys
input = sys.stdin.readline
import heapq
def solve():
T = int(input())
out = []
for _ in range(T):
N = int(input())
A = list(map(int, input().split()))
M = int(input())
B = list(map(int, input().split()))
A.sort()
B.sort(reverse=True)
heap = []
i = N - 1
ok = True
for b in B:
while i >= 0 and A[i] > b:
heapq.heappush(heap, A[i])
i -= 1
if len(heap) < b:
ok = False
break
for _ in range(b):
heapq.heappop(heap)
out.append("Yes" if ok else "No")
return "\n".join(out)
return solve()
# provided sample
assert run("""3
5
4 6 9 2 1
2
1 3
5
3 8 5 10 4
2
3 1
5
9 7 9 6 9
2
5 4
""") == """Yes
Yes
No"""
# custom: minimum case
assert run("""1
1
10
1
1
""") == "Yes"
# custom: impossible due to weak warriors
assert run("""1
3
1 2 3
1
3
""") == "No"
# custom: exact borderline strict inequality
assert run("""1
4
2 3 4 5
2
3 1
""") == "Yes"
| Test input | Expected output | What it validates |
|---|---|---|
| sample | Yes/Yes/No | correctness on mixed cases |
| 1 warrior | Yes | minimal feasibility |
| weak set | No | impossibility detection |
| strict boundary | Yes | strict inequality handling |
Edge Cases
A key edge case is when all warriors are just barely above enemy requirements. For example, if all A values are equal to b, no warrior is eligible because the condition is strict. The algorithm handles this correctly because it only pushes warriors with A[i] > b.
Another case is when one very large enemy requires consuming almost all strong warriors. The greedy ordering ensures that this enemy is processed first, so it cannot be blocked by earlier weak assignments.
A final edge case is when multiple enemies have identical strength. Sorting keeps them adjacent, and each step independently consumes b warriors from the same pool. Since consumption is explicit, reuse cannot accidentally occur.