EXQUIZ - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: am_aadvik
Tester: iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Given N and S, find the minimum possible value of c+w across all integer pairs (c, w) satisfying:

  • 0 \le c, w
  • c+w \le N
  • 4c - w = S

EXPLANATION:

Since w \ge 0 and we want 4c - w = S, certainly we must have 4c \ge S.

Further, as c gets larger and larger, the value of 4c will only move away from S.
Thus, w will also need to increase in order for 4c-w = S to hold.

Since our objective is to minimize 4c-w, the optimal choice of c is hence \frac{S}{4}.
c needs to be an integer, so we round this up to obtain

c = \text{ceiling}\left(\frac{S}{4}\right)

However, note that c \ge 0 must hold, and because S can be negative we might end up with a negative value of c by just doing this.
So, we also update c with 0, i.e. set

c = \max\left(0, \text{ceiling}\left(\frac{S}{4}\right)\right)

Once c is chosen, w = S-4c is fixed, so simply compute it and check whether c+w \le N or not.
If yes, c+w is the answer; otherwise the answer is -1 since no solution exists.

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, s = map(int, input().split())
    
    c = max(0, (s+3)//4)
    w = 4*c - s
    if c+w <= n: print(c+w)
    else: print(-1)