Central-European Olympiad in Informatics 2004 - tasks and solutions

POLISH OLYMPIAD IN INFORMATICS POLISH MINISTRY OF NATIONAL EDUCATION AND SPORT UNIVERSITY OF INFORMATION TECHNOLOGY AND MANAGEMENT IN RZESZÓW INSTITUTE OF INFORMATICS, WARSAW UNIVERSITY

The 11th Central European Olympiad in Informatics CEOI 2004 Rzeszów, Poland

Tasks and Solutions Edited by Mar in Kubi a

WARSAW, 2004

POLISH OLYMPIAD IN INFORMATICS POLISH MINISTRY OF NATIONAL EDUCATION AND SPORT UNIVERSITY OF INFORMATION TECHNOLOGY AND MANAGEMENT IN RZESZÓW INSTITUTE OF INFORMATICS, WARSAW UNIVERSITY

The 11th Central European Olympiad in Informatics CEOI 2004 Rzeszów, Poland

Tasks and Solutions Edited by Mar in Kubi a

WARSAW, 2004

Authors: Mi haª Adamaszek Tomasz Czajka Šukasz Kowalik Mar in Kubi a Mar in Mi halski Anna Niewiarowska Paweª Parys Jakub Pawlewi z Jakub Radoszewski Rafaª Rusin Woj ie h Rytter Krzysztof Sikora Piotr Sta« zyk

Proofreaders: Volume editor:



Piotr Chrz¡stowski-Wa htel, Mar in Kubi a Mar in Kubi a

Copyright by Komitet Gªówny Olimpiady Informaty znej O±rodek Eduka ji Informaty znej i Zastosowa« Komputerów ul. Nowogrodzka 73, 02018 Warszawa, Poland

ISBN 8391770060

Contents Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

Journey . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

Clouds. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Sweets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 Trips . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Football league . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 Puzzle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 Two sawmills . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

1

Preface Central European Olympiad in Informati s (CEOI) gathers the best teen-age programmers from several European ountries.

The 11-th CEOI was held at

University of Information Te hnology and Management in Rzeszów, Poland, July 1218, 2004. It was organized by Polish Olympiad in Informati s and University of Information Te hnology and Management in Rzeszów, together with Polish Ministry of National Edu ation and Sport, and Institute of Informati s, Warsaw University. Eight ountries took part in the ompetition: Bosnia and Herzegovina, Croatia, Cze h Republi , Germany, Hungary, Poland, Romania and Slovakia. All of the ountries, ex ept Poland, were represented by 4 ontestants.

Poland was

represented by one o ial team and two additional teams (not ranked o ially), ea h team onsisting of 4 ontestants. More information about this ompetition, in luding the results, an be found at

http://www.oi.edu.pl/ eoi2004.

The ontest onsisted of three sessions: a trial session and two ompetition sessions. During the trial session ontestants had an o

asion to be ome familiar with software environment and to solve a preparation task `Journey'. During ea h of the ompetition sessions they had to solve three tasks within ve hours of time: `Clouds', `Sweets' and `Trips' during the rst session, and `Football league', `Puzzle' and `Two sawmills' during the se ond one.

The time limits

given in the task des riptions refer to Pentium 4, 2.4 GHz ma hines. Four ontestants were awarded gold medals, ve ontestants were awarded silver medals and eight ontestants were awarded bronze medals. The results are as follows:

•

•

Gold medalists:

Luka Kalinov¢i¢

Croatia

Filip Wolski

Poland

Lovro Puzar

Croatia

Bartªomiej Roma«ski

Poland

Silver medalists:

Jakub Š¡ ki

Poland

Alexandru Mosoi

Romania

Erik Panzer

Germany

Thomas Fers h

Germany

Dan-Constantin Spatarel

Romania

Prefa e

4

•

Bronze medalists: Peter Pere²íni

Slovakia

Sorin Stan u-Mara

Romania

Tomasz Kuras

Poland

Gergely Tassy

Hungary

Mir ea Adrian Digules u

Romania

Balázs Kormányos

Hungary

Mi hal Polá£ik

Slovakia

Daniel Marek

Cze h Republi

This booklet presents tasks from CEOI'2004 together with the dis ussion of their solutions. Some more materials, in luding test data used during the evaluation and example solutions, an be found at

http://www.oi.edu.pl/ eoi2004.

It was prepared for the ontestants of various programming ontests to help them in their exer ises. It should also give a taste of oming 17th International Olympiad in Informati s, whi h will be held in Poland, Nowy S¡ z, in 2005. Mar in Kubi a

Task by

Solution description by

Jakub Radoszewski

Tomasz Czajka, Anna Niewiarowska

Available memory: 32 MB.

Maximum running time: 0.5 s.

Journey There are

n

ities in Byteland (numbered from

1

to

n),

onne ted by bidire -

tional roads. The king of Byteland is not very generous, so there are only

n−1

roads, but they onne t the ities in su h a way that it is possible to travel from ea h ity to any other ity.

k . He was planning k and visiting on his way ities m1 , m2 , ..., the numbers mi are all dierent and they

One day, a traveler Byterider arrived in the ity number to make a journey starting in the ity

mj

(not ne essarily in this order) 

are also dierent from

k.

Byterider  like every traveler  has only a limited

amount of money, so he would like to visit all the ities that he has planned to visit using the shortest possible path (starting in the ity

k ).

A path is one

road or a sequen e of roads, where every next road begins in the ity where the previous one ends. Help Byterider to determine the length of the shortest path for his journey.

Task Write a program that:

•

reads from the standard input:



the des ription of the roads onne ting the ities of Byteland,



the number of the ity where Byterider arrived,



a list of ities whi h Byterider would like to visit,

•

determines the minimum length of Byterider's journey,

•

writes the result to the standard output.

Input n and k separated by ≤ n ≤ 50 000, 1 ≤ k ≤ n), n is the number of ities in Byteland

The rst line of the standard input ontains two integers a single spa e (2

and k is the number of the rst ity on Byterider's path. Ea h of the following n − 1 lines ontains the des ription of one road in Byteland. Line (i + 1) (for 1 ≤ i ≤ n − 1) ontains three integers ai , bi and di separated by single spa es (1 ≤ ai , bi ≤ n, 1 ≤ di ≤ 1 000), ai and bi are the ities onne ted by the road, and di is the length of the road. Line (n + 1) ontains one integer j  the number of ities whi h Byterider would like to visit (1 ≤ j ≤ n − 1). The next line ontains j dierent integers mi separated by single spa es  the numbers of the ities that Byterider would like to visit (1 ≤ mi ≤ n, mi 6= k ).

Journey

6

Output The rst and only line of the standard output should ontain exa tly one integer: the length of the shortest path for Byterider's journey.

Example For the input data:

4 1 4 2 2 1

2 2 1 2 2 3 3

1

1

2

2

3

3

4

3

the orre t result is:

5

Solution It an be easily seen that the situation from the task an be onsidered as an

G, in whi h the ities are verti es and the roads are edges. n verti es, n − 1 edges and it is onne ted (there is a path pair of verti es). It an be easily noti ed that the graph G is a

undire ted graph The graph

G

between ea h

has

tree. Let us make the vertex the root of the tree.

k

(whi h represents the ity the traveler starts from)

The verti es

m 1 . . . mj

represent the ities the traveler

wants to visit.

Algorithm The problem an be solved using the following algorithm:

•

Build a graph (tree) data stru ture using adja en y lists.

•

Traverse the tree depth-rst, taking the starting ity

k

as a root. For ea h

subtree re ursively determine:

 

if there are any ities to visit in the subtree at all, length of the shortest path starting and ending in root and visiting the given ities,



length of the shortest path starting (but not ne essarily ending) in the root and visiting the given ities.

Journey

7

These values an easily be ba k-propagated up the tree.

•

The third value in the root is the result.

Proof of orre tness Let us all a

orre t path in a subtree

visits all of the verti es

H = (VH , EH ) ⊆ G {m1 . . . mj } ∩ VH .

 a path in

H

that

In the shortest orre t path we will not use one road more than twi e. To prove it, let us suppose that in the optimal solution we use the road

x

at least

3 times. The path looks like:

a1 . . . an , x, b1 . . . bn , x, c1 . . . cn , x, d1 . . . dn If we hange the path like this:

a1 . . . an , c1 . . . cn , x, b1 . . . bn , d1 . . . dn we will visit the same ities using a shorter path. It follows that the previous path is not optimal. Therefore in the optimal path ea h road will be used no more than twi e. It also means that using the shortest orre t path we will enter ea h subtree no more than on e.

{m1 . . . mj },

If a subtree does not ontain any of the elements

we will not enter that subtree at all.

k k 's

If we want to nd the shortest orre t path in a tree starting in the root and ending also in

hildren

v

k,

we start with an empty path

p

and for ea h of the

we have to repeat the following steps:

•

Che k if we have to enter the subtree with root in

•

If we have to enter that subtree:

 

we add to the path

the edge from

k

to

v,

we re ursively nd the shortest orre t path that begins in ends in



p

v.

v

and we add that path to

we add to the path

p

the edge from

It is easy to he k, that we an hoose

k 's

v

and

p, v

to

k.

hildren in any order and it does

not hange the path's length. Let us suppose that we want to nd the shortest orre t path starting in the root

k

and ending in any vertex. Let us denote by

k1 . . . kl  the hildren of k p and apply the following

whi h we have to visit. We start with an empty path steps:

•

Choose whi h of the verti es that vertex

•

For ea h

k1 . . . kl

should be visited last. Let us all

w.

v ∈ {k1 . . . kl }

su h that

v 6= w:

Journey

8

 

add to the path



•

the edge from

k

to

v,

re ursively nd the shortest orre t path that begins in

v

in

•

p

and add that path to

add to the path

Add to the path

p

p

the edge from

k

the edge from

to

v

to

and ends

k.

w.

Re ursively nd the shortest orre t path that begins in any vertex and add that path to

w

and ends in

p.

As in the previous task, the order of the rst the path's length.

v

p,

l−1

verti es does not hange

The only problem is to nd the vertex

ki

that should be

visited as the last one. But this task an also be solved easily. Suppose that for ea h of

k 's

• lv,1

hildren

v,

if

v

has to be entered, we know the lengths of the paths:

 the length of the path that is the sum of: the edge from

shortest orre t path (in a subtree with a root in ends in

• lv,2

v,

the edge from

v

to

v)

k

to

that begins in

v , the v and

k,

 the length of the path that is the sum of: the edge from

shortest orre t path (in a subtree with a root in

v)

k

to

that begins in

v , the v and

ends in any vertex. We an easily nd the vertex that should be entered as the last one  that is the one with the biggest value of lv,1

− lv,2 .

Knowing the above fa ts, we an modify our algorithm of nding the shortest

orre t path that begins in the root

k

and ends in any vertex in the following

way: For ea h

•

v

being a hild of

k,

we re ursively nd:

whether we have to visit the subtree beginning in visit it, if any of the verti es

•

v

or not (we have to

is in that subtree),

the length of the shortest orre t path in the subtree that begins and ends in

•

m 1 . . . mj

v,

the length of the shortest orre t path in the subtree that begins in

v

and

ends in any node,

•

the values lv,1 and lv,2 .

These values an be easily ba k-propagated up the tree. above information, we an easily hoose:

•

whi h subtrees should be visited,

•

whi h one of them should be visited last,

and so for the subtree with a root in

k

we an nd:

If we know all the

Journey •

9

whether we have to visit that subtree (if we have to visit any of the subtrees with root in

•

hild or if

v ∈ {m1 . . . mj }),

the length of the shortest orre t path in this subtree that begins and ends in

•

v 's

v

(the sum of lvi ,1 for all the hildren

vi

of

k

that should be visited),

the length of the shortest orre t path in the subtree that begins in ends in any node (the previous sum de reased by the last

k 's

hild to be visited).

lw,1 − lw,2 ,

v

where

and

w

is

Task by

Solution description by

Jakub Radoszewski

Šukasz Kowalik, Piotr Sta« zyk

Available memory: 64 MB.

Maximum running time: 3 s.

Clouds There are

n

louds in the sky, all moving ontinuously with a wind in the

same dire tion and with the same onstant velo ity real number

t≥0

v = (vx , vy ),

i.e. for any

and any point of a loud with initial oordinates

position of this point at time

t

is

(x, y)

the

(x + t ∗ vx , y + t ∗ vy ).

For the sake of simpli ity, we assume that every loud is a polygon ( ontaining its periphery), whose verti es have integer oordinates. This polygon does not have to be onvex, but no two of its edges ross ea h other (with ex eption of the ommon endpoints of onse utive edges). The louds may interse t. On the ground there is a satellite ontrol enter, at oordinates

(0, 0),

and

there is a satellite dire tly above the ontrol enter and above the louds. Straight upwards from the ontrol enter to the satellite goes a laser beam. The laser beam is used to ommuni ate with the satellite. However, when the beam

rosses a loud, the ommuni ation is not possible. Initially, the beam does not

ross any loud. During the observation, there may be several moments, when the laser beam rosses (one or more) louds, interrupting the ommuni ation. Even when the laser beam rosses a single vertex of a loud, the ommuni ation is interrupted for an instant. You are to write a program that omputes how many times the ommuni ation is interrupted, until all the louds drift away.

Task Write a program, that:

•

reads from the standard input the positions, shapes and velo ity of the

louds,

•

determines how many times ommuni ation is interrupted,

•

writes the result to the standard output.

Input n, vx and vy , separated by sin1 ≤ n ≤ 1 000, −1 000 000 000 ≤ vx , vy ≤ 1 000 000 000; n is the

louds, v = (vx , vy ) is the velo ity ve tor of the louds (v 6= (0, 0)).

The rst line of input ontains three integers gle spa es, number of

The x- oordinates orrespond to the West-East dire tion and the y- oordinates

orrespond to the North-South dire tion. The following

n

lines ontain des riptions of the louds, one loud per line.

Ea h of these lines onsists of a sequen e of integers, separated by single spa es.

k , 3 ≤ k ≤ 1 000. 2k integers: x1 , y1 , x2 , y2 , . . . xk , yk , −1 000 000 000 ≤ xi , yi ≤ 1 000 000 000; (x1 , y1 ), (x2 , y2 ), . . . (xk , yk ) are the oordinates of the onse utive

The rst integer in a line is the number of loud's verti es It is followed by

verti es in a lo kwise order. The laser beam rosses louds peripheries at most 100 000 times.

Clouds

12

Output The rst and only line of output should ontain exa tly one integer: the number of times the ommuni ation is interrupted.

Example the orre t result is:

For the input data:

4 4 4 3 5

-2 -1 6 2 6 4 8 4 8 2 2 3 1 -1 2 5 4 2 -3 1 -1 2 -1 -1 5 3 3 3 3 5 6 5 6 -1

3

5 4 3 2 1

−3

−2

−1

1

2

3

4

5

6

7

8

−1

The gure shows the louds seen from above. The dashed line marks the points that will ross the laser beam.

Solution The task Clouds is one of many geometri problems in whi h all orre t solutions (abstra ting from implementation) are based on a similar idea. It is easy to see that in order to al ulate how many times ommuni ation is interrupted one has to fo us on points in whi h the laser beam rosses louds' peripheries  these points are important for the problem given, as they are the only pla es where ommuni ation may hange its state. In our task there is a laser beam at position at the velo ity des ribed by ve tor

(vx , vy ).

(0, 0) and a set of louds moving

However we know from physi s that

the motion is relative. Thus there will be no dieren e if we assume that the

Clouds

13

louds stay at their initial positions and the laser beam is moving at the velo ity

(−vx , −vy ).

The latter formulation is more onvenient and it will be used in

the sequel. Let us draw a semi-line with the end in point

(0, 0) representing the

tra k of the laser beam in time (see Fig. 1).

5

3

4

2 3

4

2 1

1 -3

-2

-1

1

2

3

4

5

6

7

8

-1

Figure 1: Semi-line for the sample input data.

The interse tion of ea h loud with the semi-line is a set of segments of the

segments of length 0 ). For example in Fig. 1 the interse tion of the loud number 2 with semi-line (there may be single points as well but we will treat them as

the semi-line onsists of two segments, one of length 0. Ea h segment represents a time interval when the ommuni ation is broken.

In the rst phase of our

solution we ompute the segments for ea h loud separately. Subsequently we

onsider the union of the segments omputed for all the louds. Clearly in the union some segments of dierent louds may glue together reating a single segment (see louds 3 and 4 in Fig. 1). Our goal is to ompute the number of segments in the union. As an example, for the sample input data there are:

•

two segments for loud number 2, one of whi h is of length 0,

•

one segment for loud 3,

•

one segment for loud 4.

The answer in this ase is 3, as in the union there are 3 segments. Now let us move to the implementation details for the above algorithm.

Phase One: Computing Segments for Ea h Cloud Clearly one needs to nd all interse tion points between the semi-line and the

loud's periphery. To this end one has to examine every edge of the loud and

Clouds

14

ompute the point of interse tion if it exists. This part is performed in time for a

k -vertex

O(k)

loud.

However, even if the algorithm nds all interse tion points in order of o

urren e on the perimeter it is not possible to determine all segments for that

loud out of hand, as louds are of arbitrary shape (ex luding self-interse tions). To ope with that problem we represent ea h interse tion point by its distan e from the point

(0, 0).

Then we sort the interse tion points and subsequently

group them into pairs. Ea h pair orresponds to one segment (re all that no single loud overs laser beam at the very beginning). Unfortunately, the above des ription is not omplete.

It works properly

unless the semi-line ontains a vertex of some loud. We annot ex lude su h a situation. Therefore we have to onsider a set of nasty spe ial ases listed in Figure 2.

A

B

C

D

E

F

Figure 2: A olle tion of nasty ases to onsider

Two last spe ial ases an be solved straightforward by adding point the third ase and point

F

E

for

twi e for the last ase. Observe that this will work

no matter on whi h side is the interior of the loud. First two ases are harder.

type. All standard points. In the rst two

ases we will also use points marked as segment points, as follows:

To ope with them ea h interse tion point will store additionally its points added in the last two ases are alled

•

The rst ase  add point

A twi e: B

a segment point. Then add point

•

The se ond ase  add points

C

on e as a standard point and then as as a segment point.

and

D

as segment points.

When the set of interse tion points for a given loud is generated, we sort the points (leaving the points with the same oordinates in the same order). In the model program we use built-in qui k-sort routine. Then the segments an be

omputed.

We examine subsequent points in the sorted sequen e.

Standard

points in the sequen e represent left and right ends of the segments, alternately. Observe that segment points appear in pairs in the sorted sequen e. When we nd su h pair

X, Y

we look at the most re ent standard point. If it turns out

Clouds

15

to be a left end of a segment, the pair

X, Y

is ignored. Otherwise (also when

there was no previous standard point) we add segment

[X, Y ].

Clearly, the total time needed to pro ess one loud is dominated by sorting.

k -vertex loud that O(k + q log q) time.

Thus the segments for a points are omputed in

interse t with the semi-line in

q

Phase Two: Computing the Number of Communi ation Interruptions As it has been mentioned before all we need to do to obtain the result is to pi k segments omputed for all louds and ompute the number of segments in their union.

In order to do this we sort the segments a

ording to their left ends.

Subsequently we examine su

essive segments.

If the pro essed segment has

its left end farther than all ends of already pro essed intervals we in rease the answer by one (the left end of su h an interval does not interse t with previous ones and represents the left end of some segment of the union). The total time omplexity is verti es in all louds and

p

O(m + p log p),

where

m

is the total number

is the total number of interse tions.

A Hidden Cat h This solution ontains a hidden at h. As mentioned before, the algorithm sorts points, what requires omparing their oordinates. In some ases the distan e between dierent interse tions is so small, that even the

long double

type is

not pre ise enough. To solve this problem, one has to represent point's lo ation as a fra tion of two 64-bit integers. To ompare points' lo ations, it is needed to al ulate multipli ation of two 64-bit values.

Task by

Solution description by

Mar in Mi halski, Anna Niewiarowska

Šukasz Kowalik, Jakub Pawlewi z

Available memory: 64 MB.

Maximum running time: 0.1 s.

Sweets John has got

n

jars with andies. Ea h of the jars ontains a dierent kind of

andies (i.e. andies from the same jar are of the same kind, and andies from dierent jars are of dierent kinds). The i-th jar ontains

mi

andies. John has

de ided to eat some of his andies. He would like to eat at least no more than

b.

a

of them but

The problem is that John an't de ide how many andies and

of what kinds he would like to eat. In how many ways an he do it?

Task Your task is to write a program that:

•

reads from the standard input the amount of andies in ea h of the jars, and integers

•

a

and

b,

determines the number of ways John an hoose the andies he will eat (satisfying the above onditions),

•

writes the result to the standard output

Input n, a and b, separated by single ≤ n ≤ 10, 0 ≤ a ≤ b ≤ 10 000 000). Ea h of the following n lines

ontains one integer. Line i + 1 ontains integer mi  the amount of andies in the i-th jar (0 ≤ mi ≤ 1 000 000).

The rst line of input ontains three integers: spa es (1

Output Let

k

be the number of dierent ways John an hoose the andies to be eaten.

The rst and only line of output should ontain one integer: the remainder of

k

k

mod 2004 (i.e.

divided by 2004).

Example For the input data:

2 1 3 3 5

the orre t result is:

9

John an hoose andies in the following ways:

(1, 0), (2, 0), (3, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (2, 1)

Sweets

18

Solution First, let us restate the problem using more onvenient ombinatorial terms. We

r identi al obje ts n distin t ontainers so that the i-th ontainer has at most mi obje ts, for all i = 1, . . . , n. Let us denote this value by C(r). Finding solution requires

omputing C(b) − C(a − 1) or just C(b) if a = 0. have to determine the number of ways to distribute at most into

Let us re all base ombinatorial fa ts about distribution of identi al obje ts into distin t ontainers without restri tions.

Proposition 1:

The number
of distributions of r+n−1 tin t ontainers equals n−1 .

Proof:

The number of ways

r

r identi al obje ts into n dis-

obje ts an be distributed among

n

ontainers

orresponds to the number of ways to arrange r obje ts and n − 1 bars, whi h
r+n−1 amounts to n−1 . Bars divide obje ts into n groups. Ea h onse utive group is a ontainer. 

Proposition 2:

The number of
distributions of at most r+n n .

r identi al obje ts into

n distin t ontainers equals

Proof: into

n

It immediately follows from Proposition 1. Putting at most

ontainers orresponds to putting exa tly

r

obje ts into

n+1

r

obje ts

ontainers.

Additional ontainer olle ts obje ts whi h are not distributed among the rst

n

Let

U

be the set of all distributions of at most

without restri tions. Let to



ontainers.

n

Ai

r

obje ts to

n

ontainers

r obje ts mi obje ts.

be a set of all distributions of at most

ontainers su h that the

i-th

ontainer ontains more than

Ai is a set of all distributions of r i-th ontainer ontains no more than mi |A1 ∩ . . . ∩ An |. Thus

obje ts to

n

ontainers for whi h the

obje ts. Thus the sear hed number is

We determine this value using the In lusion-Ex lusion Prin iple:

|A1 ∩ . . . ∩ An | =

|U | − |A1 | − . . . − |An | + |A1 ∩ A2 | + . . . +|An−1 ∩ An | − . . . + (−1)n |A1 ∩ . . . ∩ An |

(1)

We will nd the value of |Ai1 ∩ . . . ∩ Aik | for given {i1 , . . . , ik } ⊆ {1, . . . , n}. Ai1 ∩ . . . ∩ Aik is a set of distributions of r obje ts to n ontainers su h that for every j ∈ {i1 , . . . , ik }, j -th ontainer ontains more than mj obje ts. Let us see how we an build su h distribution. First we put mj + 1 obje ts to the j -th ontainer for every j ∈ {i1 , . . . , ik }. Then we distribute the remaining obje ts to all n ontainers. From Proposition 2 follows that we an do it in


r−(mi1 +1)−...−(mik +1)+n n

ways. Hen e

  r − (mi1 + 1) − . . . − (mik + 1) + n |Ai1 ∩ . . . ∩ Aik | = . n

(2)

Sweets

19

Using (1) and (2) we an write the nal result in a single formula:

S(r) =

X

(−1)|I|

I⊆{1,...,n}

P   r − i∈I (mi + 1) + n . n

(3)

Binomial Coe ients The main di ulty we have to fa e during implementation is to ompute the values of binomial oe ients modulo 2004. There are several methods to ope with that, varying in simpli ity and time omplexity.

Pas al's Triangle We an take advantage of the widely-known re urren e leading to the Pas al's Triangle:

   p = q


1 +

p−1 q




p = 0 or q = 0, p, q > 0.
p values of n mod 2004

for

p−1 q−1

for

for p ≤ b − (m +1)+n using simple dynami programming. Then the stored numbers i i∈I

an be used to ompute S(r). This prepro essing uses an array of at most b + n Using this re urren e we an ompute all

P

integers whi h is quite mu h but still within the given limit. However the time

omplexity of the prepro essing is

omputing n

S(b) and S(a − 1).

O(bn)

whi h dominates the time needed for

The total time omplexity of the solution is then

O(bn + 2 ).

A Smarter Re urren e p Let us now present an approa h similar to binary exponentiation. To get q


p p p we al ulate values i for all i = 0, . . . , q . For p = 1 we have 0 = 1 = 1 and the other values are 0. For p > 1 we use the following formula:





  ( p−1
+ p−1 p i i−1

Pi = p/2 p/2 i j=0 j i−j

p, even p.

for odd for

p 2 q in time O(q log p) using only addition and multipli ation operations. The running time omplexity n 2 is O(2 n log b) and the spa e omplexity is O(n). Hen e we may ompute the value of a binomial oe ient




One More Approa h Finally we an take advantage of the following widely-known formula

p q




=

pq q q! , where p = p · (p − 1) · . . . · (p − q + 1). Unfortunately the value in the numerator of the above expression an be very large. One way to get rid of that obsta le is to implement big integer arithmeti (i.e. addition and subtra tion of big numbers and also multipli ation and division of a big number by a small number).

However this method ignores the useful fa t we are interested in

results modulo 2004. Then one an pro eed as follows.

Sweets

20

1. Compute the prime fa torization of

q!.

As

q = n ≤ 10, the ontestants q = 1, 2, . . . 10 and ode

an even nd the fa torization by hand for ea h it in their sour e les as a onstant array. 2. Prepare an array

A[1..q ℄ ontaining initially numbers p, p−1, p−2, . . . , p−

q + 1. 3. Next we take su

essive prime fa tors. For ea h su h fa tor we repeat the following step by

p,

divide it by

p

times: nd the rst number

and store the result in

4. Compute the produ t

int

k

A[i℄.

A[1℄·A[2℄· . . . ·A[q ℄ mod 2004.

p

of order

A[i℄

k

divisible

Clearly, to stay in

range it su es to ompute the remainder of division by 2004 after
p ea h multipli ation. The result is equal to q mod 2004.

p 2 q using the above method takes O(q n 2 that the total time omplexity is then O(2 n log n). Computing




log q)

time.

It follows

Alternative Solution: Re ursion and Dynami Programming Let

ck (r)

denote the number of distributions of exa tly

r

obje ts to the rst

k

ontainers. The following re urren e holds:

c0 (r) = [r = 0], ck (r) =

mk X

ck−1 (r − i)

i=0

Using the above equations and dynami programming we get an algorithm with the running time omplexity O(bM ) and the spa e omplexity O(b), where P M = ni=1 mi . We an speed up al ulations of ck by preparing partial sums of ck−1 . Let Pr Ck−1 (r) = i=0 ck−1 (i), then ck (r) = Ck−1 (r) − Ck−1 (r − mk − 1). Of ourse

Ck−1 (r − mk − 1) = 0 O(bn).

omplexity

if

r − mk − 1 < 0 .

This solution has the running time

Task by

Solution description by

Krzysztof Sikora

Mar in Mi halski, Anna Niewiarowska

Available memory: 64 MB.

Maximum running time: 3 s.

Trips In the forth oming holiday season, a lot of people would like to go for an unforgettable travel.

To mostly enjoy their journey, everyone wants to go with

a group of friends. A travel agen y oers several trips. A travel agen y oers group trips, but for ea h trip, the size of the group is limited: the minimum and maximum number of persons are given. Every group an hoose only one trip. Moreover, ea h trip an be hosen by only one group. The travel agen y has asked you for help. They would like to organize as many trips as possible. Your task is to mat h groups of people and trips in su h a way, that the maximum number of trips an be organized.

Task Write a program, that:

•

reads the des ription of the groups and the trips from the standard input,

•

mat hes the groups and trips in su h a way, that the maximum number of arranged trips is rea hed,

•

writes the result to standard output.

If there are several possible solutions, your program should output anyone of them.

Input n and m separated by single spa e, m is the numbered from 1 to n, and the trips are

The rst line of input ontains two integers:

1 ≤ n ≤ 400000, 1 ≤ m ≤ 400000; n number of trips.

The groups are

numbered from 1 to The following

is the number of groups and

m.

n

lines ontain group sizes, one per line. Line 9 integer si  the size of the i-th group, 1 ≤ si ≤ 10 . The following

i+1

ontains

m lines ontain trip des riptions, one trip per line. Line n+j+1 lj and uj , separated by single spa e. lj is the minimum,

ontains two integers:

uj is the maximum 1 ≤ lj ≤ uj ≤ 109 .

and

size of a group for whi h the trip an be arranged,

Output The rst line of output should ontain one integer number of trips that an be arranged. the des ription of the mat hing.

k ≥ 0  the maximum k lines should ontain

The following

Ea h of these lines should ontain a pair of

integers separated by single spa e: the number of a group and the number of a trip. There an be many answers and your program may print anyone of them.

Trips

22

Example For the input data:

the orre t result is:

5 4 54 6 9 42 15 6 6 20 50 2 8 7 20

3 2 1 3 4 4 2

Solution

Maximal mat hing in a bipartite graph Our problem an be easily redu ed to a problem alled

bipartite graph in the graph theory. In a graph a subset of

E

maximal mat hing in a

G = (V, E)

su h that no two dierent edges belonging to

a mat hing

M

M

is

have a vertex

in ommon. The problem is to nd a mat hing that onsists of the maximum number of elements. In our problem we have a bipartite graph

W is w ∈ W are

E

G = (V, W, E),

of groups,

the set of trips and

and

onne ted with an edge if the group

w.

where

V

is the set

is the set of edges. Two verti es

v

v∈V

an be sent to the trip

It means:

(i, j) ∈ E ⇔ i ∈ V ∧ j ∈ W ∧ lj ≤ si ≤ uj M in that graph represents an assignment of some groups with (v, w) ∈ M then the group v will be sent to the trip w. Ea h mat hing

A mat hing trips. If

in the graph represents a orre t assignment of the trips with the groups. The denition of a mat hing guarantees that one trip will be assigned to at most one group of people and one group of people will not go to more than one trip. Our task is to hoose a maximal mat hing

P

in the graph  su h

P ⊆E

that

∀(i,j)∈P ∀(a,b)∈P ((i, j) = (a, b) ∨ (i 6= a ∧ j 6= b)) and

|P |

is the greatest possible.

A problem of nding a maximal mat hing in a bipartite graph an be solved with many well known algorithms su h as the Hop roft-Karp algorithm. However, these algorithms are too slow for our task (and too ompli ated for su h

ompetition as CEOI). They do not use one interesting property of onsidered graphs: the set E is onvex, i.e.: ∀(i,j),(k,j)∈E (i + 1, j), . . . , (k − 1, j) this property, the problem an be solved in a greedy way.

∈ E.

Using

Trips

23

Greedy algorithm Our problem an be solved by a greedy algorithm. Below there is a des ription of the algorithm: 1. Sort groups by size in the as ending order. 2. For ea h group i: (a) nd su h a trip minimal (where

j si

uj ≥ si ≥ lj and uj is i-th group, lj - the maximum size of the j -th

whi h is still not used,

- the number of people in the

j -th

minimum size of the

group,

uj

- the

group), (b) if su h a trip exists then send the

i-th

group on this trip (it means

that this trip is now used) and in rease the number of trips. 3. Print the result and all mat hed pairs.

Proof of orre tness After mat hing a group to a trip we remove the trip from the trip list. Let us

k − 1 groups optimally and now we k -th group. Let us presume that we an send the k -th group on trips a1 , a2 , . . . , ap (it means that those trips haven't been hosen earlier) and that ua1 ≤ ua2 ≤ . . . ≤ uap . As we mat hed previous k − 1 groups optimally there is at least one optimal solution S . I am going to prove that there is an optimal solution in whi h the k -th group is send on trip a1 and all previous groups are mat hed as before.

say that we have already mat hed previous are going to do so for the

There are three possibilities: 1. in the solution

S

the

k -th

group is send on the trip

a1 ,

2. in the solution

S

the

k -th

group is send on the trip

ax

3. in the solution

S

the

k -th

group is not mat hed.

and

x 6= 1,

If the rst ondition is met then it is perfe t and we have an optimal solution with the mat hing we wanted. If the

k -th

group is not mat hed then the trip

wise we ould simply send the

k -th

a1

must be mat hed. (Other-

group on the trip

better solution). Let us presume that in the solution with a group trip

a1

z.

Of ourse the group

z

a1 and we would have a S the trip a1 is mat hed

has not been pro essed yet be ause the

would have been deleted before (as we delete trips after using them).

So if we mat h the

k -th

group with the trip

a1

and

z

with nothing, we will still

have an optimal solution (the number of mat hings stays un hanged). The last possibility is that the

x 6= 1. •

There are two ases:

the trip

a1

is not mat hed,

k -th

group is mat hed with the trip

ax

and

Trips

24

•

the trip

a1

is mat hed with a group

z

and the group

z

has not been

pro essed yet. If the trip

a1

a1

is not mat hed, we simply  hange mat hing from the trip

as that will not hange the number of mat hings. If

and

z

a1

ax

to

z

is mat hed with

has not been pro essed yet, then we an swap these two mat hings. It

means we mat h the be ause if

k

k -th

a1 and the group z z with ax then

group with

is mat hed with

a1

and

with

ax .

We an do it

la1 ≤ sk ≤ ua1 lax ≤ sz ≤ uax But from the denition of

ax

a1

and

we have

lax , la1 ≤ sk and

ua1 ≤ uax And so we have:

la1 , lax ≤ sk ≤ sz ≤ ua1 ≤ uax So we an mat h

k

with

a1

and

z

with

ax .

And this also does not de rease the

number of mat hings. We managed to prove that if our algorithm optimally mat hed rst groups it will mat h optimally the

k -th

k−1

group. By the mathemati al indu tion,

presuming that the mat hing of zero groups is optimal, the above algorithm generates a orre t answer.

Implementation:

The solution uses a heap

H

to keep all the possible trips

for the urrent group. If the group is hanged, some trips are added and others are removed. In the root of the heap there is always a trip with the smallest

ui

from all the trips that are in the heap. The algorithm onsists of the following steps:

•

Sort the groups in the as ending order of

•

Sort the trips in the as ending order of lj .

•

For ea h group



i

si .

(taking the groups in the as ending order of

add to the heap

H

si ):

all the trips, that have not been added before

and that have minimal demands (lj ) not bigger than the size of the

urrent group,



take from the heap

H

all the groups that have the maximal demands

(uj ) smaller that the size of the urrent group,



take from the heap the group with the minimal

uj

(if the heap is not

empty now) - this is the orre t mat hing for the group i. The time omplexity is

Θ(n + m).

Θ(nlogn) + Θ(n + mlogm),

and the memory ost is

Task by

Solution description by

Jakub Pawlewi z, Paweª Parys

Jakub Radoszewski

Available memory: 32 MB.

Maximum running time: 3 s.

Football league There are

n

teams in a football league (we assume that

n

is even). During a

season ea h team plays with every other team exa tly on e. The season onsists of

n−1

turns. Every team plays exa tly on e during a turn. It is desired for a

team to play onse utive mat hes on dierent stadia: one at home stadium, and one away, et . Unfortunately it is not always possible to onstru t su h a game s hedule that no team plays twi e in a row at home stadium, or twi e in a row away. When onstru ting the s hedule the number of su h situations should be minimized. (For example, if a team plays on e away, then four times at home stadium and then on e away, it ounts as three su h situations.) Your task is to minimize the number of situations in whi h a team plays twi e in a row at home or away and to onstru t su h game s hedule for the whole season. The s hedule should onsist of n − 1 turns. Ea h turn onsists of n(n−1) n mat hes in 2 mat hes  ea h team plays exa tly one mat h. There are 2 the whole season, and every two teams should play exa tly one mat h against ea h other.

Ea h mat h is played at one of the opponents' stadium  one

team plays at home stadium and the other one plays away. The total number of situations in whi h a team plays two onse utive mat hes at home or away should be minimal.

Task Write a program, that:

• •

reads the number of teams from the standard input,

omputes the minimum total number of situations in whi h a team plays twi e in a row at home or away and onstru ts the game s hedule,

•

writes the result to standard output.

Input The rst and only line of the standard input ontains one even integer

n ≤ 1000)

n (2 ≤

 the number of teams.

Output The rst line of the standard output should ontain a single integer  the minimum total number of situations in whi h a team plays twi e in a row at home or away. The following line

k+1

n−1

lines should ontain a game s hedule: the

should ontain the des ription of the

{1, 2, . . . , n}

n

k -th

turn.

dierent numbers d1 , d2 , . . . , dn from n separated by single spa es. For i = 1, 2, . . . , 2 the pair d2i−1 , d2i

The des ription of a turn onsists of

Football league

26

denotes a mat h between teams team

d2i

d2i−1

and

d2i .

Team

d2i−1

plays at home and

plays away.

Example For the input data:

the orre t result is:

4

2 1 4 2 3 1 2 4 3 2 4 3 1

Solution To des ribe the optimal solution we need to prove a few lemmas rst.

Lower bound Lemma 1:

The lower bound of the number of situations when a team plays twi e in a row at home or away is n − 2, where n is the number of teams.

Proof:

Let us assume (without losing the generality) that in the rst turn 1,. . . , n2 play at home (and teams n2 + 1,. . . ,n play n away). When any two of teams 1,. . . , 2 have to play together, then one of them has to play twi e in a row at home or away (be ause all of those teams are in of the game s hedule teams

the same phase of playing at home and away in the beginning, so if none of the teams would hange its phase, then it would not be possible for any two teams to play together without hanges of phase  meaning teams playing alternately at home and away in the whole league). Let us assume that this team whi h n plays two onse utive mat hes at home or away, has number 2 . (It is worth noti ing, that when this team a tually hanges its phase, it an play with all n the teams 1,. . . , − 1, if they have not hanged their phases earlier.) 2 n This argumentation an be repeated for teams 1,. . . , − 1, as they also have 2 to play all possible mat hes with ea h other. More pre isely, ea h of the teams 2, . . . , n2 − 1 has to hange its phase at least on e in order to be able to play mat hes with all the teams with numbers lower than its. So there have to be at n least 2 − 1 situations, when a team plays two onse utive mat hes at home or away.

n The whole above argumentation an be repeated for teams 2 + 1, . . . , n (as they played away in the rst turn and their situation is symmetri to the n situation analyzed above), getting another −1 previously mentioned situations. 2 So, the total number of su h situations, when a team plays two mat hes at home or away in a row is at least

n − 2.



Applying lemma 1, we get a lower bound of situations when a team plays two

onse utive mat hes at home or away.

In fa t, the onstru tion of a game

s hedule where the number of su h situations is equal to

n− 2 is always possible.

Football league

27

At rst su h a onstru tion will be des ribed, and then we prove that it meets all the onditions of orre t game s hedule, and that it generates exa tly

n−2

oni ts.

The onstru tion For onvenien e we will number turns and teams from 0 (so the last team has

n − 1, and the last turn has number n − 2). Then we dene fun tions pk : {0, . . . , n − 2} 7→ {0, . . . , n − 1} for k = 0, . . . , n − 2. Let i ∈ {0, . . . , n − 2}. Let j ∈ {0, . . . , n − 2} be su h that i + j ≡ k (mod n − 1). Then if i 6= j , then we set pk (i) = j , and when i = j , we set pk (i) = n − 1. k+1 Now we an show how the k -th turn looks like. Let l = ⌊ k is 2 ⌋. When

even, then in k -th turn we arrange pairs: l, p (l) , l + 1, p (l + 1) , . . . , l+ k k

n n − 1, p (l + − 1) . When k is odd, we arrange pairs: p (l), l , p (l + 1), l+ k k k 2
2
1 , . . . , pk (l + n2 − 1), l + n2 − 1 . Below it is proved, that the above onstru tion

number

meets all the expe ted onditions.

The orre tness and optimality of the onstru tion

Lemma 2: For the above onstru tion, every team from on e (so every single turn of the s hedule is orre t). Proof:

For onvenien e, let us onsider ases when

k

0 to n−1 plays exa tly is even and

k

is odd

separately: 1. If k is even, then there exists an integer m su h that k = ⌊ 2m+1 2 ⌋ = m. In this ase, the pairs that we onstru t are:

2m.

So,

l =




n n m, pk (m) , m + 1, pk (m + 1) , . . . , m + − 1, pk (m + − 1) 2 2

If we use the denition of

pk

to ount its value, we get a pre ise represen-

tation of these pairs:




m, n − 1 , m + 1, (m − 1) mod (n − 1) , m + 2, (m − 2) mod (n − 1) , . . . , m+


n n − 1, (m − + 1) mod (n − 1) 2 2

where mod is an operation of taking the remainder in the integer division

n − 1, whi h is always of the range between 0 and n − 2. The numbers m − n2 + 1, . . . , m − 1, m, . . . , m + n2 − 1 are onse utive n − 1 integers, so every one of them gives a dierent remainder when divided by n− 1, hen e they represent every team between 0 and n−2. As team (n−1)-th appears

by

exa tly on e in this list, every team appears exa tly on e in this list of pairs n k n n−2 n (it is true be ause, as k ≤ n−2, m+ 2 −1 = 2 + 2 −1 ≤ 2 + 2 −1 = n−2, so none of the teams on the rst positions in the pairs will be n − 1, and of ourse none of the teams appearing on the se ond position in the pairs apart from the rst pair may be

n − 1).

Football league

28

k is odd, then there exists su h an integer m, that k = 2m + 1. Hen e, l = ⌊ 2m+2 2 ⌋ = m + 1. In this ase, the pairs that we onstru t are:

n n
pk (m + 1), m + 1 , pk (m + 2), m + 2 , . . . , pk (m + ), m + 2 2

2. If

If we use the denition of

pk

to ount its value, we similarly, like above

get a pre ise representation of these pairs:



m, m + 1 , (m − 1) mod (n − 1), m + 2 , . . . ,


n n n
) mod (n − 1), m + − 1 , n − 1, m + 2 2 2 n n n n (as m − + 1 = m + − (n − 1), so m − + 1 ≡ m + mod (n − 1)  and 2 2 2 2 that is why we get n − 1 in the last pair). Similarly like in the previous

ase, in this list of pairs all the team numbers between 0 and n − 2 appear n exa tly on e, and be ause k = 2m + 1 ≤ n − 2, m ≤ 2 − 2 (as n is always n even), m + 2 ≤ n − 2, the team number n − 1 appears also exa tly on e, (m −

and that ompletes the proof of the lemma in this ase.



Lemma 3:

When we take the whole game s hedule into onsideration, every pair of teams plays exa tly on e (so the whole s hedule is orre t).

Proof:

i ∈ {0, . . . , n − 2}. The opponents of i-th team will be teams with jk , that i + jk ≡ k (mod n − 1) (when su h jk is equal to i, the opponent of i will be of ourse n − 1)  it is true, be ause i plays in every round exa tly on e (we get it applying lemma 2). So, these numbers jk will be: (−i) mod (n − 1), (−i + 1) mod (n − 1), . . . , (−i + n − 2) mod (n − 1). The numbers −i, −i+1, . . . , −i+n−2 are n−1 onse utive integers, so after ounting the values of the appropriate remainders, we get every number between 0 and n − 2 exa tly on e. Of ourse, the number i will appear here be ause of that, and so in the pla e of its appearan e the team n − 1 will be the opponent of i-th team, so every (other than i-th) team will appear exa tly on e in the list p0 (i), . . . , pn−2 (i). From this part of proof we an dedu e, that the team number n − 1 will also play with all the teams between 0 and n − 2 exa tly on e in the s hedule. It is true, be ause for every i ∈ {0, . . . , n − 2} there exists su h a round number, that in this round i-th team plays with team (n − 1)-th, and  applying lemma 2  the team (n − 1) plays exa tly on e in every round, so this implies that the mat hes of the team n − 1 also satisfy the thesis of lemma 3. This ompletes the proof of lemma 3.  Let

su h numbers

From lemmas 2 and 3 we dedu e, that the game s hedule onstru ted is orre t. In the nal theorem we will prove, that it is also optimal.

Theorem 1: The game s hedule onstru ted above is optimal, meaning that the number of situations, when a team plays twi e at home or away, is equal to the lower bound from lemma 1, that is n − 2.

Football league Proof:

29

In this proof, similarly to the proof of lemma 2, we will rstly onsider

ases when we move from a turn with an even number to a turn with an odd number and se ondly the remaining ones: 1. If we onsider turns

k -th

and

(k + 1)-th

where

k

is even, using the reprek m
= 2 ) we get

sentation of the pairs des ribed in lemma 2's proof (with


k -th turn pairs: m, n − 1 , m + 1, (m − 1) mod (n − 1)
, m + 2, (m −
n 2) mod (n − 1) , . . . , m + 2 −
1, (m − n2 + 1) mod (n − 1) ,
and for the (k + 1)-th turn pairs: m, m
+ 1 , (m − 1) mod
(n − 1), m + 2 , . . . , (m − n n n ) mod (n − 1), m + − 1 , n − 1, m + 2 2 2 . Now, we an easily noti e, that only the team number m plays here twi e in a row at home, and the n team number m + 2 plays twi e in a row away (as  what was already n n (mod n − 1)), with all the other teams mentioned  m − 2 + 1 ≡ m + 2 for

not hanging their phases. So, every su h hange of turns gives two teams n

hanging their phases, and there are exa tly 2 − 1 su h hanges, what n gives 2 · ( − 1) = n − 2 situations we onsider. 2

k is odd, again using k m = ⌊

2 ⌋); for kn-th turn we have pairs: m, m+1 , (m−1) mod (n−1), m+2 , . . . , (m− 2 ) mod (n−

n n 1), 1, n−
m+ 2 − 1 , n− 1, m+
2 , and for the (k + 1)-th turn
pairs: m+ n 1 , m + 2, m mod
(n − 1) , m + 3, (m − 1) mod (n − 1) , . . . , m + 2 , (m − n 2 +2) mod (n−1) . If we onsider the rst teams in the se ond set of pairs

2. Now let us onsider turns

k -th

and

(k + 1)-th

where

the representation from lemma 2's proof (with

and the se ond teams in the rst set of pairs we easily noti e, that these sets of teams are the same, what implies that all the teams maintain their phases in playing at home and away, so there are no previously mentioned

oni ts. After onsidering both ases we get, that there are exa tly

n−2

situations

when a team plays twi e at home or away in a row, and that proves the thesis



of theorem 1. The orre t and optimal solution of the task, has time omplexity 2 size of the output is O(n )) and requires onstant memory.

O(n2 )

(the

Task by

Solution description by

Rafaª Rusin, Anna Niewiarowska

Šukasz Kowalik, Mar in Mi halski

Available memory: 32 MB.

Maximum running time: 0.3 s.

Puzzle The king of Byteland has re eived a gift, a jigsaw puzzle. The puzzle onsists of

n×n. The eld in the i-th row and j -th olumn (1 ≤ i, j ≤ n) has (i, j) and ontains a pie e with the number p(i, j), 1 ≤ p(i, j) ≤ n2 . 2 numbers 1 . . . n appears on exa tly one of the pie es. To solve the

a board of size

oordinates Ea h of the

1 1

...

j

...

n

p(1,1)

... i

p(i,j)

... n

Figure 3: Coordinates of the elds puzzle, you have to put the pie es in order, so that for ea h eld

(i, j)

ontains the pie e with number

1 ≤ i, j ≤ n

the

j + (i − 1) · n.

The following moves are allowed to solve the puzzle:

•

a y li shift of all pie es in a row a ertain number of elds to the right,

•

a y li shift of all pie es in a olumn a ertain number of elds down.

The king of Byteland managed to solve his puzzle, but he is not sure if he would be able to solve it starting from a dierent initial onguration.

Help

him to solve this problem.

Task Write a program that:

•

Reads from the standard input the des ription of the initial onguration of the puzzle.

•

Finds out if the pie es on the board an be put in order using only the moves given above. If the solution is possible, the program should nd the moves putting the pie es in order.

•

Writes the result to the standard output.

Puzzle

32

Input In the rst line of the standard input there is one integer board side (2

≤ n ≤ 200).

The following

initial onguration. The line

i+1

n

n

 the size of the

lines ontain the des ription of the

n

ontains

p(i, 1), p(i, 2), . . . p(i, n)

integers

separated by single spa es.

Output If there is no solution, the program should write to the standard output only one line ontaining only one word

NO.

If a solution exists, the rst line should ontain one integer

m  the number

of moves leading to the solution of the puzzle. The number of moves in your solution must not ex eed

400 000.

The following

m

lines should ontain the

des riptions of the moves, one move per line. Ea h su h line should onsist of a letter

or

C

R

(for shifting a row to the right)

k and l separated 1 ≤ k ≤ n, 1 ≤ l ≤ n − 1. A line ontaining R k l des ribes a y li the k -th row l elds to the right. Su h a move leads to the following

(for shifting a olumn down), a spa e, and two integers:

by a spa e; shift of

board onguration:

′

p (i, j) =

(

Similarly, a line ontaining

p(i, j + n − l) p(i, j − l) p(i, j)

Ck l

if if if

i=k i=k i 6= k

and and

j≤l j>l

des ribes a y li shift of the

k -th

olumn

l

elds down. If there are several possible solutions, your program should output anyone of them.

Example For the input data:

the orre t result is:

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

2 C 2 1 R 1 3

The above sequen e of moves gives the following sequen e of ongurations: 4 5 9 13

6 10 14 1

2 7 11 15

3 8 12 16

4 5 9 13

1 6 10 14

2 7 11 15

3 8 12 16

1 5 9 13

2 6 10 14

3 7 11 15

4 8 12 16

Puzzle

33

Solution The puzzle des ribed in the task seems to be similar to the Rubik's ube. Indeed, the approa h we are going to present an be used also for solving the Rubik's

ube. It onsists of two phases: 1. put appropriate pie es in all rows but the last one, 2. rearrange the last row.

First phase In this phase we put su

essive pie es assume that we already moved pie es fo us on the pie e number

k

1, 2, . . . , n2 − n on proper elds. Let us 1, 2, . . . , k − 1 to proper elds. Now we

and we want to pla e it in the proper eld in su h

a way that the pre eding pie es stay at their positions. There are four possible

ases:

•

the pie e is already on the proper eld,

•

the pie e is in the proper row,

•

the pie e is in the proper olumn,

•

the pie e is somewhere else.

In the rst ase nothing should be done. If the pie e is in the proper row we pro eed as in Figure 4. Note that after the four shifts shown in the gure only three pie es hange their positions:

j, k

and

m.

If the pie e is in the proper

olumn we pro eed similarly  again four shifts are su ient.

a

a j

k m

j

k

k

m

j

m

k j

a

a m

k

m j

a

Figure 4: Four shifts to move the pie e

k

to the proper (gray) eld, provided

that it was already in the proper row.

Finally, if the pie e stays in improper row and olumn we pro eed as in Figure 5.

Note again that after the four shifts shown in the gure only two

pie es hange their positions:

j

and

k.

It ends the des ription of the rst phase.

Se ond Phase Before we show how to rearrange pie es in the last row let us think a bit on the problem raised by the king of Byteland  is there puzzle?

always a way to solve the

Puzzle

34

b

b

b

j

k

k

b k

j

a

b k

a

j

k

j

a

Figure 5: Four shifts to move the pie e no.

k

j

a

a

to the proper (gray) eld, provided

that it was in improper row and olumn.

Permutations Let f : {1, . . . , n} → {1, . . . , n} be some permutation. If we start from an arbitrary element x ∈ {1, . . . , n} and iterate f obtaining x, f (x), f (f (x)), f (f (f (x))), . . . after several (at most n) iterations we will get x again. It follows that ea h permutation is a

olle tion of y les. For example, the permutation (2, 4, 5, 1, 3) onsists of two

y les and we write (2, 4, 5, 1, 3) = [2, 4, 1][5, 3]. We also say that the permutation (2, 4, 5, 1, 3) is the produ t of [2, 4, 1] and [5, 3]. Cy les of length 2 are of Let us re all some basi fa ts about permutations.

spe ial importan e and they are alled

transpositions. Ea h y le an be written

as a produ t of transpositions:

[1, 2, . . . , k] = [1, k][1, k − 1] . . . [1, 3][1, 2] (We apply su

essive transpositions from right to left).

It follows that every

permutation an be written as a produ t of transpositions. tion is not unique, e.g.

This de omposi-

(2, 4, 5, 1, 3) = [4, 1][2, 1][5, 3] = [2, 4][4, 1][5, 3].

Even

the numbers of transpositions in two de ompositions need not to be the same:

[1, 3][1, 7][1, 3] = [3, 4][4, 5][5, 6][6, 7][5, 6][4, 5][3, 4].

However, there is some in-

variant. The following proposition is widely-known:

Proposition 1: If a permutation f an be written as a produ t of an even number of transpositions, then it annot be written as a produ t of an odd number of transpositions. Thus we an divide all permutations into two groups:

even permutations odd

whi h have an even number of transpositions in every de omposition and permutations  the remaining ones.

Consider a permutation with only one

y le. It follows that the length of the y le is even if and only if the permutation is odd.

Permutations and the Puzzle Clearly the initial onguration is some permutation of all denote it by

π0 .

n2

pie es.

Let us

Ea h y li shift is also a ertain permutation. Trivially it on-

sists of one y le. The nal onguration of pie es is the identity permutation

Puzzle id.

35

id. In s1 , s2 , . . . sk ,

orresponding to row and olumn shifts, su h that sk sk−1 · · · s2 s1 π0 = id. Assume that n is odd. Then ea h si is an even permutation. As id is even it 2 follows that the puzzle is solvable only if π0 is even. It takes O(n )-time to verify whether the initial onguration is even when n is odd. Nevertheless, what should we do if it turns out that n is even or π0 is We want to apply a number of shifts to the initial onguration to get

other words, we are looking for a sequen e of y li permutations

even? After the rst phase we obtain at most one row disarranged (namely the last row).

Observe that when

n

is even and the onguration after the rst

phase is odd we an make it even by shifting the last row by one. Thus in the sequel we an assume that after ompleting the rst phase we have got an even

onguration of pie es.

n2 − n + 1, n2 − n + 2, . . . , n2 to proper elds as follows. Consider a pie e with number k . Assume that some pie e number l is pla ed in the k -th eld. There must be also a pie e number m, su h that m > k and m 6= l , as otherwise our onguration onsists of just Then, we an move su

essive pie es

one transposition and is odd. Figure 6 shows that 7 moves su e to apply the [k,l,m℄ permutation. As a result, pie e

j
k

nds its way to the proper eld and every

stays at its position. That ends the des ription of the se ond phase.

Observe that the number of shifts performed by the algorithm is at most

4n(n − 1) + 7n < 400 000. k

i j l

m

k

j m

j m l

k

l

i

i

j

k

l

i

k

i j

j m

i

l

k 's

j

l m

i

j

l

k

Figure 6: Rearranging the last row: to

m

k

k

m

k

i

moves to l 's pla e,

l

to

m's

m

l

pla e and

m

pla e.

Implementation There are many ways to ode the orre t solution but there are some tri ks that

an help to speed up the program. 2 If we store a board of n pie es and simulate ea h move by moving pie es in 3 the board the time omplexity is O(n ). The time omplexity an in rease even

Puzzle

36

to

O(n4 )

2 when we do not store positions of the pie es  then we need O(n ) O(n2 ) pie es. 2 Solution running in O(n ) time is based on a simple observation. We have

time to nd ea h of

des ribed three ways of moving a pie e to its proper eld. Ea h way onsists of a group of 4 or 7 shifts but as a result of these shifts only two or three pie es

hange their positions. Thus, positions of pie es after performing ea h group of shifts an be updated in onstant time.

Task by

Solution description by

Woj ie h Rytter, Paweª Parys

Mi haª Adamaszek, Šukasz Kowalik

Available memory: 32 MB.

Maximum running time: 0.1 s.

Two sawmills There are

n

old trees planted along a road that goes from the top of a hill to

its bottom. Lo al government de ided to ut them down. In order not to waste wood ea h tree should be transported to a sawmill. Trees an be transported only in one dire tion:

downwards.

There is a

sawmill at the lower end of the road. Two additional sawmills an be built along the road. You have to de ide where to build them, as to minimize the ost of transportation. The transportation osts one ent per meter, per kilogram of wood.

Task Write a program, that:

•

reads from the standard input the number of trees, their weights and lo ations,

•

al ulates the minimum ost of transportation,

•

writes the result to the standard output.

Input n  the number of trees (2 ≤ n ≤ 1, 2, . . . , n, starting from the top of the hill and going downwards. Ea h of the following n lines ontains two positive integers separated by single spa e. Line i + 1 ontains: wi  weight (in kilograms) of the i-th tree and di  distan e (in meters) between trees number i and i + 1, 1 ≤ wi ≤ 10 000, 0 ≤ di ≤ 10 000. The last of these numbers, dn , is the distan e from the tree number n to the lower end of the road. It is guaranteed that the The rst line of the input ontains one integer

20 000).

The trees are numbered

total ost of transporting all trees to the sawmill at the end of the road is less than

2 000 000 000 ents.

Output The rst and only line of output should ontain one integer: the minimum ost of transportation.

Two sawmills

38

Example For the input data:

9 1 2 3 1 3 1 2 1 1

the orre t result is:

26

2 1 3 1 2 6 1 2 1 2

1

1

2

3 3

1

2

1

3

6

1

1

2

2 1

1 1

The gure shows the optimal lo ation of sawmills for the example data. Trees are depi ted as ir les with weights given below. Sawmills are marked bla k. The result is equal to: 1 · (2 + 1) + 2 · 1 + 1 · (1 + 2) + 3 · 2 + 2 · (1 + 2 + 1) + 1 · (2 + 1) + 1 · 1

Solution First of all let us make a trivial observation: it is not reasonable to build the sawmills between trees  in su h ase the ost will surely be lower if we move the sawmill to the nearest tree up. Before we des ribe the algorithm let us introdu e a few useful denitions. Let

Cost(a, b)

denote the total ost of transportation when the two additional

sawmills are lo ated at trees

a

additional sawmill is in point

alled

opt(i)

and

i,

b, a < b.

Moreover, assuming that the lower

let the optimal position of the se ond one be

opt(i) denotes the a, b su h that Cost(a, b)

(when there are several optimal positions then

smallest of them). What we have to do is to nd a pair is minimized. Our rst goal is to learn how to ompute

Cost(a, b)

qui kly.

Suppose we

store the following values:

• D(i)  the distan e from tree 1 to tree i (with D(n + 1) being the

distan e

from tree 1 to the sawmill in the valley),

• W (i)

 the sum of weights of trees

• T otalCost

1, . . . , i,

 the ost of transportation of all trees to the sawmill in the

valley (when there are no additional sawmills).

Two sawmills

39

All these values an be omputed in

O(n) time

without mu h eort  simply by

moving from tree 1 downwards and adding su

essive weights and distan es. Let us now observe that after this prepro essing one an ompute values of

Cost(a, b)

in

O(1)

time for given

a, b.

The following, easy to verify, formula

holds:

Cost(a, b) = T otalCost − W (a) · (D(b) − D(a)) − W (b) · (D(n + 1) − D(b)).

O(n2)

algorithm

At this moment we are ready to give an algorithm that works in

O(n2 )

time.

It does the linear-time prepro essing and nds the optimal pla ement of the
n sawmills simply by he king all 2 possible pairs (ea h pair takes O(1) time). This, however, is not qui k enough. We shall make an observation thanks to

whi h we will be able to redu e the number of pairs to he k.

Key observation Our key observation is as follows: for any

i<j

there is

opt(i) ≤ opt(j).

In other words, if we move the lower sawmill down, then the optimal lo ation of the upper sawmill annot move up. It is not di ult to prove this fa t. First observe the following lemma:

Lemma 1:

For any

k < k ′ , i < j if Cost(k ′ , i) ≤ Cost(k, i) then Cost(k ′ , j) ≤

Cost(k, j).

Proof:

Cost(k ′ , i) ≤ Cost(k, i) means that it is heaper to ′ ′ transport trees 1, . . . , k from point k to k than to transport trees k + 1, . . . , k ′ ′ ′ from point k to i. Clearly transporting the trees k + 1, . . . , k from point k to j would be at least that expensive. It follows that Cost(k ′ , j) ≤ Cost(k, j).  The inequality

k ′ = opt(i) in the above lemma. Cost(k ′ , i) ≤ Cost(k, i) holds by ′ ′ the denition of k . The lemma implies that any k su h that k < k is not opt(j) ′ (be ause it introdu es higher ost than k ). This proves our key observation. Now, let us put

Now let us see how to use this fa t.

Faster algorithm ∗ Assume that we have al ulated a = opt(⌊n/2⌋). We now know, that for any i < ∗ ⌊n/2⌋ we have opt(i) ≤ a and also for any j > ⌊n/2⌋ we have opt(j) ≥ a∗ . Thus

Solve(amin , amax , bmin , bmax ) whi h nds b ∈ {bmin , . . . bmax } su h that Cost(a, b) is minimized. ∗ It al ulates the value of a = opt(⌊(bmin + bmax )/2⌋) simply in O(amax − amin ) ∗ time. Then it alls re ursively Solve(amin , a , bmin , ⌊(bmin + bmax )/2⌋ − 1) and ∗ Solve(a , amax , ⌊(bmin + bmax )/2⌋ + 1, bmax). Obviously, the general task is solved by alling Solve(1, n, 1, n). we an write a re ursive pro edure

a ∈ {amin , . . . amax }

and

Two sawmills

40

Time omplexity We see that the number of pairs he ked is redu ed. Let us estimate it. Consider the binary tree of re ursive alls. Its depth is bounded by value of

bmax − bmin

⌈log n⌉

be ause the

is divided by 2 in ea h re ursive all. At ea h level of the

re ursion the possible

n

values of

a

is divided into several segments su h that

two su

essive segments have exa tly 1 ommon value. It follows that the total number of values of

a

onsidered at ea h level of the re ursion is

opt(·) is O(n) for algorithm is O(n log n).

the total time spent on omputing the time omplexity of our

O(n).

Thus

ea h level. It shows that

Other Solutions There are quite a few dierent approa hes to this problem (as well as its generalizations), not all orre t. Let us take a loser look at a few of them.

Naive solutions Solutions with time omplexity by the ontestants.

O(n3 )

or even

O(n4 )

an easily be a hieved

What they do is test all possible lo ations of sawmills,

but ompute the ost for them with slow algorithms  in linear or even (pure brute-for e) quadrati time.

An O(kn2 ) Solution Working for k Sawmills The following solution omputes optimal ost when

ated. For any lo ating

l

i = 1, . . . , n, l = 1, . . . , k

let

T [i, l]

k

sawmills have to be lo-

denote the optimal ost of

i (we assume that (i + 1)-th tree). We use the dyof T [i, l] an be omputed in O(i)

sawmills when we onsider only trees from 1 to

there is one more sawmill at the position of nami programming approa h.

The value

i possibilities of pla ing the last sawmill using stored values 2 of T [1, l − 1], . . . T [i − 1, l − 1]. The overall time omplexity is O(kn ) whi h 2 gives another O(n ) algorithm for our ase where k = 2.

time: we he k all

In orre t Greedy Solution We start with nding an optimal position for one sawmill in

O(n)

time. One of

the sawmills will be lo ated at that position. Then the other sawmill is pla ed in the position that minimizes the ost of transportation.

omplexity is

O(n).

The overall time

One an easily nd a test ase where this greedy approa h

does not work.

A linear algorithm The problem in more general setting is widely known as the where one has to hoose

k

verti es for

k -median

problem,

fa ilities in a given graph with weights

at verti es and edges subje t to minimize the total ost, i.e.

the sum for all

Two sawmills

41

verti es of distan e to the losest fa ility multiplied by the weight of the vertex. The problem is NP- omplete for general graphs (undire ted as well as dire ted) and polynomial for trees. For a dire ted path there is an

O(nk)

1

algorithm . It

is, however, far too ompli ated to onsider it for a programming ontest.

1 See V. Auletta, D. Parente and G. Persiano, Algorithms, vol. 26, no. 1, 1998, pages 87-100.

Pla ing Resour es on a Growing Line, J.

ISBN 8391770060