ICPC Asia Pacific Regionals

icpc diamondmulti-regional sponsor

icpc global sponsor
programming tools

The 2021 ICPC
Asia Yokohama
Regional Contest

Official Problem Set

ICPC — International Collegiate Programming Contest
Asia Regional Contest, Yokohama, 2022–03–16

Problem A
Loop of Chocolate
Time Limit: 2 seconds
Let’s make sweets of a fancy shape that is a loop of chocolate.

Figure A.1. A loop of chocolate formed by a union of six spheres

The shape of a loop is formed by a union of a number of spheres of the same size, where every
sphere intersects with exactly two others.

(a) Union of four spheres(b) Four intersections of the four spheres in (a)Figure A.2. A loop of chocolate formed by a union of four spheres
Your job is to write a program that, for given the size and the positions of spheres, computes
the total volume of the union of the spheres, i.e., the amount of chocolate required for filling theloop formed by the union.

[Hints] Two spheres of the same radius r intersect each other when the distance between theircenters, d, is less than 2r. The volume of the intersection is known to be2π(r − d/2)2 (2r + d/2).
3
The volume of the sphere of radius r is 4πr3 /3.

1

Input
The input consists of a single test case of the following format.
nr
x 1 y1 z1..
.
xn yn znn and r are integers. n is the number of spheres (4 ≤ n ≤ 100). All the spheres has the sameradius r (2 ≤ r ≤ 100). (xk , yk , zk ) indicates the coordinates of the center of the k-th sphere(k = 1, . . . , n). All of xk , yk , and zk are integers between −100 and 100, inclusive.
The k-th and the k + 1-th spheres intersect each other for 1 ≤ k < n. The 1-th and the n-th
spheres also intersect. No other pairs of spheres intersect.

OutputOutput in a line the volume of the union of the spheres. Relative error of the output should bewithin 10−7 .
Sample Input 1

Sample Output 1

6 9
20 0 1020 10 0
10 20 00 20 10
0 10 20
10 0 2017149.528141

Sample Input 2

Sample Output 2

4 12
10 10 0
10 -10 0-10 -10 0-10 10 027813.56696

Sample Input 3

Sample Output 3

6 9
23 3 1320 10 0
10 20 03 23 13
0 10 20
10 0 2017470.837758

2

Sample Input 4

Sample Output 4

4 2
0 0 0
3 0 0
3 3 0
0 3 0

122.52211349

Sample Input 5

Sample Output 5

8 70
100 100 0
0 100 0-100 100 0-100 0 0-100 -100 0
0 -100 0
100 -100 0
100 0 010220648.1

3

ICPC — International Collegiate Programming Contest
Asia Regional Contest, Yokohama, 2022–03–16

Problem B
Lottery Fun TimeTime Limit: 2 seconds
The biggest fun of lottery is not in receiving the (usually a tiny amount of) prize money, but in dreamingof the big fortune you may possibly (that is, virtually
never) receive.
You have a number of lottery tickets at hand, eachwith a six-digit number. All the numbers are different, of course. Tomorrow is the drawing day and theprizes are the following.
• The first prize of 300,000 yen is won by the ticket with exact match of all the six digits
with the six-digit first prize winning number.
• The second prizes of 4,000 yen are won by all of the tickets with their last four digits
matching the four-digit second prize winning number.
• The third prizes of 500 yen are won by all of the tickets with their last two digits matching
any of the three two-digit third prize winning numbers.
The six digits on the lottery tickets and all of the winning numbers may start with zeros.
The last two digits of all the prize winning numbers are made different so that tickets winning
the third prize cannot also win the first nor the second prizes. Note that this rule also made thelast two digits of the first and the second prize winning numbers different.
To enjoy the climax of the lottery fun time, you decided to calculate the possible maximum
amount you may win with your tickets. You have too many tickets to hand-calculate it, but itshould also be your joy to write a program for making the calculation.

Input
The first line of the input has a positive integer n (n ≤ 105 ), which is the number of tickets you
have at hand. Each of the following n lines has the six-digit number on one of your tickets. All
the n numbers are different from one another.

OutputOutput in a line a single integer, which is the maximum possible total of winning prizes withthe tickets you have.
4Sample Input 1

Sample Output 1

7034207924837372745382947274637083907294837309500Sample Input 2

Sample Output 2

10012389456789234589678989890189567889123489263784901289345689304500For the first sample, the following combination of prize winners allows the maximum total
amount of 309500 yen.
• The first prize winner of 382947 makes one ticket with that number win 300000 yen.
• The second prize winner of 4837 makes two tickets, 924837 and 294837, win 4000 yen each.
• The third prize winners 07 and 45 make three tickets, 034207, 083907, and 372745, win
500 yen each. 37 cannot be a third prize winner, as the second prize winner, 4837, has the
final two digits of 37. The ticket 274637, thus, wins nothing. You have no more tickets towin whatever the remaining third prize winner may be.
For the second sample, nine out of the ten tickets have the same last two digits, 89, and thus
the third prize winner of 89 allows nine third prizes, totaling 4500 yen. This is more than thesecond prize of 4000 yen possibly won by one of these nine tickets. The only remaining ticket
263784 should, of course, win the first prize.

5

ICPC — International Collegiate Programming Contest
Asia Regional Contest, Yokohama, 2022–03–16

Problem C
Reversible Compression
Time Limit: 2 seconds
Data compression is an essential technology in our information society. It is to encode a given
string into a (preferably) more compact code string so that it can be stored and/or transferred
efficiently.
You are asked to design a novel compression algorithm such that even a code string is reversed
it can be decoded into the given string.
Currently, you are considering the following specification as a candidate.
• A given string is a sequence of decimal digits, namely, 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9.
• A code string is a sequence of code words, and a code word consists of two decimal digits
A and L. So, a code string is a sequence of even number of decimal digits.
• A code string A1 L1 · · · Ak Lk is decoded into a string by the following procedure. Here,for brevity, a decimal digit (Ai or Li ) is also treated as the single digit decimal integer it
represents.
1. i ← 1
2. while (i is not greater than k) {3.
if (Ai is zero) { output Li }4.
else if (Li is zero) { do nothing }5.
else if (Ai is larger than the number of digits output so far) { raise an error }6.
else {
7.
repeat Li times {8.
output the Ai -th of the already output digits counted backwards
9.
}
10.
}
11.
i←i+1
12. }
For example, a code string 000125 is decoded into a string 0101010 as follows:
1. The first code word 00 outputs 0.
2. The second code word 01 outputs 1.

6

3. The first digit 2 of the last code word 25 means that the second digit in the already decoded
digits, counted backwards, should be output. This should be repeated five times. For the
first repetition, the decoded digits so far are 0 and 1, and thus the second last digit is 0,
which is output. For the second repetition, digits decoded so far are 0, 1, and 0, and thesecond last is 1, which is output. Repeating this three more times outputs 0, 1, and 0.
A sequence of code words that raises no error is a valid code string. A valid code string is said
to be reversible when its reverse is also valid and both the original and its reverse are decoded
into the same string.
For example, the code string 000125 is not reversible, because its reverse, 521000, raises anerror and thus is not valid. The code string 0010 is not reversible though its reverse is valid. It
is decoded into 0, but its reverse 0100 is decoded into 10. On the other hand, 0015599100 isreversible, because this and its reverse, 0019955100, are both decoded into 00000000000000000.
You want to evaluate the performance of this compression method when applied to a variety ofcases. Your task is to write a program that, for an arbitrary given digit string, finds the shortest
reversible code string that is decoded into the given string.

Input
The input consists of a single line containing a non-empty string s of decimal digits. The lengthof s does not exceed 500.

OutputOutput the shortest reversible code string that is decoded into s. If there are multiple solutions
with the same shortest length, output the earliest in the lexicographic order. Note that it iseasily shown that a reversible code string always exists for any input string (e.g., see Sample
Output 4).
Sample Input 1

Sample Output 1

00000000000000000

0015599100

Sample Input 2

Sample Output 2

0101010000122221000

Sample Input 3

Sample Output 3

123123123123123123123123123123

01020336699993302010

Sample Input 4

Sample Output 4123456789

010203040506070809908070605040302010

7

ICPC — International Collegiate Programming Contest
Asia Regional Contest, Yokohama, 2022–03–16

Problem D
Wireless Communication Network
Time Limit: 5 seconds
We are setting up a wireless communication network in a mountain range. Communication
stations are to be located on the summits. The summits are on a straight line and have different
altitudes.
To minimize the cost, our communication network should have a tree structure, which is aconnected graph with the least number of edges. The structure of the network, that is, which
stations to communicate with which other stations, should be decided in advance.
We construct the communication network as follows.
1. Initially, each station forms a tree consisting of only that station.
2. In each step, we merge two trees that are adjacent by making a link between two stations
in different trees. Two trees are called adjacent when all the summits in between a summit
in one tree and a summit in the other belong to one of these two trees. Stations to link
are those on the highest summits of the two trees; they are uniquely determined because
the altitudes of the summits are distinct.
3. Repeat the step 2 until all the stations are connected, directly or indirectly.
Figure D.1 depicts an example of the tree formation for Sample 1.
When a station detects an emergency event, an alert message should be broadcast to all thestations. On receiving a message, each station relays the message to all the stations with direct
links, except for one from which it has come. The diameter of the network, that is, how many
hops are sufficient to distribute messages initiated at any stations, depends on the choice of thetwo trees in the step 2 above.
To estimate the worst case delay of broadcast, we want to find the largest diameter of the
network possibly constructed by the above procedure.

8

Obtained after some repetitions of step 2
with a certain series of choices. There arethree trees, T1 , T2 , and T3 . Here, the stationh forms the tree T3 consisting of only thestation h.
Obtained by linking stations g and h in step
2. Trees T2 and T3 , with top summits g andh respectively, are adjacent.

Obtained by linking stations b and h in thenext step 2, merging two adjacent trees.
Now all the stations form a single tree.
Figure D.1. The tree formation for Sample 1

Input
The input consists of a single test case of the following format.
n
h1
..
.
hn
Here, n is the number of communication stations (3 ≤ n ≤ 106 ), and hi is an integer representing
the altitude of the i-th station (1 ≤ hi ≤ n). The altitudes of the stations are distinct, that is,hi 6= hj if i 6= j.

OutputOutput in a line a single integer representing the largest possible diameter of the tree.
Sample Input 1

Sample Output 1

8
1
8
2
3
5
4
6
7

6

9

Sample Input 2

Sample Output 2

4
1
2
3
4

3

10

ICPC — International Collegiate Programming Contest
Asia Regional Contest, Yokohama, 2022–03–16

Problem E
Planning Railroad Discontinuation
Time Limit: 5 seconds
The ICPC Kingdom has a large round lake in its center, and all of its cities are developed aroundthe lake, forming a circle of cities. Because all of them are developed under the same urban
plan, the cities are made quite similar. They have exactly the same subway networks. Some of
their stations are also stations of inter-city bullet trains connecting two corresponding stationsof adjacent cities. All of the train routes provide two-way traffic between two terminal stations
without any intermediate stations.
The cities have the same number of subway stations and subway routes. In each city, thestations are numbered sequentially as 0, 1, 2, . . . . Whether two stations in a city are connectedby a subway route depends only on their station numbers and not on the city. If a station v isconnected to a station u in one city, so is in all the other cities. The travel distance between
two stations v and u are the same for all the cities.
All the cities have exactly the same list of station numbers of bullet train stations. If a stations is a bullet train station in one city, so is in all the other cities. All the pairs of two bullet train
stations of the same station number in two adjacent cities are connected by a bullet train route.
If a station s is one end of a bullet train route, the station s in an adjacent city is the otherend. There exist no other bullet train routes. One can travel between any two stations in theKingdom via one or more subway and/or bullet train services.
Due to financial difficulties in recent years, the Kingdom plans to discontinue some of the
subway and bullet train services to reduce the maintenance cost of the railroad system. The
maintenance cost is the sum of maintenance costs of the subway routes and the bullet train
routes. The maintenance cost of a subway route is the sum of base cost depending on the cityand cost proportional to the travel distance of the route. The maintenance cost of a bullet train
route depends only on the two cities connected by the route.
You are asked to make a plan to discontinue some of the routes that minimizes the total maintenance cost. Of course, all the pairs of the stations in the Kingdom should still be connected
through one or more subway and/or bullet train services after the discontinuation.

11

Input
The input consists of a single test case of the following format.
nm
v1 u1 d1..
.
vm um dm
l
a0 b0
..
.
al−1 bl−1
r
s1
..
.
sr
Here, n is an integer satisfying 2 ≤ n ≤ 104 , which is the number of the subway stations in a city.
The stations in each city are numbered from 0 to n − 1. m is an integer satisfying 1 ≤ m ≤ 105 ,which is the number of the subway routes in a city. The following m lines are information on
the subway system in a city. The i-th of the m lines has three integers vi , ui , and di , satisfying
0 ≤ vi < n, 0 ≤ ui < n, vi 6= ui , and 1 ≤ di ≤ 109 . They mean that a subway route connects
stations numbered vi and ui , and its maintenance cost proportional to the travel distance is di .
There is at most one subway route between two stations. All the subway stations in a city areconnected directly or indirectly via one or more subway routes.
l in the next line is an integer satisfying 3 ≤ l ≤ 105 , which is the number of cities in theKingdom. The cities are numbered from 0 to l − 1, and the city 0 is also called the city l. For
each 0 ≤ j ≤ l − 1, the cities j and j + 1 are adjacent. aj and bj in the following l lines areintegers satisfying 1 ≤ aj ≤ 109 and 1 ≤ bj ≤ 109 . aj is the maintenance cost of a bullet train
route connecting the cities j and j + 1. bj is the base cost of the subway routes in the city j.
r is an integer satisfying 1 ≤ r ≤ n, which is the number of the bullet train stations in each city.
s1 , s2 , . . . , sr are the station numbers of the bullet train stations in each city.

OutputOutput in a single line the integer representing the minimum maintenance cost of the railroad
system after the discontinuation that minimizes the cost while keeping all the stations connected,
directly or indirectly.

12Sample Input 1

Sample Output 1

2 1
0 1 3
3
6 1
4 2
5 3
1
1

24

Sample Input 2

Sample Output 2

3 3
0 1 7
1 2 8
2 0 5
4
8 1
5 1
9 3
7 3
2
1
2

76

13

Sample Input 3

Sample Output 3

5 8
0 1 1
2 1 2
4 0 5
3 4 7
3 2 8
0 2 4
4 1 3
2 4 6
6
3 2
9 3
7 1
5 3
3 2
5 2
4
0
2
3
4

120

14

ICPC — International Collegiate Programming Contest
Asia Regional Contest, Yokohama, 2022–03–16

Problem F
It’s Surely Complex
Time Limit: 30 seconds
As you know, a complex number is often represented as the sum of a real part and an imaginary
part. 3 + 2i is such an example, where 3 is the real part, 2 is the imaginary part, and i is theimaginary unit.
Given a prime number p and a positive integer n, your program for this problem should output
the product of all the complex numbers satisfying the following conditions.
• Both the real part and the imaginary part are non-negative integers less than or equal ton.
• At least one of the real part and the imaginary part is not a multiple of p.
For instance, when p = 3 and n = 1, the complex numbers satisfying the conditions are
1 (= 1 + 0i), i (= 0 + 1i), and 1 + i (= 1 + 1i), and the product of these numbers, that is,
1 × i × (1 + i) is −1 + i.

Input
The input consists of a single test case of the following format.
pn
p is a prime number less than 5 × 105 . n is a positive integer less than or equal to 1018 .

OutputOutput two integers separated by a space in a line. When the product of all the complex numbers
satisfying the given conditions is a + bi, the first and the second integers should be a modulo
p and b modulo p, respectively. Here, x modulo y means the integer z between 0 and y − 1,
inclusive, such that x − z is divisible by y.
As exemplified in the main section, when p = 3 and n = 1, the product to be calculated is−1 + i. However, since −1 modulo 3 is 2, 2 and 1 are displayed in Sample Output 1.

15

Sample Input 1

Sample Output 1

3 1

2 1

Sample Input 2

Sample Output 2

5 5

0 0

Sample Input 3

Sample Output 3

499979 1000000000000000000

486292 0

16

ICPC — International Collegiate Programming Contest
Asia Regional Contest, Yokohama, 2022–03–16

Problem G
Genealogy of Puppets
Time Limit: 2 seconds
The Inventive and Creative Puppets Corporation (ICPC) sells a variety of educational puppets
for children, and also for grown-ups who were once children and still remember it. To celebrate
its centennial anniversary, ICPC has decided to offer for sale a collection of many of its mostpopular puppets in its history of one hundred years, which will be a collectors’ envy for sure.
Each puppet has a ring attached to its head, with which it can be hung below one of two
toes of another puppet. At most one puppet can be hung on one toe. As puppets do not feel
comfortable in handstand positions, loops of puppets should be avoided. A tree of puppets canthus be made by hanging all the puppets to a toe of another puppet, leaving the ring of the
topmost puppet to be hung on the wall.
You are enthusiastic in ICPC puppets since childhood. You like imagining genealogies of thepuppets, assuming that puppets are hung on a parent puppet. You also imagine personalitiesof puppets, and decided to obey the following rules on forming the tree:• each puppet has its own constraints on the number of children, that are its minimum andmaximum, and• if a puppet has any children, at least one of them should have release date later than theparent.
Note that, if a puppet has two children, one of them may have its release date earlier than theparent.
You want to write a program to calculate how many different trees can be made by the collection,satisfying the rules. Two trees are considered different if any of the puppets are hung on different
parents, or hung on different toes of the same parent.

Input
The input consists of a single test case of the following format.
n
x 1 y1..
.
x n yn17

The first line contains an integer n (2 ≤ n ≤ 300), representing the number of puppets. The
i-th line of the following n lines describes the personality of a puppet. Lines are in the orderof the release dates of the puppets, from older to newer. Two integers in the line, xi and yi ,are the minimum number and the maximum number of children of the puppet, respectively.
0 ≤ xi ≤ yi ≤ 2 holds.

OutputOutput a single integer in a line which is the number of the different trees satisfying the rules
modulo 109 + 7.
Sample Input 1

Sample Output 1

3
0 1
1 2
0 2

6

Sample Input 2

Sample Output 2

2
0 2
1 2

0

For Sample Input 1, there are 6 possible trees satisfying the rules shown in Figure G.1.
For Sample Input 2, no trees can satisfy the rules.

Figure G.1. Trees satisfying the rules for Sample Input 1. The numbers on the puppets
represent the release order.

18

ICPC — International Collegiate Programming Contest
Asia Regional Contest, Yokohama, 2022–03–16

Problem H
Cancer DNA
Time Limit: 10 seconds
The Investigation Center for Potential Cancer (ICPC) found out patterns of a DNA sequencethat cause cancer! We would like you to write a computer program that approximates theprobability that a random DNA sequence matches one of the given patterns.
A DNA sequence can be represented by a string consisting of four letters, ‘A’, ‘G’, ‘C’, and ‘T’. A
DNA pattern is a string over the same four letters plus ‘?’. We say that a DNA pattern matchesa DNA sequence of the same length if each of the characters in the pattern is either ‘?’ or isthe same as the character at the corresponding position in the DNA sequence. For example, apattern “AC?” matches DNA sequences “ACA”, “ACG”, “ACC”, and “ACT”.
Your task is to write a program that, given a set of DNA patterns of the same length, computes
the probability that a uniformly random DNA sequence of the same length matches any of thegiven patterns. A multiplicative error up to 5% is permissible.

Input
The input consists of a single test case of the following format.
nm
P1
..
.
Pm
The first line of the input contains two positive integers n and m such that 1 ≤ n ≤ 100 and
1 ≤ m ≤ 30 hold. The next m lines contain m patterns P1 , . . . , Pm . Each pattern Pi is a stringof length n over ‘A’, ‘G’, ‘C’, ‘T’, and ‘?’.

OutputLet S be a DNA sequence of length n chosen uniformly at random. Let w be the probability
that S matches at least one of P1 , . . . , and Pm . The output is a real number v that approximatesw.
The output v is judged to be correct if v approximates w within a multiplicative error of 5%,i.e.,
0.95 × w ≤ v ≤ 1.05 × w.
v should be represented either with or without exponent component. For example, 0.045 can be
represented as 4.5e-2 or 0.045.
19

Sample Input 1

Sample Output 1

3 1
AC?

0.0625

Sample Input 2

Sample Output 2

6 2
AC??A?
A??A?T

0.0302734375

Sample Input 3

Sample Output 3

30 1
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

8.673617379884035e-19

In the first sample, there are 43 DNA sequences of length 3. There are 4 DNA sequences, “ACA”,“ACG”, “ACC”, and “ACT”, that match the pattern “AC?”. Thus, the probability is 4/43 = 0.0625.
Any real number between 0.059375 and 0.065625 is accepted as a correct output.
As in the third sample, the probability can be a small real number. Note that “0” is not acorrect output, as 0 is less than 95% of the precise probability.

20

ICPC — International Collegiate Programming Contest
Asia Regional Contest, Yokohama, 2022–03–16

Problem I“Even” Division
Time Limit: 4 seconds
If you talk about an even division in the usual sense of the words, it means dividing a thingequally. Today, you need to think about something different. A graph is to be divided into
subgraphs with their numbers of nodes being even, that is, multiples of two.
You are given an undirected connected graph with even number of nodes. The given graph is tobe divided into its subgraphs so that all the subgraphs are connected and with even number ofnodes, until no further such division is possible. Figure I.1 illustrates an example. The originalgraph of 8 nodes is divided into subgraphs with 4, 2, and 2 nodes. All of them have even numbersof nodes.

Figure I.1. Example of a division (Sample Input/Output 1)

To put it mathematically, an even division of a graph is the set of subsets V1 , . . . , Vk of the graphnodes satisfying the following conditions.
1. V1 ∪ · · · ∪ Vk is the set of all the nodes of the input graph, and Vi ∩ Vj = ∅ if i 6= j.
2. Each Vi is non-empty, and has an even number of elements.
3. Each Vi induces a connected subgraph. In other words, any nodes in Vi are reachable fromeach other by using only the edges of the input graph connecting two nodes in Vi .
4. There is no further division. For any U1 ∪ U2 = Vi , the division obtained by replacing Viwith the two sets, U1 and U2 , does not satisfy either of the conditions 1, 2, or 3.
Your task is to find an even division of the given graph.

21

Input
The input consists of a single test case of the following format.
nm
x 1 y1..
.
xm ym
The first line consists of two integers n and m. The first integer n (2 ≤ n ≤ 105 ) is an evennumber representing the number of the nodes of the graph to be divided. The second integer m(n − 1 ≤ m ≤ 105 ) is the number of the edges of the graph.
The nodes of the graph are numbered from 0 to n − 1.
The subsequent m lines represent the edges of the graph. A line xi yi (0 ≤ xi < yi < n) meansthat there is an edge connecting the two nodes xi and yi . There are no duplicated edges. The
input graph is guaranteed to be connected.

OutputIf there exists an even division of the node set of the given graph into subsets V1 , . . . , Vk , print k
in the first line of the output. The next k lines should describe the subsets V1 , . . . , Vk . The orderof the subsets does not matter. The i-th of them should begin with the size of Vi , followed by
the node numbers of the elements of Vi , separated by a space. The order of the node numbers
does not matter either.
If there are multiple even divisions, any of them are acceptable.
Sample Input 1

Sample Output 1

8 9
0 1
1 2
2 3
0 4
1 6
3 7
4 5
5 6
6 7

3
2 3 7
2 4 5
4 0 1 2 6

Sample Input 2

Sample Output 2

2 1
0 1

1
2 0 1

In the Sample 2, the singleton set of the set of the nodes of the original graph is already an evendivision.
22

ICPC — International Collegiate Programming Contest
Asia Regional Contest, Yokohama, 2022–03–16

Problem J
The Cross Covers Everything
Time Limit: 3 seconds
A cross-shaped infinite area on the x-y plane can be specified by two distinct points as depictedon the figure below.

Figure J.1. The cross area specified by two points numbered 2 and 4
Given a set of points on the plane, you are asked to figure out how many pairs of the points
form a cross-shaped area that covers all the points. To be more precise, when n points withcoordinates (xi , yi ) (i = 1, . . . , n) are given, the ordered pair hp, qi is said to cover a point (x, y)
if xp ≤ x ≤ xq , yp ≤ y ≤ yq , or both hold. Your task is to find how many pairs hp, qi cover all
the n points. No two given points have the same x-coordinate nor the same y-coordinate.

Input
The input consists of a single test case of the following format.
n
x 1 y1..
.
xn yn
The first line contains an integer n (2 ≤ n ≤ 2 × 105 ), which is the number of points given. Two
integers xi and yi in the i-th line of the following n lines are the coordinates of the i-th point(1 ≤ xi ≤ 106 , 1 ≤ yi ≤ 106 ). You may assume that xj 6= xk and yj 6= yk hold for all j 6= k.

OutputPrint in a line the number of ordered pairs of points that satisfy the condition.
23

Sample Input 1

Sample Output 1

4
2 1
1 2
6 3
5 4

4

Sample Input 2

Sample Output 2

20
15 9
14 13
2 7
10 5
11 17
13 8
9 3
8 12
6 4
19 18
12 1
3 2
5 10
18 11
4 19
20 16
16 15
1 14
7 6
17 20

9

Figure J.1 depicts the cross specified by two points numbered 2 and 4, that are the second andthe fourth points of the Sample Input 1. This is one of the crosses covering all the points.

Amendment
The conditions xp ≤ xq , and yp ≤ yq , have to be added to be satisfied for the the ordered pair
hp, qi that are counted. This was announced during the contest.

24

ICPC — International Collegiate Programming Contest
Asia Regional Contest, Yokohama, 2022–03–16

Problem K
Distributing the Treasure
Time Limit: 4 seconds
You are the leader of a treasure hunting team. Under your great direction, your team has madea big success in a quest, and got a lot of treasure. The only, but crucial, remaining issue is how
to distribute the obtained treasure to the team members.
The excavated treasure includes a variety of precious items: gold ingots, jewelry with brilliant
gem stones, exquisite craft works, etc. Each team member individually estimates the values of
the items. The estimated values are consistent, in that, for any pair of two items, when somemember estimates one to be strictly higher than the other, no member estimates oppositely,
although some may give equal estimates.
All the members are sensible and thus understand the difficulty of even distribution of the items.
Hence, no member will complain simply because, based on the member’s own estimation, thesum of the values of the member’s share is lower than that of another member’s share. The
members, however, may get angry if their own shares look unreasonably shabby compared tosome other member’s; what they cannot stand is when their own shares are estimated strictly
lower than the share of that other member even after getting rid of one item with the least
estimated value.
Your last mission as the leader is to decide who receives which items so that no member gets
angry. Some of the members may receive nothing as long as they do not get angry.

Input
The input consists of a single test case of the following format.
n mv1,1 · · · v1,m..
.
vn,1 · · · vn,m
The first line of the input has two positive integers n and m whose product does not exceed
2 × 105 ; n is the number of members of your treasure hunting team, and m is the number oftreasure items. The members and items are numbered 1 through n and 1 through m, respectively.
The i-th of the following n lines has m positive integers not exceeding 2 × 105 in descendingorder: vi,1 ≥ vi,2 ≥ · · · ≥ vi,m . Here, vi,j is the value of the item j estimated by the member i.

25

Output
If you can distribute the items to the members without making any member angry, output sucha distribution in a line as m positive integers x1 , x2 , . . . , xm separated by spaces. Here, xj = imeans that the member i receives the item j. If two or more such distributions exist, any ofthem shall be deemed correct. If there is no way to distribute the items without making any
member angry, just output 0 in a line.
Sample Input 1

Sample Output 1

2 3
4 2 1
3 3 3

1 2 1

Sample Input 2

Sample Output 2

1 7
64 32 16 8 4 2 1

1 1 1 1 1 1 1

Let Vi (X) denote the sum of the values of items in the set X estimated by the member i.
In Sample 1, V1 ({1, 3}) is 4 + 1 = 5, V1 ({2}) is 2, V2 ({1, 3}) is 3 + 3 = 6, and V2 ({2}) is 3. The
distribution shown as output does not make the member 1 angry as V1 ({1, 3}) ≥ V1 ({2}). The
member 2 does not get angry either even though V2 ({2}) < V2 ({1, 3}) holds. If the member 1
waives one of the two items, the sum of the values of items received by the member 1 would
become V2 ({1}) = 3 or V2 ({3}) = 3, neither of which is higher than V2 ({2}) = 3.
Note that their shares should not be exchanged. Suppose that the member 1 receives {2} and themember 2 receives {1, 3}. This makes the member 1 angry because V1 ({2}) = 2 < 4 = V1 ({1})
holds, meaning that, even if the member 2 waives the item 3, which is estimated to be the lesserof {1, 3}, the value of the sole remaining item 1 is still estimated higher than V1 ({2}) = 2.
In Sample 2, you are the sole member of your team, so you can take them all. Congratulations!

26