FOOTBALLTIES - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: raysh07
Tester: sky_nik
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

In the Premier League, the winner of a match gets 3 points and the loser zero. A draw gets both teams 1 point.

The score between two teams is X:Y. What’s the minimum possible number of draws between them?

EXPLANATION:

There are a couple of different ways to approach this task: a smart solution and a brute-force solution.

Brute force

Note that the constraints are quite small (X and Y both don’t exceed 14), so it’s possible to simply try every possibility.
That is, fix the number of matches won by A, the number of matches won by B, and the number of draws (all of these can be at most 14).

Once you know the number of matches each team wins and the number of draws, it’s easy to compute their scores. Check if the resulting score is X:Y, and take the smallest number of draws that gets you to it.

Smart solution

Both teams start at 0 points. When one team wins, their score increases by 3 and the other team’s doesn’t change. When it’s a draw, both teams get one point.
Looking at scores modulo 3 (that is, the remainder when you divide by 3), observe that:

  • If some team wins, both scores don’t change modulo 3.
  • If it’s a draw, both scores increase by 1 modulo 3 (so the remainder goes 0\to 1\to 2 \to 0 \to\ldots)

So, the scores of both teams modulo 3 will always be equal - and this remainder modulo 3 is exactly the minimum number of draws needed!

  • If the scores are 0 modulo 3, both scores are multiplies of 3 so it’s easy to see that they can be attained by wins and losses.
  • If the scores are 1 modulo 3, one draw is enough - the remaining part is 0 modulo 3.
  • If the scores are 2 modulo 3, two draws are enough.

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (Python, solution 1) 
for _ in range(int(input())):
    x, y = map(int, input().split())
    ans = 100
    for awin in range(5):
        for bwin in range(5):
            if 3*awin <= x and 3*bwin <= y and x - 3*awin == y - 3*bwin:
                ans = min(ans, x - 3*awin)
    print(ans)
Editorialist's code (Python, solution 2) 
for _ in range(int(input())):
    x, y = map(int, input().split())
    print(x%3)