iTranslated by AI
Reviewing the First Three Problems of AtCoder Beginner Contest 308
Hi there.
I'm bun913, a huge fan of the manga "Dragon Quest: The Adventure of Dai."
Are you familiar with AtCoder, a service where you can enjoy competitive programming?
I've been participating in contests as a hobby from time to time, and I also took part in the CodeQUEEN 2023 Final (AtCoder Beginner Contest 308) held on Saturday, July 1, 2023!
In this contest, I was only able to solve problems A and B within the time limit. However, I was impressed by the various approaches to problem C after the contest, so I'd like to reflect on it.
Problems Solved and Path to the Correct Answer
A - New Scheme
This problem asks whether a sequence S satisfies the following conditions:
- S1 <= S2 <= S3 ... <= S8
- All elements of sequence S are between 100 and 675 (inclusive)
- All elements of sequence S are multiples of 25
Thinking about the first condition was a bit tedious, so I thought, "I'll prepare a pre-sorted array and if the elements or order of S have changed, it's NG."
So, I implemented and submitted it as follows:
S = list(map(int, input().split()))
# Pre-sorted array
so = sorted(S)
for i, s in enumerate(S):
# 1st condition
if s != so[i]:
print("No")
exit()
# 2nd condition
if s < 100 or s > 676:
print("No")
exit()
# 3rd condition
if s % 25 != 0:
print("No")
exit()
print("Yes")
B - Default Price
When I first saw the problem, I had a brief "Huh?" moment, but it seemed like I could think about it simply like this:
- Array C contains the colors of the plates Takahashi ate.
- Since the price is determined by the plate color, it should be fine if we know the price for each plate color.
- Color D1 corresponds to price P1, color D2 to price P2, and so on.
- For any color not in D, the price is P0.
So, I tried implementing it like this.
Note that since I was in a hurry during the contest, there is some unnecessary implementation.
from collections import defaultdict
setrecursionlimit(10**7)
N, M = map(int, input().split())
# The i-th plate color eaten
C = list(map(str, input().split()))
# Dishes on Di plates cost Pi each
D = list(map(str, input().split()))
P = list(map(int, input().split()))
# First, look at the colors in C and D to create a price correspondence table
pc = defaultdict(int) # A regular dict would have been fine since I'm not using defaultdict features
for i, d in enumerate(D):
pc[d] = P[i+1]
ans = 0
for c in C:
# If the color is not in D, use P[0]
if c not in pc:
ans += P[0]
continue
ans += pc[c]
print(ans)
C - Standings
This is the problem I couldn't solve during the contest and really struggled with.
- There are N people, each with Ai coin toss successes and Bi failures.
- Sort them in descending order of their success rate.
- If the success rates are the same, sort them by person number in ascending order.
As stated in the problem, the success rate can be calculated as A[i] / (A[i] + B[i]). However, it was obvious that calculating it directly like this would not work correctly due to errors in floating-point calculations.
Therefore, I thought I had to calculate it using integers somehow and came up with the following incorrect answer.
Incorrect Answer 1: Resolving as an Integer Problem via Least Common Multiple Approach
- My reasoning was as follows:
- Isn't it complex to think about the rate because the number of trials (A+B) is different for each person?
- In that case, if I consider the least common multiple (LCM) of the trial counts for each of the N people, wouldn't I be able to handle it without decimals by calculating it like this!?
- Each person's success rate score:
(LCM // (A[i] + B[i])) * A[i]
- Each person's success rate score:
With that in mind, I submitted the following:
from math import gcd
from functools import reduce
def lcm(a, b):
return a * b // gcd(a, b)
N = int(input())
A = []
B = []
S = []
for _ in range(N):
a, b = map(int, input().split())
A.append(a)
B.append(b)
S.append(a+b)
lc = reduce(lcm, S)
scores = []
for i in range(N):
# Calculate the success rate score here
scores.append((lc//S[i]*A[i], i+1))
# If the second element of scores[i] is the same, sort the first element in ascending order
sort_list = sorted(scores, reverse=True, key=lambda x: (x[0], -x[1]))
ans_list = []
for i, score in enumerate(sort_list):
ans_list.append(score[1])
print(*ans_list, sep=' ')
However, since there are cases where A[i] and B[i] are large numbers, calculating it this way results in a TLE.
Incorrect Answer 2: Handling with Rational Numbers using Fraction
Forget it! If there are decimal errors, I'll use rational numbers! Here is the code I submitted with that thought.
# -*- coding: utf-8 -*-
"""
Trying Fraction, which I really didn't want to use
"""
from fractions import Fraction
N = int(input())
fractions = []
for _ in range(N):
a, b = map(int, input().split())
# Handle as rational numbers instead of decimals
success_rate = Fraction(a, a + b)
fractions.append(success_rate)
people = list(range(1, N + 1))
people.sort(key=lambda i: (-fractions[i-1], i))
print(*people, sep=" ")
As explained very clearly in the article below, Fraction seems to have very slow calculation speeds, so it also resulted in a TLE.
Incorrect Answer 3: Fine! Then I'll solve it with Decimal! (Close call)
After seeing the article above, I thought, "Maybe Decimal will work?" and submitted the following code.
# -*- coding: utf-8 -*-
"""
I also didn't want to use this, but let's try Decimal
"""
from decimal import Decimal
N = int(input())
decimals = []
for _ in range(N):
a, b = map(int, input().split())
success_rate = Decimal(a) / Decimal(a + b) # Calculate success rate using Decimal
decimals.append(success_rate)
people = list(range(1, N + 1))
people.sort(key=lambda i: (-decimals[i-1], i))
print(*people, sep=' ')
I submitted this code using PyPy out of habit, but if I had submitted it using Python 3, it would have been a correct submission. (I found this out after the contest.)
Apparently, in PyPy, calculations involving floating-point numbers can actually be slower. (This was news to me.)
I'd like to look into exactly what kind of processing is slow.
Solution that worked after the contest
Since Python supports arbitrary-precision integers, I decided to try a calculation using a very large integer. Here is the code I submitted:
# -*- coding: utf-8 -*-
"""
Changing direction and trying integer arithmetic using a very large number
"""
N = int(input())
success_rates = []
for _ in range(N):
a, b = map(int, input().split())
# Incorporating integer arithmetic with a very large number
success_rate = a * (10**20) // (a + b)
success_rates.append(success_rate)
people = list(range(1, N + 1))
people.sort(key=lambda i: (-success_rates[i-1], i))
print(*people, sep=' ')
By doing this, the precision improved and the answer was accepted.
Furthermore, the official editorial describes various methods, and it is very interesting just to look through them.
Conclusion
At the moment, I am aiming to be a "person who can solve up to Problem C with near certainty," so I was a bit frustrated that I got so caught up in Problem C that I ended up not being able to reach the final answer.
However, more than that, I learned the following points, making it a contest I'm glad I participated in!
- Decimal is actually slower in PyPy.
- Since Python handles arbitrary-precision integers, you can easily improve precision by multiplying by a very large power of 10.
- The sorting method in the official solution is wonderful.
- I didn't know about the method of passing a sort key using
cmp_to_keyeither. - Editorial - CodeQUEEN 2023 Final (AtCoder Beginner Contest 308)
- I didn't know about the method of passing a sort key using
I'll continue to keep at it at my own pace!
Thank you for reading to the end!
Discussion