USACO

Elite 2008 January Competition USACO

Contest Analysis and Data
BRONZE PROBE!S
*****************************************************************************
Costume Party "Neal #u$ 200%&
It's Halloween! Farmer John is taking the cows to a costume party, but unfortunately he only has one costume. The
costume fits precisely two cows with a length of S ! "# S "# !,$$$,$$$%. FJ has & cows ' "# & "# '$,$$$%
con(eniently numbere) !...&* cow i has length +i ! "# +i "# !,$$$,$$$%. Two cows can fit into the costume if the
sum of their lengths is no greater than the length of the costume. FJ wants to know how many pairs of two )istinct
cows will fit into the costume.
I&,-T F./01T2
3 +ine !2 Two space4separate) integers2 & an) S
3 +ines '..&5!2 +ine i5! contains a single integer2 +i
S10,+6 I&,-T file costume.in%2
7 8
9
:
'
!
.-T,-T F./01T2
3 +ine !2 1 single integer representing the number of pairs of cows FJ
can choose. &ote that the or)er of the two cows )oes not
matter.
S10,+6 .-T,-T file costume.out%2
7
.-T,-T ;6T1I+S2
The four pairs are as follows2 cow ! an) cow 9* cow ! an) cow 7* cow ' an)
cow 7* an) finally cow 9 an) cow 7.
We first sort the heights, using an efficient sort, which takes O(N log N)
time. Then, for each height k in the list, we wish to (efficiently) find the
index of the largest height that, when added to k, produces a sum less than .
!fter we find this index, we can count the num"er of heights that, when added
to k, satisfy the gi#en property. The simplest way to find this is with a
"inary search, which is implemented in the solution "elow$
%include &algorithm'
%include &cstdio'
using namespace std(
)*+, *fout - fopen (.costume.out., .w.)(
)*+, *fin - fopen (.costume.in., .r.)(
const int /!0N - 12223(
int N, , total(
int height 4/!0N5(
66 finds the index of the first position whose height is &- #alue
inline int "insearch (int #alue)
7
int lo - 2, hi - N 8 9, mid(
while (lo & hi)
7
mid - (lo : hi : 9) '' 9(
if (height 4mid5 &- #alue)
lo - mid(
else
hi - mid 8 9(
;
return lo(
;
int main ()
7
fscanf (fin, .<d <d., =N, =)(
for (int i - 2( i & N( i::)
fscanf (fin, .<d., height : i)(
sort (height, height : N)(
total - 2(
for (int i - 2( i & N( i::)
7
66 >uery the largest index satisfying the conditions
int ind - "insearch ( 8 height 4i5)(
66 only count if ind ' i
if (ind ' i)
total :- ind 8 i(
else "reak(
;
fprintf (fout, .<d?n., total)(
return 2(
;
Ele'tion (ime "Je)rey #an*$ 200%&
The cows are ha(ing their first election after o(erthrowing the tyrannical Farmer John, an) <essie is one of & cows
! "# & "# :$,$$$% running for ,resi)ent. <efore the election actually happens, howe(er, <essie wants to )etermine
who has the best chance of winning.
The election consists of two roun)s. In the first roun), the = cows ! "# = "# &% cows with the most (otes a)(ance
to the secon) roun). In the secon) roun), the cow with the most (otes becomes ,resi)ent.
>i(en that cow i e?pects to get 1i (otes ! "# 1i "# !,$$$,$$$,$$$% in the first roun) an) <i (otes ! "# <i "#
!,$$$,$$$,$$$% in the secon) roun) if he or she makes it%, )etermine which cow is e?pecte) to win the election.
Happily for you, no (ote count appears twice in the 1i list* likewise, no (ote count appears twice in the <i list.
I&,-T F./01T2
3 +ine !2 Two space4separate) integers2 & an) =
3 +ines '..&5!2 +ine i5! contains two space4separate) integers2 1i an) <i
S10,+6 I&,-T file elect.in%2
: 9
9 !$
@ '
: 8
A 7
8 :
I&,-T ;6T1I+S2
There are : cows, 9 of which will a)(ance to the secon) roun). The cows e?pect to get 9, @, :, A, an) 8 (otes,
respecti(ely, in the first roun) an) !$, ', 8, 7, an) : (otes, respecti(ely, in the secon).
.-T,-T F./01T2
3 +ine !2 The in)e? of the cow that is e?pecte) to win the election.
S10,+6 .-T,-T file elect.out%2
:
.-T,-T ;6T1I+S2
Bows ', 7, an) : a)(ance to the secon) roun)* cow : gets : (otes in the secon) roun), winning the election.
,roblem where the goal is simply to follow the rules of the task )escription. This one is slightly comple? owing to
the reCuirement for a 'sort' routine. B an) B55 programmers ha(e easily use) built4in sort routines e.g., Csort%.
Furthermore, the sort routine has to be able to sort one number while carrying two other numbers in the e?changes.
The program below is a simple )emonstration of how Csort can be use) to perform such operations. Ja(a an) ,ascal
programmers ha) merely to augment their (ariable4swap routines to swap three (ariables. Some folks wrote two
separate but similar sort routines* some use) an if statement to )ifferentiate (ariable for testing.
Bomplete cre)it relie) on an .&log&% solution* .&
'
% sorts were not fast enough to get full points.
%include &stdio.h'
%include &stdli".h'
struct #ote@f 7
int a(
int "(
int cownum(
; #otes4322225(
comparea (struct #ote@f *a, struct #ote@f *") 7 return "8'a 8 a8'a( ;
compare" (struct #ote@f *a, struct #ote@f *") 7 return "8'" 8 a8'"( ;
main() 7
)*+, *fin - fopen (.elect.in., .r.)(
)*+, *fout - fopen (.elect.out., .w.)(
int n, k, i(
fscanf (fin, .<d <d., =n, =k)(
for (i - 2( i & n( i::) 7
fscanf (fin, .<d <d., =#otes4i5.a, =#otes4i5.")(
#otes4i5.cownum - i(
;
>sort(#otes, n, siAeof (struct #ote@f), comparea)(
>sort(#otes, k, siAeof (struct #ote@f), compare")(
fprintf (fout, .<d?n., #otes425.cownum:9)(
exit (2)(
;
iCo+ "Je)rey #an*$ 2008&
Fatigue) by the en)less toils of farming, Farmer John has )eci)e) to try his han) in the 0,9 player market with the
new iBow. It is an 0,9 player that stores & songs ! "# & "# !,$$$% in)e?e) ! through & that plays songs in a
Dshuffle)D or)er, as )etermine) by Farmer John's own algorithm2
3 6ach song i has an initial rating /i ! "# /i "# !$,$$$%.
3 The ne?t song to be playe) is always the one with
the highest rating or, if two or more are tie), the highest
rate) song with the lowest in)e? is chosen%.
3 1fter being playe), a song's rating is set to Eero, an) its rating
points are )istribute) e(enly among the other &4! songs.
3 If the rating points cannot be )istribute) e(enly i.e.,
they are not )i(isible by &4!%, then the e?tra points are
parcele) out one at a time to the first songs on the list
i.e., /F!, /F', etc. 44 but not the playe) song% until no
more e?tra points remain.
This process is repeate) with the new ratings after the ne?t song is playe).
;etermine the first T songs ! "# T "# !$$$% that are playe) by the iBow.
I&,-T F./01T2
3 +ine !2 Two space4separate) integers2 & an) T
3 +ines '..&5!2 +ine i5! contains a single integer2 /i
S10,+6 I&,-T file icow.in%2
9 7
!$
A
!!
I&,-T ;6T1I+S2
The iBow contains 9 songs, with ratings !$, A, an) !!, respecti(ely. Gou must )etermine the first 7 songs to be
playe).
.-T,-T F./01T2
3 +ines !..T2 +ine i contains a single integer that is the i4th song that the iBow plays.
S10,+6 .-T,-T file icow.out%2
9
!
'
9
.-T,-T ;6T1I+S2
The ratings before each song playe) are2
/F! /F' /F9
!$ A !! 4H play I9 !!J' # :, lefto(er # !
!8 !9 $ 4H play I! !8J' # A
$ '! A 4H play I' '!J' # !$, lefto(er # !
!! $ !A 4H play I9 ...
This program is a .pure programming. task. *t re>uires nothing more than the
implementation of a set of rules. The example e#en showed how one of the
potentially trou"lesome rules actually worked.
The program "elow is commented to show how each step is performed. The only
potentially tricky part is the use of two #aria"les for the distri"ution$ one
to count how many pieces get distri"uted and the second to say where they go.
The second #aria"le is the trick for implementing the .BonCt redistri"ute "ack
to the currently playing song. rule.
%include &stdio.h'
%include &stdli".h'
#oid main() 7
int "estrate, "estD, i, D, k, n, t, r49222:95(
int e#enlydistri"ute, lefto#er(
)*+, *fin - fopen (.icow.in., .r.)(
)*+, *fout - fopen (.icow.out., .w.)(
fscanf (fin, .<d <d., =n, =t)(
for (i - 2( i & n( i::)
fscanf (fin, .<d., =r4i5)(
for (i - 2( i & t( i::) 7 6* play t songs *6
6* find highest rated song *6
"estrate - 89(
for (D - 2( D & n( D::) 7
if (r4D5 ' "estrate) 7 6* "est, lowest index *6
"estD - D(
"estrate - r4D5(
;
;
fprintf (fout, .<d?n., "estD:9)( 6* play it *6
e#enlydistri"ute - r4"estD56(n89)(
lefto#er - r4"estD5 < (n89)(
r4"estD5 - 2(
for (D - 2( D & n( D::)
if (D E- "estD)
r4D5 :- e#enlydistri"ute(
for (k - D - 2( D & lefto#er( D::, k::) 7
if (D -- "estD) k::(
r4k5::(
;
;
;
S,-ER PROBE!S
**********************************************************************
Co+ Contest "Neal #u$ 200%&
N (9 &- N &- 922) cows, con#eniently num"ered 9..N, are participating in a
programming contest. !s we all know, some cows code "etter than others. ,ach
cow has a certain constant skill rating that is uni>ue among the competitors.
The contest is conducted in se#eral head8to8head rounds, each "etween two
cows. *f cow ! has a greater skill le#el than cow F (9 &- ! &- N( 9 &- F &- N(
! E- F), then cow ! will always "eat cow F.
)armer Gohn is trying to rank the cows "y skill le#el. Hi#en a list the
results of / (9 &- / &- I,322) two8cow rounds, determine the num"er of cows
whose ranks can "e precisely determined from the results. *t is guaranteed
that the results of the rounds will not "e contradictory.
*NJKT )OL/!T$
* +ine 9$ Two space8separated integers$ N and /
* +ines 1../:9$ ,ach line contains two space8separated integers that
descri"e the competitors and results (the first integer, !, is the winner) of
a single round of competition$ ! and F
M!/J+, *NJKT (file contest.in)$
3 3
I N
I 1
N 1
9 1
1 3
OKTJKT )OL/!T$
* +ine 9$ ! single integer representing the num"er of cows whose ranks
can "e determined
M!/J+, OKTJKT (file contest.out)$
1
OKTJKT B,T!*+M$
Oow 1 loses to cows 9, N, and I. Thus, cow 1 is no "etter than any of the cows
9, N, and I. Oow 3 loses to cow 1, so cow 1 is "etter than cow 3. Thus, cow 1
must "e fourth, and cow 3 must "e fifth. The ranks of the other cows cannot "e
determined.
)irst, note that the pro"lem can "e con#erted into a graph, with the cows as
the nodes, and the games as the edges. (*n particular, note that the graph is
a directed acyclic graph, or a B!H.)
)or a certain cow 0, 0Cs rank can "e determined if and only if the following
property is true$ for e#ery other cow P, either cow 0 must "e "etter than cow
P, or cow P must "e "etter than cow 0.
Thus, we can find which pairs of #ertices in the graph are connected either "y
doing a F)M for O(N/) o#erall or )loyd8Warshall for O(N
N
) o#erall. Then, for
each cow, we check if e#ery other cow is connected to it, and if so, we
increment our answer "y 9.
The following is a sample solution$
%include &cstdio'
using namespace std(
)*+, *fout - fopen (.contest.out., .w.)(
)*+, *fin - fopen (.contest.in., .r.)(
const int /!0N - 923(
int N, /, total - 2(
"ool reach 4/!0N54/!0N5(
#oid main ()
7
fscanf (fin, .<d <d., =N, =/)(
66 cows are CconnectedC to themsel#es
for (int i - 2( i & N( i::)
reach 4i54i5 - true(
66 read input
int a, "(
for (int i - 2( i & /( i::)
7
fscanf (fin, .<d <d., =a, =")(
a88, "88(
reach 4a54"5 - true(
;
66 use )loyd8Warshall to compute transiti#e closure
for (int k - 2( k & N( k::)
for (int i - 2( i & N( i::)
if (reach 4i54k5)
for (int D - 2( D & N( D::)
if (reach 4k54D5)
reach 4i54D5 - true(
for (int i - 2( i & N( i::)
7
"ool good - true(
66 we can find the rank of a cow if all other cows are connected to it
for (int D - 2( D & N( D::)
if (Ereach 4i54D5 == Ereach 4D54i5)
7
good - false(
"reak(
;
if (good)
total::(
;
fprintf (fout, .<d?n., total)(
;
Runnin* "Neal #u$ 200%&
The cows are trying to "ecome "etter athletes, so Fessie is running on a track
for exactly N (9 &- N &- 92,222) minutes. Buring each minute, she can choose
to either run or rest for the whole minute.
The ultimate distance Fessie runs, though, depends on her Cexhaustion factorC,
which starts at 2. When she chooses to run in minute i, she will run exactly a
distance of B
i
(9 &- B
i
&- 9,222) and her exhaustion factor will increase "y 9
88 "ut must ne#er "e allowed to exceed / (9 &- / &- 322). *f she chooses to
rest, her exhaustion factor will decrease "y 9 for each minute she rests. Mhe
cannot commence running again until her exhaustion factor reaches 2. !t that
point, she can choose to run or rest.
!t the end of the N minute workout, FessieCs exaustion factor must "e exactly
2, or she will not ha#e enough energy left for the rest of the day.
)ind the maximal distance Fessie can run.
*NJKT )OL/!T$
* +ine 9$ Two space8separated integers$ N and /
* +ines 1..N:9$ +ine i:9 contains the single integer$ B
i
M!/J+, *NJKT (file cowrun.in)$
3 1
3
N
I
1
92
OKTJKT )OL/!T$
* +ine 9$ ! single integer representing the largest distance Fessie can run
while satisfying the conditions.
M!/J+, OKTJKT (file cowrun.out)$
Q
OKTJKT B,T!*+M$
Fessie runs during the first minute (distance-3), rests during the second
minute, runs for the third (distance-I), and rests for the fourth and fifth.
Note that Fessie cannot run on the fifth minute "ecause she would not end with
a rest factor of 2.
This is a straightforward dynamic programming (BJ) pro"lem. To sol#e the
pro"lem, we want to find, for each k such that 2 &- k &- N, the maximum
possi"le distance Fessie could ha#e run after the first k minutes, if she has
a rest factor of 2. ()or example, if we can o"tain a distance of 9I after 3
minutes with a rest factor of 2, or we can o"tain a distance of 93 after 3
minutes with a rest factor of 2, we would always choose the second o#er the
first.) Olearly, the "est such #alue for 2 is 2. Then, for each minute i of
the N minutes, we can compute all of the next #alues possi"le with the
following method$
8)irst, try to not run during the minute, and see if this produces an
impro#ement. (Thus, check if the "est #alue for i is "etter than the one for i
: 9.)
8Then, for each num"er k from 9 to /, let Fessie run for exactly k minutes and
then rest for k minutes. Mee if this new #alue produces a greater #alue than
the "est #alue for i : 1k (which is the num"er of minutes finished after
running for k minutes and resting for another k minutes).
Thus, since we do / updates for each of the N minutes, our total complexity is
O(N/). The following is a sample solution$
%include &cstdio'
using namespace std(
)*+, *fout - fopen (.cowrun.out., .w.)(
)*+, *fin - fopen (.cowrun.in., .r.)(
const int /!0N - 92223(
int N, /, dist 4/!0N5, "est 4/!0N5(
#oid main ()
7
fscanf (fin, .<d <d., =N, =/)(
for (int i - 2( i & N( i::)
fscanf (fin, .<d., dist : i)(
for (int i - 2( i & N( i::)
7
66 skip the #alue
if ("est 4i5 ' "est 4i : 95)
"est 4i : 95 - "est 4i5(
int sum - "est 4i5, pos - i(
for (int D - 2( D & / == pos & N( D::)
7
66 update each #alue
sum :- dist 4i : D5(
pos :- 1(
if (sum ' "est 4pos5)
"est 4pos5 - sum(
;
;
fprintf (fout, .<d?n., "est 4N5)(
;
(elep.one ines "Paul C.ristiano$ 200%&
)armer Gohn wants to set up a telephone line at his farm. Knfortunately, the
phone company is uncooperati#e, so he needs to pay for some of the ca"les
re>uired to connect his farm to the phone system.
There are N (9 &- N &- 9,222) forlorn telephone poles con#eniently num"ered
9...N that are scattered around )armer GohnCs property( no ca"les connect any
them. ! total of J (9 &- J &- 92,222) pairs of poles can "e connected "y a
ca"le( the rest are too far apart.
The i
th
ca"le can connect the two distinct poles !
i
and F
i
, with length +
i
(9
&- +@i &- 9,222,222) units if used. The input data set ne#er names any 7!
i
,F
i
;
pair more than once. Jole 9 is already connected to the phone system, and pole
N is at the farm. Joles 9 and N need to "e connected "y a path of ca"les( the
rest of the poles might "e used or might not "e used.
!s it turns out, the phone company is willing to pro#ide )armer Gohn with R (2
&- R & N) lengths of ca"le for free. Feyond that he will ha#e to pay a price
e>ual to the length of the longest remaining ca"le he re>uires (each pair of
poles is connected with a separate ca"le), or 2 if he does not need any
additional ca"les.
Betermine the minimum amount that )armer Gohn must pay.
*NJKT )OL/!T$
* +ine 9$ Three space8separated integers$ N, J, and R
* +ines 1..J:9$ +ine i:9 contains the three space8separated integers$
!
i
, F
i
, and +
i
M!/J+, *NJKT (file phoneline.in)$
3 S 9
9 1 3
N 9 I
1 I T
N 1 N
3 1 Q
N I S
I 3 U
*NJKT B,T!*+M$
There are 3 poles. Jole 9 cannot "e connected directly to poles I or 3. Jole 3
cannot "e connected directly to poles 9 or N. !ll other pairs can "e
connected. The phone company will pro#ide one free ca"le.
OKTJKT )OL/!T$
* +ine 9$ ! single integer, the minimum amount )armer Gohn can pay. *f it is
impossi"le to connect the farm to the phone company, print 89.
M!/J+, OKTJKT (file phoneline.out)$
I
OKTJKT B,T!*+M$
*f pole 9 is connected to pole N, pole N to pole 1, and pole 1 to pole 3 then
)armer Gohn re>uires ca"les of length I, N, and Q. The phone company will
pro#ide the ca"le of length Q, so the longest ca"le needed has length I.
We construct the following graph H$ each pole is a #ertex, and each possi"le
connection "etween poles is an edge "etween corresponding #ertices with weight
e>ual to the distance "etween the poles.
Now imagine we ha#e a function f(lim) that tells us if there exists a path
from #ertex 9 to #ertex N using no more than R edges whose weights are greater
than lim. *f we ha#e such a function f, we can perform a "inary search for the
answer$ the smallest lim that works (in other words, the smallest k such that
f(k) is true) is the minimum amount )armer Gohn must pay.
Mo the pro"lem now is implementing function f(lim) efficiently, and to do so,
we consider the graph , which has the same #ertices and edges as H "ut
different edge weights. /ore precisely, an edge "etween #ertices a and " in
has weight 2 if the corresponding edge in H has weight w &- lim, and weight 9
otherwise (if the corresponding edge in H has weight w ' lim), so the shortest
path "etween two #ertices a and " in represents the minimum num"er of edges
with weight greater than lim on a path "etween a and " in H. Thus computing
f(lim) is e>ui#alent to checking if the shortest path "etween 9 and N in is
less than or e>ual to R, and we can do this in O(, log V) time with
BiDkstraCs.
*n the worst case, we will need to e#aluate function f O(log V) times ("ecause
of the "inary search), so the total running time of the entire algorithm is
O(, log1 V). (*tCs actually possi"le to compute the shortest path "etween two
#ertices in a graph where all edges ha#e weight 2 or 9 in linear time, "ut
thatCs not needed here.)
#include<fstream>
#include<vector>
using namespace std;
ifstream fin ("phoneline.in");
ofstream fout ("phoneline.out");
const int MAX = !!! " #;
vector <int> a$MAX%& '$MAX%;
int e$MAX ( !%;
'ool mar)$MAX%;
int dis $MAX%& saf$MAX%& head& tail;
int n& )& *& M;
void dfs (int u)
+
dis$u% = *;
mar)$u% = true;
saf$tail""% = u;
for (int i = !; i < a$u%.si,e (); i"") +
if (-mar)$a$u%$i%% .. '$u%$i% <= M)
dfs (a$u%$i%);
/
/
void 0fs (int MM)
+
M = MM;
memset (mar)& !& si,eof mar));
head = tail = !;
* = !;
dfs (n 1 );
2hile (head < tail) +
int ) = saf$head""%;
for (int i = !; i < a$)%.si,e (); ""i) +
if (-mar)$a$)%$i%%) +
* = dis$)% " ;
dfs (a$)%$i%);
/
/
/
/
void 's (int 3& int 4)
+
if (4 == 3 " ) +
fout << e$4% << endl;
e3it (!);
/
int mid = (4 " 3) 5 6;
0fs (e$mid%);
if (dis$!% <= ))
's (3& mid);
else
's (mid& 4);
/
void main ()
+
int ee;
fin >> n >> ee >> );
int u& v& 2;
for (int i = !; i < ee; ""i) +
fin >> u >> v >> 2;
u11;
v11;
a$u%.push7'ac) (v);
'$u%.push7'ac) (2);
a$v%.push7'ac) (u);
'$v%.push7'ac) (2);
e$i " % = 2;
/
sort (e& e " " ee);
0fs (!);
if (-mar)$!%) +
fout << "1" << endl;
return !;
/
if (dis$!% <= )) +
fout << "!" << endl;
return !;
/
's (!& ee);
/
/OD PROBE!S
*****************************************************************************
0ay1ale /uessin* "Brian Dean$ 2002&
The cows, who always ha#e an inferiority complex a"out their intelligence,
ha#e a new guessing game to sharpen their "rains.
! designated Cay OowC hides "ehind the "arn and creates N (9 &- N &-
9,222,222) uni>uely8siAed stacks (con#eniently num"ered 9..N) of hay "ales,
each with 9..9,222,222,222 "ales of hay.
The other cows then ask the ay Oow a series of W (9 &- W &- 13,222) >uestions
a"out the the stacks, all ha#ing the same form$
What is the smallest num"er of "ales of any stack in the range of stack
num"ers W
l
..W
h
(9 &- W
l
&- N( W
l
&- W
h
&- N)X
The ay Oow answers each of these >ueries with a single integer ! whose
truthfulness is not guaranteed.
elp the other cows determine if the answers gi#en "y the ay Oow are self8
consistent or if certain answers contradict others.
*NJKT )OL/!T$
* +ine 9$ Two space8separated integers$ N and W
* +ines 1..W:9$ ,ach line contains three space8separated integers that
represent a single >uery and its reply$ W
l
, W
h
, and !
M!/J+, *NJKT (file "ales.in)$
12 I
9 92 S
3 9Q S
N 91 T
99 93 91
*NJKT B,T!*+M$
The minimum num"er of "ales in stacks 9..92 is S, the minimum num"er of "ales
in stacks 3..9Q is S, the minimum num"er of "ales in stacks N..91 is T, and
the minimum num"er of "ales in stacks 99..93 is 91.
OKTJKT )OL/!T$
* +ine 9$ Jrint the single integer 2 if there are no inconsistencies
among the replies (i.e., if there exists a #alid realiAation
of the hay stacks that agrees with all W >ueries). Otherwise,
print the index from 9..W of the earliest >uery whose answer
is inconsistent with the answers to the >ueries "efore it.
M!/J+, OKTJKT (file "ales.out)$
N
OKTJKT B,T!*+M$
Wuery N (.N 91 T.) is the first that is inconsistent with those "efore it.
)rom >ueries 9 and 1 and the fact that all hay stacks ha#e a distinct num"er
of "ales, we deduce that one of stacks 3..92 must contain exactly S "ales.
owe#er, this stack contradicts the answer to >uery N.
The first (and most crucial) o"ser#ation to make is that if there exists a
list of stack siAes that satisfies >ueries 9...m, then the same set satisfies
>ueries 9...m89. Mo we can perform "inary search on the "iggest se>uence of
>ueries that can "e satisfied, and reduce the pro"lem to finding whether a set
of >ueries is satisfia"le.
Then, gi#en a se>uence of >uery results, we can find out whatCs the lowest
num"er of "ales in each stack in O(N:W
log
W) time "y sweeping through the
>ueries and tracking the Climiting >ueryC using a heap. This can alternati#ely
"e done using a range tree, although thatCs a "it slower.
We then need to check that minimum #alues are indeed present in the ranges.
)or all the >ueries whose answer is x, the #alue x must "e present in their
intersection since x can only appear once total. Then x must appear once as
one of the CminimumC #alues since x is also an upper "ound on that region as
well. Mo this can "e checked in O(N) time using a lookup list as well. Note
that this condition is sufficient since all the other duplicated #alues (in
the lower "ound list) can ha#e their #alues rised to ar"itrary #alues without
causing any further pro"lems.
Felow is Lichard JengCs solution$
%include &cstdio'
%include &algorithm'
%include &>ueue'
%include &#ector'
using namespace std(
%define /!0N 9922222
%define /!0W N2222
struct >type 7
int p9, p1, res, id(
"ool operator & (const >type = o)const 7 return p9 & o.p9( ;
;lis4/!0W5(
pair &int, int' lis94/!0W5(
int last4/!0W5, #4/!0N5, left4/!0W5, right4/!0W5, n, >, needt(
priority@>ueue &pair &int, int' 'lim(
pair &pair &int, int', int' need4/!0W5(
int work (int len)
7
int i, i9, i1(
if (len ' >) return 2(
while (Elim.empty ()) lim.pop ()(
for (i - 2( i & >( i::)
7
left4i5 - last4i5 - 2(
right4i5 - n(
;
for (i - 2( i & >( i::)
if (lis4i5.id & len)
7
left4lis4i5.res5 'X- lis4i5.p9(
right4lis4i5.res5 &X- lis4i5.p1(
;
needt - 2(

for (i - 2( i & >( i::)
if (left4i5 E- 2)
7
need4needt5.first.first - right4i5(
need4needt5.first.second - left4i5(
need4needt::5.second - i(
;
sort (need, need : needt)(

for (i - 9, i9 - i1 - 2( i &- n( i::)
7
for (( (i9 & >) == (lis4i95.p9 -- i)( i9::)
if (lis4i95.id & len)
lim.push (pair & int, int '(lis4i95.res, lis4i95.p1))(
while ((Elim.empty ()) == (lim.top ().second & i))
lim.pop ()(
#4i5 - lim.empty () X 2 $ #4i5 - lim.top ().first(
last4#4i55 - i(
for (( (i1 & needt) == (need4i15.first.first -- i)( i1::)
if (last4need4i15.second5 & need4i15.first.second)
return 2(
;
return 9(
;
#oid main ()
7
int i, D, tot, ans, del(
freopen (."ales.in., .r., stdin)(
freopen (."ales.out., .w., stdout)(
scanf (.<d<d., =n, =>)(
for (i - 2( i & >( i::)
7
scanf (.<d<d<d., =lis4i5.p9, =lis4i5.p1, =lis4i5.res)(
lis4i5.id - i(
lis94i5.first - lis4i5.res(
lis94i5.second - i(
;

sort (lis9, lis9 : >)(

for (i - tot - 2( i & >( i::)
7
tot :- ((i -- 2) YY (lis94i5.first E- lis94i 8 95.first))(
lis4lis94i5.second5.res - tot(
;
sort (lis, lis : >)(
for (del - 9 && 9U, ans - 2( del( del 6- 1)
if (work (ans : del))
ans :- del(
printf (.<d?n., (ans & >) X (ans : 9) $ 2)(
;
Arti3'ial a4e "!att !'Cut'.en$ 2005&
The oppressi#ely hot summer days ha#e raised the cowsC clamoring to its
highest le#el. )armer Gohn has finally decided to "uild an artificial lake.
)or his engineering studies, he is modeling the lake as a two8dimensional
landscape consisting of a contiguous se>uence of N soon8to8"e8su"merged le#els
(9 &- N &- 922,222) con#eniently num"ered 9..N from left to right.
,ach le#el i is descri"ed "y two integers, its width W@i (9 &- W
i
&- 9,222)
and height (like a relati#e ele#ation)
i
(9 &-
i
&- 9,222,222). The heights
of )GCs le#els are uni>ue. !n infinitely tall "arrier encloses the lakeCs
model on the left and right. One example lake profile is shown "elow.

* * $
* * $
* * T
* *** * S
* *** * U
* *** * 3
* ********** I &8 height
* ********** N
*************** 1
*************** 9
+e#el Y 9 Y1Y N Y
*n )GCs model, he starts filling his lake at sunrise "y flowing water into the
"ottom of the lowest ele#ation at a rate of 9 s>uare unit of water per minute.
The water falls directly downward until it hits something, and then it flows
and spreads as room8temperature water always does. !s in all good models,
assume that falling and flowing happen instantly. Betermine the time at which
each ele#ationCs "ecomes su"merged "y a single unit of water.
W!T,L W!T,L OV,L)+OWM
Y Y
* Y * * Y * * *
* V * * V * * *
* * * .... * *ZZZZZZZZZZZZ*
* ** * *ZZZZ** $ * *ZZZZ**ZZZZZZ*
* ** * *ZZZZ** $ * *ZZZZ**ZZZZZZ*
* ** * *ZZZZ**ZZZZZZ* *ZZZZ**ZZZZZZ*
* ********* *ZZZZ********* *ZZZZ*********
*ZZZZ********* *ZZZZ********* *ZZZZ*********
************** ************** **************
************** ************** **************
!fter I mins !fter 1U mins !fter 32 mins
+#l 9 su"merged +#l N su"merged +#l 1 su"merged
Warning$ The answer will not always fit in N1 "its.
*NJKT )OL/!T$
* +ine 9$ ! single integer$ N
* +ines 1..N:9$ +ine i:9 descri"es le#el i with two space8separated
integers$ W
i
and
i
M!/J+, *NJKT (file alake.in)$
N
I 1
1 S
U I
*NJKT B,T!*+M$
Three le#els Dust as in the example a"o#e. Water will fill the first le#el
"ecause it is the lowest.
OKTJKT )OL/!T$
* +ines 9..N$ +ine i contains a single integer that is the num"er of
minutes that since sunrise when le#el %i is co#ered "y water
of height 9.
M!/J+, OKTJKT (file alake.out)$
I
32
1U
Ke try to sol(e the problem for each le(el separately. For each le(el, the amount of water
reCuire) until it o(erflows can be broken )own into three parts. K.+.>, we assume the le(el is
to the left of the le(el of minimum height. The three parts are2
To the left of the le(el. Kater will flow this way unti it encounters the first le(el that has a
higher height. So, for each le(el, we nee) to fin) the first le(el to its left that has a higher
height. This can be )one using a stack in .n% time.
<etween the le(el an) the lowest le(el. The water le(els forms a series of 'steps', which can
be tracke) in a stack if we consi)er the le(els from right to left. This can also be
calculate) in .n% time.
To the right of the lowest le(el. If we consi)er the le(els one by one leftwar)s starting from
the one to the left of the lowest le(el, the water le(el at the lowest le(el can only increase.
So it suffices to keep a pointer to how far to the right gets submerge) an) increase this
counter as we go. This clearly also runs in .n%
Bombining these three parts, we get an .n% algorithm. 0any of the solutions submitte) by
contestants use) much cle(erer algorithms that combines these three steps into a single one, but
most are still base) on this 'step' i)ea. Here is &eal Ku's e?planation on how he )i) this problem2
1)) in the two infinite barriers as 'le(els' with infinite height for simplicity. Ke will fin) the
answer for each le(el in the or)er they are fille), keeping track of the current time when
calculating each.
&ote that after we ha(e fille) le(el +, the water will go in the )irection of the shorter neighbor
le(el of +. For e?ample, in the following )iagram, after le(el ' is fille), the water will flow to the
right2
3 3 A
3 3 L
3333 3 8
3333 33 3 : "44 heights
3333 3333 3 7
3333 3333333 3 9
3333 333333333 '
333333333333333 !
! ' 9 7 : 8
+e(els
The water will keep flowing to the right an) thus 'skipping' le(els% until an increase in height
occurs. Thus, in the e?ample abo(e, le(el 8 will be fille) ne?t after le(el ' is finishe).
1lso, note that at this point both le(el ' an) le(el 9 share the same water le(el. They will always
remain at the same height since the water fills them e(enly. Thus, we can 'merge' le(el ' into
le(el 9 the new wi)th of le(el 9 will be the sum of its original wi)th an) the wi)th of le(el '%,
an) )elete le(el '. &ote that to implement this merging efficiently we can use a linke) list of
le(els which enables constant time )eletion of a le(el%.
This gi(es us a fairly simple algorithm2 fin) the le(el which the water currently fills starting
with the shortest le(el%, an) calculate the time at which it becomes submerge) which is eCual to
the time when the le(el began to fill up a))e) to the wi)th of the le(el%. &e?t, fin) how long it
takes for the le(el to fill up to the height of the shorter of its two neighbors, an) a)) this to our
current time. Finally, continue in the )irection of the shorter neighbor until we reach an increase
in le(el heights. This le(el is the ne?t le(el to fill with water.
1t first, it seems this approach is .&
'
%, since we can skip up to .&% le(els each time. Howe(er,
the algorithm is actually linear time because of the following fact2 after we skip a le(el, we
cannot skip it again. This is because after a le(el is skippe), the water must come back to it from
the opposite )irection, which means it must fill the le(el. In the abo(e e?ample, the water will
skip le(el :, fill le(el 8, an) then come back to le(el : an) fill it.% Therefore each le(el can be
skippe) at most once, so the algorithm takes .&% time o(erall. The following is a sample
implementation2
#include <cstdio>
using namespace std;
89:; (fin = fopen ("ala)e.in"& "r");
89:; (fout = fopen ("ala)e.out"& "2");
const int MAX< = !!!!#& 9<8 = !!!!!!!!!;
int <& 2idth $MAX<%& height $MAX<%;
int prev $MAX<%& ne3t $MAX<%; 55 simplified lin)ed list
long long ans $MAX<%& total = !;
void main () +
fscanf (fin& "=d"& .<);
height $!% = height $< " % = 9<8; 55 infinite 2alls
int ind = ; 55 the current level 'eing filled 2ith 2ater
for (int i = ; i <= <; i"") +
fscanf (fin& "=d =d"& 2idth " i& height " i);
prev $i% = i 1 & ne3t $i% = i " ; 55 initiali,e
55 ind starts as the shortest level
if (height $i% < height $ind%)
ind = i;
/
55 continue until the current level is one of the 2alls
2hile (height $ind% < 9<8)
+
55 calculate our current inde3
ans $ind% = total " 2idth $ind%;
55 delete the current inde3
ne3t $prev $ind%% = ne3t $ind%& prev $ne3t $ind%% = prev $ind%;
55 ta)e the smaller of the neigh'ors
if (height $prev $ind%% < height $ne3t $ind%%)
+
55 add the time ta)en to our current total
total "= (long long) 2idth $ind% ( (height $prev $ind%% 1 height $ind%);
55 merge the levels together
2idth $prev $ind%% "= 2idth $ind%;
ind = prev $ind%;
55 find the ne3t inde3
2hile (ind > ! .. height $prev $ind%% < height $ind%)
ind = prev $ind%;
/
else
+ 55 do similarl4 for the other neigh'or
total "= (long long) 2idth $ind% ( (height $ne3t $ind%% 1 height $ind%);
2idth $ne3t $ind%% "= 2idth $ind%;
ind = ne3t $ind%;
2hile (ind <= < .. height $ne3t $ind%% < height $ind%)
ind = ne3t $ind%;
/
/
for (int i = ; i <= <; i"")
fprintf (fout& "=lld>n"& ans $i%);
/
Cell P.one Net+or4 "Je)rey #an*$ 200%&
)armer Gohn has decided to gi#e each of his cows a cell phone in hopes to
encourage their social interaction. This, howe#er, re>uires him to set up cell
phone towers on his N (9 &- N &- 92,222) pastures (con#eniently num"ered 9..N)
so they can all communicate.
,xactly N89 pairs of pastures are adDacent, and for any two pastures ! and F
(9 &- ! &- N( 9 &- F &- N( ! E- F) there is a se>uence of adDacent pastures
such that ! is the first pasture in the se>uence and F is the last. )armer
Gohn can only place cell phone towers in the pastures, and each tower has
enough range to pro#ide ser#ice to the pasture it is on and all pastures
adDacent to the pasture with the cell tower.
elp him determine the minimum num"er of towers he must install to pro#ide
cell phone ser#ice to each pasture.
JLOF+,/ N!/,$ tower
*NJKT )OL/!T$
* +ine 9$ ! single integer$ N
* +ines 1..N$ ,ach line specifies a pair of adDacent pastures with two space8
separated integers$ ! and F
M!/J+, *NJKT (file tower.in)$
3
9 N
3 1
I N
N 3
*NJKT B,T!*+M$
)armer Gohn has 3 pastures$ pastures 9 and N are adDacent, as are pastures 3
and 1, pastures I and N, and pastures N and 3. Heometrically, the farm looks
like this (or some similar configuration)
I 1
Y Y
988N883
OKTJKT )OL/!T$
* +ine 9$ ! single integer indicating the minimum num"er of towers to
install
M!/J+, OKTJKT (file tower.out)$
1
OKTJKT B,T!*+M$
The towers can be place) at pastures ' an) 9 or pastures 9 an) :.
This problem, known as the Dminimum )ominating set problemD in a tree, has a nice gree)y
solution. &ote that the graph in the problem is in)ee) a tree because it has M4! e)ges. Ke say a
(erte? is )ominate) by a set of (ertices if it is either in the set or a)Nacent to a (erte? in the set.
The algorithm is as follows2
!% =eep track of a set of (ertices S.
'% /oot the tree at an arbitrary no)e.
9% Misit the (ertices of the tree with a postor)er tra(ersal.
7% 1t each (erte?, if it is not )ominate) by S, a)) it an) all of its neighbors to S.
:% .nce the tra(ersal is )one, (isit the (ertices in S in the re(erse or)er that they were a))e).
8% 1t each (erte?, if S is still a )ominating set when the (erte? is remo(e), then )o so.
The (ertices left in S form a minimum )ominating set. For a proof of why this works, see
http2JJwww.cs.clemson.e)uJObc)eanJgree)yFtreeF)om.swf.
&ote that the running time of this algorithm is (ery goo), .&%, since each (erte? is (isite) once
in the postor)er tra(ersal an) each (erte? is a))e) to S at most once. Bhecking whether a (erte?
can be remo(e) can also be )one efficiently by keeping track of how many (ertices in S it is
a)Nacent to. 1n implementation of this algorithm is shown below.
#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;
int <& c$!!!%& p$!!!%;
vector <vector <int> > ;;
vector <int> 0;
void traverse(int v)
+
for(int i=!; i<;$v%.si,e(); i"")
if(p$v% -= ;$v%$i%)
+
p$;$v%$i%% = v;
traverse(;$v%$i%);
/

if(c$v% == !)
+
0.push7'ac)(v);
c$v%"";

for(int i=!; i<;$v%.si,e(); i"")
+
c$;$v%$i%% "= 6; 0.push7'ac)(;$v%$i%);
for(int ?=!; ?<;$;$v%$i%%.si,e(); ?"")
c$;$;$v%$i%%$?%%"";
/
/
/
void main()
+
89:;( in = fopen("to2er.in"& "r");
89:;( out = fopen("to2er.out"& "2");

fscanf(in& "=d"& .<);
;.resi,e(<);
for(int i=!; i<<; i"") + p$i% = 1; c$i% = !; /

int u& v;

for(int i=!; i<<1; i"")
+
fscanf(in& "=d =d"& .u& .v);
;$u1%.push7'ac)(v1);
;$v1%.push7'ac)(u1);
/

traverse(!);

int num@emove = !;
for(int i=0.si,e()1; i>=!; i11)
+
'ool can@emove = (c$0$i%% > );
for(int ?=!; ?<;$0$i%%.si,e(); ?"")
can@emove = can@emove .. (c$;$0$i%%$?%% > );
if(can@emove)
+
c$0$i%%11;
for(int ?=!; ?<;$0$i%%.si,e(); ?"")
c$;$0$i%%$?%%11;
/
num@emove "= can@emove;
/

fprintf(out& "=d>n"& 0.si,e()1num@emove);
/
Spe'ial 200% C.inese Competition 'ontest
/OD PROBE!S
*****************************************************************************
Summin* Sums "Neal #u$ 200%&
The N (9 &- N &- 32,222) cows, con#eniently num"ered 9..N, are trying to learn
some encryption algorithms. !fter studying a few examples, they ha#e decided
to make one of their ownE owe#er, they are not #ery experienced at this, so
their algorithm is #ery simple$
,ach cow i is gi#en a starting num"er O
i
(2 &- O
i
& Q2,222,222), and then all
the cows perform the following process in parallel$
* )irst, each cow finds the sum of the num"ers of the other N89
cows.
* !fter all cows are finished, each cow replaces her num"er
with the sum she computed. To a#oid #ery large num"ers, the
cows will keep track of their num"ers modulo QT,SU3,IN9.
They told Oanmuu the moose a"out it in No#em"er( he was >uite impressed.
Then one foggy Ohristmas ,#e, Oanmuu came to say$ .Pour algorithm is too easy
to "reakE Pou should repeat it T (9 &- T &- 9,I9I,19N,3U1) times instead..
O"#iously, the cows were #ery frustrated with ha#ing to perform so many
repetitions of the same "oring algorithm, so after many hours of arguing,
Oanmuu and the cows reached a compromise$ Pou are to calculate the num"ers
after the encryption is performedE
*Mome extra feed"ack will "e pro#ided for the first 92 su"missions to this
pro"lem.
*NJKT )OL/!T$
* +ine 9$ Two space8separated integers$ N and T
* +ines 1..N:9$ +ine i:9 contains a single integer$ O
i
M!/J+, *NJKT (file sumsums.in)$
N I
9
2
I
*NJKT B,T!*+M$
Three cows, with starting num"ers 9, 2, and I( four repetitions of the
encryption algorithm.
OKTJKT )OL/!T$
* +ines 9..N$ +ine i contains a single integer representing the num"er of cow
i (modulo QT,SU3,IN9) at the end of the encryption.
M!/J+, OKTJKT (file sumsums.out)$
1U
13
1Q
OKTJKT B,T!*+M$
The following is a ta"le of the cowsC num"ers for each turn$
OowsC num"ers
Turn Oow9 Oow1 OowN
2 9 2 I
9 I 3 9
1 U 3 Q
N 9I 93 99
I 1U 13 1Q
+et M "e the sum of all the num"ers at the "eginning. We can construct a ta"le
of the #alue of each cowCs num"ers after each turn$
Turn Oow iCs num"er Mum of all cowsC num"ers
2 O
i
M
9 M 8 O
i
(n 8 9) * M
1 (n 8 1) * M : O
i
(n 8 9)
1
* M
N (n
1
8 Nn : N) * M : O
i
(n 8 9)
N
* M
*n particular, note that the coefficient of M in cow iCs num"er on the t8th
turn is (n 8 9)
t 8 9
8 (n 8 9)
t 8 1
: (n 8 9)
t 8 N
8 ... [ (n 8 9)
9
(n 8 9)
2
, and
the coefficient of O
i
is (89)
t
. (Foth of these statements can "e pro#en "y
induction.)
Now, all we need to do to sol#e the pro"lem is e#aluate this sum (modulo
QT,SU3,IN9). owe#er, the sum can ha#e 9 "illion terms, so we need to find an
efficient way of doing this. Two possi"le methods, that can "oth "e
implemented in O(log t), are descri"ed "elow$
The first is to e#aluate the sum somewhat directly. Note that (n 8 9)
t 8 9
8 (n
8 9)
t 8 1
: (n 8 9)
t 8 N
8 (n 8 9)
t 8 I
: ... [ (n 8 9)
9
(n 8 9)
2
- (n 8 1) * (n 8
9)
t 8 1
: (n 8 1) * (n 8 9)
t 8 I
: ..., with two possi"le endings for the sum
depending on whether t is e#en or odd. We can compute the #alue of the sum for
#alues of t that are powers of two, and then com"ine these #alues to find our
actual sum.
The second method is to find the sum using matrix powering. We note that on
each turn, the coefficient of M in each cowCs num"er is multiplied "y (n 8 9),
and then 9 is either added to the coefficient or su"tracted from it, depending
on whether t is e#en or odd. *n order to simulate this using matrix powering,
we would like to create a 18element #ector V and a 1 x 1 matrix / such that V
425 is the coefficient of M, and V 495 is either 9 or 89. /ultiplying V "y the
matrix / once should simulate one turn. *n particular, we want to multiply V
425 "y n 8 9, and then add V 495 to it, and we want to CflipC V 495 "etween 9
and 89 each time. Thus, / should "e the following matrix$
Y n 8 9 2 Y
Y Y
Y 9 89 Y
When V is multiplied "y /, V 425 "ecomes (n 8 9) * V 425 : 9 * V 495, and V
495 "ecomes 2 * # 425 : (89) * V 495, which was exactly what we wanted. Thus,
multiplying V "y / a total of t times will suffice, "ut instead we can use
efficient O(log t) matrix powering to do this.
Two solutions are presented corresponding to the two methods gi#en a"o#e. The
following is a power of two summation solution from Neal Wu$
%include &cstdio'
using namespace std(
)*+, *fin - fopen (.sumsums.in., .r.)(
)*+, *fout - fopen (.sumsums.out., .w.)(
const int /!0N - 32223, /!0+ - N3(
const int /OB - QTSU3IN9(
int N, T, nums 4/!0N5(
long long power 4/!0+5, ssum 4/!0+5(
66 computes !\(F 8 9) 8 !\(F 8 1) : ... :68 ! 86: 9
66 "y computing (! 8 9) * !\(F 8 1) : ...
66 takes O(log F) time
long long calc (int !, int F)
7
power 425 - ! < /OB(
ssum 425 - (! 8 9) < /OB(
66 power 4i5 - !\(1\i)
66 ssum 4i5 - the sum of the first 1\i terms of the second sum a"o#e
for (int i - 2( i : 9 & /!0+( i::)
7
power 4i : 95 - (power 4i5 * power 4i5) < /OB(
ssum 4i : 95 - (ssum 4i5 * power 4i : 95 : ssum 4i5) < /OB(
;
"ool odd - (F = 9)(
F ''- 9(
long long p - 9, total - 2(
for (int i - 2( (9 && i) &- F( i::)
if (F = (9 && i))
7
66 com"ine the sums for each power of two in the "inary representation of F
total - (total : ssum 4i5 * p) < /OB(
p - (p * power 4i : 95) < /OB(
;
66 do a special case for odd F
if (odd)
total - (total * ! : 9) < /OB(
return total(
;
Void main ()
7
fscanf (fin, .<d <d., =N, =T)(
long long sum - 2(
for (int i - 2( i & N( i::)
7
fscanf (fin, .<d., nums : i)(
sum :- nums 4i5(
;
sum <- /OB(
int add - (sum * calc (N 8 9, T)) < /OB(
for (int i - 2( i & N( i::)
fprintf (fout, .<d?n., (add : (T = 9 X 8nums 4i5 $ nums 4i5) : /OB) <
/OB)(
;
The following is a matrix multiplication solution from Lichard Jeng$
%include &cstdio'
%include &cstring'
%define /!0N 32222
%define / QTSU3IN9
int res415,#415415,tem415415,t,t9(
int lis4/!0N5,dif4/!0N5,n(
long long tot(
#oid mul(int a415415,int "415415)7
int i,D,k(
for(i-2(i&1(i::)
for(D-2(D&1(D::)
for(tem4i54D5-2,k-2(k&1(k::)
tem4i54D5-(tem4i54D5:(long long)a4i54k5*"4k54D5)</(
;
#oid main()7
int i(
freopen(.sumsums.in.,.r.,stdin)(
freopen(.sumsums.out.,.w.,stdout)(
scanf(.<d<d.,=n,=t)(
for(i-tot-2,2(i&n(i::)7
scanf(.<d.,=lis4i5)(
dif4i5-lis4i58lis425(
tot:-dif4i5(
;
memset(#,2,siAeof(#))(
memset(res,2,siAeof(res))(
res425-lis425</(
res495-tot</(
#425425-(n89)</(
#425495-9(
#495495-89(
for(t9-t(t9(t96-1)7
if(t9<1)7
res425-((long long)res425*#425425:(long long)res495*#425495)
</(
res495-((long long)res495*#495495)</(
;
mul(#,#)(
memcpy(#,tem,siAeof(#))(
;
for(i-2(i&n(i::)
printf(.<d?n.,((res425:((t<1--2)X(dif4i5)$(8dif4i5)))</:/)</)(;
(.e Bo6ine A''ordion and Ban7o Or'.estra "ei 0uan*$ 200%&
The 1*N (N &- N &- 9,222) cows ha#e assem"led the Fo#ine !ccordion and FanDo
OrchestraE They possess #arious le#els of skill on their respecti#e
instruments$ accordionist i has an associated talent le#el !
i
(2 &- !
i
&-
9,222)( "anDoist D has an associated talent le#el F
D
(2 &- F
D
&- 9,222).
The com"ined ]awesomenessC of a pairing "etween cows with talents !
i
and F
D
is
directly proportional to the talents of each cow in the pair so a concert with
those two cows will earn )G precisely !
i
* F
D
dollars in .charita"le
donations.. )G wishes to maximiAe the sum of all re#enue o"tained "y his cows
"y pairing them up in the most profita"le way.
Knfortunately, )GCs accordionists are a "it stuck up and stu""orn. *f
accordionist i is paired with "anDoist D, then accordionists i:9..N refuse to
"e paired with "anDoists 9..D89. This creates restrictions on which pairs )G
can form. )G thus realiAes that in order to maximiAe his profits, he may ha#e
to lea#e some cows unpaired.
To make matters worse, when one or more of the musicians is skipped, they will
"e greatly upset at their wasted talent and will engage in massi#e "inge
drinking to wash away their sorrows.
!fter all pairings are made, a list is constructed of the groups of each of
the consecuti#e skipped musicians (of either instrument). ,#ery group of one
or more consecuti#e skipped cows will gather together to consume kegs of ice
cold orange soda in an amount proportional to the s>uare of the sum of their
wasted talent.
Mpecifically, )G has calculated that if the x8th to y8th accordionists are
skipped, they will consume precisely (!
x
: !
x:9
: !
x:1
: ... : !
y
)
1
dollars worth
of orange soda in the process of drinking themsel#es into o"li#ion. !n
identical relationship holds for the "anDoists. )G realiAes that heCll end up
getting stuck with the "ill for his cowsC drinking, and thus takes this into
account when choosing which pairings to make.
)ind the maximum amount of total profit that )G can earn after the
contri"utions are collected and the orange soda is paid for.
/emory +imit$ UI/F
*NJKT )OL/!T$
* +ine 9$ ! single integer$ N
* +ines 1..N:9$ +ine i:9 contains the single integer$ !
i
* +ines N:1..1*N:9$ +ine i:N:9 contains the single integer$ F
i
M!/J+, *NJKT (file "aa"o.in)$
N
9
9
3
3
9
9
*NJKT B,T!*+M$
There are U cows$ N accordionists and N "anDoists. The accordionists ha#e
talent le#els (9, 9, 3), and the "anDoists ha#e talent le#els (3, 9, 9).
OKTJKT )OL/!T$
* +ine 9$ ! single integer that represents the maximum amount of cash that )G
can earn.
M!/J+, OKTJKT (file "aa"o.out)$
9S
OKTJKT B,T!*+M$
)G pairs accordionist N with "anDoist 9 to get earn !@N * F@9 - 3 * 3 - 13 in
profit. e loses a total of (9 : 9)\1 : (9 : 9)\1 - T dollars due to the cost
of soda for his remaining cows. Thus his final (net) profit is 13
8 T - 9S.
Mince the pairings cannot intersect, this pro"lem can "e sol#ed using BJ with
the state "eing the last CpairC of accordionist and "anDoist (denoted ! and F
from here on). This gi#es O(N
1
) states and O(N
1
) state transitions for each
state as there are O(N
1
) possi"le pre#ious pairs, the state transition
function is$
Fest(i,D)-max7i9&i,D9&DYFest(i9,D9)8MWL(sum(!@i9...!@(i89)))8
MWL(sum(F@D9...F@(D89)));:!@i*F@D
where MWL is the s>uare of a num"er.
This gi#es an O(N
I
) solution, which we try to optimiAe all the way down to
O(N
1
). The first o"ser#ation we make is we cannot skip cows in "oth ! and F
when we go from the current pair to the pre#ious one. This "ecause pairing any
two from those skipped ones will increase the total profit. Mo this gi#es an
O(n\N) solution, sufficient to get U2< of the points.
Now we try to get down to O(N
1
) "y optimiAing the state transition using
con#exity. We first consider the case where no cows in ! are skipped, or when
i9-i89. Mo we need to find$
max7D9&DYFest(i89,D)8MWL(sum(F@D9...F@(D89));:!@i*F@D
*f we let MF denote the partial sum of the F array, then our transition
formula "ecomes$
max7D9&DYFest(i89,D)8MWL(MF@(D89)8MF(D989));:!@i*F@D -max7D9&DYFest(i89,D)8
MWL(MF@(D989)):1*MF@(D989)*MF@(D89);:!@i*F@D:MWL(MF@(D89))
We can ignore the last two terms since theyCre constant depending only on i
and D. *f we look at the first term, weCre looking for the max of a linear
com"ination of two #alues depending on D9 where the ratio is dependent on D.
Heometrically, this is e>ui#alent to taking the y8intercept of a line with a
gi#en slope within a set of points. With some proof, it can "e shown that only
points on the con#ex hull matters. Mo we can insert #alues of (1*MF@D,Fest(i8
9,D)8MWL(MF@(D89)))) into the con#ex hull (note MF@D is always increasing, so
we can do this using a stack). !nd when we >uery, we can show the point where
this #alue is minimiAed6maximiAed is always monotone in respect to x. This
gi#es an algorithm that does this in O(9) amortiAed cost.
The case where nothing in F is skipped can "e dealt with similarly. The only
catch is that should we process the states in incremental i and then
incremental D, weCll need to keep track of N:9 con#ex hulls, one for the
pre#ious CrowC and one for each of the columns.
This gi#es the desired O(N
1
) algorithm.
%include &cstdio'
%include &cstring'
%define /!0N 9122
int n(
dou"le a4/!0N5,"4/!0N5,"es4/!0N54/!0N5,ans(
dou"le s94/!0N5,s14/!0N5(
dou"le s>r(dou"le x)7return x*x(;
dou"le hull4/!0N54/!0N5415(
int hullt4/!0N5,p4/!0N5(
#oid initialiAe(int id)7
hullt4id5-p4id5-2(
;
dou"le crossp(dou"le a415,dou"le "415,dou"le c415)7
return ("4258a425)*(c4958a495)8(c4258a425)*("4958a495)(
;
#oid hulladd(int id,dou"le x,dou"le y)7
dou"le point415(
point425-x(
point495-y(
if((hullt4id5'2)==(x--hull4id54hullt4id5895425))7
if(y'hull4id54hullt4id5895495) hullt4id588(
else return(
;
while((hullt4id5'9)==(crossp(point,hull4id54hullt4id5895,hull4id5
4hullt4id5815)&-2))
hullt4id588(
hull4id54hullt4id55425-x(
hull4id54hullt4id55495-y(
p4id5&X-hullt4id5(
hullt4id5::(
;
dou"le >uery(int id,dou"le a)7
dou"le tem,tem9(
tem-hull4id54p4id55425*a:hull4id54p4id55495(
while((p4id5:9&hullt4id5)==((tem9-(hull4id54p4id5:95425*a:hull4id54p4id5
:95495))'tem))7
tem-tem9(
p4id5::(
;
return tem(
;
#oid main()
7
int i,D,i9,D9(
freopen(.mkpairs.in.,.r.,stdin)(
freopen(.mkpairs.out.,.w.,stdout)(
scanf(.<d.,=n)(
for(i-2(i&n(i::) scanf(.<lf.,=a4i5)(
for(s9425-a425,i-9(i&n(i::) s94i5-s94i895:a4i5(
for(i-2(i&n(i::) scanf(.<lf.,="4i5)(
for(s1425-"425,i-9(i&n(i::) s14i5-s14i895:"4i5(
memset("es,2,siAeof("es))(
for(i-9(i&n(i::)
initialiAe(i)(
for(ans-i-2(i&n(i::)7
initialiAe(2)(
for(D-2(D&n(D::)7
"es4i54D5-8((i--2)X2$s>r(s94i895))8((D--2)X2$s>r(s14D895))(
if(i'2)7
if(D'2)7
"es4i54D5'X->uery(2,1*s14D895)8s>r(s14D895)(
"es4i54D5'X->uery(D,1*s94i895)8s>r(s94i895)(
;
hulladd(2,s14D5,"es4i8954D58s>r(s14D5))(
;
"es4i54D5:-a4i5*"4D5(
ans'X-"es4i54D58s>r(s94n8958s94i5)8s>r(s14n8958s14D5)(
;
for(D-2(D:9&n(D::)7
hulladd(D:9,s94i5,"es4i54D58s>r(s94i5))(
;
;
printf(.<2.2lf?n.,ans)(
;
(reasure "8an* 8i$ 200%&
Oanmuu and his friends ha#e recently ac>uired a large cache of plutonium and
ha#e agreed to "ury their newfound treasure at some road intersection deep in
the Oanadian wilderness. !ny sort of treasure "urial calls for a treasure map
so theyC#e decided to create one of their own.
The road network consists of N (I &- N &- 922,222) intersections (con#eniently
num"ered 9..N) with N roads connecting them. !s "usy intersections confuse
e#ery"ody, e#ery intersection has at least one road that leads to it, and no
intersection has more than four roads connected to it. ,xcellent maintenance
has ensured that a moose can always run either way "etween any pair of
intersections. )urthermore, Oanmuu has decided the plutonium should not "e
"uried at any of the I8way intersections since "usy traffic decreases the
secrecy of the "uried treasure.
The treasure map will contain all the roads and all the intersections. Fut, to
conceal the treasureCs location, only one road intersection on the treasure
map is to "e la"eled$ the intersection at which the treasure is "uried (which
has a "ig red C0C, of course).
,#er the alert moose, Oanmuu drew some trial maps to see what they would look
like depending on where the treasure was "uried. Oanmuu noticed that the moose
might draw similar maps e#en if they "ury their treasure in two different
locations. Their curiosity pi>ued, the herd "egan trying to figure out how
many distinct maps they could end up making.
/aps are indistinct if it is possi"le to assign a mapping such that$
* the 08la"eled intersections on "oth maps correspond,
* a correspondence can "e created for the other intersections,
such that
* when the well8chosen intersection correspondence is determined,
the roads that connect the intersections also correspond.
Fy way of example, consider the maps "elow where N - I( the treasure might "e
"uried at any of four intersections$
: : 0 :
6Y 6Y 6Y 6Y
0888: Y :8880 Y :888: Y :888: Y
?Y ?Y ?Y ?Y
: : : 0
The final two maps, howe#er, are not distinct since one can create a
correspondence for the #ertices (consider the map upside down) and then the
roads correspond exactly. Thus, only three maps are distinct.
ow many distinct maps are possi"le for a gi#en set of roadsX
T*/, +*/*T$ 9 second( might "e increased for "ig test cases
/,/OLP +*/*T$ UI/F
*Mome extra feed"ack will "e pro#ided for the first 92 su"missions to this
pro"lem.
JLOF+,/ N!/,$ treasure
*NJKT )OL/!T$
* +ine 9$ ! single integer$ N
* +ines 1..N : 9$ Two space8separated integers$ ! and F (9 &- ! &- N(
9 &- F &- N), indicating that there is a road connecting
intersections ! and F
M!/J+, *NJKT (file treasure.in)$
I
9 1
1 N
N 9
9 I
*NJKT B,T!*+M$
ere is a drawing of the roads and the intersections.
I88898881
? 6
N
OKTJKT )OL/!T$
* +ine 9$ ! single integer that is the num"er of distinct treasure
maps
M!/J+, OKTJKT (file treasure.out)$
N
OKTJKT B,T!*+M$
The treasure can "e "uried at any intersection. owe#er, "urying it at
intersections 1 and N yields maps that are identical to each other. Mo the
total num"er of distinct treasure maps is N.
To tackle this pro"lem most effecti#ely, we first esta"lish that the road
network descri"ed in the pro"lem is a cycle with trees Ccoming offC it. Mo we
can root all the trees "y the #ertex they ha#e on the cycle and denote nodes
"y CparentC and childrenC.
We essentially want to assign an CidC to the graph surrounding each of the
#ertices, which is a collection of se#eral su"trees (its children) and a graph
that contains the cycle.
There are two ways of doing this, either "y computing hash #alues for each
su"graph or "y computing CidsC as we proceed and only hash cyclic shifts of
the cycle. The first method is faster in practice and Dust accurate, "ut the
second is slightly easier to code due to usage of O:: MT+.
Mince a tree is a collection of its su"trees, we can assign CidCs to all the
su"trees rooted at each #ertex "y proceeding at the outermost layer and
proceed inwards.
Then we ha#e to distinguish "etween all the cyclic shifts (with reflections)
of the cycles (which is how we could CorientC the cycle with respect to the
tree the treasure is "uried in). This can "e accomplished "y the standard
La"in8Rarp string hash, done once clockwise and once counter clockwise.
Then for each distinct tree, we can Dust count the trees that ha#e distinct
ids "y going down recursi#ely, and when weCre at a node, only count its
children that ha#e distinct ids (so if two of its children ha#e the same
su"tree, only count one of them). This is correct since the CrootC is now a
special node (an orientation of the cycle).
This runs in O(N) time if hashing is used and O(NlogN) if set6map is used. The
test data were generated as follows$
Oase 9$ Mample.
Oase 1$ N chains with different lengths.
Oase N$ random tree with edge
Oase I$ random tree with edge
Oase 3$ 92 trees with !!!FFOOOFF pattern, N - 3N, the trees are specially
designed that they co#er almost e#ery simple cases.
Oase U$ 32 same trees.
Oase S$ 12 trees each with 12 nodes.
Oase T$ random tree with edge
Oase Q$ Twin fi"onacci trees.
Oase 92$ ! se>uence repeated S times.
Oase 99$ ! cycle connected with a chain.
Oase 91$ Lepeated !FO!OF! pattern.
Oase 9N$ Lepeated !F pattern, changed one F into a special "ig tree.
Oase 9I$ ! se>uence repeated U times with reflection.
Oase 93$ random tree with edge
%include &stdio.h'
%include &string.h'
%define maxn 922222
%define maxh 12222N
%define max 922222222N++
int ind4maxn5, next4maxn * 15, to4maxn * 15, p(
int n(
int used4maxn5(
int f(
int stack4maxn5, sp(
int hash4maxh5, hashans4maxh5, hp(
int hashli"4maxh54N5(
long long h94maxn5, h14maxn5(
long long hash14maxh5(
int addhash (int *data) 7
long long c - 91NI3U(
for (int i - 2( i & N( i ::)
c - c * IS \ data4i5(
c - c * IS < maxh(
while (hash4c5 E- 89 == (hashli"4c5425 E- data425 YY hashli"4c5495 E-
data495 YY hashli"4c5415 E- data415)) 7
c ::(
if (c -- maxh)
c - 2(
;
if (hash4c5 -- 89) 7
hashli"4c5425 - data425(
hashli"4c5495 - data495(
hashli"4c5415 - data415(
hash4c5 - hp ::(
;
return hash4c5(
;
int add1 (long long x, int i) 7
long long c - x < maxh(
c - c * IS < maxh(
while (hash14c5 E- 89 == hash14c5 E- x) 7
c ::(
if (c -- maxh)
c - 2(
;
if (hash14c5 -- 89) 7
hash14c5 - x(
hash4c5 - i(
return 89(
;
else
return hash4c5(
;
int test (int a, int ") 7
for (int i - 2( i & sp( i ::)
if (stack4i : a '- spX i : a 8 sp$ i : a5 E- stack4i : " '- spX i
: " 8
sp$ i : "5)
return 2(
return 9(
;
int dfs1 (int x, int dad) 7
int li"4N5, lp - 2(

for (int i - ind4x5( i E- 89( i - next4i5)
if (to4i5 E- dad == Eused4to4i55)
li"4lp ::5 - dfs1(to4i5, x)(
if (dad -- 89)
li"4lp ::5 - maxh 8 1(
while (lp & N)
li"4lp ::5 - maxh 8 9(
for (int i - 2( i & N( i ::)
for (int D - 2( D & 1( D ::)
if (li"4D5 ' li"4D : 95)
li"4D5 \- li"4D : 95 \- li"4D5 \- li"4D : 95(
lp - addhash(li")(
int ans - 2(
for (int i - 2( i & N( i ::)
if (li"4i5 E- maxh 8 9 == li"4i5 E- maxh 8 1 == (i -- 2
YY li"4i5 E-
li"4i895))
ans :- hashans4li"4i55(
if (li"415 -- maxh 8 9)
ans ::(
hashans4lp5 - ans(
return lp(
;
#oid dfs (int x, int dad) 7
if (f)
return(
if (used4x5 E- 2x),),),),) 7
f - 9(
sp - 2(
dad - to4dad5(
stack4sp ::5 - dad(
while (dad E- x) 7
dad - used4dad5(
stack4sp ::5 - dad(
;
return(
;
used4x5 - dad -- 89X 89 $ to4dad5(
for (int i - ind4x5( i E- 89( i - next4i5)
if (i E- dad)
dfs(to4i5, i\9)(
;
int main () 7
int i, a, ", c(

freopen(.cowmstr.in., .r., stdin)(
freopen(.cowmstr.out., .w., stdout)(

scanf(.<d.,=n)(
p - 2(
memset(ind, 89, siAeof(ind))(
for (i - 2( i & n( i ::) 7
scanf(.<d<d.,=a,=")(
a 88(
" 88(

next4p5 - ind4a5(
to4p5 - "(
ind4a5 - p ::(
next4p5 - ind4"5(
to4p5 - a(
ind4"5 - p ::(
;

memset(used, 81, siAeof(used))(
f - 2(
sp - 2(
dfs(2, 89)(

memset(used, 2, siAeof(used))(
for (i - 2( i & sp( i ::)
used4stack4i55 - 9(
6*
for (i - 2( i & sp( i ::)
printf(.<d?n.,stack4i5)(
fflush(stdout)(
*6

memset(hash, 89, siAeof(hash))(
hp - 2(
for (i - 2( i & sp( i ::)
stack4i5 - dfs1(stack4i5, 89)(

long long "ig - 9(
h9425 - 2(
for (i - sp 8 9( i '- 2( i 88) 7
h9425 - (h9425 * 9IST2I31N : stack4i5) < max(
"ig - "ig * 9IST2I31N < max(
;
for (i - sp 8 9( i ' 2( i 88)
h94i5 - (h94(i : 9) < sp5 * 9IST2I31N < max : stack4i5 : max 8 "ig *
stack4i5 < max) < max(

h1425 - 2(
for (i - 9( i & sp( i ::)
h1425 - (h1425 * 9IST2I31N : stack4i5) < max(
h1425 - (h1425 * 9IST2I31N : stack425) < max(
for (i - 9( i & sp( i ::)
h14i5 - (h14i 8 95 * 9IST2I31N < max : stack4i5 : max 8 "ig *
stack4i5 < max) < max(

memset(hash1, 89, siAeof(hash1))(
a - 89(
for (i - 2( a -- 89 == i & sp( i ::)
if ((" - add1(h94i5, i)) E- 89)
if (test(", i))
a - i 8 "(
if (a -- 89)
a - sp(

" - 2(
c - 2(
for (i - 2( i & sp( i ::) 7
if (h94i5 -- h14i5) 7
" Y- 9(
c - i(
;
if (h94i5 -- h14(i : 9) < sp5 == E("=9)) 7
" Y- 1(
c - (i : 9) < sp(
;
;
if (" = 9)
a - a 6 1 : 9(
else
if (" = 1)
a - a 6 1(
int ans - 2(
for (i - 2( i & a( i ::)
ans :- hashans4stack4(i : c) < sp55(

printf(.<d?n., ans)(
;
Elite 200% De'em1er Competition 'ontest
BRONZE PROBE!S
*****************************************************************************
Boo4s.el9 "Neal #u$ 200%&
)armer Gohn recently "ought a "ookshelf for cow li"rary, "ut the shelf is
getting filled up >uite >uickly, and now the only a#aila"le space is at the
top.
,ach of the N cows (9 &- N &- 12,222) has some height of
i
(9 &-
i
&-
92,222) and a total height summed across all N cows of M. The "ookshelf has a
height of F (9 &- F &- M & 1,222,222,22S).
To reach the top of the "ookshelf taller than the tallest cow, one or more of
the cows can stand on top of each other in a stack, so that their total height
is the sum of each of their indi#idual heights. This total height must "e no
less than the height of the "ookshelf. Mince more cows than necessary in the
stack can "e dangerous, your Do" is to find the set of cows that produces a
stack of the smallest num"er of cows possi"le such that the stack can reach
the "ookshelf.
*NJKT )OL/!T$
* +ine 9$ Two space8separated integers$ N and F
* +ines 1..N:9$ +ine i:9 contains a single integer$
i
M!/J+, *NJKT (file shelf.in)$
U I2
U
9T
99
9N
9Q
99
*NJKT B,T!*+M$
Mix cows( "ookshelf height I2. Oow heights fall in the range U..9Q.
OKTJKT )OL/!T$
* +ine 9$ ! single integer representing the siAe of the smallest set of cows
that can reach the "ookshelf.
M!/J+, OKTJKT (file shelf.out)$
N
OKTJKT B,T!*+M$
One way to reach I2 with N cows is 9T:99:9N( many others exist
Note that if it is possi"le to reach the "ookshelf with a certain set of O
cows, then it must "e possi"le with the O tallest cows. Thus, in order to
determine if it is possi"le to reach the "ookshelf with O cows, we must check
only the O tallest cows. Mo we can loop o#er each O in increasing order, and
find the first O that satisfies the conditions.
To do this, we must sort the num"ers in non8increasing order "eforehand in O(N
log N) time, which can "e done "y either coding the sort yourself (using an
efficient sort such as >uicksort or mergesort) or "y using the pro#ided
li"raries. !fterward, loop o#er all k from 9 to N, until we find the first k
that produces a large enough sum. We must "e careful to accumulate the sum
with our loop efficiently to a#oid ha#ing an O(N
1
) runtime.
With a properly8coded solution, the o#erall runtime will "e O(N
log
N), as the
maDority of the runtime comes from the initial sort. The following is a sample
solution$
%include &cstdio'
%include &algorithm'
using namespace std(
)*+, *fout - fopen (.shelf.out., .w.)(
)*+, *fin - fopen (.shelf.in., .r.)(
const int /!0N - 12223(
int N, F(
int heights 4/!0N5(
int sol#e () 7
int sum - 2(
for (int i - 2( i & N( i::) 7
sum :- heights 4i5(
if (sum '- F)
return i : 9(
;
return 89( 66 should not happen
;
#oid main () 7
fscanf (fin, .<d <d., =N, =F)(
for (int i - 2( i & N( i::)
fscanf (fin, .<d., heights : i)(
sort (heights, heights : N)(
re#erse (heights, heights : N)(
fprintf (fout, .<d?n., sol#e ())(
;
Boo4s.el9 2 "Neal #u$ 200%&
)armer Gohn recently "ought another "ookshelf for the cow li"rary, "ut the
shelf is getting filled up >uite >uickly, and now the only a#aila"le space is
at the top.
)G has N cows (9 &- N &- 12) each with some height of
i
(9 &-
i
&- 9,222,222
8 these are #ery tall cows). The "ookshelf has a height of F (9 &- F &- M,
where M is the sum of the heights of all cows).
To reach the top of the "ookshelf, one or more of the cows can stand on top of
each other in a stack, so that their total height is the sum of each of their
indi#idual heights. This total height must "e no less than the height of the
"ookshelf in order for the cows to reach the top.
Mince a taller stack of cows than necessary can "e dangerous, your Do" is to
find the set of cows that produces a stack of the smallest height possi"le
such that the stack can reach the "ookshelf. Pour program should print the
minimal CexcessC height "etween the optimal stack of cows and the "ookshelf.
*NJKT )OL/!T$
* +ine 9$ Two space8separated integers$ N and F
* +ines 1..N:9$ +ine i:9 contains a single integer$
i
M!/J+, *NJKT (file shelf1.in)$
3 9U
N
9
N
3
U
OKTJKT )OL/!T$
* +ine 9$ ! single integer representing the (non8negati#e) difference "etween
the total height of the optimal set of cows and the height of the shelf.
M!/J+, OKTJKT (file shelf1.out)$
9
OKTJKT B,T!*+M$
ere we use cows 9, N, I, and 3, for a total height of N : N : 3 : U - 9S. *t
is not possi"le to o"tain a total height of 9U, so the answer is 9.
To sol(e this problem, we simply nee) to look at the sums of all '
&
subsets of the numbers. This
is possible since & "# '$, an) so there are at most aroun) one million such subsets.% There are
se(eral metho)s of )oing this, but two fairly simple metho)s are the following2
The first metho) is to iterate o(er all binary numbers from $ to '
&
4 !, inclusi(e. In each binary
number, we can imagine it as ha(ing e?actly & bits similar to base !$ ')igits'%. 1 '!' in bit
number i means that we shoul) use cow i, while a '$' means that we shoul) not. Thus, each
binary number from $ to '
&
4 ! represents a subset of the & cows, an) in fact they represent e(ery
subset. This approach gi(es us a runtime of .& '
&
%.
The secon) metho) is to use recursion to generate e(ery sum. For each cow, we ha(e two
possibilities2 we either use the cow or we )on't. This gi(es us a fairly simple solution that is
.'
&
% with a me)ium o(erhea) of function calls.
<oth the bitmask an) the recursi(e solutions are presente)2
#include <cstdio>
using namespace std;
89:; (fout = fopen ("shelf6.out"& "2");
89:; (fin = fopen ("shelf6.in"& "r");
const int 9<8 = !!!!!!!!!;
const int MAX< = 6#;
int <& 0;
int heights $MAX<%;
int sum& 'est = 9<8;
void main () +
fscanf (fin& "=d =d"& .<& .0);
for (int i = !; i < <; i"")
fscanf (fin& "=d"& heights " i);
55 iterate over ever4 'itmas)
for (int mas) = !; mas) < ( << <); mas)"") +
sum = !;
55 calculate the sum of the su'set
for (int i = !; i < <; i"")
if (mas) . ( << i)) 55 is 'it num'er i setA
sum "= heights $i%;
if (sum >= 0 .. sum < 'est)
'est = sum;
/
fprintf (fout& "=d>n"& 'est 1 0);
/
#include <cstdio>
using namespace std;
89:; (fout = fopen ("shelf6.out"& "2");
89:; (fin = fopen ("shelf6.in"& "r");
const int 9<8 = !!!!!!!!!;
const int MAX< = 6#;
int <& 0;
int heights $MAX<%;
int 'est = 9<8;
void solve (int num& int sum) +
55 update our 'est value
if (sum >= 0 .. sum < 'est)
'est = sum;
55 either 2e are finished or our current sum is 2orse than the 'est so far
if (num == < BB sum >= 'est)
return;
55 t2o options 1 use the ne3t num'er or not
solve (num " & sum " heights $num%);
solve (num " & sum);
/
void main ()
+
fscanf (fin& "=d =d"& .<& .0);
for (int i = !; i < <; i"")
fscanf (fin& "=d"& heights " i);
solve (!& !);
fprintf (fout& "=d>n"& 'est 1 0);
/
Card Sta'4in* "Je)rey #an*$ 200%&
Fessie is playing a card game with her N89 (1 &- N &- 922) cow friends using a
deck with R (N &- R &- 922,222( R is a multiple of N) cards. The deck
contains / - R6N .good. cards and R8/ ."ad. cards. Fessie is the dealer and,
naturally, wants to deal herself all of the .good. cards. Mhe lo#es winning.
er friends suspect that she will cheat, though, so they de#ise a dealing
system in an attempt to pre#ent Fessie from cheating. They tell her to deal as
follows$
9. Mtart "y dealing the card on the top of the deck to the cow
to her right
1. ,#ery time she deals a card, she must place the next J (9 &-
J &- 92) cards on the "ottom of the deck( and
N. Oontinue dealing in this manner to each player se>uentially
in a counterclockwise manner
Fessie, desperate to win, asks you to help her figure out where she should put
the .good. cards so that she gets all of them. Notationally, the top card is
card %9, next card is %1, and so on.
JLOF+,/ N!/,$ cheat
*NJKT )OL/!T$
* +ine 9$ Three space8separated integers$ N, R, and J
M!/J+, *NJKT (file cheat.in)$
N Q 1
*NJKT B,T!*+M$
Fessie is playing cards with two cow friends and a deck of Q cards. Mhe must
place two cards on the "ottom of the deck each time she deals one.
OKTJKT )OL/!T$
* +ines 9../$ Jositions from top in ascending order in which Fessie
should place .good. cards, such that when dealt, Fessie will
o"tain all good cards.
M!/J+, OKTJKT (file cheat.out)$
N
S
T
OKTJKT B,T!*+M$
Fessie should put the .good. cards in positions N, S, and T. The cards will "e
dealt as follows( the card num"ers are .position in original deck.$
Oard Beck J9 J1 Fessie
*nitial configuration 9 1 N I 3 U S T Q 8 8 8 8 8 8 8 8 8
Beal top card 495 to Jlayer 9 1 N I 3 U S T Q 9 8 8 8 8 8 8 8 8
Top card to "ottom (%9 of 1) N I 3 U S T Q 1 9 8 8 8 8 8 8 8 8
Top card to "ottom (%1 of 1) I 3 U S T Q 1 N 9 8 8 8 8 8 8 8 8
Beal top card 4I5 to Jlayer 1 3 U S T Q 1 N 9 8 8 I 8 8 8 8 8
Top card to "ottom (%9 of 1) U S T Q 1 N 3 9 8 8 I 8 8 8 8 8
Top card to "ottom (%1 of 1) S T Q 1 N 3 U 9 8 8 I 8 8 8 8 8
Beal top card 4S5 to Fessie T Q 1 N 3 U 9 8 8 I 8 8 S 8 8
Top card to "ottom (%9 of 1) Q 1 N 3 U T 9 8 8 I 8 8 S 8 8
Top card to "ottom (%1 of 1) 1 N 3 U T Q 9 8 8 I 8 8 S 8 8
Beal top card 415 to Jlayer 9 N 3 U T Q 9 1 8 I 8 8 S 8 8
Top card to "ottom (%9 of 1) 3 U T Q N 9 1 8 I 8 8 S 8 8
Top card to "ottom (%1 of 1) U T Q N 3 9 1 8 I 8 8 S 8 8
Beal top card 4U5 to Jlayer 1 T Q N 3 9 1 8 I U 8 S 8 8
Top card to "ottom (%9 of 1) Q N 3 T 9 1 8 I U 8 S 8 8
Top card to "ottom (%1 of 1) N 3 T Q 9 1 8 I U 8 S 8 8
Beal top card 4N5 to Fessie 3 T Q 9 1 8 I U 8 S N 8
Top card to "ottom (%9 of 1) T Q 3 9 1 8 I U 8 S N 8
Top card to "ottom (%1 of 1) Q 3 T 9 1 8 I U 8 S N 8
Beal top card 4Q5 to Jlayer 9 3 T 9 1 Q I U 8 S N 8
Top card to "ottom (%9 of 1) T 3 9 1 Q I U 8 S N 8
Top card to "ottom (%1 of 1) 3 T 9 1 Q I U 8 S N 8
Beal top card 435 to Jlayer 1 T 9 1 Q I U 3 S N 8
Top card to "ottom (%9 of 1) T 9 1 Q I U 3 S N 8
Top card to "ottom (%9 of 1) T 9 1 Q I U 3 S N 8
Beal top card 4T5 to Fessie 8 9 1 Q I U 3 S N T
Fessie will end up with the .good cards. that ha#e "een placed in
positions N, S, and T in the original deck.
This problem is one of )ata structure manipulation. The e?plicit e?ample in the )irections shows
e(erything one nee)s to sol(e the task2
/ea) the parameters
Set up a ')ummy' )eck so you can see where the car)s en) up
;eal out the car)s accor)ing to the proce)ure making special note when <etsy's car)s go by%
Sort <etsy's positions
.utput <etsy's positions
The simplest brute force approach is simple until it comes time to Dput the top car) on the
bottomD. .ne can implement this in a few ways2
sa(e the top car), mo(e all the car)s 'up' one slot in an array, set the bottom car) to the sa(e)
top car)
a linke) list2 remo(e the hea) element an) place it on the en)
an o(ersiEe) array that is large enough to accommo)ate a large number of car)s4mo(e)4to4
bottom* keep an in)e? of the ')ecktop' an) ')eckbottom'. 0o(ing a car) to the bottom Nust
increments )ecktop an) )eckbottom while copying the first car) to the bottom.
0y solution below% uses the thir) metho) since it's pretty )arn simple to implement2
#include <stdio.h>
int cmp (int (a& int (') + return (a 1 ('; /
main () +
89:; (fin = fopen ("cheat.in"& "r");
89:; (fout = fopen ("cheat.out"& "2");
int n& )& p& i& ?;
int dec)$!!!!! ( %& dec)top& dec)'ottom& 'ets4$!!!!!%& n'ets4;
int pla4er;
fscanf (fin& "=d =d =d"& .n& .)& .p);
for (i = !; i < ); i"") dec)$i% = i;
pla4er = dec)top = !;
dec)'ottom = )1;
for (i = !; i < ); i"") + 5( ) cards to 'e dealt (5
5(printf ("deal =d to pla4er =d>n"& dec)$dec)top%"& pla4er);(5
if (pla4er == n1) 'ets4$n'ets4""% = dec)$dec)top%";
pla4er = (pla4er " ) = n;
dec)top""; 5( that card is gone (5
for (? = !; ? < p; ?"")
dec)$""dec)'ottom% = dec)$dec)top""%; 5( card to 'ottom (5
/
Csort('ets4& )5n& si,eof (int)& cmp);
for (i = !; i < )5n; i"") fprintf (fout& "=d>n"& 'ets4$i%);
e3it (!);
/
S,-ER PROBE!S
*****************************************************************************
C.arm Bra'elet ":olstad;Co<$ 2005&
Fessie has gone to the mallCs Dewelry store and spies a charm "racelet. Of
course, sheCd like to fill it with the "est charms possi"le from the N (9 &- N
&- N,I21) a#aila"le charms. ,ach charm i in the supplied list has a weight W
i
(9 &- W
i
&- I22), a Cdesira"ilityC factor B
i
(9 &- B
i
&- 922), and can "e used
at most once. Fessie can only support a charm "racelet whose weight is no
more than / (9 &- / &- 91,TT2).
Hi#en that weight limit as a constraint and a list of the charms with their
weights and desira"ility rating, deduce the maximum possi"le sum of ratings.
*NJKT )OL/!T$
* +ine 9$ Two space8separated integers$ N and /
* +ines 1...N:9$ +ine i:9 descri"es charm i with two space8separated integers$
W
i
and B
i
M!/J+, *NJKT (file charm.in)$
I U
9 I
1 U
N 91
1 S
*NJKT B,T!*+M$
)our potential charms( maximum weight U
OKTJKT )OL/!T$
* +ine 9$ ! single integer that is the greatest sum of charm
desira"ilities that can "e achie#ed gi#en the weight constraints
M!/J+, OKTJKT (file charm.out)$
1N
OKTJKT B,T!*+M$
Without the second possi"le charm, the I:91:S-1N is the highest #alue for
weight 9:1:N &- U
This is one of the classic DknapsackD problems2 'Items' with a '(alue' an) 'siEe' can be stuffe) an
integer number of times into a container of some limite) siEe with the goal of ma?imiEing the
(alue of the items inserte).
The classic solution pi(ots on a list of the best possible (alue that can be obtaine) for the set of
items so far seen. The array's subscript is 'siEe'* it's (alue is Dthe best (alue that can be obtaine)
for the items so far processe).
Initially, of course, the array's (alues are all Eero. 1))ing the first element is easy2
best(aluePitemweightQ # item(alue.
SubseCuent items are processe) one4by4one as follows. The item's weight an) (alue are
e?perimentally% a))e) to each of the 3e?isting3 weightJ(alue pairs in the best(alue array
inclu)ing the $J$ element%. If the new weightJ(alue pair is better, it replaces the ol) weight
(alue.
<y way of e?ample, consi)er the four items from the problem )escription2
! 7
' 8
9 !'
' L
The ma?imum allowe) weight is 8, so 85! elements are nee)e) in the 'best(alue' array2
$ $ $ $ $ $ $ "44 best (alue
$ ! ' 9 7 : 8 "44 for this weight subscript%
The first element weight !, (alue 7% is easy to insert2
$ 7 $ $ $ $ $ "44 best (alue
$ ! ' 9 7 : 8 "44 for this weight subscript%
The secon) element weight ', (alue 8% reCuires two a))itions. For purposes of e?planation, we
will first a)) it to the $J$ element2
M4444444M
$ 7 383 $ $ $ $ "44 best (alue
$ ! ' 9 7 : 8 "44 for this weight subscript%
an) then to the weight#! element, which currently has (alue 72
M4444444M
$ 7 8 3!$3 $ $ $ "44 best (alue
$ ! ' 9 7 : 8 "44 for this weight subscript%
Important point:It is now clear that we can run into trouble if, for instance, our weight was !. In
that case, we') be mo)ifying seCuential elements 44 elements whose new (alue shoul) be base)
on the original 'best' matri? (alue an) not the newly increase) (alues. Thus, we must either
make a new (properly copied) best matrix so modifications are made properly OR we must
modify the 'best' matrix from the larger elements to smaller
The thir) element weight 9, (alue !'% reCuires four a))itions to weights $, !, ', an) 9%. Ke will
start at weight 9 an) procee) 'backwar)s'2
M44444444444M
$ 7 8 !$ $ $ 3''3 "44 best (alue
$ ! ' 9 7 : 8 "44 for this weight subscript%
M44444444444M
$ 7 8 !$ $ 3!'3 '' "44 best (alue
$ ! ' 9 7 : 8 "44 for this weight subscript%
M44444444444M
$ 7 8 !$ 3!83 !' '' "44 best (alue
$ ! ' 9 7 : 8 "44 for this weight subscript%
In the final case, we will overwrite a now inferior 'best (alue' element2
M44444444444M
$ 7 8 3!'3 !8 !' '' "44 best (alue
$ ! ' 9 7 : 8 "44 for this weight subscript%
The fourth an) final element weight ', (alue L% will reCuire potential augmentation of all L of
the best (alues since all slots are now occupie). Korking backwar)s2
M4444444M
$ 7 8 !' !8 !' '' "44 best (alue
$ ! ' 9 7 : 8 "44 for this weight subscript%
&o mo)ifications since the aggregate weight is too large. +ikewise2
M4444444M
$ 7 8 !' !8 !' '' "44 best (alue
$ ! ' 9 7 : 8 "44 for this weight subscript%
/egular calculations an) potential mo)ifications then commence. The 8th item is o(erwritten
since !85L H '' an) so on%2
M4444444M
$ 7 8 !' !8 !' 3'93 "44 best (alue
$ ! ' 9 7 : 8 "44 for this weight subscript%
M4444444M
$ 7 8 !' !8 3!@3 '9 "44 best (alue
$ ! ' 9 7 : 8 "44 for this weight subscript%
For weight ' 5 ', the new (alue 85L#!9 is less than the current best (alue of !8, so no
mo)ification occurs2
M4444444M
$ 7 8 !' !8 !@ '9 "44 best (alue
$ ! ' 9 7 : 8 "44 for this weight subscript%
+ikewise for weight ! 5 ' no mo)ificastion occurs since 75L#!! " !'2
M4444444M
$ 7 8 !' !8 !@ '9 "44 best (alue
$ ! ' 9 7 : 8 "44 for this weight subscript%
The final weight $5' has a new best (alue2
M4444444M
$ 7 3L3 !' !8 !@ '9 "44 best (alue
$ ! ' 9 7 : 8 "44 for this weight subscript%
Ha(ing now processe) all the input, the 'best (alue' array is complete. In this case element
best(alueP8Q#'9 is the largest of all the (alues. .ne can well imagine this woul) not be the case
if, e.g., an item with weight : an) (alue !,$$$ e?iste). That might make the largest (alue appear
in some slot other than the final one i.e., if the other weights were all H !%. Thus we scan the
best (alue array to fin) the largest element, which is the highest possible (alue that can be
create) within the siEeJweight constraints.
I co)e) this task using two arrays an) inefficient copy operators2
Iinclu)e "st)io.hH
I)efine 01R !'AA$
int bestP01R5!Q, newbestP01R5!Q, nb*
main % S
FI+6 3fin # fopen Dcharm.inD, DrD%*
FI+6 3fout # fopen Dcharm.outD, DwD%*
int n, m, w, ), i, N, biggest*
fscanf fin, DT) T)D, Un, Um%*
bEero best, m5!%3siEeofint%%*
bEero newbest, m5!%3siEeofint%%*
for i # $* i " n* i55% S
fscanf fin, DT) T)D, Uw, U)%*
for N # $* N "# m* N55% S
if N !# $ UU bestPNQ ## $ VV N5w H m% continue*
nb # bestPNQ 5 )*
if nb H newbestPN5wQ% newbestPN5wQ # nb*
W
bcopy newbest, best, m5!%3siEeofint%%*
J3for N # $* N "# m* N55% printfDT') D, bestPNQ%*
printf D 44 T) T)XnD, w, )%* J3 )ebug 3J
W
biggest # bestP$Q*
for N # !* N "# m* N55%
if bestPNQ H biggest% biggest # bestPNQ*
fprintf fout, DT)XnD, biggest%*
e?it $%*
W
/ichar) ,eng, who has co)e) tasks like this many times, has e(ol(e) a more sophisticate)
solution that reCuires but one array processe) in re(erse or)er% an) uses the cool 'HY#' operator
for replacing 'impro(e)' elements. &ote that his loops are generally 'correct by construction' 44 no
nee) to check for out4of4boun)s in)ices since the loops are properly constraine). .f course his
solution is also Nust about as fast as we know how to sol(e a task like this2
Iinclu)e "cst)ioH
Iinclu)e "cstringH
int besP!'AA$Q, n, m, a, b, i, N*
int main % S
freopen Dcharm.inD, DrD, st)in%*
freopen Dcharm.outD, DwD, st)out%*
scanf DT)T)D, Un, Um%*
memset bes, $, siEeof bes%%*
for i#$* i"n* i55%S
scanf DT)T)D, Ua, Ub%*
for N#m* NH#a* N44%
besPNQHY#besPN4aQ5b*
W
printf DT)XnD, besPmQ%*
return $*
W
Buildin* Roads "Ri'.ard 0o$ 200%&
)armer Gohn had Dust ac>uired se#eral new farmsE e wants to connect the farms
with roads so that he can tra#el from any farm to any other farm #ia a
se>uence of roads( roads already connect some of the farms.
,ach of the N (9 &- N &- 9,222) farms (con#eniently num"ered 9...N) is
represented "y a position (0@i, P@i) on the plane (2 &- 0@i &- 9,222,222( 2 &-
P@i &- 9,222,222). Hi#en the preexisting / roads (9 &- / &- 9,222) as pairs
of connected farms, help )armer Gohn determine the smallest length of
additional roads he must "uild to connect all his farms.
*NJKT )OL/!T$
* +ine 9$ Two space8separated integers$ N and /
* +ines 1..N:9$ Two space8separated integers$ 0@i and P@i
* +ines N:1..N:/:1$ Two space8separated integers$ i and D, indicating
that there is already a road connecting the farm i and farm D.
M!/J+, *NJKT (file roads.in)$
I 9
9 9
N 9
1 N
I N
9 I
*NJKT B,T!*+M$
)our farms at locations (9,9), (N,9), (1,N), and (I,N). )arms 9 and I are
connected "y a road.
OKTJKT )OL/!T$
* +ine 9$ Mmallest length of additional roads re>uired to connect all
farms, printed without rounding to two decimal places. Fe sure to calculate
distances as UI8"it floating point num"ers.
M!/J+, OKTJKT (file roads.out)$
I.22
OKTJKT B,T!*+M$
Oonnect farms 9 and 1 with a road that is 1.22 units long, then connect farms
N and I with a road that is 1.22 units long. This is the "est we can do, and
gi#es us a total of I.22 unit lengths.
Ke note that since all e)ges ha(e non4negati(e weights, there will not be a cycle in the final
(ersion of the graph. Thus, this problem is eCui(alent to fin)ing the minimum spanning tree in a
graph where the e)ge weights are the 6ucli)ean )istances with the e?ception of a few whose
)istances are set to Eero%.
Se(eral minimum spanning tree algorithms can be use here. Since we're fin)ing the 0ST of a
)ense graph, the best option is probably the .nZ'% (ersion of the ,rim algorithm2
Start with the tree being a single (erte?
=eep a list of )istances of e(ery other (erte? to the tree
1t each iteration
1)) the closest (erte? to the tree
-p)ate the )istances accor)ingly.
This runs in .nZ'% time, which suffices for this problem.
<y the way2 This problem can actually be )one in .nlogn5m% time. The i)ea is basically the
e)ges that coul) potentially be in the minimum spanning tree must belong to what's known as the
;elaunay triangulation, which has .n% e)ges. Ke can fin) the ;elaunary triangulation in
.nlogn% time an) apply a fast (ersion of =ruskal's algorithm for sparse graphs to get the )esire)
runtime.
<elow is Bhinese sophomore Shi0en Ru's compact solution which might or might not match
the )escription abo(e%2
Iinclu)e "iostreamH
Iinclu)e "fstreamH
Iinclu)e "cmathH
using namespace st)*
ifstream fin Droa)s.inD%*
struct Tpoint S
long long ?, y*
W*
Tpoint pP!$!$Q*
)ouble )isP!$!$Q*
int &, 0*
int us P!$!$Q*
)ouble ans*
(oi) init %*
int fin)/oot int i%*
(oi) work %*
int main % S
FI+6 3f # fopen Droa)s.outD, DwD%*
init %*
work %*
fprintf f, DT$.'lfXnD, ans%*
return $*
W
int fin)/oot int i% S
if usPiQ ## i%
return i*
return usPiQ # fin)/oot usPiQ%*
W
(oi) init % S
fin HH & HH 0*
for int i # !* i "# &* i55%
fin HH pPiQ.? HH pPiQ.y*
for int i # $* i "# &* i55%
usPiQ # i*
for int i # $* i " 0* i55% S
int a , b, a!, b!*
fin HH a HH b*
if a! # fin)/oot a%% !# b! # fin)/oot b%%%
usPa!Q # b!*
W
W
(oi) work % S
int root, cntP!$!$Q, i)*
root # fin)/oot !%*
memset cnt, $, siEeof cnt%%*
for int i # $* i "# &* i55%
)isPiQ # !$$$$$$$.$ 3 !$$$$$$.$*
for i) # !** i)55% S
for int i # !* i "# &* i55%
if cntPiQ ## $%
if root ## fin)/oot i%%
cntPiQ # i)*
)ouble min)is # )isP$Q*
int minN # $*
for int i # !* i "# &* i55%
if cntPiQ ## i)%
for int N # '* N "# &* N55%
if cntPNQ ## $% S
)ouble )! # sCrt pPNQ.? 4 pPiQ.?% 3 pPNQ.? 4 pPiQ.?% 5
pPNQ.y 4 pPiQ.y% 3 pPNQ.y 4 pPiQ.y%%*
)isPNQ "Y # )!*
if )isPNQ " min)is% S
min)is # )isPNQ*
minN # N*
W
W
if minN ## $%
break*
int N! # fin)/oot minN%*
ans 5# min)is*
usPN!Q # root*
W
W
!ud Puddles "Je)rey #an*$ 200%&
)armer Gohn is lea#ing his house promptly at U !/ for his daily milking of
Fessie. owe#er, the pre#ious e#ening saw a hea#y rain, and the fields are
>uite muddy. )G starts at the point (2, 2) in the coordinate plane and heads
toward Fessie who is located at (0, P) (8322 &- 0 &- 322( 8322 &- P &- 322).
e can see all N (9 &- N &- 92,222) puddles of mud, located at points (!@i,
F@i) (8322 &- !@i &- 322( 8322 &- F@i &- 322) on the field. ,ach puddle
occupies only the point it is on.
a#ing Dust "ought new "oots, )armer Gohn a"solutely does not want to dirty
them "y stepping in a puddle, "ut he also wants to get to Fessie as >uickly as
possi"le. eCs already late "ecause he had to count all the puddles. *f )armer
Gohn can only tra#el parallel to the axes and turn at points with integer
coordinates, what is the shortest distance he must tra#el to reach Fessie and
keep his "oots cleanX There will always "e a path without mud that )armer Gohn
can take to reach Fessie.
*NJKT )OL/!T$
* +ine 9$ Three space8separate integers$ 0, P, and N.
* +ines 1...N:9$ +ine i:9 contains two space8separated integers$ !@i
and F@i
M!/J+, *NJKT (file mud.in)$
9 1 S
2 1
89 N
N 9
9 9
I 1
89 9
1 1
*NJKT B,T!*+M$
Fessie is at (9, 1). )armer Gohn sees S mud puddles, located at (2, 1)( (89,
N)( (N, 9)( (9, 9)( (I, 1)( (89, 9) and (1, 1). Jictorially$
I . . . . . . . .
N . / . . . . . .
P 1 . . / F / . / .
9 . / . / . / . .
2 . . * . . . . .
89 . . . . . . . .
8189 2 9 1 N I 3
0
OKTJKT )OL/!T$
* +ine 9$ The minimum distance that )armer Gohn has to tra#el to reach
Fessie without stepping in mud.
M!/J+, OKTJKT (file mud.out)$
99
OKTJKT B,T!*+M$
The "est path for )armer Gohn is (2, 2)( (89, 2)( (81, 2)( (81, 9)(
(81, 1)( (81, N)( (81, I)( (89, I)( (2, I)( (2, N)( (9, N)( and (9,
1), finally reaching Fessie.
I ******* . . . .
N * / . * . . . .
P 1 * . / F / . / .
9 * / . / . / . .
2 ***** . . . . .
89 . . . . . . . .
8189 2 9 1 N I 3
0
This is a classic 'Floo) fill' algorithm. The i)ea is that one see)s a 'floo) fill' with an initial point
followe) by massi(e recursion to fin) the points aroun) that point.
-sing a small : ? : matri? as an e?ample2
7 . . . . .
9 . . . . .
' . . 3 . .
! . . . . .
$ . . . . .
$ ! ' 9 7
one can easily imagine starting at point ',' an) then e?amining points aroun) it after marking
those points with the ')istance' from the initial point2
7 . . . . .
9 . . ! . .
' . ! 3 ! .
! . . ! . .
$ . . . . .
$ ! ' 9 7
an) then e?amining points aroun) those !'s2
7 . . ' . .
9 . ' ! ' .
' ' ! 3 ! '
! . ' ! ' .
$ . . ' . .
$ ! ' 9 7
an) so on until all )istances are )etermine)2
7V7 9 ' 9 7
9V9 ' ! ' 9
'V' ! 3 ! '
!V9 ' ! ' 9
$V7 9 ' 9 7
5444444444
$ ! ' 9 7
1))ing in obstacles Nust makes some of the )istances a bit )ifferent since certain cells can not be
use) in the recursi(e search. Here is the floo)e) (ersion of the sample input )ata2
7V 8 L A @ !$ !! !$ @
9V : 0 @ !$ !! !$ @ A
G 'V 7 : 0 < 0 !! 0 L
!V 9 0 ! 0 9 0 : 8
$V ' ! 3 ! ' 9 7 :
4!V 9 ' ! ' 9 7 : 8
544444444444444444444444
4' 4! $ ! ' 9 7 :
R
The final '!!' has not been written on to the '<' sCuare on which <essie sits, but it's clear that !!
is the answer.
The ob(ious way to implement this algorithm is so simple yet wrong%2
check?,y,)ist% S
if )ist H matri?P?,yQ% return*
matri?P?,yQ # )ist*
if (ali)subscript ?5!, y % check ?5!, y , )ist5!%*
if (ali)subscript ?4!, y % check ?4!, y , )ist5!%*
if (ali)subscript ? , y5!% check ? , y5!, )ist5!%*
if (ali)subscript ? , y4!% check ? , y4!, )ist5!%*
W
The pleasing intuiti(e bre(ity, though, is nothing but a trap. KhyY <ecause, as shown, the
subprogram will Cuickly recurse to check?5!, ...%, check ?5', ...% an) so on )own the ? a?is
instea) of the geometrically nice circular pattern e?hibite) a few paragraphs back. Kill the
algorithm still get the right answerY Ges! Is there a way to implement the algorithm that will take
longer to get to the right answerY ,robably not.
Instea), one nee)s to implement a FIF. Cueue structure so that all four of the 'ne?t elements to
search' are Cueue) before any of them is e?amine). <onus performance for knowing if an
element is alrea)y Cueue) an) thus a(oi)ing reCueueing it%. &ote that one shoul) reCueue
elements whose (alue has change) 44 but it's har)ly e(er an a)(antage to ha(e the same element
on the Cueue more than once.
Aside: queues can be nicely implemented with linked lists. Such lists are slightly tricky to get
'right the first time' and sometimes are implemented to allocate a tiny bit of storage for each
element added to the list. In contest programming, one might as well just make a big array and
circle through it. If you need more space than the array allows, you would hae needed more
linked!list space !! and failed ery late in the program's e"ecution. #etter to e"pose the potential
failure up front$
The final challenge in this task was the coor)inate scheme2 it starts at some large negati(e
number, so all subscripts nee) to be shifte) into a (ali) range. The first program below )oes this
with I)efine's* the secon) e?plicitly co)es the shift into each subscript.
0y solution is inten)e) to be straightforwar) with the tiny trick of using a bit more storage to set
up a 'bor)er' aroun) the e)ges of the matri?. This a(oi)s ha(ing to (ali)ate e(ery possible
enCueueing to ensure the subscripts will not go out of boun)s for the array2
Iinclu)e "st)io.hH
I)efine /1&>6 :$$
I)efine FI6+;i,N% fiel)Pi%5/1&>65'QPN%5/1&>65'Q
I)efine ;.&6i,N% )onePi%5/1&>65'QPN%5/1&>65'Q
I)efine [-6-6;i,N% Cueue)Pi%5/1&>65'QPN%5/1&>65'Q
short fiel)P'3/1&>65:QP'3/1&>65:Q*
char )oneP'3/1&>65:QP'3/1&>65:Q, Cueue)P'3/1&>65:QP'3/1&>65:Q*
struct C S int ?, y* W CueuePA$$$$$Q*
int nC # $, hea) # $* tail # $*
tryenC ?,y,this)ist% S
if FI6+;?,y% !# $ UU this)ist H# FI6+;?,y%% return*
if [-6-6;?,y%% return*
[-6-6;?,y% # !*
FI6+;?,y% # this)ist*
if 55nC H# L@$$$$% e?it @%*
CueuePtailQ.? # ?*
CueuePtailQ.y # y*
if 55tail H# A$$$$$% tail # $*
W
main % S
FI+6 3fin # fopen Dmu).inD, DrD%*
FI+6 3fout # fopen Dmu).outD, DwD%*
int R, G, &, i, N, 1, <*
fscanf fin, DT) T) T)D, UR, UG, U&%*
for i # $* i " &* i55% S
fscanf fin, DT) T)D, U1, U<%*
;.&61,<% # 4!*
W
J3 set up a bor)er so we )on't look outsi)e bo?2 3J
for i # 4/1&>6* i "# /1&>6* i55%
FI6+;4/1&>64!,i% # FI6+;/1&>65!,i% # FI6+;i,/1&>65!% #
FI6+;i,4/1&>64!% # 4!*
tryenC $,$,$%*
while nC% S
int ?#CueuePhea)Q.?* J3 )eCueue 3J
int y#CueuePhea)Q.y*
[-6-6;?,y% # $*
nC44*
if 55hea) H# A$$$$$% hea) # $*
J3 enCueue if nee)e)2 3J
if ;.&6?,y%% continue*
;.&6?,y% # !*
tryenC?5!, y , FI6+;?,y%5!%*
tryenC?4!, y , FI6+;?,y%5!%*
tryenC? , y5!, FI6+;?,y%5!%*
tryenC? , y4!, FI6+;?,y%5!%*
W
fprintf fout, DT)XnD, FI6+;R,G%%*
e?it $%*
W
/ichar) ,eng's solution is a bit shorter as usual%. 1mong the techniCues for compaction2
The ')ir' array of the four pairs of integers that )escribe the four potential sCuares to be newly
e?amine)
-sing array subscripts rather than an structure for storing the Cueue probably a bit more
obscure to un)erstan) if you look at the program si? months later%
.mission of tagging to pre(ent e?tra CueueingJchecking
Inclusion of negati(e elements in the '(is' array to pre(ent e?tra processing probably a big
win%
/ichar)'s program is o(er !.:? faster than the program abo(e.
Iinclu)e "cst)ioH
Iinclu)e "cstringH
short (isP!$'$QP!$'$Q, r, c, shif, CP!!$$$$$QP'Q*
int a, b, ?, y, n, tai*
int )irP7QP'Q#S4!, $, !, $, $, 4!, $, !W*
(oi) a)) int r!, int c!, int )% S
if r!H#$ UU r!"r UU c!H#$ UU c!"c UU (isPr!QPc!Q##4!% S
(isPr!QPc!Q#)*
CPtaiQP$Q#r!*
CPtaiQP!Q#c!*
tai55*
W
W
int main % S
int i, N*
freopen Dmu).inD, DrD, st)in%*
freopen Dmu).outD, DwD, st)out%*
r # !$!$* c # !$!$* shif # :$:*
tai # $*
scanf DT)T)T)D, U?, Uy, Un%*
for i # $* i " r* i55%
for N # $* N " c* N55%
(isPiQPNQ # 4!*
for i # $* i " n* i55%S
scanf DT)T)D, Ua, Ub%*
(isPa5shifQPb5shifQ # 4'*
W
tai # $*
a)) shif, shif, $%*
for i # $* i " tai* i55%
for N # $* N " 7* N55%
a)) CPiQP$Q5)irPNQP$Q, CPiQP!Q5)irPNQP!Q, (isPCPiQP$QQPCPiQP!QQ5!%*
printf DT)XnD, (isP?5shifQPy5shifQ%*
return $*
W
/OD PROBE!S
33333333333333333333333333333333333333333333333333333333333333333333333333333
Si*.tseein* Co+s "Reid Barton$ 200%&
Farmer John has )eci)e) to rewar) his cows for their har) work by taking them on a tour of the big city! The cows
must )eci)e how best to spen) their free time.
Fortunately, they ha(e a )etaile) city map showing the + ' "# + "# !$$$% maNor lan)marks con(eniently
numbere) !.. +% an) the , ' "# , "# :$$$% uni)irectional cow paths that Noin them. Farmer John will )ri(e the
cows to a starting lan)mark of their choice, from which they will walk along the cow paths to a series of other
lan)marks, en)ing back at their starting lan)mark where Farmer John will pick them up an) take them back to the
farm. <ecause space in the city is at a premium, the cow paths are (ery narrow an) so tra(el along each cow path is
only allowe) in one fi?e) )irection.
Khile the cows may spen) as much time as they like in the city, they )o ten) to get bore) easily. Misiting each new
lan)mark is fun, but walking between them takes time. The cows know the e?act fun (alues FFi ! "# FFi "# !$$$%
for each lan)mark i.
The cows also know about the cowpaths. Bowpath i connects lan)mark +!Fi to +'Fi in the )irection +!Fi 4H +'Fi%
an) reCuires time TFi ! "# TFi "# !$$$% to tra(erse.
In or)er to ha(e the best possible )ay off, the cows want to ma?imiEe the a(erage fun (alue per unit time of their
trip. .f course, the lan)marks are only fun the first time they are (isite)* the cows may pass through the lan)mark
more than once, but they )o not percei(e its fun (alue again. Furthermore, Farmer John is making the cows (isit at
least two lan)marks, so that they get some e?ercise )uring their )ay off.
Help the cows fin) the ma?imum fun (alue per unit time that they can achie(e.
I&,-T F./01T2
3 +ine !2 Two space4separate) integers2 + an) ,
3 +ines '..+5!2 +ine i5! contains a single one integer2 FFi
3 +ines +5'..+5,5!2 +ine +5i5! )escribes cow path i with three space4separate) integers2 +!Fi, +'Fi, an) TFi
S10,+6 I&,-T file sightsee.in%2
: L
9$
!$
!$
:
!$
! ' 9
' 9 '
9 7 :
9 : '
7 : :
: ! 9
: ' '
.-T,-T F./01T2
3 +ine !2 1 single number gi(en to two )ecimal places )o not perform e?plicit roun)ing%, the ma?imum
possible a(erage fun per unit time, or $ if the cows cannot plan any trip at all in accor)ance with the abo(e rules.
S10,+6 .-T,-T file sightsee.out%2
8.$$
.-T,-T ;6T1I+S2
The trip ! 4H ' 4H 9 4H : 4H ! has a total fun (alue of 8$ an) a length of !$ units for an a(erage fun per unit time of
8. The trip ' 4H 9 4H : 4H ' only has an a(erage fun per unit time of 9$J8 # :, an) any trip in(ol(ing lan)mark 7 has
an a(erage fun per unit time of less than 7.
This pro"lem in#ol#es a graph in which each edge e has an associated length
+(e) and fun #alue )(e). Our goal is to find a directed cycle O minimiAing
+(O) 6 )(O), where +(O) denotes the total length of all edges in O and )(O)
denotes the total fun #alue of all edges in O (note$ the actual pro"lem asks
us to maximiAe )(O) 6 +(O), "ut *C#e con#erted it to a minimiAation pro"lem
since this is more common when we discuss shortest path type pro"lems).
To sol#e this pro"lem >uickly, we employ a common trick$ "inary search on the
answer. +et us make a guess that the answer is 0. Fy running one instance of
the Fellman8)ord shortest path algorithm (in O(+J) time), we will "e a"le to
tell if this guess is too high or too low, there"y homing in on the correct
answer. The one feature of the Fellman8)ord algorithm we use here is the fact
that it can detect whether or not a negati#e8length direct cycle exists in a
graph (we wonCt go into how this is done here, since this is a common
algorithm).
ow can negati#e cycle detection tell us if our guess 0 is too high or too
lowX Well, we would like to check if the minimum #alue of +(O)6)(O) o#er all
cycles O is less than 0 (i.e., if there exists a cycle O such that +(O)6)(O)
&- 0). *f so, then our guess is too high( otherwise it is too low. Fut asking
whether there exists a cycle O such that +(O)6)(O) &- 0 is the same as asking
whether there exists a cycle O such that +(O) &- 0 )(O), which is the same as
asking whether there exists a cycle O such that +(O) 8 0 )(O) &- 2. Mo if we
define the cost of each edge e as ^(e) - +(e) 8 0 )(e), then this turns into a
negati#e cycle detection pro"lem with respect to the ^(e)CsE
Felow is Ohinese Gunior Ban>i OhenCs full8credit "eautifully formatted J!MO!+
solution (this is precisely as she su"mitted it) which might or might not
match the description a"o#e.
program sightsee(
const
finp - Csightsee.inC(
fout - Csightsee.outC(
maxn - 9222 : 3(
eps - 9e8I(
type
nodeptr - \node(
node - record
p, len $ longint(
next $ nodeptr(
end(
#ar
hash $ array 49 .. maxn5 of "oolean(
>ueue, edge $ array 49 .. maxn5 of longint(
dist $ array 49 .. maxn5 of extended(
a $ array 49 .. maxn5 of nodeptr(
cost $ array 49 .. maxn5 of longint(
n, m $ longint(
procedure create(x, y, c $ longint)(
#ar
tmp $ nodeptr(
"egin
new(tmp)( tmp \.p $- y( tmp \. len $- c(
tmp \.next $- a4x5( a4x5 $- tmp(
end(
procedure init(
#ar
i $ longint(
x, y, c $ longint(
"egin
read(n, m)(
for i $- 9 to n do read(cost4i5)(
for i $- 9 to n do a4i5 $- nil(
for i $- 9 to m do
"egin
read(x, y, c)(
create(x, y, c)(
end(
end(

function nxt(i $ longint)$ longint(
"egin
if i - maxn then nxt $- 9 else nxt $- i : 9(
end(
function check(limit $ extended)$ "oolean(
#ar
h, t, i $ longint(
tmp $ nodeptr(
# $ extended(
"egin
check $- true(
fillchar(hash, siAeof(hash), false)(
h $- 2( t $- 2(
for i $- 9 to n do
"egin
inc(t)( >ueue4t5 $- i( hash4i5 $- true(
dist4i5 $- 2( edge4i5 $- 2(
end(
while (h &' t) do
"egin
h $- nxt(h)(
tmp $- a4>ueue4h55(
while (tmp &' nil) do
"egin
# $- tmp \. len * limit 8 cost4tmp\.p5(
if (dist4>ueue4h55 : # & dist4tmp\.p5) then
"egin
dist4tmp\.p5 $- dist4>ueue4h55 : #(
edge4tmp\.p5 $- edge4>ueue4h55 : 9(
if edge4tmp \. p5 ' n then exit(
if not hash4tmp\.p5 then
"egin
t $- nxt(t)(
>ueue4t5 $- tmp\. p(
hash4tmp \.p5 $- true(
end(
end(
tmp $- tmp \. next(
end(
hash4>ueue4h55 $- false(
end(
check $- false(
end(
procedure work(
#ar
l, r, mid $ extended(
"egin
l $- 2( r $- 9222(
while (r 8 l ' eps) do
"egin
mid $- (l : r) 6 1(
if check(mid) then l $- mid else r $- mid(
end(
writeln(l $ 2 $ 1)(
end(
"egin
assign(input, finp)( reset(input)(
assign(output, fout)( rewrite(output)(
init(
work(
close(input)( close(output)(
end.
/ourmet /ra=ers "Ale< S'.+endner$ 200%&
+ike so many others, the cows ha(e )e(elope) (ery haughty tastes an) will no longer graEe on Nust any grass.
Instea), Farmer John must purchase gourmet organic grass at the >reen >rass >rocers store for each of his & ! "#
& "# !$$,$$$% cows.
6ach cowFi )eman)s grass of price at least 1Fi ! "# 1Fi "# !,$$$,$$$,$$$% an) with a greenness score at least <Fi
! "# <Fi "# !,$$$,$$$,$$$%. The >>> store has 0 ! "# 0 "# !$$,$$$% )ifferent types of grass a(ailable, each
with a price BFi ! "# BFi "# !,$$$,$$$,$$$% an) a greenness score of ;Fi ! "# ;Fi "# !,$$$,$$$,$$$%. .f course,
no cow woul) sacrifice her in)i(i)uality, so no two cows can ha(e the same kin) of grass.
Help Farmer John satisfy the cows' e?pensi(e gourmet tastes while spen)ing as little money as is necessary.
I&,-T F./01T2
3 +ine !2 Two space4separate) integers2 & an) 0.
3 +ines '..&5!2 +ine i5! contains two space4separate) integers2 1Fi an) <Fi
3 +ines &5'..&505!2 +ine i5&5! contains two space4separate) integers2 BFi an) ;Fi
S10,+6 I&,-T file gourmet.in%2
7 L
! !
' 9
! 7
7 '
9 '
' !
7 9
: '
: 7
' 8
7 7
.-T,-T F./01T2
3 +ine !2 1 single integer which is the minimum cost to satisfy all the cows. If that is not possible, output 4!.
S10,+6 .-T,-T file gourmet.out%2
!'
.-T,-T ;6T1I+S2
Bow ! eats grass ' at cost ', cow ' eats grass 9 at cost 7, cow 9 eats grass 8 at cost ', an) cow 7 eats grass L at cost
7, for a total cost of !'.
The greedy solution works for this task. The first o"ser#ation is if we sort
the re>uests and grasses "y decreasing order of green8ness, the set of grass
we need to consider for each re>uest is precisely the set of all grass that
hasnCt "een used yet that has a higher greenness. Mo we can add grasses to the
set as we CsweepC "y them and remo#e the grasses as we use them.
+etCs Dust consider the prices. The claim is that at each moment, we can pick
the cheapest grass that will satisfy the cow. This is true since suppose we
pick a more expensi#e grass and use the cheaper one later, we can swap the
choices while keeping "oth cows satisfied without increasing the total cost.
Now the pro"lem "ecomes a data structure pro"lem, we need to support the
following operations$ insertion, deletion, find the first element with key
"igger than a gi#en #alue and we want to do each operation in O(logn) time.
This can "e done using MT+ set. *tCs also possi"le to do this without MT+
using a "inary index tree "y first assigning #alues from 9 to n to the prices,
then construct a full "inary tree with the prices at leafs and track on each
node whether the su"tree "elow has #alues. Foth gi#e O(nlogn) solutions.
Felow is an extraordinarily compact full8credit solution su"mitted "y
FelarusCs Hennady Rorotke#ich$
%include &iterator'
%include &fstream'
%include &#ector'
%include &algorithm'
%include &set'
%define @@intUI long long
using namespace std(
#ector & pair &int,int' ' c,f(
set & pair &int,int' ' a(
int main () 7
)*+, *in - fopen (.gourmet.in.,.r.)(
)*+, *out - fopen (.gourmet.out.,.w.)(
int n, m, i, >, w(
fscanf (in, .<d<d., =n, =m)(
for (i-2( i&n( i::) 7
fscanf (in, .<d<d., =>, =w)(
c.push@"ack (make@pair (w, >))(
;
for (i-2( i&m( i::) 7
fscanf (in, .<d<d., =>, =w)(
f.push@"ack (make@pair (w, >))(
;
sort (c."egin (), c.end ())(
sort (f."egin (), f.end ())(
int r - m 8 9(
@@intUI ans - 2(
a.clear ()(
for (i-n89(i'-2(i88) 7
while (9) 7
if (r & 2) "reak(
if (f4r5.first '- c4i5.first) 7
a.insert (make@pair (f4r5.second, r))(
r88(
;
else "reak(
;
set& pair &int,int' '$$iterator d -
a.lower@"ound (make@pair (c4i5.second, 89))(
if (d -- a.end ()) 7
fprintf (out, .89?n.)(
return 2(
;
ans :- (*d).first(
a.erase (d)(
;
fprintf (out, .<+d?n., ans)(
return 2(
;
Best Co+ ine$ /old "C.ristos (=amos$ 200%&
FJ is about to take his & ! "# & "# 9$,$$$% cows to the annual DFarmer of the GearD competition. In this contest
e(ery farmer arranges his cows in a line an) her)s them past the Nu)ges.
The contest organiEers a)opte) a new registration scheme this year2 simply register the initial letter of e(ery cow in
the or)er they will appear e.g., If FJ takes <essie, Syl(ia, an) ;ora in that or)er, he Nust registers <S;%. 1fter the
registration phase en)s, e(ery group is Nu)ge) in increasing le?icographic or)er i.e., alphabetical or)er% accor)ing
to the string of the initials of the cows' names.
FJ is (ery busy this year an) has to hurry back to his farm, so he wants to be Nu)ge) as early as possible. He )eci)es
to rearrange his cows, who ha(e alrea)y line) up, before registering them.
FJ marks a location for a new line of the competing cows. He then procee)s to marshal the cows from the ol) line to
the new one by repeate)ly sen)ing either the first or last cow in the remain)er of the% original line to the en) of the
new line. Khen he's finishe), FJ takes his cows for registration in this new or)er.
>i(en the initial or)er of his cows, )etermine the least le?icographic string of initials he can make this way.
,/.<+60 &1062 bclgol)
I&,-T F./01T2
3 +ine !2 1 single integer2 &
3 +ines '..&5!2 +ine i5! contains a single initial '1'..'\'% of the cow in the ith position in the original line
S10,+6 I&,-T file bclgol).in%2
8
1
B
;
<
B
<
I&,-T ;6T1I+S2
FJ has 8 cows in this or)er2 1B;<B<
.-T,-T F./01T2
The least le?icographic string he can make. 6(ery line e?cept perhaps the last one% contains the initials of A$ cows
'1'..'\'% in the new line.
S10,+6 .-T,-T file bclgol).out%2
1<B<B;
.-T,-T ;6T1I+S2
Step .riginal &ew
I! 1B;<B<
I' B;<B< 1
I9 B;<B 1<
I7 B;< 1<B
I: B; 1<B<
I8 ; 1<B<B
IL 1<B<B;
This problem can be sol(e) with )ynamic programming on the inter(als of cows but there is also a simple gree)y
strategy.
<etween the two cows in the e)ges, you must always pick the cow with the smallest initial letter. If both cows ha(e
the same initial letter in or)er to )eci)e you must look a little bit )eeper an) check the secon) cows in the line's
e)ges or the thir) ones if those are eCual an) so on until you fin) two cows that are )ifferent. Then you pick the cow
from the si)e of the smallest one.
This process can be summariEe) as follows.
1t any gi(en inter(al Pa,bQ with string SPa,bQ% you choose2
Bow a if SPa,bQ% " re( SPa,bQ% %
Bow b otherwise
where re(S% is the re(erse string e.g. re(DabcD% # DcbaD
This can be implemente) in .&Z'% but we can achie(e .&log&% by using suffi? arrays.
Here are the two implementations2
The .&Z'%
Iinclu)e"cst)ioH
char SP'$!$Q,ln#$*
(oi) prntchar a% S
ifln##A$% SprintfDXnD%*ln#$*W
printfDTcD,a%*ln55*
W
int main% S
int i,N,&,pi,pN,(al*
freopenDbcl.inD ,DrD,st)in %*
freopenDbcl.outD,DwD,st)out%*
scanfDT)D,U&%*
fori#$*i"&*i55% scanfD Tc D,S5i%*
i#$,N#&4!*
whilei"#N% S
ifSPiQ"SPNQ% SprntSPiQ%*i55*W
else ifSPiQHSPNQ% SprntSPNQ%*N44*W
else S
pi#i5!*pN#N4!*(al#SPiQ*
while pN4piH! UU SPpiQ##SPpNQ% Spi55,pN44*W
ifSPpiQ"SPpNQ% prntSPiQ%,i55*
else prntSPNQ%,N44*
W
W
printfDXnD%*
return $*
W
1n) the .&log&%
Iinclu)e"cst)ioH
Iinclu)e"cstringH
Iinclu)e"cst)libH
I)efine 01R& :$$$:$
char SP'301R&Q*
int &,ln#$*
int oP'QP'301R&Q, tP'301R&QP'Q*
int 1P'301R&Q, <P'301R&Q, BP'301R&Q, ;P'301R&Q*
(oi) prntchar a% S
ifln##A$% SprintfDXnD%*ln#$*W
printfDTcD,a%*ln55*
W
int main% S
int i, N, NN, ?, k*
freopenDbcl.inD ,DrD,st)in %*
freopenDbcl.outD,DwD,st)out%*
scanfDT)D,U&%*
fori#$*i"&*i55% S
scanfD Tc D,S5i%*
SP&5iQ # SPiQ*
W
memset1, $, siEeof1%%*
for i # $* i " '3&* 55i% 1Pint%SPiQ4'1'%Q # !*
for i # !* i " '8* 55i% 1PiQ 5# 1Pi4!Q*
for i # $* i " '3&* 55i% oP$QPiQ # 1Pint%SPiQ4'1'%Q*
?#$*
for N # $, NN # !, k # $* NN " & UU k " '3&* 55N, NN ""# !% S
memset1, $, siEeof1%%*
memset<, $, siEeof<%%*
for i # $* i " &* 55i% S
551P tPiQP$Q # oP?QPiQ Q*
55<P tPiQP!Q # i5NN"&% Y oP?QPi5NNQ 2 $ Q*
W
for i # &* i " '3&* 55i% S
551P tPiQP$Q # oP?QPiQ Q*
55<P tPiQP!Q # i4NNH#&% Y oP?QPi4NNQ 2 $ Q*
W
for i # !* i "# '3&* 55i% S
1PiQ 5# 1Pi4!Q*
<PiQ 5# <Pi4!Q*
W
for i # '3&4!* i H# $* 44i%
BP44<PtPiQP!QQQ # i*
for i # '3&4!* i H# $* 44i%
;P441PtPBPiQQP$QQQ # BPiQ*
? Z# !*
oP?QP;P$QQ # k # !*
for i # !* i " '3&* 55i%
oP?QP;PiQQ # k 5# tP;PiQQP$Q !# tP;Pi4!QQP$Q VV tP;PiQQP!Q !# tP;Pi4!QQP!Q%%*
W
i#$,N#&4!*
whilei"#N% S
ifSPiQ"SPNQ% SprntSPiQ%*i55*W
else ifSPiQHSPNQ% SprntSPNQ%*N44*W
else ifoP?QPiQ"oP?QP&5NQ% SprntSPiQ%*i55*W
else SprntSPNQ%*N44*W
W
printfDXnD%*
return $*
W
Elite 200% No6em1er Competition 'ontest
BRONZE PROBE!S
**********************************************************************
E<ploration "Je)rey #an*$ 200%&
Fessie is tra#eling on a road teeming with interesting landmarks. The road is
la"eled Dust like a num"er line, and Fessie starts at the .origin. (x - 2). !
total of N (9 &- N &- 32,222) landmarks are located at points x@9, x@1, ...,
x@N (8922,222 &- x@i &- 922,222). Fessie wants to #isit as many landmarks as
possi"le "efore sundown, which occurs in T (9 &- T &- 9,222,222,222) minutes.
Mhe tra#els 9 distance unit in 9 minute.
Fessie will #isit the landmarks in a particular order. Mince the landmarks
closer to the origin are more important to )armer Gohn, she always heads for
the un#isited landmark closest to the origin. No two landmarks will "e the
same distance away from the origin.
elp Fessie determine the maximum num"er of landmarks she can #isit "efore the
day ends.
*NJKT )OL/!T$
* +ine 9$ Two space8separated integers$ T and N
* +ines 1..N:9$ +ine i:9 contains a single integer that is the
location of the ith landmark$ x@i
M!/J+, *NJKT (file explore.in)$
13 3
92
8N
T
8S
9
*NJKT B,T!*+M$
Fessie has 13 minutes "efore sundown, and there are 3 landmarks located at
positions 92, 8N, T, 8S, and 9.
OKTJKT )OL/!T$
* +ine 9$ The maximum num"er of landmarks Fessie can #isit.
M!/J+, OKTJKT (file explore.out)$
I
OKTJKT B,T!*+M$
Fessie se>uentially #isits the landmarks at locations 9, 8N, 8S, and T, after
which she has tra#eled a total of 1I minutes. Mhe cannot #isit the next
intended landmark at position 92, since this would extend her total tra#el
time to 1U minutes.
This is another Cad hocC pro"lem$ no generic algorithm. *t was intended to "e
the easy pro"lem "ut ended ranked the most difficult. * expect many folks read
far more into it than was re>uired.
This is not an optimiAation pro"lem (it is not one where you find an optimal
route). The route procedure was explicit$ #isit the next un#isited node that
is closest to the origin. We know that in one dimension, distance is the
a"solute #alue "etween two points so the distance to the origin for point ^ is
Dust Y^Y, the a"solute #alue of ^.
Thus, the pro"lem de#ol#es into finding the route (sorting the a"solute #alue
of the input data) and then simulating the tra#ersal (i.e., #isit successi#e
landmarks until the time runs out). The pro"lem was unclear a"out whether the
time limit was & T or &- T, "ut the test data did not exploit this.
The only Ctricky partC is that the data was chosen such that an O(N
1
) sort
would not succeed on the largest test cases. One needed to in#oke a system
sort (e.g., >sort) or include a CgoodC sort in the su"mitted program.
Felow is my straightforward solution$
%include &stdio.h'
%include &stdli".h'
a"s(i) 7 return i & 2 X 8i$i( ;
int compare@a"s(int *a, int *") 7
return a"s(*a) 8 a"s(*")(
;
int list4322225(
main() 7
)*+, *fin - fopen (.explore.in., .r.)(
)*+, *fout - fopen (.explore.out., .w.)(
int T, N, i, D, "essloc, n#isit, time#isit(
fscanf (fin, .<d <d., =T, =N)(
for (i - 2( i & N( i::)
fscanf (fin, .<d., =list4i5)(
>sort (list, N, siAeof(int), compare@a"s)(
6* start #isiting$ *6
"essloc - 2(
n#isit - 2(
time#isit - 2(
for (i - 2( i & N( i::) 7
time#isit :- a"s(list4i5 8 "essloc)(
if (time#isit ' T) "reak(
n#isit::(
"essloc - list4i5(
;
fprintf (fout, .<d?n., n#isit)(
exit (2)(
;
Speed Readin* "Je)rey #an*$ 200%&
!ll R (9 &- R &- 9,222) of the cows are participating in )armer GohnCs annual
reading contest. The competition consists of reading a single "ook with N (9
&- N &- 922,222) pages as fast as possi"le while understanding it.
Oow i has a reading speed M@i (9 &- M@i &- 922) pages per minute, a maximum
consecuti#e reading time T@i (9 &- T@i &- 922) minutes, and a minimum rest
time L@i (9 &- L@i &- 922) minutes. The cow can read at a rate of M@i pages
per minute, "ut only for T@i minutes at a time. !fter she stops reading to
rest, she must rest for L@i minutes "efore commencing reading again.
Betermine the num"er of minutes (rounded up to the nearest full minute) that
it will take for each cow to read the "ook.
*NJKT )OL/!T$
* +ine 9$ Two space8separated integers$ N and R
* +ines 1..R:9$ +ine i:9 contains three space8separated integers$ M@i,
T@i, and L@i
M!/J+, *NJKT (file read.in)$
92 N
1 I 9
U 9 3
N N N
*NJKT B,T!*+M$
The "ook has 92 pages( N cows are competing. The first cow reads at a rate of
1 pages per minute, can read for at most I minutes at a time, and must rest
for 9 minute after reading. The second reads at a rate of U pages per minute,
can read for at most 9 minute at a time, and must rest 3 minutes after
reading. The last reads at a rate of N pages per minute, can read for at most
N minutes at a time, and must rest for N minutes after reading.
OKTJKT )OL/!T$
* +ines 9..R$ +ine i should indicate how many minutes (rounded up to
the nearest full minute) are re>uired for cow i to read the whole "ook.
M!/J+, OKTJKT (file read.out)$
U
S
S
OKTJKT B,T!*+M$
The first cow can read T pages in I minutes, rest for 9 minute, and read the
last 1 pages in a minute. The second reads U pages in a minute, rests for 3
minutes, and finishes in the next minute. The last reads Q pages in N minutes,
rests for N minutes, and finishes in the next minute.
This is an Cad hocC programming pro"lem$ Dust Cfigure it outC and make it
work. No commonly used algorithm or anything like that.
* personally read this as a sort of CsimulationC pro"lem so * wrote the simple
solution that would simulate whatCs going on in a step8"y8step way. * ran a
counter for the minutes and reduced the num"er of pages remaining "y the speed
for each minute that went "y (and incremented the "usy counter so *Cd know
when to rest). When it was time to rest, * incremented the minutes so that
resting would take place and then reset my "usy counter. * think the solution
is simple 88 and it surely runs >uickly enough$
%include &stdio.h'
%include &stdli".h'
main() 7
)*+, *fin - fopen (.read.in., .r.)(
)*+, *fout - fopen (.read.out., .w.)(
int N, R, speed, timex, rest, i, t, minutes, pages, "usy(
fscanf(fin, .<d <d., =N, =R)(
for (i - 2( i & R( i::) 7
fscanf (fin, .<d <d <d., =speed, =timex, =rest)(
pages - N(
"usy - 2(
for (minutes - 9( ( minutes::) 7
pages 8- speed(
"usy::(
if (pages &- 2) "reak(
if ("usy -- timex) 7
minutes :- rest(
"usy - 2(
;
;
fprintf (fout, .<d?n., minutes)(
;
exit (2)(
;
Lichard Jeng (and a host of others), on the other hand, created tricky (in my
opinion) formulae that would yield the answer at least somewhat directly (at
least without looping). One of these solutions is "elow. Knfortunately,
another coach who tried the same thing got wrong answers on some of the cases.
alf those who su"mitted solutions to this pro"lem missed the final test case(
it appears at least some of them tried the trickier math procedures.
ereCs LichardCs compact >uick solution$
%include &cstdio'
int ans, n, r, s, t(
int main() 7
int ct(
freopen (.read.in., .r., stdin)(
freopen (.read.out., .w., stdout)(
scanf (.<d<d., =n, =ct)(
while (ct88) 7
scanf (.<d<d<d., =r, =s, =t)(
ans - (s:t)*(n6(r*s))(
if( n<(r*s)--2 == nE-2) ans 8- t(
ans :- ((n<(r*s)):r89)6r(
printf(.<d?n.,ans)(
;
return 2(
;
A6oid (.e a4es "Je)rey #an*$ 200%&
)armer GohnCs farm was flooded in the most recent storm, a fact only
aggra#ated "y the information that his cows are deathly afraid of water. is
insurance agency will only repay him, howe#er, an amount depending on the siAe
of the largest .lake. on his farm.
The farm is represented as a rectangular grid with N (9 &- N &- 922) rows and
/ (9 &- / &- 922) columns. ,ach cell in the grid is either dry or su"merged,
and exactly R (9 &- R &- N*/) of the cells are su"merged. !s one would expect,
a lake has a central cell to which other cells connect "y sharing a long edge
(not a corner). !ny cell that shares a long edge with the central cell or
shares a long edge with any connected cell "ecomes a connected cell and is
part of the lake.
*NJKT )OL/!T$
* +ine 9$ Three space8separated integers$ N, /, and R
* +ines 1..R:9$ +ine i:9 descri"es one su"merged location with two
space separated integers that are its row and column$ L and O
M!/J+, *NJKT (file lake.in)$
N I 3
N 1
1 1
N 9
1 N
9 9
*NJKT B,T!*+M$
The farm is a grid with three rows and four columns( fi#e of the cells are
su"merged. They are located in the positions (row N, column 1)( (row 1, column
1)( (row N, column 9)( (row 1, column N)( (row 9, column 9)$
% . . .
. % % .
% % . .
OKTJKT )OL/!T$
* +ine 9$ The num"er of cells that the largest lake contains.
M!/J+, OKTJKT (file lake.out)$
I
OKTJKT B,T!*+M$
The largest lake consists of the inputCs first four cells.
This is one of the incarnations of the a"solute classic Cflood fillC pro"lems.
The goal is to figure out which s>uares are I8connected (no diagonals) to a
gi#en s>uare.
The solution relies on simple scanning of the ClakeC looking for water spots.
When one is found, a count is commenced for that spot and, recursi#ely, its
neigh"ors (see the four in#ocations of ClsiAeC inside ClsiAeC itself). ,ach
spot that is scanned is marked so that scanning will not "e attempted for that
spot again. Thus, the algorithm is linear in the num"er of s>uares scanned,
O(L*O).
One can implement a >ueue for scanning (a sort of C"readth8firstC approach) or
use simple recursion as the solution "elow indicates. Mimple recursion works
"ecause the CmarkingC occurs "efore any of the recursi#e calls, each of which
is conditional on checking the CmarkingC.
The solution here is cle#er in that it creates a "uffer Aone of CmarkedC
(i.e., 28#alued) s>uares around the input matrix. Thus no range8 or "ounds8
checking is re>uired to ensure that the test for I8connectedness stays in the
legal range.
ere is coach Br. Frian BeanCs solution$
%include &stdio.h'
%include &stdli".h'
%define /!0(a,") ((a) ' (") X (a) $ ("))
%define /!0@N 922
int N, /, R, map4/!0@N:154/!0@N:15(
int lsiAe(int i, int D) 7
int a - 9( 6* this s>uare gets single count *6
map4i54D5 - 2(
if (map4i54D895) a :- lsiAe(i,D89)(
if (map4i54D:95) a :- lsiAe(i,D:9)(
if (map4i8954D5) a :- lsiAe(i89,D)(
if (map4i:954D5) a :- lsiAe(i:9,D)(
return a(
;
int main(#oid) 7
)*+, *fp(
int i, D, k, "est-2(
fp - fopen (.lake.in., .r.)(
fscanf (fp, .<d <d <d., =N, =/, =R)(
for (k-2( k&R( k::) 7
fscanf (fp, .<d <d., =i, =D)(
map4i54D5 - 9(
;
fclose (fp)(
for (i-9( i&-N( i::)
for (D-9( D&-/( D::)
if (map4i54D5)
"est - /!0 ("est, lsiAe(i,D))(
fp - fopen (.lake.out., .w.)(
fprintf (fp, .<d?n., "est)(
fclose (fp)(
return 2(
;
S,-ER PROBE!S
*****************************************************************************

Co+ 0urdles "Neal #u$ 200%&
)armer Gohn wants the cows to prepare for the county Dumping competition, so
Fessie and the gang are practicing Dumping o#er hurdles. They are getting
tired, though, so they want to "e a"le to use as little energy as possi"le to
Dump o#er the hurdles.
O"#iously, it is not #ery difficult for a cow to Dump o#er se#eral #ery short
hurdles, "ut one tall hurdle can "e #ery stressful. Thus, the cows are only
concerned a"out the height of the tallest hurdle they ha#e to Dump o#er.
The cowsC practice room has N (9 &- N &- N22) stations, con#eniently la"eled
9..N. ! set of / (9 &- / &- 13,222) one8way paths connects pairs of stations(
the paths are also con#eniently la"eled 9../. Jath i tra#els from station M@i
to station ,@i and contains exactly one hurdle of height @i (9 &- @i &-
9,222,222). Oows must Dump hurdles in any path they tra#erse.
The cows ha#e T (9 &- T &- I2,222) tasks to complete. Task i comprises two
distinct num"ers, !@i and F@i (9 &- !@i &- N( 9 &- F@i &- N), which connote
that a cow has to tra#el from station !@i to station F@i ("y tra#ersing o#er
one or more paths o#er some route). The cows want to take a path the minimiAes
the height of the tallest hurdle they Dump o#er when tra#eling from !@i to
F@i. Pour Do" is to write a program that determines the path whose tallest
hurdle is smallest and report that height.
*NJKT )OL/!T$
* +ine 9$ Three space8separated integers$ N, /, and T
* +ines 1../:9$ +ine i:9 contains three space8separated integers$ M@i,
,@i, and @i
* +ines /:1../:T:9$ +ine i:/:9 contains two space8separated integers
that descri"e task i$ !@i and F@i
M!/J+, *NJKT (file hurdles.in)$
3 U N
9 1 91
N 1 T
9 N 3
1 3 N
N I I
1 I T
N I
9 1
3 9
OKTJKT )OL/!T$
* +ines 9..T$ +ine i contains the result for task i and tells the
smallest possi"le maximum height necessary to tra#el "etween the stations.
Output 89 if it is impossi"le to tra#el "etween the two stations.
M!/J+, OKTJKT (file hurdles.out)$
I
T
89
OKTJKT B,T!*+M$
Wuery %9$ The "est way is to simply tra#el on the path from station N to
station I.
Wuery %1$ There is a path from station 9 to station 1, "ut a "etter way
would "e to tra#el from station 9 to station N and then to station 1.
Wuery %N$ There are no paths that start at station 3, so it is clear that
there is no way to reach station 9 from station 3.
)irst of all, it is clear that this pro"lem can "e con#erted into a (directed)
graph, and for each of the T >ueries, we wish to find the shortest path
"etween two nodes ! and F.
One possi"le solution is for e#ery >uery, use either a single8source shortest
path algorithm (such as BiDkstra) or do a depth8first search to find the
shortest path. owe#er, this can take up to O(N
1
) time for each >uery, and
would then ha#e a total running time of O(N
1
T), which is too large for this
pro"lemCs constraints.
Thus we instead want to find a way to precompute all of the shortest paths
"eforehand. We do this "y initialiAing all distances "etween two nodes ! and F
to the cost of the edge "etween ! and F, or infinity if no such edge exists.
Then we run the standard )loyd8Warshall algorithm (more info can "e found in
the Training pages or here) to compute the shortest paths, with one
difference$ *f cost (a, ", c,...) represents the cost of tra#eling from a to "
and then from " to c, etc., then instead of
cost (i, D, k) - cost (i, D) : cost (D, k)
we now ha#e
cost (i, D, k) - max (cost (i, D), cost (D, k)).
(The proof that this method does correctly find the shortest path is left to
the reader.)
!nother possi"ility is to compute the all8pairs shortest path "eforehand with
a different method, such as doing BiDkstra from each node. owe#er, this is
still O(N
N
) and has a slightly higher constant factor.
!fter computing the all8pairs shortest paths, we then input each >uery and
output the result (in constant time for each >uery). Note that if the distance
"etween ! and F is still infinity after running the shortest path algorithm,
it means that no path exists from ! to F, so we output 89.
Our total running time is thus O(N
N
: T), since the )loyd8Warshall takes O(N
N
)
time to compute the shortest paths, and each >uery takes O(9) time.
The following is a solution using this idea$
%include &cstdio'
%include &cstring'
using namespace std(
)*+, *fout - fopen (.hurdles.out., .w.)(
)*+, *fin - fopen (.hurdles.in., .r.)(
const int *N) - 9222222222(
const int /!0N - 323(
int N, /, T(
int dist 4/!0N54/!0N5(
inline #oid minimiAe (int =a, int ") 7 if (" & a) a - "( ;
int main () 7
66 initialiAe to CinfinityC
memset (dist, UN, siAeof (dist))(
fscanf (fin, .<d <d <d., =N, =/, =T)(
int a, ", c(
66 input data
for (int i - 2( i & /( i::) 7
fscanf (fin, .<d <d <d., =a, =", =c)(
a88, "88( 66 use 28"ased indexing
dist 4a54"5 &X- c(
;
66 compute the shortest paths using )loyd8Warshall
for (int k - 2( k & N( k::)
for (int i - 2( i & N( i::)
if (dist 4i54k5 & *N))
for (int D - 2( D & N( D::)
minimiAe (dist 4i54D5, dist 4i54k5 'X dist 4k54D5)(
66 output results
for (int i - 2( i & T( i::) 7
fscanf (fin, .<d <d., =a, =")(
a88, "88(
fprintf (fout, .<d?n., dist 4a54"5 & *N) X dist 4a54"5 $ 89)(
;
return 2(
;
!il4in* (ime "Je)rey #an*$ 200%&
Fessie is such a hard8working cow. *n fact, she is so focused on maximiAing
her producti#ity that she decides to schedule her next N (9 &- N &- 9,222,222)
hours (con#eniently la"eled 2..N89) so that she produces as much milk as
possi"le.
)armer Gohn has a list of / (9 &- / &- 9,222) possi"ly o#erlapping inter#als
in which he is a#aila"le for milking. ,ach inter#al i has a starting hour (2
&- starting@hour@i & N), an ending hour (starting@hour@i & ending@hour@i &-
N), and a corresponding efficiency (9 &- efficiency@i &- 9,222,222) which
indicates how many gallons of milk that he can get out of Fessie in that
inter#al. )armer Gohn starts and stops milking at the "eginning of the
starting hour and ending hour, respecti#ely. When "eing milked, Fessie must "e
milked through an entire inter#al.
,#en Fessie has her limitations, though. !fter "eing milked during any
inter#al, she must rest L (9 &- L &- N) hours "efore she can start milking
again. Hi#en )armer Gohns list of inter#als, determine the maximum amount of
milk that Fessie can produce in the N hours.
*NJKT )OL/!T$
* +ine 9$ Three space8separated integers$ N, /, and L
* +ines 1../:9$ +ine i:9 descri"es )GCs ith milking inter#al with
three space8separated integers$ starting@hour@i, ending@hour@i, and
efficiency@i
M!/J+, *NJKT (file milkprod.in)$
91 I 1
9 1 T
92 91 9Q
N U 1I
S 92 N9
*NJKT B,T!*+M$
Fessie wants to schedule the next 91 hours( )armer Gohn has four inter#als in
which he can milk her( Fessie must rest 1 hours after e#ery milking. The first
inter#al lasts from hour 9 to hour 1, the second from hour 92 to hour 91, the
third from hour N to hour U, and the fourth from hour S to hour 92. )armer
Gohn can get T, 9Q, 1I, and N9 gallons of milk, respecti#ely, from Fessie in
those inter#als.
OKTJKT )OL/!T$
* +ine 9$ The maximum num"er of gallons of milk that Fessie can
product in the N hours
M!/J+, OKTJKT (file milkprod.out)$
IN
OKTJKT B,T!*+M$
*f Fessie uses the first inter#al, she cannot use the third "ecause she needs
1 hours of rest. *f she uses the second, she cannot use the fourth. +astly,
if she uses the third, she cannot use the fourth. The "est situation is
choosing the second and third inter#als, producing IN gallons of milk.
The goal of this pro"lem is to select a disDoint set of inter#als ha#ing
maximum total efficiency. The technical term for such a pro"lem would "e to
find a maximum8efficiency .packing. of inter#als. *f the inter#als all ha#e
the same efficiency (i.e., if we simply want to select a maximum num"er of
disDoint inter#als), then this is a rather well8known pro"lem with a simple
greedy solution$ repeatedly choose the inter#al ending earliest, remo#e all
the inter#als it o#erlaps from consideration, and repeat. Mince our pro"lem is
a more complicated .weighted. #ersion of this pro"lem, howe#er, we can no
longer use a simple greedy approach, and we need to use dynamic programming
instead.
We "egin "y sorting the inter#als according to their ending times. +et ,(D)
denote the maximum efficiency we can o"tain "y a disDoint collection of Dust
inter#als i...D. We will compute ,(9), ,(1), ..., ,(n) in order. When it comes
time to compute ,(D), this will "e easy since we will ha#e already computed
,(9) ... ,(D89). ere is the formula$
,(D) - max(,(D89), D.efficiency : max7,(i) $ i
&-.D.start;). i.end and' What does this meanX Well, the optimal solution for
inter#als 9...D either includes inter#al D or it doesnCt. To co#er "oth cases,
we take the "est of two solutions$ the "est solution for inter#als 9...D that
@doesnCt@ contain D, and the "est solution for inter#als 9...D that @does@
contain D. *n the first case, the optimal solution #alue is Dust ,(D89), since
we only get to use inter#als 9...D89. *n the second case, we get to count the
efficiency of inter#al D towards our total #alue, and then we finish off our
solution "y adding in ,(i) for the ."est. preceding inter#al i (where we only
consider those inter#als i ending "efore D starts).
! straightforward application of the formula a"o#e to compute ,(9), ,(1), ...,
,(n) gi#es us an O(n\1) running time, which is fine for this pro"lem. With a
"it of extra cle#erness, we can actually get the running time down to O(n log
n).
*f you would like to test whether or not you understand the principle "ehind
this solution well, consider the following related pro"lem$ you are gi#en n
inter#als that collecti#ely co#er the range 2....9,222,222, where each
inter#al has an associated cost. Pour goal is to find a minimum8cost su"set of
the inter#als that still co#ers the range 2....9,222,222. Target running time$
O(n\1), or O(n log n) if you are extra cle#er.
ere is an O(n\1) solution to the milking time pro"lem "y Frian Bean$
%include &stdio.h'
%include &stdio.h'
%define /!0@/ 9222
typedef struct 7
int start(
int end(
int efficiency(
; *nter#al(
*nter#al *4/!0@/5(
int N, /, R, Fest4/!0@/5(
static int *comp(const #oid *p9, const #oid *p1)
7
*nter#al **9 - (*nter#al *)p9(
*nter#al **1 - (*nter#al *)p1(
return *98'end 8 *18'end(
;
int main(#oid)
7
int i, D, "est-89(
)*+, *fp(
fp - fopen (.milkprod.in., .r.)(
fscanf (fp, .<d <d <d., =N, =/, =R)(
for (i-2( i&/( i::)
fscanf (fp, .<d <d <d., =*4i5.start, =*4i5.end, =*4i5.efficiency)(
fclose (fp)(

>sort (*, /, siAeof(*nter#al), *comp)(
for (D-2( D&/( D::) 7
Fest4D5 - *4D5.efficiency(
for (i-2( i&D( i::)
if (*4i5.end : R &- *4D5.start == Fest4i5 : *4D5.efficiency ' Fest4D5)
Fest4D5 - Fest4i5 : *4D5.efficiency(
if (Fest4D5 ' "est) "est - Fest4D5(
;
fp - fopen (.milkprod.out., .w.)(
fprintf (fp ,.<d?n., "est)(
fclose (fp)(
;
Best Co+ ine "C.ristos (=amos$ 200%&
)G is a"out to take his N (9 &- N &- 1,222) cows to the annual .)armer of the
Pear. competition. *n this contest e#ery farmer arranges his cows in a line
and herds them past the Dudges.
The contest organiAers adopted a new registration scheme this year$ simply
register the initial letter of e#ery cow in the order they will appear (i.e.,
*f )G takes Fessie, Myl#ia, and Bora in that order he Dust registers FMB).
!fter the registration phase ends, e#ery group is Dudged in increasing
lexicographic order according to the string of the initials of the cowsC
names.
)G is #ery "usy this year and has to hurry "ack to his farm, so he wants to "e
Dudged as early as possi"le. e decides to rearrange his cows, who ha#e
already lined up, "efore registering them.
)G marks a location for a new line of the competing cows. e then proceeds to
marshal the cows from the old line to the new one "y repeatedly sending either
the first or last cow in the (remainder of the) original line to the end of
the new line. When heCs finished, )G takes his cows for registration in this
new order.
Hi#en the initial order of his cows, determine the least lexicographic string
of initials he can make this way.
JLOF+,/ N!/,$ "cl
*NJKT )OL/!T$
* +ine 9$ ! single integer$ N
* +ines 1..N:9$ +ine i:9 contains a single initial (C!C..C^C) of the
cow in the ith position in the original line
M!/J+, *NJKT (file "cl.in)$
U
!
O
B
F
O
F
*NJKT B,T!*+M$
)G has U cows in this order$ !OBFOF
OKTJKT )OL/!T$
The least lexicographic string he can make. ,#ery line (except perhaps the
last one) contains the initials of T2 cows (C!C..C^C) in the new line.
M!/J+, OKTJKT (file "cl.out)$
!FOFOB
OKTJKT B,T!*+M$
Mtep Original New
%9 !OBFOF
%1 OBFOF !
%N OBFO !F
%I OBF !FO
%3 OB !FOF
%U B !FOFO
%S !FOFOB
This problem can be sol(e) with )ynamic programming on the inter(als of cows but there is also
a simple gree)y strategy.
<etween the two cows in the e)ges, you must always pick the cow with the smallest initial letter.
If both cows ha(e the same initial letter in or)er to )eci)e you must look a little bit )eeper an)
check the secon) cows in the line's e)ges or the thir) ones if those are eCual an) so on until you
fin) two cows that are )ifferent. Then you pick the cow from the si)e of the smallest one.
This process can be summariEe) as follows.
1t any gi(en inter(al Pa,bQ with string SPa,bQ% you choose2
Bow a if SPa,bQ% " re( SPa,bQ% %
Bow b otherwise
where re(S% is the re(erse string e.g. re(DabcD% # DcbaD
This can be implemente) in .&Z'% but we can achie(e .&log&% by using suffi? arrays.
Here are the two implementations2
The .&Z'%
Iinclu)e"cst)ioH
char SP'$!$Q,ln#$*
(oi) prntchar a% S
ifln##A$% SprintfDXnD%*ln#$*W
printfDTcD,a%*ln55*
W
int main% S
int i,N,&,pi,pN,(al*
freopenDbcl.inD ,DrD,st)in %*
freopenDbcl.outD,DwD,st)out%*
scanfDT)D,U&%*
fori#$*i"&*i55% scanfD Tc D,S5i%*
i#$,N#&4!*
whilei"#N% S
ifSPiQ"SPNQ% SprntSPiQ%*i55*W
else ifSPiQHSPNQ% SprntSPNQ%*N44*W
else S
pi#i5!*pN#N4!*(al#SPiQ*
while pN4piH! UU SPpiQ##SPpNQ% Spi55,pN44*W
ifSPpiQ"SPpNQ% prntSPiQ%,i55*
else prntSPNQ%,N44*
W
W
printfDXnD%*
return $*
W
1n) the .&log&%
Iinclu)e"cst)ioH
Iinclu)e"cstringH
Iinclu)e"cst)libH
I)efine 01R& :$$$:$
char SP'301R&Q*
int &,ln#$*
int oP'QP'301R&Q, tP'301R&QP'Q*
int 1P'301R&Q, <P'301R&Q, BP'301R&Q, ;P'301R&Q*
(oi) prntchar a% S
ifln##A$% SprintfDXnD%*ln#$*W
printfDTcD,a%*ln55*
W
int main% S
int i, N, NN, ?, k*
freopenDbcl.inD ,DrD,st)in %*
freopenDbcl.outD,DwD,st)out%*
scanfDT)D,U&%*
fori#$*i"&*i55% S
scanfD Tc D,S5i%*
SP&5iQ # SPiQ*
W
memset1, $, siEeof1%%*
for i # $* i " '3&* 55i% 1Pint%SPiQ4'1'%Q # !*
for i # !* i " '8* 55i% 1PiQ 5# 1Pi4!Q*
for i # $* i " '3&* 55i% oP$QPiQ # 1Pint%SPiQ4'1'%Q*
?#$*
for N # $, NN # !, k # $* NN " & UU k " '3&* 55N, NN ""# !% S
memset1, $, siEeof1%%*
memset<, $, siEeof<%%*
for i # $* i " &* 55i% S
551P tPiQP$Q # oP?QPiQ Q*
55<P tPiQP!Q # i5NN"&% Y oP?QPi5NNQ 2 $ Q*
W
for i # &* i " '3&* 55i% S
551P tPiQP$Q # oP?QPiQ Q*
55<P tPiQP!Q # i4NNH#&% Y oP?QPi4NNQ 2 $ Q*
W
for i # !* i "# '3&* 55i% S
1PiQ 5# 1Pi4!Q*
<PiQ 5# <Pi4!Q*
W
for i # '3&4!* i H# $* 44i%
BP44<PtPiQP!QQQ # i*
for i # '3&4!* i H# $* 44i%
;P441PtPBPiQQP$QQQ # BPiQ*
? Z# !*
oP?QP;P$QQ # k # !*
for i # !* i " '3&* 55i%
oP?QP;PiQQ # k 5# tP;PiQQP$Q !# tP;Pi4!QQP$Q VV tP;PiQQP!Q !# tP;Pi4!QQP!Q%%*
W
i#$,N#&4!*
whilei"#N% S
ifSPiQ"SPNQ% SprntSPiQ%*i55*W
else ifSPiQHSPNQ% SprntSPNQ%*N44*W
else ifoP?QPiQ"oP?QP&5NQ% SprntSPiQ%*i55*W
else SprntSPNQ%*N44*W
W
printfDXnD%*
return $*
W
/OD PROBE!S
33333333333333333333333333333333333333333333333333333333333333333333333333333
(elep.one #ire "Je)rey #an*$ 200%&
Farmer John's cows are getting restless about their poor telephone ser(ice* they want FJ to replace the ol) telephone
wire with new, more efficient wire. The new wiring will utiliEe & ' "# & "# !$$,$$$% alrea)y4installe) telephone
poles, each with some heightFi meters ! "# heightFi "# !$$%. The new wire will connect the tops of each pair of
a)Nacent poles an) will incur a penalty cost B 3 the two poles' height )ifference for each section of wire where the
poles are of )ifferent heights ! "# B "# !$$%. The poles, of course, are in a certain seCuence an) can not be mo(e).
Farmer John figures that if he makes some poles taller he can re)uce his penalties, though with some other
a))itional cost. He can a)) an integer R number of meters to a pole at a cost of RZ'.
Help Farmer John )etermine the cheapest combination of growing pole heights an) connecting wire so that the cows
can get their new an) impro(e) ser(ice.
I&,-T F./01T2
3 +ine !2 Two space4separate) integers2 & an) B
3 +ines '..&5!2 +ine i5! contains a single integer2 heightFi
S10,+6 I&,-T file telewire.in%2
: '
'
9
:
!
7
I&,-T ;6T1I+S2
There are : telephone poles, an) the (ertical )istance penalty is ]'Jmeter. The poles initially ha(e heights of ', 9, :,
!, an) 7, respecti(ely.
.-T,-T F./01T2
3 +ine !2 The minimum total amount of money that it will cost Farmer John to attach the new telephone wire.
S10,+6 .-T,-T file telewire.out%2
!:
.-T,-T ;6T1I+S2
The best way is for Farmer John to raise the first pole by ! unit an) the fourth pole by ' units, making the heights in
or)er% 9, 9, :, 9, an) 7. This costs ]:. The remaining wiring will cost ]'3$5'5'5!% # ]!$, for a
total of ]!:.
+et 4i5 "e the original height of the i8th pole, and let f(n, h) "e the
minimum cost for n poles with the n8th pole ha#ing height h. Then$
f(n, h) - min 7 (4i58h)\1 : f(n89, hC) : OYhC8hY ; for all hC
With a straightforward dynamic programming implementation, this runs in
O(N*
1
), where is the maximum height. owe#er, "y splitting up the
recurrence relation into two cases, one where hC '- h and one where hC & h, we
can rewrite it as$
f(n, h) - (4i58h)\1 : min 7 8O*h : min 7 f(n89, hC):O*hC ; (for hC '- h),
O*h : min 7 f(n89, hC)8O*hC ; (for hC & h) ;
Befine low(n, h) $- min o#er hC '- h 7 f(n, hC):O*hC ;
and high(n, h) $- min o#er hC & h 7 f(n, hC)8O*hC ;
Then f(n, h) - (4i58h)\1 : min 7 8O*h:low(n89, h), O*h:high(n89, h) ;
low(n, h) and high(n, h) for all n, h can "e computed in O(N*) time( thus
f(n, h) can "e computed in O(N*) time as well. ! final implementation detail$
an array of siAe O(N*) exceeds the the memory limit, "ut only two .rows. of
the BJ ta"le are needed at a time, so an array of siAe 1* is sufficient.
Felow is Lichard JengCs solution$
%include &cstdio'
%define /!0N 992222
%define /!0 929
int h4/!0N5, "es4154/!05, ans, huge, "es9, c, n(
inline int s>r (int x)7return x*x( ;
int main ()7
int i, D, pre, cur(
freopen (.telewire.in., .r., stdin)(
freopen (.telewire.out., .w., stdout)(
huge - 1922222222(
scanf (.<d<d., =n, =c)(
for (i - 2( i&n( i::) scanf (.<d?n., =h4i5)(
for (i - 2( i&/!0( i::)
"es4254i5 - (i' - h425) X s>r(h4258i) $ huge(
for (i - 9( i&n( i::)7
pre - (i:9)<1(
cur - i<1(
for ("es9 - huge, D - 2( D&/!0( D::)7
"es9 &X- "es4pre54D58D*c(
"es4cur54D5 - "es9:D*c(
;
for ("es9 - huge, D - /!089( D' - 2( D88)7
"es9 &X- "es4pre54D5:D*c(
"es4cur54D5 &X- "es98D*c(
;
for (D - 2( D&/!0( D::)
"es4cur54D5 - (D' - h4i5)X ("es4cur54D5 : s>r(D8h4i5)) $ huge(
;
ans - huge(
for (i - 2( i&/!0( i::) ans&X - "es4cur54i5(
printf (.<d?n., ans)(
return 2(
;
Co+ Relays "Eri4 Bern.ardsson$ 2002&
For their physical fitness program, & ' "# & "# !,$$$,$$$% cows ha(e )eci)e) to run a relay race using the T ' "#
T "# !$$% cow trails throughout the pasture.
6ach trail connects two )ifferent intersections ! "# I!Fi "# !,$$$* ! "# I'Fi "# !,$$$%, each of which is the
termination for at least two trails. The cows know the lengthFi of each trail ! "# lengthFi "# !,$$$%, the two
intersections the trail connects, an) they know that no two intersections are )irectly connecte) by two )ifferent
trails. The trails form a structure known mathematically as a graph.
To run the relay, the & cows position themsel(es at (arious intersections some intersections might ha(e more than
one cow%. They must position themsel(es properly so that they can han) off the baton cow4by4cow an) en) up at the
proper finishing place.
Krite a program to help position the cows. Fin) the shortest path that connects the starting intersection S% an) the
en)ing intersection 6% an) tra(erses e?actly & cow trails.
I&,-T F./01T2
3 +ine !2 Four space4separate) integers2 &, T, S, an) 6
3 +ines '..T5!2 +ine i5! )escribes trail i with three space4separate) integers2 lengthFi, I!Fi, an) I'Fi
S10,+6 I&,-T file relays.in%2
' 8 8 7
!! 7 8
7 7 A
A 7 @
8 8 A
' 8 @
9 A @
.-T,-T F./01T2
3 +ine !2 1 single integer that is the shortest )istance from intersection S to intersection 6 that tra(erses e?actly
& cow trails.
S10,+6 .-T,-T file relays.out%2
!$
)irst, note that there cannot "e more than T distinct nodes in our graph,
"ecause there are exactly T edges in the graph, and each node is an endpoint
for at least two edges.
The simplest solution that is reasona"ly fast is to let s4+54V5 "e the
shortest path from node M to node V that has length +. We can compute the
#alues in this array "y iterating N times, each time trying to tra#el through
one edge from each node. The memory for this can "e reduced "y using a sliding
window (since computing the #alues for length + only uses the #alues for
length + 8 9), and this solution uses O(N T
1
) time. To o"tain a faster
solution, we do the following.
!ssume we ha#e the shortest path, from M to ,, of length N. Then we can "reak
up this path into smaller paths whose lengths are powers of two. Thus, we can
compute, for each power of two that is no greater than N, the shortest path
"etween e#ery pair of nodes that has a length of that power of two. This can
"e done using a method similar to )loyd8Warshall in O(T
N
log N) time. (Mee the
code "elow for more details.)
!fter we compute the shortest paths mentioned a"o#e, we can compute shortest
paths, of length N, from M to e#ery other node. We do this "y "reaking N up
into its "inary representation, and for each power of two that occurs, we
compute shortest paths after adding in paths of length e>ual to this power.
This can "e done in O(T
1
log N) time. (!gain, see the code "elow for more
details.) Thus, our o#erall runtime is O(T
N
log N).
%include &cstdio'
%include &cstring'
using namespace std(
)*+, *fout - fopen (.relays.out., .w.)(
)*+, *fin - fopen (.relays.in., .r.)(
const int *N) - 9222222222(
const int /!0V - 923(
const int /!0* - 9223(
const int /!0+ - 12(
int N, V, T, M, ,(
66 compress nodes to smaller #alues
int change 4/!0*5(
66 shortest path "etween two nodes with a length of a power of two
int dist 4/!0+54/!0V54/!0V5(
66 "est path from M to a node
int "est 4/!0V5, "est1 4/!0V5(
66 change a node to a CcompressedC #alue
inline #oid check (int =ind)
7
if (change 4ind5 -- 89)
change 4ind5 - V::(
ind - change 4ind5(
;

int main () 7
66 initialiAe arrays
memset (change, 89, siAeof (change))(
memset (dist, UN, siAeof (dist))(
memset ("est, UN, siAeof ("est))(
fscanf (fin, .<d <d <d <d., =N, =T, =M, =,)(
check (M)(
check (,)(
for (int i - 2( i & T( i::) 7
int !, F, +(
fscanf (fin, .<d <d <d., =+, =!, =F)(
check (!)(
check (F)(
66 edges are paths of length 9
dist 4254!54F5 &X- +(
dist 4254F54!5 &X- +(
;
66 compute shortest paths whose lengths are powers of two
66 a path of length 1\p can "e made "y two paths of length 1\(p 8 9)
for (int p - 9( (9 && p) &- N( p::)
for (int i - 2( i & V( i::)
for (int D - 2( D & V( D::)
if (dist 4p 8 954i54D5 & *N))
for (int k - 2( k & V( k::)
if (dist 4p 8 954i54D5 : dist 4p 8 954D54k5 & dist 4p5
4i54k5)
dist 4p54i54k5 - dist 4p 8 954i54D5 : dist 4p 8 95
4D54k5(
66 com"ine results of each power of two in the "inary representation of N
"est 4M5 - 2(
for (int p - 2( (9 && p) &- N( p::)
if (N = (9 && p)) 7
66 use a temporary array C"est1C to hold the new #alues, and copy them to the
old array afterward
memset ("est1, UN, siAeof ("est1))(
for (int i - 2( i & V( i::)
if ("est 4i5 & *N))
for (int D - 2( D & V( D::)
if ("est 4i5 : dist 4p54i54D5 & "est1 4D5)
"est1 4D5 - "est 4i5 : dist 4p54i54D5(
memcpy ("est, "est1, siAeof ("est1))(
;
66 "est 4,5 is now the shortest path from M to , using N edges
fprintf (fout, .<d?n., "est 4,5)(
return 2(
;
Suns'reen "Russ Co<$ 200>&
To a(oi) unsightly burns while tanning, each of the B ! "# B "# ':$$% cows must co(er her hi)e with sunscreen
when they're at the beach. Bow i has a minimum an) ma?imum S,F rating ! "# minS,FFi "# !,$$$* minS,FFi "#
ma?S,FFi "# !,$$$% that will work. If the S,F rating is too low, the cow suffers sunburn* if the S,F rating is too
high, the cow )oesn't tan at all.
The cows ha(e a picnic basket with + ! "# + "# ':$$% bottles of sunscreen lotion, each bottle i with an S,F rating
S,FFi ! "# S,FFi "# !,$$$%. +otion bottle i can co(er co(erFi cows with lotion. 1 cow may lotion from only one
bottle.
Khat is the ma?imum number of cows that can protect themsel(es while tanning gi(en the a(ailable lotionsY
,/.<+60 &1062 tanning
I&,-T F./01T2
3 +ine !2 Two space4separate) integers2 B an) +
3 +ines '..B5!2 +ine i )escribes cow i's lotion reCuires with two integers2 minS,FFi an) ma?S,FFi
3 +ines B5'..B5+5!2 +ine i5B5! )escribes a sunscreen lotion bottle I with space4separate) integers2 S,FFi an)
co(erFi
S10,+6 I&,-T file tanning.in%2
9 '
9 !$
' :
! :
8 '
7 !
I&,-T ;6T1I+S2
9 cows* ' lotions. Bows want S,F ratings of 9..!$, '..:, an) !..:. +otions
a(ailable2 8 for two cows%, 7 for ! cow%. Bow ! can use the S,F 8 lotion.
6ither cow ' or cow 9 can use the S,F 7 lotion. .nly ' cows can be co(ere).
.-T,-T F./01T2
1 single line with an integer that is the ma?imum number of cows that
can be protecte) while tanning
S10,+6 .-T,-T file tanning.out%2
'
This pro"lem is sol#a"le "y a simple greedy algorithm$ consider the "ottles of
sunscreen in increasing order of MJ), and assign each one (if possi"le) to the
cow ha#ing the lowest maxMJ) rating.
Why does this gi#e an optimal solutionX +et F denote a "ottle of sunscreen
with the lowest MJ) rating. *f no cow is compati"le with F, then clearly F
cannot "e assigned in any solution, so we can ignore F. Otherwise, let O "e
the cow ha#ing lowest maxMJ) rating that is compati"le with F. We claim that
there is always an optimal solution in which O is paired with F, so it is
.safe. to make this assignment as our algorithm progresses (i.e., it will
ne#er make a wrong decision and end up in a situation where an optimal
solution is no longer reacha"le). To see this, suppose there is an optimal
solution M where O is @not@ paired with F, and consider a few cases$
(i) O and F are "oth unassigned in M. This case cannot happen, since we could
assign O with F and o"tain an e#en "etter solution, contradicting the
optimality of M.
(ii) O is assigned in M "ut F is not. ere, "y reassigning O to F, we o"tain
an e>ually8good solution in which O and F are assigned.
(iii) F is assigned in M "ut O is not. Mame as (ii), only we reassign F.
(i#) O and F are "oth assigned in M. +et FC "e the "ottle assigned to O, and
OC "e the cow assigned to F. ere, you can check that it is #alid to reassign
O with F and OC with FC, gi#ing us an e>ually good assignment in which O and F
are assigned.
ence, an optimal solution always exists in which O and F are paired, so it is
safe to match them together.
!n alternate, symmetric, solution to this pro"lem is the following$ process
the cows in increasing order of maxMJ), and for each cow O in se>uence, assign
O to the minimum MJ) "ottle compati"le with O. The analysis of this approach
follows essentially the same reasoning as a"o#e.
*n terms of running time, one can implement either of the two algorithms a"o#e
in O(n log n) time. One way to do this is the following (in the case of the
first algorithm a"o#e)$ We first sort the "ottles "y MJ) rating and the cows
"y minMJ) rating. We then scan the "ottles in order and maintain a min8heap on
the cows (keyed on maxMJ)) with minMJ) lower than the MJ) of our current
"ottle. )or each "ottle F in order, we match it with the minimum cow from the
heap (after first remo#ing any cows from the heap ha#ing maxMJ) less than the
MJ) of F).
ere is a sample O:: solution written "y Lichard Jeng$
%include &cstdio'
%include &cstring'
%include &cstdli"'
%include &algorithm'
%include &>ueue'
using namespace std(
%define /!0N 12222
int n,m,ans(
pair&int,int' cow4/!0N5,lotion4/!0N5(
priority@>ueue&int' >(
#oid process()7
int i,i9(
while(E>.empty()) >.pop()(
sort(cow,cow:n)(
sort(lotion,lotion:m)(
for(ans-i-i9-2(i&m(i::)7
while((i9&n)==(cow4i95.first&-lotion4i5.first))
>.push(8cow4i9::5.second)(
while((E>.empty())==(8(>.top())&lotion4i5.first))
>.pop()(
while((E>.empty())==(lotion4i5.second88))7
ans::(
>.pop()(
;
;
;
int main()7
int i,D(
freopen(.tanning.in.,.r.,stdin)(
freopen(.tanning.out.,.w.,stdout)(
scanf(.<d<d.,=n,=m)(
for(i-2(i&n(i::)
scanf(.<d<d.,=cow4i5.first,=cow4i5.second)(
for(i-2(i&m(i::)
scanf(.<d<d.,=lotion4i5.first,=lotion4i5.second)(
ans-2(
process()(
printf(.<d?n.,ans)(
return 2(
;