LOSELESS - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

A team receives 3 points for winning, 1 point for a tie, and 0 points for a loss.
What’s the minimum number of losses possible if they have N points in M matches?

EXPLANATION:

Suppose there are W wins, T ties, and L losses among the M matches.
Then,

  • W+T+L = M must hold.
  • The number of points received is 3\cdot W + T. This must equal N.
  • Our objective is to minimize L.

There are now various solutions possible.
From worst to best,

  1. Iterate over all choices of W, T, L, each from 0 to M.
    For each triple, check if the equalities to M and N hold.
    If they do, minimize the answer with L.
    This has a complexity of \mathcal{O}(M^3).
  2. A slight optimization is to note that after fixing two out of W, T, L, the third one is automatically fixed via the equation W+T+L = M.
    Thus, we only need to iterate over two of them instead of all three.
    This brings the complexity to \mathcal{O}(M^2).
  3. A further optimization is to note that fixing only W is enough, since that also fixes T via the equation 3W+T = N.
    This brings the complexity to \mathcal{O}(M).

The constraints are quite low, so any of the above three approaches will work.

It’s also possible to solve the problem in constant time with a bit of math and casework (in particular, with the observation that for N \ge M the answer is always either 0 or 1).
This is left as an exercise to the reader.

TIME COMPLEXITY:

\mathcal{O}(M) \sim \mathcal{O}(M^3) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    m, n = map(int, input().split())
    ans = m
    
    for win in range(m+1):
        tie = n - 3*win
        if tie >= 0 and win+tie <= m:
            ans = min(ans, m - win - tie)
    print(ans)