CF 102697024 - Missed Basketball Game

Rating: -
Tags: -
Solve time: 2m 54s
Verified: yes

Solution

Problem Understanding

Two basketball teams played a game, and we are given enough statistics to reconstruct each team's final score. For each team, the input gives the total number of made baskets, the number of those baskets that were three-pointers, and the number of free throws.

A made basket is either a two-pointer or a three-pointer. Since the total basket count includes both types, a team with b total baskets and t three-pointers made b - t two-pointers. Its basket points are therefore

2 * (b - t) + 3 * t.

Adding the f free throws gives the complete score:

2 * (b - t) + 3 * t + f.

This simplifies to 2 * b + t + f. The task is simply to calculate this value for both teams and print the name of the team with the larger score. The statement guarantees that the scores are different, so there is no tie case to resolve.

There are no explicit upper bounds for the numerical counts in the published statement. The input contains only a constant number of integers and strings, so the intended solution performs a constant amount of arithmetic and string handling. Even with very large integer values, there is no reason to iterate over baskets, three-pointers, or free throws individually. In Python, integer arithmetic also avoids the overflow concerns that would arise in a fixed-width language if unusually large values were supplied.

The main edge cases come from correctly interpreting what the basket count means. A common mistake is to treat every basket as two points and then separately add three points for every three-pointer. That double-counts the two-point portion of a three-pointer.

For example, consider:

Team A made one basket, and that basket was a three-pointer. Its score is 3, while B has 0, so the correct output is:

A careless implementation using 2 * baskets + 3 * three_pointers would give 5 for A. The winner would happen to remain correct here, but the computed score is wrong and the same mistake can change the winner on another input.

Free throws are another separate scoring category. For example:

The scores are 5 and 4, so the correct output is:

An implementation that only considers baskets and three-pointers would incorrectly conclude that both teams scored zero.

Finally, a team can have many ordinary two-pointers and no three-pointers. For example:

The scores are 6 and 4, so the correct output is:

The three-pointer count is not the total number of baskets. It is specifically the number of baskets worth three points, and the remaining baskets are worth two.

Approaches

A brute-force approach could try to reconstruct the scoring events one by one. For example, if there are E scoring events in total, an unnecessarily general search could consider three possible point values for every event, producing up to 3^E possible sequences. The final score could then be calculated for each candidate and the winner selected. This is correct if every possible scoring sequence is considered, because the actual game is one of those sequences.

The problem is that the order of scoring events contains no information that affects the final score. The input has already given us the aggregate counts needed to determine exactly how many two-pointers, three-pointers, and free throws each team made. Enumerating their possible orders is therefore wasted work. If E were large, the 3^E search would become infeasible very quickly, and even a more carefully constrained brute-force enumeration would be unnecessary.

The key observation is that the number of two-pointers is not given directly, but it can be derived immediately. If a team made B baskets in total and T of them were three-pointers, then exactly B - T were two-pointers. The score is consequently

2(B - T) + 3T + F

which simplifies to

2B + T + F.

Once this formula is recognized, the entire game can be solved with two score calculations and one comparison. The brute-force works because it can eventually recover the same totals, but it fails because it explores information that the answer does not depend on. The observation that only the aggregate scoring counts matter reduces the problem to constant-time arithmetic.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(3^E) in a general event enumeration	O(E)	Too slow and unnecessary
Optimal	O(1)	O(1)	Accepted

Algorithm Walkthrough

Read the two team names. Their order in the input determines which score belongs to which team, so we keep the names in the same order as all subsequent statistics.
Read the two total basket counts. Call them b1 and b2. These counts include both two-pointers and three-pointers.
Read the two three-pointer counts, t1 and t2. For each team, the number of ordinary two-pointers is its total basket count minus its three-pointer count.
Read the two free-throw counts, f1 and f2. Free throws are independent of the basket count, so they are added directly to the score.
Compute each team's score using 2 * baskets + three_pointers + free_throws. This is equivalent to explicitly counting two-pointers as 2 * (baskets - three_pointers) and three-pointers as 3 * three_pointers, but the simplified formula is shorter and avoids unnecessary intermediate work.
Compare the two scores. Since the statement guarantees that there is a winner, equality does not need to be handled. Print the name corresponding to the larger score.

Why it works

For each team, let B be its total number of baskets and T be its number of three-pointers. Exactly B - T baskets are two-pointers, so the basket contribution is 2(B - T) + 3T. Adding F free throws gives 2B + T + F. Thus the algorithm computes the exact final score for each team. Since the winner is precisely the team with the larger final score, comparing these two computed values always produces the required answer.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    teams = input().split()

    baskets = list(map(int, input().split()))
    threes = list(map(int, input().split()))
    free_throws = list(map(int, input().split()))

    score1 = 2 * baskets[0] + threes[0] + free_throws[0]
    score2 = 2 * baskets[1] + threes[1] + free_throws[1]

    if score1 > score2:
        print(teams[0])
    else:
        print(teams[1])

if __name__ == "__main__":
    solve()

The first line is stored as teams, preserving the correspondence between each team's name and its statistics. The next three lines are converted to integer lists because all scoring information is numeric.

The score calculation uses the simplified expression 2 * baskets + threes + free_throws. Starting from 2 * baskets treats every basket as a two-pointer. Every three-pointer needs one additional point because it is worth three instead of two, so adding threes corrects exactly those baskets. Free throws are then added separately.

There is no loop over individual scoring events because the input already provides their aggregate counts. There are also no boundary issues involving indices beyond the fixed positions 0 and 1, since exactly two teams are present.

Python's integers can represent arbitrarily large values subject to available memory, so the arithmetic does not require any special overflow handling. The problem also guarantees a winner, allowing the else branch to safely represent the second team without a separate equality case.

Worked Examples

Sample 1

The official sample is:

Syracuse Duke
35 31
11 9
14 20

The algorithm maintains the following values:

Team	Baskets	Three-pointers	Free throws	Score
Syracuse	35	11	14	`2*35 + 11 + 14 = 95`
Duke	31	9	20	`2*31 + 9 + 20 = 91`

Syracuse has 95 points and Duke has 91, so the algorithm prints:

Syracuse

The trace demonstrates why the three-pointer count is an adjustment rather than an independent basket count. Starting with two points for each of Syracuse's 35 baskets gives 70 points, and the 11 three-pointers contribute one additional point each, followed by 14 free throws.

Sample 2

A useful second example is:

Lions Tigers
10 12
4 2
5 1

The calculation is:

Team	Baskets	Three-pointers	Free throws	Score
Lions	10	4	5	`2*10 + 4 + 5 = 29`
Tigers	12	2	1	`2*12 + 2 + 1 = 27`

Although Tigers made more total baskets, Lions made more three-pointers and free throws. Lions therefore wins with 29 points.

The trace demonstrates that comparing only the total number of baskets is insufficient. The type of those baskets matters, and free throws contribute to the final score independently.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	A fixed number of input values is read and a fixed number of arithmetic operations is performed.
Space	O(1)	Only the two team names and three pairs of scoring statistics are stored.

The solution does not depend on the magnitude of the number of scoring events because it never iterates through them. With the published 1 second time limit and 256 MB memory limit, this constant-size computation is comfortably within the available resources.

Test Cases

The following test harness uses a separate solve_data function so each test can be executed without replacing the process-wide standard input.

import sys
import io

def solve_data(inp: str) -> str:
    data = inp.splitlines()

    teams = data[0].split()
    baskets = list(map(int, data[1].split()))
    threes = list(map(int, data[2].split()))
    free_throws = list(map(int, data[3].split()))

    score1 = 2 * baskets[0] + threes[0] + free_throws[0]
    score2 = 2 * baskets[1] + threes[1] + free_throws[1]

    return teams[0] if score1 > score2 else teams[1]

def run(inp: str) -> str:
    return solve_data(inp).strip()

# Provided sample
assert run("""Syracuse Duke
35 31
11 9
14 20
""") == "Syracuse", "sample 1"

# Minimum-size style case: only one point separates the teams.
assert run("""A B
0 0
0 0
1 0
""") == "A", "free throw only"

# All baskets are three-pointers.
assert run("""A B
1 2
1 0
0 0
""") == "A", "three-pointer scoring"

# All baskets are ordinary two-pointers.
assert run("""A B
3 2
0 0
0 0
""") == "A", "two-pointer scoring"

# Large values, exercising arithmetic and winner comparison.
assert run("""Alpha Beta
1000000000000000000 999999999999999999
500000000000000000 0
0 1000000000000000000
""") == "Alpha", "large integer values"

# Boundary-sensitive case where the three-pointer adjustment changes the winner.
assert run("""Left Right
5 6
5 0
0 5
""") == "Left", "three-pointer adjustment changes winner"

Test input	Expected output	What it validates
`A B / 0 0 / 0 0 / 1 0`	`A`	A game decided entirely by free throws
`A B / 1 2 / 1 0 / 0 0`	`A`	Correct treatment of three-pointers
`A B / 3 2 / 0 0 / 0 0`	`A`	Correct treatment of ordinary baskets
`Alpha Beta / 10^18 10^18-1 / 5*10^17 0 / 0 10^18`	`Alpha`	Very large integer arithmetic
`Left Right / 5 6 / 5 0 / 0 5`	`Left`	A case where basket counts alone give the wrong winner

Edge Cases

The first non-obvious case is a team whose only score comes from three-pointers. Consider:

For A, the formula gives 2 * 1 + 1 + 0 = 3. For B, it gives zero. The output is A. The algorithm does not count the three-pointer as both a two-pointer and a separate three-pointer. The initial two points are only a convenient baseline, and the extra one point converts that basket to three points.

The second case contains only free throws:

The scores are 5 and 4, so the output is A. Because free throws are not included in the basket count, they must be added separately. The algorithm does exactly that through the final + free_throws term.

The third case has only ordinary baskets:

The scores are 6 and 4, so the output is A. With no three-pointers, the simplified formula becomes 2 * baskets, matching the direct interpretation.

The fourth case shows why the largest raw basket count does not necessarily determine the winner:

Left Right
5 6
5 0
0 5

Left scores 2 * 5 + 5 + 0 = 15. Right scores 2 * 6 + 0 + 5 = 17, so the correct output is actually:

Right

This is a useful boundary case because it catches implementations that incorrectly assume each three-pointer should simply be counted as another basket without adjusting its value, or implementations that compare basket counts without considering free throws and three-pointers.

The final case is a large-value input. For example:

Alpha Beta
1000000000000000000 999999999999999999
500000000000000000 0
0 1000000000000000000

The algorithm performs the same three arithmetic operations per team regardless of the magnitude of the values. Python's integer representation handles these values directly, so no special overflow logic is necessary.

The official statement confirms that the problem is CodeRams Practice Archive problem 024, with a 1 second limit, 256 MB memory limit, and the sample Syracuse Duke.