In [1]:
# SAMPLE INPUT
# 4
# 1 0
# 0 1
# -1 0
# 0 -1
In [2]:
fin = open ('moop.in', 'r')
fout = open ('moop.out', 'w')
# N = particles
N = int(fin.readline().strip())
print("N",N)
In [3]:
moo = [] # EACH PARTICLE HAS A DISTINCT SPIN
for i in range(N):
x,y = map(int,fin.readline().split())
moo.append((x,y))
moo.sort(reverse=True)
print(moo)
In [4]:
# Find the Pareto Frontier, the points that are not dominated by any other points
# i.e. no points above or to the right
a,b = moo[0]
# the first point has largest X, so it is on the frontier
frontier = [(a,b)]
# As the pareto particles are identified
# keep track of the minimum Y value observed among subordinate particles that
# are dominated by the current pareto particle
miny = b
minyList = []
for x,y in moo[1:]:
if x<=a and y<=b:
if y<miny:
miny=y
continue
else:
frontier.append((x,y))
minyList.append(miny)
a=x
b=y
miny=b
minyList.append(miny)
# the list of pareto particles, ordered by descending X value
print("frontier",frontier)
# list of minimum Y values associated with each pareto particle
print("minyList",minyList)
In [5]:
# we need to scan the pareto list in order of increasing X value
# this is the reverse of the current list
# We want to examine each dominant point to see if it shares any subordinate
# points with the dominant points before it on the list (with lower X value)
#
# Here we reverse the list and take of the first point; we can begin with the second
# point and check if it shares with the first point.
rfrontier = frontier[len(frontier)-2::-1]
print("rfrontier",rfrontier)
In [6]:
# We need to reverse the minimum Y values associated with the pareto points
# The last point on the reversed list can be dropped because we begin by
# comparing the first minimum Y value with the second pareto point (so the last
# Y value will never be used).
# Also, we need to carry forward the global minimum Y value observed, since this
# may be a subordinate point for all pareto points going forward in the scan
ry = []
lasty = 999999999
for i in minyList[:0:-1]:
if i < lasty:
lasty = i
ry.append(lasty)
print("ry",ry)
In [7]:
# Now we can scan the pareto points and count the connected components.
# If the next pareto point in the scan has a higher Y value than the
# minimum Y value associated with previous points, then there is a shared
# subordinate point and the point is not counted.
count = 1
for pair, y in zip(rfrontier,ry):
a,b = pair
if b<y:
count+=1
print(count)
fout.write(str(count)+"\n")
fout.close()
This code passes all test cases in analysis mode. The official solution recommends looking at the particles as nodes in a graph, with edges indicating that the particles can interact. Then this becomes a UNION-FIND problem and the answer is the number of connected components. Unfortunately, I took a more complicated approach, but it was still possible to solve the problem with a sub-optimal approach.
