TWORANGES - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: utkarsh_25dec
Testers: iceknight1093, rivalq
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Given two ranges [A, B] and [C, D]; count the number of integers contained in their union.

EXPLANATION:

Notice that the bounds on the ranges are quite small; between 1 and 8.
This means the union of the ranges is also a subset of \{1, 2, 3, 4, 5, 6, 7, 8\}.

So, for each integer from 1 to 8, check whether it belongs to one of the ranges.
That is, for each 1 \leq x \leq 8, check at least one of

  • A \leq x \leq B; or
  • C \leq x \leq D

is true.
The number of x satisfying this condition is the answer.

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Code (Python) 
for _ in range(int(input())):
    a, b, c, d = map(int, input().split())
    ans = 0
    for i in range(1, 9):
        if a <= i <= b or c <= i <= d: ans += 1
    print(ans)
2 
t=int(input())
for i in range(t):
    a,b,c,d=map(int,input().split())
    l1=set(range(a,b+1))
    l2=set(range(c,d+1))
    l=l1.union(l2)
    print(len(l))

This method too works right?

3

Yes, pretty much any method to find the union of two sets will also work for this problem, since the constraints are so small.

1 Like
4

So say I am going to make the constrains larger. In that case how can we code the thing?

5

Using the fact that they’re intervals, you can solve the problem in \mathcal{O}(1) time with a little casework.

If [A, B] and [C, D] are disjoint intervals, the length of their union is just the sum of their lengths, i.e, (B-A+1) + (C-D+1).
If they intersect each other, the union is a single interval, which equals [\min(A, C), \max(B, D)]; the length of this is just \max(B, D) - \min(A, C) + 1.

Checking whether they intersect or not is quite simple, just see whether B lies in [C, D] or D lies in [A, B].

2 Likes