SEQCLAMP - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

You have N arrays A and B.
For a starting integer X, define f(X) as follows:

  • For i = 1, 2, \ldots, N in order, clamp X to the range [A_i, B_i] by setting it to A_i if it’s smaller than A_i, setting it to B_i if it’s larger than B_i, or leaving it unchanged otherwise.
  • f(X) is the final value of X.

Find the maximum possible value of f(X) across all X.

EXPLANATION:

For a fixed initial value of X, it’s quite easy to compute f(X) in \mathcal{O}(N) time: just go through indices from 1 to N and apply the requisite changes.

This allows for a simple solution, by observing that we don’t actually have to check too many values of X.
In particular, note that for any initial input X,

  • If X \lt A_1, after the first step it’ll become A_1.
    We could’ve just chosen X = A_1 instead and gotten the same result.
  • Similarly, if X \gt B_1, after the first step it’ll become B_1; so we could’ve just started with B_1 itself.

This means we only need to care about initial values of X that are in the range [A_1, B_1].
Since 1 \le A_1 \le B_1 \le 100, there are at most 100 potential inputs - so we can simply compute f(X) for each of them and then output the largest value.
This has a complexity of \mathcal{O}(100\cdot N).

It’s also possible to solve the problem in \mathcal{O}(N) time by noting that for any integer X, we always have f(X) \le f(X+1).
That is, if the initial input is higher, the eventual output cannot decrease either.
So, the optimal choice is to always just choose X = 100 (any larger is pointless) and compute f(X).

TIME COMPLEXITY:

\mathcal{O}(N) or \mathcal{O}(N\cdot 100) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    x = 100
    for i in range(n):
        ai, bi = map(int, input().split())

        if x < ai: x = ai
        elif x > bi: x = bi
    print(x)
1 Like