Transcript Penicillin

HKOI 2012 (Junior)
Q4 - Penicillin
Gary Wong
For any question, please ask via
Email: [email protected]
MSN: [email protected]
For your interest (if any)
• The history in the problem is really
true!
• Penicillin refers to a group of
antibiotics
• Examples:
• Penicillin G
• Amoxicillin
• Ampicillin
•…
• Bacteria and viruses are 2 different
things
Problem Statement
• Each of N points (xi, yi) can “grow”
into an “unclean” square with side 2t
at time t, with (xi, yi) as the “centre”
• A special point P(h, k) can “grow”
into a square with side 2ts at time t
• “Growth” is bounded by a rectangle
with dimension P x Q
• Area covered by square centred at P
will be always clean
Problem Statement
• Find the area of unclean area
• N.B.: Overlapped area should be counted
repeatedly
• Constraints:
• 50%
• N <= 50
• P, Q, s, t <= 100
• 100%
• 1 <= N <= 10,000
• 1 <= P, Q, s, t <= 100,000
• 0 <= xi, h <= P
• 0 <= yi, k <= Q
Statistics
•
•
•
•
Max. score: 100
No. of max: 2
Std dev: 27.38
Mean: 5.29
• Disappointed…
Statistics
• Disappointed…
No. of contestants
25
20
15
10
5
0
0
10
20
30
40
50
Score
60
70
80
90 100
Solution – 50%
• N <= 50
• P, Q, s, t <= 100
• How about declaring a 2D array to
mimic the agar plate?
• Simulate the growth step by step!
• Count how many times each cell was
covered, clear all sterile part
• Complexity?
• Very roughly, O(NPQt)
• In fact much less than this
Solution – 100%
• 1 <= N <= 10,000
• 1 <= P, Q, s, t <= 100,000
• O(NPQt) cannot work anymore…
• Note that
• Each point is independent from
each other, because overlapped
areas are counted repeatedly
• If you know how to do for one
point, same for other (N-1) points
Solution – 100%
• The problem reduces to:
• Given 2 “growing” squares, find
the brown area without covered by
green square
Solution – 100%
• Consider the brown square
• Top-left corner: (xi – t, yi – t)
• Bottom-right corner: (xi + t, yi + t)
Solution – 100%
• But what if it reaches/exceeds
boundaries?
• Actual top-left corner
• (max(0, xi – t), max(0, yi – t))
• Actual bottom-right corner
• (min(P, xi + t), min(Q, yi + t))
Solution – 100%
• Similarly, for green square,
• Top-left corner
• (max(0, h – st), max(0, k – st))
• Bottom-right corner
• (min(P, h + st), min(Q, k + st))
Solution – 100%
• Next task: how to find intersection
area between the 2 squares?
Solution – 100%
• Consider the corners of the
intersection area!
(a1, b1)
(a2, b2)
(c1, d1)
(c2, d2)
Solution – 100%
• For the intersection area,
• Top-left corner
• (max(a1,a2), max(b1,b2))
• Bottom-right corner
• (min(c1,c2), min(d1,d2))
(a1, b1)
(a2, b2)
(c1, d1)
(c2, d2)
Solution – 100%
• How to detect the case of “no
intersection”?
Solution – 100%
• Area of brown square minus area of
intersection
• Do this for N times
• Complexity?
• O(N)
Common mistakes
• Areas were not counted repeatedly
• Cannot even pass the sample
input in the problem
• Misunderstand that penicillin can kill
only one layer of bacteria
• Forgot to use 64-bit integer type to
store the answer
Any question?