Home

Final Report on the IOI 2002 Competition

1. C REMARK After we proposed this task we have found that some games are similar to this XOR task The game is to ask a user to clear the given image 10 by 10 by only applying cross shape XOR It is interesting to see and play in the following web sites http www ida net users housley atag htm http www math hkbu edu hk cstong sci3510 xchess html http www math hkbu edu hk cwyeung xchess Page 38 of 142 IOI 2002 Yong In Korea D Source code for XOR Solution3 Jung Gun Lim include lt cstdio gt define MAXN 2000 typedef struct int rn int cn corner int n count corner ct MAXN 2 MAXN 2 data structure using linked list that contains corners int cor MAXN 2 coc MAXN 2 cor corners on the row coc corners on the column int b MAXN 2 MAXN 2 input int sols MAXN MAXN 4 solution int mcount msols MAXN MAXN 4 best solution found void flip corner int r int c if r c is a corner make it not otherwise vice versa int p p 0 while 1 if ct r p cn oc ct r p cn Corr i 3 break ct r c cn if ct r pl en gt c et r c cn ct r p en etre Ep cn o cor rl t break p ct r p cn p 0 while 1 if ct pl cl rn r ct p c rn ct r cl rn eoclc 3 break if ct p cl rn gt r ct r c rn ct p Le rn ct p c
2. A Comment This problem can be reduced to the problem for the finding the largest empty circle in L4 metric So the solution of this problem can be computed by constructing an L metric Voronoi diagram We can consider a black grid as a point in Euclidean plane then each black grid has integer coordinates To construct an Lj metric Voronoi Diagram of these points we should compute the bisector between two points Due to L metric the distance of every Page 87 of 142 IOI 2002 Yong In Korea two points is an integer To compute a bisector between two points no floating point arithmetic is needed Moreover the slope of all bisector is either 1 1 0 or co Therefore we can easily compute an L metric Voronoi diagram in O N log N by using divide and conquer technique In this diagram we can find the largest empty diamond which contains no black grid in O N Let D be the size of this diamond and let D be the optimal size of this problem Let D D Using a Voronoi diagram of Lj metric we can solve our problem as follows For every point p we reconstruct the Voronoi diagram of L metric partially without p then update D This step can be done in O N Therefore we can solve this problem in O N log N If we try to solve this problem directly in grid space then at least O N time algorithm may be needed B Reference 1 D T Lee and C K Wong Voronoi diagrams in L1 metrics with 2 dimensional storage appli
3. 3 996 1 0 1 9 Grading System Response Time No 1 5 answer Slow 2 2 4 Fast ALe A 3 3 a 6 18 66 Submit Ho 2 9 6 8 5 8 17 5 64 1 77 Megan 3 a 9 2 19 a 4 25 7 896 3 9 5 8 8 7 18 5 55 3 i EE 22 3 5 11 16 49 jn 21 4 2 996 1 9 10 7 15 5 47 6 i Page 130 of 142 IOI 2002 Yong In Korea 3 4 T 6 12 67 xm P 12 6 3 9 1 0 5 8 11 7 65 0 Do you like the Grading System No 1 5 answer No i Much PAGA 3 3 3 13 27 54 Submit 9 2 9 2 9 12 6 26 2 52 5 2 44 8 5 7 1 28 Testing 7590 4 8 6 8 10 7 27 2 02779 4 04 EN 3 3 14 17 45 NET 20 4 2 9 2 9 13 6 16 5 43 7 SE 14 3 7 16 15 48 jon P 13 6 2 9 6 8 15 5 14 6 46 6 Task Understanding No 1 5 answer Easy Hard mure 2 45 31 17 5 3 FROG 1 9 43 7 30 1 16 5 4 9 2 9 191 1 Jot 2 31 32 16 12 10 UTOPIA 1 9 30 1 31 1 15 5 11 7 9 7 23 3 46 29 1 5 9 XOR 9 44 7 28 1 11 7 499 8 7 9 2 14 19 29 26 13 BATCH 1 90 13 6 18 4 28 2 25 2 12 6 32
4. int brl br2 bcl bc2 boundary of rods void boundary search n gridsize brl top to bottom search br2 bottom to top search 1 n 2 1 n bcl left to right search Dflt3 n 1 nj 1 n 1 n 2 bc2 right to left search 1 n bcl 3 n brl t t bel br2 bc2 flipping coordinates horizontally vertically diagonally int h flip 0 v flip 0 d flip 0 boundary with virtual coordinates int prl pcl pr2 pc2 initializing the virtual boundary void pseudo init if h flip pc2 n 1 bc1 pcil n 1 bc2 else pcl bcl pc2 bc2 if v_flip pr2 n 1 br1 pri n 1 br2 else prl brl pr2 br2 if d_flip swi amp prl amp pcl swi amp pr2 amp pc2 int pseudo rect int rl int r2 int cl int c2 if d flip swi amp rl amp cl swi amp r2 amp c2 if v_flip Page 77 of 142 IOI 2002 Yong In Korea swi amp rl amp r2 if h flip c1z nt1 c1 c22 nt1 c2 swi amp cl amp c2 return rect rl r2 cl c2 submitting result with virtual coordinates void pseudo output int rl int cl int r2 int c2 int pl int ql q2 if d flip swi amp rl amp cl swi amp r2 amp c2 swi amp pl amp q1 Swi amp p2 amp q2 if v flip rl nt 1 r1 r2 nt 1 r2 pl n t1 pl p2 n 1 p2 if h fli
5. 4 5 7 8 and a sequence of signs we have S 69 5 X 4 45 7 S X 5 7 8 X 2 55 Thus X 45 X 45 7 X 5 7 4 K5 gy Example 4 For X 1 42 3 and 5 S i X 42 3 2 2 X 2 3 Thus X 3 X 3 42 X 3 2 1 Page 26 of 142 IOI 2002 Yong In Korea Now we are ready to present an algorithm for the problem of Utopia Divided Algorithm Utopia_Divided Step 1 read input 1 1 read N 1 2 read 2N code numbers and partition them into A and B such that A B 1 3 read a sequence of regions R rn ry Step 2 find x coordinates of code pairs 2 1 find a sequence of signs S 5 5 5 such that forall j IS j SN s z amp if r 14 otherwise s 2 2 find an alternating sequence X x X Xy from A such that the sign of x is equal to sy 2 3 given X and S find a valid sequence X x x x Wat S according to the proof of Theorem 1 Step 3 find y coordinates of code pairs 3 1 find a sequence of signs S s 5 5 such that forall j IS j SN s Z amp ifr 12 otherwise s 2 3 2 find an alternating sequence Y y y yy from B such that the sign of y is equal to sy 3 3 given Y and S find a valid sequence Y y y Yi Wat S according to the proof of Theorem 1 Step 4 write output print x Vi NG s Qs Yi
6. 92 Test in grading system is not useful Some script or batch file would be more useful for testing Maybe the refresh could be automatically 97 Make not need to Reload Page 134 of 142 IOI 2002 Yong In Korea 99 Quite ok but using Reload is uncomfortable 101 Pick up errors in output format for output only tasks Other Comments 4 Test data for open test data problems should be uploaded to the server for contestants to download in case the input files are erased accidentally 8 The browser s homepage could have been set to the IP address for the web services The web page should have included task related materials such as inputs for XOR and the library for RODS Why limit the size of stderr if you can just redirect it to dev null It seems unreasonable for a contestant to lose points just because s he forgot to remove debugging information from his her code 9 we were forbidden to bring food with us and we weren t given any food except those cookies So I was hungry 13 There is no file manager on IOI It makes work more hard 16 Although XOR was a hard task the idea of having a task with relative scoring is nice and makes the competition more interesting Continue with the hard work 31 More food and water less cookies less strict rules day before the competition 43 Warn about extra output for submissions 45 Internet competition 65 The system should be able to auto ref
7. Page 133 of 142 IOI 2002 Yong In Korea 42 Native code editor would have been very useful RHIDE is unstable in 50 line mode and responds slowly with the S option so a state of the art editor with a resizable window and syntax highlighting indentation would have been more ergonomic for coding 60 RHIDE was very non stable 63 More editors 64 Better editors e g Editplus or Writesource 72 XP crashes consistently Solution use 98 Windows was very unstable if you offer an environment make sure it works correctly so as not to leave some people with disadvantages Don t let people down 73 RHIDE not crashing Visual C 74 Microsoft VC would be nice good compiler and debugger although it s not gcc compatible But it s the only really useful Windows programming environment Windows 2000 would be more useful 75 Make it crash safe 76 RHIDE doesn t work 79 Please use RHIDE with Win 98 and not with Win XP which accidentally crashes 80 There are some problems with Freepascal IDE 81 Include turbo Pascal as well 84 Better IDE than RHIDE 97 Add FAR or NC or sth like it BP 98 Include FAR Manager http www Farmanager com or any similar program In Linux we have midnight commander but no corresponding software in Windows XP 99 More usable version of RHIDE that does not crash Grading System 8 You might want to disallow multiple logins form the same account in the web services for s
8. Theorem 2 Algorithm Utopia Divided is correct and its running time is O N log N Proof The correctness of the algorithm is mainly due to Theorem 1 The complexity of each step except Step 2 2 and 3 2 is O N where Step 2 2 and 3 2 require O N log N time for sorting We do not know of a faster solution nor do we have a proof that sorting is necessary for this problem Another reasonable approach to the problem is backtracking The approach is effective on small inputs fewer than 100 points or so Page 27 of 142 IOI 2002 Yong In Korea B Test Data Information Kee Moon Song The test data consists of 25 test cases each generated mainly at random Some region sequences i consist of at most two regions such as 1 and 2 or ii visit regions in a circular way Some small inputs 9 test cases of size N lt 100 and 1 test case of size N 500 are included so that inefficient but correct solutions can score some points Timing Tests for Utopia sec Optimal O N Optimal O N in f In C C BackTrackingl BackTracking2 pal o0 01 o1 ot so so so sg Z0 zo 257 377 Page 28 of 142 IOI 2002 Yong In Korea Testing Data Description for Utopia Size 4 Example 2 0 Key value 1 20 Circular plane sweep Key value Starting from 20 step 1 or 2 scrambled Z Z Key value Starting from 30 step 1 or 2 scrambled i i i Visit plane 1 except last visit A
9. X lt 10000 OUTPUT Your program writes output to standard output The output contains one integer the number of distinct values in Xi X2 XN EXAMPLE INPUTS AND OUTPUTS Example 1 input output N H N WA Bb OB WN H H Example 2 input output Page 6 of 142 IOI 2002 Yong In Korea SCORING If the output is correct you get full score for the test case Otherwise the score for the test case is 0 Practice Task 2 STRING Sung Kwon Kim String from Substrings PROBLEM Every DNA string consists of only 4 letters A T G and C You have an unknown DNA string and must determine the string The only way you can access information about the hidden string is through an oracle The oracle when given a query string S answers whether the hidden string contains S as a substring For example let the hidden string be So ATTGCGCGATCG Then ATTG and CGCG T AT are substrings of So But neither of TGG or GCGATG is not a substring of So When a string So is represented as So s 1 s 2 s 3 s N where s i is the i th character of So then a substring of So is a consecutive subsequence represented as s i s i 1 s i 2 s 7 where 1 lt i lt j lt N 255 You are to write a program which determines the hidden string using as few oracle queries as possible LIBRARY You are given a library in the following GNU C C Library oracle h oracl
10. i data i 1 0 0 void solveproblem int head 0 tail 1 dris SEL ps queue 0 num table num 0 for j num 1 j gt 0 j for i head i lt tail 1 i Page 57 of 142 IOI 2002 Yong In Korea if func j gt delta queue i 1 queue i headt else break table j table queue head cost j queue head for i tail 1 i gt head i if delta j queue i lt delta queue i queue i 1 tail else break queue tailt4 j answer table 0 void outputs printf Sd n answer int main getdata preprocessing solveproblem outputs return 0 Page 58 of 142 IOI 2002 Yong In Korea Task 2 BUS Chan Su Shin Djura Paunic Bus Terminals PROBLEM Yong In city plans to build a bus network with N bus stops Each bus stop is at a street corner Yong In is a modern city so its map is a grid of square blocks of equal size Two of these bus stops are to be selected as hubs H and M2 The hubs will be connected to each other by a direct bus line and each of the remaining N 2 bus stops will be connected directly to either H or H but not to both but not to any other bus stop The distance between any two bus stops is the length of the shortest possible route following the streets That is if a bus stop is represented as x y with x coordinate x and y coordinate y then the distance between two bus stop
11. p ct 0 col i destroyed with a rectangle of corners 2 jll rn Ei EN links iJ j links j i ij xrn j xrn matching Destroying matched pairs SEIS q ct 0 col match i xn min n 2 while p lt n 2 amp amp q n 2 if p gt q q ct q col match i rn Eins if psg pect p col i rn m if p r l if min cor p min cor p minp p Page 42 of 142 IOI 2002 Yong In Korea for i1 0 i lt cols itt if match i gt i if void destroy col structure with destroy row s int int int int p 0 rows row MAXN 2 Pr q i min min rows 0 while for for ct p p ct p col i rn q ct q col match i rn prefers the row that contains least column add to sol col i col match i r minp islinked i not matched pairs min n 1 p ct 0 col i rn while p lt n t2 if cor p lt min amp amp p r min cor p minp p p ct p col i rn p ct 0 col match i rn while pxnt2 if cor p min amp amp p r min cor p minp p pect p col match il rn add to sol col i col match i r minp int c destroying all corners in the corner the sam Ji p c rn n 2 p ct p c rn row rows p rowstt i20 i rows i links i i1 0 i lt rows 1 itt for j i p
12. void Sort int 1 int r ING Ly Py KO xl ys i 1 j7 f7 XO p l tr 2 01 xl p l r T do while p i 0 lt x0 while x0 lt p j 0 if i lt j I p 1 0 x0 amp amp plill1 lt x1 i I p 3 0 x0 amp amp x1 lt pl31 1 j y p ill0 pl11 0 plj 0 plj 0 vr y p il 1 plil 1 p 3jl 1 7 pljl 1 yr itt Sete while i lt 4 it L 2 5 Sort l As If Ii AF S rt 1 ry int IsRegular int a int b int c if p b 0 pla 0 plc 0 pib 0 if p b 1 pla 1 p c 1 pfb 1 return 1 else if p b 1 p a 1 p cl 1 pib 1 return 2 else return 3 else if p b 0 p a 0 lt p c 0 p b 0 return 1 else return 3 void Run int i j k a b count flag for i 0 i lt n 2 i flag 0 j ie l k i 1 while flag k lt n if flag j else k switch IsRegular i j k case 1 flag 1 break case 2 l il j k break case 3 flag 0 break Page 21 of 142 IOI 2002 Yong In Korea if p b 0 2 pfa 0 lt 1 II p b 1 2 plal1 1 lt 1 p b 0 2 pfa 0 gt r plb 1 2 pla 1 5 c sa count gt sol sol count void WriteOutput printf Sd n sol int main ReadInput Sort 0 n 1 Run WriteOutput return 0 Page 22 of 142 IOI 2002 Yon
13. 2002 Page 65 of 142 IOI 2002 Yong In Korea D Source Code for BUS Kyung Young Lim TASK BUS LANG C Optimal Solution O N 3 f include stdio h include lt math h gt define maxn 1001 int int int int int int n x maxn y maxn p maxn dis maxn maxn pivot min void input int scanf d for i 1 scanf d scanf d iE amp n p ose ne i amp x i amp y i void preprocess int for dis i j abs x i dis j i dis i j x J abs y i yl31 void qsort int s int e int int if i j t Vi s lt e dis pivot p e 1 s j lt e 1 j dis pivot p j lt v itt t j if p i p i p j p j t t plel plel pla ilz pli t1 t qsort s i qsort i 2 e void process Page 66 of 142 IOI 2002 Yong In Korea int i j k int bp bq int mm for i 1 i lt n itt fay 273G min 9999999 for i 1 i lt n 1 i pivot i qsort 1 n for j i 1 j lt n j if min gt dis i p n disti Ipin 1 min dis i l p n dis i p n 1 bp p n bq 99 for k n k gt 2 k if dis j bp lt dis j p k bq bp bp p k if bq 99 dis j bq lt dis j P k11 if p k bp bq p k mm dis i p k 1 dis i j dis
14. David ANANIAN COOPER Clarence DANG Alex FLINT Roland SCHATZ Christian WIRTH Thomas WUERTHINGER Isa ALIYEV Teymur GULIYEV Tofig HASANOV Farid AHMADOV Emir KUMALIC Mirza SEJTO Damir ZEKIC Senad UKA Lucas FURUKAWA GADANI Cesario BARROS MARTINS Jason THEAN Denis ROSSET Urban SUPPIGER David FREY Jamer CUEVAS Edwin NINO Juan SARRIA Alberto Eliseo PACHECO ALLENDE Ledesma YOGERLAN ALMANZA Avgoustinos KADIS George PAPADOPOULOS Kyriakos MATSIKARIS Alexis CHRISTOFORIDES Milan STRAKA Jiri STEPANEK Urs GANSE Melanie SCHMIDT Michael RASMUSSEN Ulrik BUCHHOLTZ Jens BOLDSEN Dia SAMI Page 124 of 142 144 143 141 140 139 135 IOI 2002 Yong In Korea Mohamed ABDEL GAWAD EGY EGY EGY ESP ESP ESP FRA FRA FRA GBR GEO GEO GRC GRC GRC GRC HKG HUN IDN IDN IND IND IND IND IRL IRL IRL ISR ITA ITA ITA KAZ KAZ KAZ KAZ KGZ KGZ KGZ KWT KWT KWT LKA LKA LTU LUX LUX LVA LVA MAC MAC Page 125 of 142 EGYC02 EGYC03 EGYC04 ESPC02 ESPC03 ESPC04 FRACOI FRAC02 FRACO3 GBRC02 GEOC02 GEOC03 GRCCOI GRCC02 GRCC03 GRCC04 HKGC02 HUNCO01 IDNC03 IDNC04 INDC01 INDC02 INDC03 INDC04 IRLC01 IRLC02 IRLC03 ISRC04 ITACO01 ITACO2 ITACO3 KAZCOI KAZC02 KAZC03 KAZC04 KGZC01 KGZC03 KGZC04 KWTCOI KWTCO2 KWTCO3 LKACOI LKACO2 LTUCO3 LUXC03 LUXC04 LVAC02 LVAC04 MACCOI MACCO2 Omar FAWZY Abd El Kader EL HAIDARY Xavier ROCA Raul VINYES Antoni Italo DE
15. The windows environment includes vim and emacs as well as notepad GCC on Windows The GCC compiler version we are using in the windows environment is GCC 2 95 3 WARNING If you install Freepascal and GCC e g as in DJGPP in the same Windows installation be sure to have DJGPP in your path before Freepascal or GCC won t work This seems to be because it finds cpp exe from the pascal binaries and then thinks that the pascal binary directory is the place for its compiler binaries which it subsequently fails to find For windows we are using the DJGPP You can find out about DJGPP and downloading it from http www delorie com djgpp Our current installation includes the following packages v2 copying dj DJGPP Copyright info v2 djdev203 zip DJGPP Basic Development Kit v2 faq230b zip Frequently Asked Questions v2 readme 1st Installation instructions v2gnu bnu2121b zip Basic assembler linker v2gnu fil141b zip GNU fileutils v2gnu gcc2953b zip Basic GCC compiler v2gnu gdb511b zip GNU debugger v2gnu gpp2953b zip C compiler v2gnu grep24b zip GNU Grep v2gnu 1ss374b zip GNU Less v2gnu mak3791b zip Make processes makefiles v2gnu txi41b zip Info file viewer rhide15b 20020625 prerelease zip RHIDE snapshot from http www rhide com Pascal on Windows We have installed Freepascal 1 0 6 See http www freepascal org for obtaining a copy If you install the full version dos106full zip yo
16. ans which means k th function call rect a b c d returns ans EXAMPLE INPUT AND OUTPUT Example rods in rods out Dis ds W Qo ds IN Oo oud N ds w Qo ds 4 00 SCORING If your program violates any of the constraints e g more than 400 rect calls or if your program s output the locations of the rods is not correct the score is 0 If your program s output is correct then your score depends on the number of rect calls for each testing data For each test case if the number of rect calls is at most 100 then you get 5 points If your program calls rect 101 to 200 times you get 3 points If the number of rect calls is between 201 and 400 then you get 1 point Page 70 of 142 IOI 2002 Yong In Korea A Solution Ian Munro The fastest approach we know is to perform six binary searches Using entire rows columns as the query rectangle the top and bottom rows and leftmost and rightmost columns containing any portion of a rod can be found using 4 binary searches or 4 lg N calls to rect We now have the smallest rectangle containing all of both rods By checking the corners of this rectangle 4 calls to rect each with a 1 by 1 query rectangle we can determine the general form of the structure as in the examples of the figure and their rotations Finally the solution can be found in one or two more binary searches depending on the case el Saas 3 comers 2 opposite corners 2 adjacent corners
17. be the minimum total cost of all partitionings of jobs Jj Ji 1 Jy into batches Let Ci k be the minimum total cost when the first batch is selected as J Ji i Jet That is C k Cy S T Tag Tki Fit Fm Fy Then we have that C min C k k i 1 N 1 for 1 lt i lt N and CN 1 0 a O N Time Algorithm The time complexity of the above algorithm is O N Page 53 of 142 IOI 2002 Yong In Korea b O N Time Algorithm Investigating the property of C x P Bucker 1 showed that this problem can be solved in O N time as follows From Ck Cy SH GA Taa Ty Fi Fin Fr we have that fori k l Ci k CD 8 Ci C Tk Ta ot Ti Fit Fait Fy 2 0 Cy C Ti Tea Ti S Fit Fait Fy Let g k C Cj Tk Tat E Tr and fi F Fi T On Property 1 Assume that g k lt Ki for 1 xi k lt I Then Ck lt Ci Property 2 Assume g j k lt g k for some 1 lt j lt k lt n Then for each i with 1 Six Is Ci lt Ci k or Ci lt Ck Property 2 implies that if g j k lt g k for j lt k lt l Cy is not needed for computing Fi Using this property a linear time algorithm can be designed which is given in the following Algorithm Batch The algorithm calculates the values C for i N down to 1 It uses a queue like list O i ini 12 11 with tail
18. plane 3 else return plane gt 3 void solveproblem int bound 2 2 int target add int i loop for loop 0 loop lt 2 looptt maintain that AK X MA K AN2 b na ok BROOD 1 2x nci 4 x n 39 ke x l 1 or 0 bound 0 0 check dest num 1 loop num 2 bound 0 1 num 2 check dest num 1 loop bound 1 0 1 bound 0 0 bound 1 1 num 2 3 bound 0 1 for i bound 0 0 i lt bound 0 1 it 2 data loop i data loop i for i num 2 i gt 0 i if check dest i loop check dest i 1 loop Page 30 of 142 IOI 2002 Yong In Korea target bound 0 1 gt bound 1 1 amp bound 0 1 amp bound 1 1 add 2 else target bound 0 0 lt bound 1 0 amp bound 0 0 amp bound 1 0 add 2 answer i 1 loop data loop target target add answer 0 loop data loop bound 0 0 gt bound 0 1 bound 1 0 bound 0 0 void writeresult int i for i 0 ix num i printf Std Std n answer i 0 answer i 1 int main getdata preprocessing solveproblem writeresult return 0 Page 31 of 142 IOI 2002 Yong In Korea Task 3 XOR Hwan Gue Cho Chong Dae Park Jyrki Nummenmaa XOR PROBLEM You are implementing an application for a mobile phone which has a black and white screen
19. return 0 Page 80 of 142 IOI 2002 Yong In Korea Result of Day2 Competition A Summary Task Name Submission gon Average Standard scores deviation BATCH 235 23 15 28 28 BUS 234 6 22 56 21 76 RODS 216 37 14 34 85 Note The averages and standard deviations are calculated from submitted solutions only B Contestants Scores sorted to X axis batch Submit 235 Average 23 15 Full Score 11 120 100 80 60 40 20 0 50 100 150 200 250 Page 81 of 142 IOI 2002 Yong In Korea bus submit 234 Average 22 56 Full Score 6 120 100 M 80 60 40 20 0 50 100 150 200 250 rods Submit 216 Average 37 14 Full score 14 120 100 80 60 40 20 0 0 50 100 150 200 250 Page 82 of 142 IOI 2002 Yong In Korea BACKUP TASKS Back Up Task 1 NETWORK Jung Heum Park Robust Communication PROBLEM Your company has a head office in Seoul and a number of local branch offices located in other cities around Korea Every office has a communication computer The computer in each local branch is connected to the main computer in the head office via a bidirectional communication link Furthermore some pairs of computers in local branches are also connected to each other via direct communication links However there can only be a single communication link between any pair of computers Messages sent from one computer to
20. 1 might have been a frog path with hop length 4 except there are only 2 plants flattened so we are not interested and the diagonal path including the plants on row 2 col 3 row 3 col 4 and row 6 col 7 has three flat plants but there is no regular hop length which could have spaced the hops in this way while still landing on at least 3 plants and hence it is not a frog path Note also that along the line a frog path follows there may be additional flattened plants which do not need to be landed on by that path see the plant at 2 6 on the horizontal path across row 2 in Figure 4 and in fact some flattened plants may not be explained by any frog path at all Your task is to write a program to determine the maximum number of landings in any single frog path where the maximum is taken over all possible frog paths In Figure 4 the answer is 7 obtained from the frog path across row 6 INPUT Your program is to read from standard input The first line contains two integers R and C respectively the number of rows and columns in your rice paddy 1 lt R C lt 5000 The second line contains the single integer N the number of flattened rice plants 3 lt N lt 5000 Each of the remaining N lines contains two integers the row number 1 row number lt R and the column number 1 lt column number lt C of a flattened rice plant separated by one blank Each flattened plant is only listed once OUTPUT Your program is to write to stan
21. 142 IOI 2002 Yong In Korea 28 Greater variety of useful editors we suggest FTE 31 To delete bugs in IDE and RHIDE 35 Stability of competition environment mainly IDEs still needs to be improved Alternative or additional IDEs might be made available 36 We need a better Pascal compiler Windows Environment 2 RHIDE IDE still has lot of bugs we really need it 6 We need the better IDE 10 Try to document all the RHIDE bugs and make a manual of them 30 Commercial compilers tools are desirable 31 To delete bugs in IDE and RHIDE 35 Stability of competition environment mainly IDEs still needs to be improved Alternative or additional IDEs might be made available 36 We need a better Pascal compiler Grading System 2 The way to grade relative score is good to identify who the best However it is not good for average contestant The suggestion is to improve the formula of the grading system 14 It is better to make the interface more easy and the response time short for the Grading system 20 The grading system should give more response The checker programs find out one reason to reject the result if it is not correct you should write that reason to the checker response file Also when a program in a test case does not meet the time limit it would be give to know when the program execution is cut Naturally it would be very useful to have the running time in cases when the program solves the case with
22. 2 27 33 23 9 9 BUS 1000 26 2 32 0 22 3 8 7 8 7 74 2 50 27 18 4 2 RODS 1 9 48 6 26 2 17 5 3 9 1 9 18 Task Finding Algorithm No 1 5 answer Easy z 2 4 Hard SE 2 24 33 22 15 7 FROG 1 9 23 3 32 0 21 4 14 6 6 8 74 2 1 3 15 31 51 UTOPIA 1 9 1 0 2 9 14 6 30 1 49 5 77 1 4 9 19 29 41 XOR 1 0 3 9 8 7 18 4 28 2 39 8 3 BATCH 2 2 5 22 39 33 3 95 Page 131 of 142 IOI 2002 Yong In Korea 1 9 1 9 4 9 21 4 37 9 32 0 1 1 7 15 33 46 BUS 1995 1 0 6 8 14 6 32 0 44 6 41 2 22 31 21 16 11 RODE 1 9 21 4 30 1 20 4 15 5 10 7 AT Task Writing Program No 1 5 answer Easy 2 2 s Hard aee 2 24 27 23 20 7 FROG 1 9 23 3 26 2 22 4 19 4 6 8 7 4 20 21 20 15 23 UTOPIA 3 9 19 4 20 4 19 4 14 6 22 3 09 2 10 25 28 19 19 XOR 2 0 9 7 24 3 27 2 18 4 18 4 21 3 16 27 23 16 18 BATCH 9 9 15 5 26 2 22 4 15 5 17 5 27 9 8 10 30 27 19 BUS 8 7 7 8 9 7 29 1 26 2 18 5 2 4 2 3 14 28 18 38 ROD
23. 2 D 4 29 29 5 0 0 22 8 4 5 43 2 Backu P Q I d 16 4 16 P 29 5 099 2 3 20 4 11 4 86 499 Do you like the Grading System No 1 5 answer No 3 i Much Average Submit 8 2 1 3 1 19 4 22 Page 139 of 142 IOI 2002 Yong In Korea 18 2 4 5 2 3 6 8 25 0 43 2 Testin 8 2 P 3 LI al 4 42 18 256 0 0 11 4 25 0 45 4 Dun 3 9 t 2 4 58 18 2 096 0 9 1 15 9 56 8 8 0 0 7 6 23 Backup 13 2 0 0 15 9 13 6 52 3 444 Receiving Contents of Students Home Directories Useful Not useful 42 2 95 594 4 5 Opinion on the 1 page solution handout multiple selections Useful sis Not useful 2 T Too detailed T Just right RIR Not detailed enough Pee 13 delegations marked both of Useful and Just right 3 delegations marked both of Useful and Not detailed enough IOI LIST YES NO Are you subscribed to the 32 12 IOI LIST 72 7 27 3 Written Comments Linux Environment 2 RHIDE IDE still has lot of bugs we really need it 10 Try to document all the RHIDE bugs and make a manual of them 14 For Linux it is better to provide the environment under X window and the tools with better GUI Page 140 of
24. 6 15 9 12 5 11 4 11 4 22 7 Least 6 2 9 10 8 4 5 13 6 4 5 20 5 22 7 18 2 9 1 11 4 Note A delegation marked both of FROG and XOR for BEST We count it as 0 5 each A delegation marked All are OK for LEAST We count it as No mark Page 138 of 142 IOI 2002 Yong In Korea The Idea of Output Only and Relative Scoring YES NO Do you like the idea of 34 5 9 5 output only Tasks 78 4 21 6 Do you like the idea of 37 7 the relative scoring 84 1 15 9 Note A delegation was divided in opinion on output only tasks The leader claims NO and the deputy leader claims YES We count it as 0 5 each Grading System Usability No 1 5 answer Easy A 3 d Hard spes 10 21 9 9 0 2 Submit 5 705 47 7 20 4 4 6 0 4 6 17 TU 10 18 1 4 1 0 is sme 22 7 40 9 25 0 9 1 2 3 094 i 9 25 5 5 Printing 9 4 56 8 11 4 1 49 9 ne 9 21 8 6 Backup 00500 47 7 18 2 13 6 i id Grading System Response Time No 1 S answer Slow 2 i Fast UES 12 0 1 11 3 17 Submit 973 0 Q399 25 0 6 8 38 6 42 Testin a 0 2 10 19 4 06 S 27 3 0 4 5 22 7 9 1 86499 Printin i 9 9 d
25. TUR CZE HRV LUX ZAF LKA HKG NLD LTU YUG YUG IDN ISR GEO MEX MDACO3 NLDC02 GBRC04 BGRC02 BRAC03 DEUC03 LTUC02 ARGCOI CANCOI ITAC04 VNMCO03 ESTCO2 ESPC01 HUNC04 LKAC03 SVNC03 CUBCOI BLRC03 IRLC04 FINCO2 IRNC02 CHEC03 TPEC04 UKRC03 ARGC03 BRAC02 HKGCOI LUXCO2 THACO3 HKGC03 ARMC02 BLRC02 ARGC02 SWEC04 GBRC03 TURC03 CZEC02 HRVC04 LUXCOI ZAFC02 LKAC04 HKGC04 NLDC04 LTUC04 YUGC02 YUGC04 IDNC02 ISRCO3 GEOC04 MEXCOI Dumitru CIUBATII Bram KUIJVENHOVEN Nicholas KREMPEL Veselin RAYCHEV Rafael TEIXEIRA PAULINO Alexander HULLMANN Vilius NAUDZIUNAS Pablo DAL LAGO Marcin MIKA Stefano MAGGIOLO Nhat LAM XUAN Hendrik NIGUL Tomas LLORET Gabor SIMKO Chethiya ABEYSINGHE Matej JAN Jos David RODR GUEZ VELAZCO Sarge ROGATCH Martin ORR Olli Pentti SAIRA Siavosh BENABBAS Ruben ANDRIST Tsung Chieh CHANG Volodymyr TKACHUK Alejandro DEYMONNAZ Daniel BUENO DONADON Man Hon CHAN Thierry STEINBERG Vasan CHIENMANEETAWEESIN Siu On CHAN Davit HAYKAZYAN Aliaksei SIKORSKI Diego Alejandro GAVINOWICH Dan NILSSON Adam BULL Mustafa Onur KILAVUZ Pavel CIZEK Marko ZIVKOVIC Michel CONRAD Heinrich DU TOIT Nayana P SOMARATNA Koon Ho WONG Marijn KRUISSELBRINK Martynas KRIAUCIUNAS Nikola TODOROVIC Aleksandar ILIC Randy SUGIANTO Noam RAFHAEL Alexander TARKHNISHVILI Jorge DEL RIO Page 123 of 142 118 124 90 118 159 182 124 91 122 112 107 177 10
26. Yong In Korea define ERRNORECTCALL 9 define upperbound 400 ifdef USERLIB define De x x define En x x define INFILE rods in define OUTFILE rods out define LOGFILE rods log static int rectlib initialized En 0 static int srl sp2 sel spl sq2 SC2 sr2 sql static FILE lgfile oufile static int count N else define En x x 3 5 define De x x 5 3 define INFILE rods sin define OUTFILE rods sout define LOGFILE rods slog static int srl sp2 scl static int rectlib initialized En 0 static int count N static int spl Sr2 sql sq2 sc2 static FILE lgfile oufile endif static void erroroutput int errno FILE f f fopen OUTFILE w printf Ss n errmsg errno fprintf f Sd n s n En 0 errmsg errno fclose f static void init Read Data and initilization FILE fg if De rectlib initialized return rectlib initialized En 1 count En 0 if f fopen INFILE rt 1f erroroutput ERROPENINPUTFILE Page 73 of 142 IOI 2002 Yong In Korea exit 0 if fscanf f Sd amp N 1 erroroutput ERRINVINPUTFILE exit 0 if De N lt 5 De N gt 10000 erroroutput ERRNOUTOFRANGE exit 0 if fscanf f Sd sd Sd Sd Sd s
27. a topological layout i e a drawing in the plane of a graph the deciding the existence of a noncrossing path connecting path connecting two given vertices is NP complete even if the graph is 3 regular 2 B Testing data generation plan Although this problem belongs to NP hard many cases could be solved easily The test should not contain many impossible cases since the lazy program says just O may get higher scores C References 1 K Jansen and G J Woeginger The complexity of detecting crossingfree configurations in the plane B T 33 4 580 595 1993 2 J Kratochvil A Lubiw and J Nesetril Noncrossing subgraphs in topological layout SIAM J Discrete Mathematics 4 223 244 1991 Page 97 of 142 IOI 2002 Yong In Korea APPENDIX I IOI 2002 Competition Rules These Competition Rules include the Competition Procedures and Judging Procedures which the host is obliged to send to invited countries four months prior to the competition Minor changes to these rules will likely be made the final version will be distributed in the first GA meeting of IOI 2002 Competition Dates IOI 2002 will take place from Sunday August 18 Arrival Day to Sunday August 25 Departure Day The First Competition Day is Tuesday August 20 and the Second Competition Day is Thursday August 22 On each competition day contestants will be given three tasks to complete in the five hours from 9 00 to 14 00 There will also be a
28. and worm One of the methods used in sequencing a unknown DNA Page 9 of 142 IOI 2002 Yong In Korea sequence is to use DNA chips An experiment with DNA chips tell us which substrings in the chips belong to the unknown DNA sequence and which substrings do not Constructing the whole sequence by collecting these information is a place where this problem might apply D History This problem is a variant of the so called superstring problem in which given a set of strings we want to find a shortest string that contains the strings in the set as substrings This problem is known to be NP complete E References 1 S Skiena Reconstructing strings from substrings Journal of Computational Biology 2 1995 333 353 Practice Task 3 RED Chong Dae Park Red Devil PROBLEM Red Devil the Korean national soccer team supporters club will have a country wide tour to N cities to celebrate the achievement in 2002 FIFA World Cup Korea Japan Cities are represented by numbers 1 2 N The Red Devil s tour starts with city 1 and visits all N cities exactly once after which it should return to city 1 the starting position The travel distance between two cities and J denoted by d is known Note that the distance from city to city J is symmetric to the distance from city J to city I that is d 1 J d J I For any three distinct cities Z J and K it holds that dU K d 1 J d J K Furthermore it holds
29. another can follow any continuous path between the computers using any links and passing through any intermediate computers p Figure 1 shows an example communication network of a company with one head office and four local branches Circles represent communication computers and lines represent communication links The number shown next to a circle is the index of that computer The main computer 4 always has index 1 the remaining computers are numbered sequentially starting at index 2 Observe that there are three different communication paths between computer 2 z and computer 3 Figure 2 3 use the direct communication link between 2 and 3 2 1 3 use the link from 2 to the head office 1 plus the link from 1 to 3 2 1 4 3 from 2 to the head office 1 from 1 to 4 and from 4 to 3 over the direct link N Unfortunately computers or links can fail knocking out communication paths that use them In the example above if the link from 1 to 3 were to fail then path 2 would not be usable but paths 1 and 3 would still work If instead computer 4 were to fail then path 3 would not be usable but paths 1 and 2 would still work Your company wants its communication network to be robust to a single failure that is designed so that neither a single computer failure nor a single communication link failure would interfere with the ability of each fault free computer to communicate with all other fault free computers You may add bidirecti
30. button to upload a text file to be printed 8 Backup restore facility Backup File box and Backup button can be used to store user s file on the IOI 2002 Contest System server The filenames of backup files are advised to be in English and follow UNIX filename conventions alphanumeric no white spaces Press Restore button to display the restore page Page 113 of 142 IOI 2002 Yong In Korea Restore Page Login ID sllee Time 2002 07 29 17 35 42 Reload Stored Files Filename with spaces 2002 08 07 11 06 12 delete Ute non english filename 2002 08 08 11 51 34 delete test cpp 2002 08 08 12 09 47 delete delete all 9 Stored files table The files stored in the IOI 2002 Contest System server using the backup facility in the main screen are listed in the stored files table The files in the table are sorted by the backup time The files can be displayed or downloaded by following the HTML links at the filenames in the first column of the table Click delete on the right of the filename to delete the file from the server The file will be permanently deleted Clicking delete all at the bottom of the table will delete all the files stored in the server A confirmation window will pop up for the delete options FEATURES The IOI 2002 Contest System provides user facilities to help them through International Olympiad in Informatics Users can submit solutions to tasks test solu
31. computers Logging in is not necessary for Windows Under Linux contestants should log in as username ioi password ioi Questions During the first hour of competition contestants may submit written questions concerning any ambiguities or points needing clarification in the competition tasks Questions must be submitted on the provided Clarification Request Forms expressed either in the contestant s native language or in English If required delegation leaders will translate their contestants questions to English after they are submitted before sending the questions to the Scientific Committee The Scientific Committee will answer every question submitted by the contestants Since this may take some time contestants should continue working while waiting for the answer to their questions The only responses which will be given are YES NO and NO COMMENT contestants should phrase their questions so that a yes no answer will be meaningful Contestants will not be involved in or exposed to discussion regarding their questions Assistance Contestants may ask the support staff for assistance at any time The staff members will not answer questions about the competition tasks but will deliver Clarification Request Forms and printouts help locate toilets and refreshments and assist with computer problems Printing Contestants will be able to print via a facility provided in the competition environment The support staff will
32. contains an XOR call which does not have positive coordinates or your output file contains an XOR call with a coordinate value exceeding N then your score is zero Otherwise your score is 1 9xCallsInBestAnswerOfAllContestants CallsIn Y ourAnswer The score is rounded to the first decimal place for each case The total score is rounded off to the nearest integer Suppose that you submit a solution with 121 XOR calls If that is the best submission of all contestants your score is 10 If the best of the submitted solution of all contestants uses 98 XOR calls your score becomes 1 9x98 121 8 289 which will be rounded to 8 3 Page 33 of 142 IOI 2002 Yong In Korea A Solution Jung Gun Lim Chong Dae Park A TWO OPTIMAL SOLUTION FOR XOR We start by giving some definitions which will help us to explain our solution Definition 1 A grid point is an intersection point of two grid lines Definition 2 An imagecorner is grid point adjacent to an odd number of black pixels If a grid point p is an imagecorner we say that the ic value of p is 1 and we write ic p 1 and if p is not an imagecorner we say that the ic value of p is 0 and we write ic p 0 A grid point x Figure 1 An example image For example in Figure 1 the grid point x is adjacent to four pixels of which 1 is black and 3 are white This way the grid point x is also an imagecorner In total there are 10 imagecorners in the image in Figure 1 Itis
33. ct q ct whil 0 1 4 lt rows j row i 0 cn row j 0 cn e p n 2 amp amp q n 2 if p gt q q ct row j q cn else if p lt q p ct row i p cn Page 43 of 142 IOI 2002 Yong In Korea else if p c link i Links i j links i link j Links j i links j break p ct row i p cn q ct row j q cn matching rows for i 0 i lt rows itt if match i gt i if islinked i p ct row i 0 cn q ct row match i 0 cn min n 2 while p lt nt 2 gg q lt n 2 if p gt q g ct row match i q cn else if p lt q p ct row i p cn else if p c if min coc p min coc p minp p p ct row i p cn q ct row match i q cn add to sol c minp row i row match i for i 0 i lt rows itt if match i gt i if islinked i min n 1 p ct row i 0 cn while p lt n t2 if coc p lt min amp amp p c min coc p minp p p ct row i p cn p ct row match i 0 cn Page 44 of 142 IOI 2002 Yong In Korea while p lt n 2 if coc p lt min amp amp p c min coc p minp p en JIp ecn add to sol c minp row i row match i void update sol updating the best solution int i j if mcount count mcount count for i 0 i lt mcount i t for j50 3 4 j msols i jl sols i j
34. eon eesisseqeete ben even tete Inde ena get estat as 104 APPENDIX III User Manual for IOI 2002 ice de riim ex net aio dietus 107 APPENDIX IV IOI 2002 Contest System Users Manual sess 111 APPENDIX V List of Contestants o se y eco re etm eae Di eie in 121 APPENDIX VI Contestant Questionnaire 111 1 01177 a 127 Appendix VII Delegation Questionnaire ccceccccesceeeseceseceeeeeeseeceaeceseeeeeeesseeenseeneeee 136 Page 2 of 142 IOI 2002 Yong In Korea INTRODUCTION First we will explain the procedure used by the ISC International Scientific Committee and the HSC Host Scientific Committee to prepare and select the competition tasks Then we will give an overview of the tasks including solutions for and the basic theory behind them After the Call for Tasks announcement our HSC received 20 problems from Korea and abroad Of these we excluded 4 problems which were not mature enough to be used in IOI style competition tasks The HSC then prepared all solutions and test data sets 20 test cases for each task and discussed these sets with the ISC members in July The meetings held concerning IOI2002 task preparation were follows Call for Tasks announcement Oct 2001 Ist HSC meeting at KAIST Jan 4 discussed computer specification discussed Competition Rules 2nd HSC meeting in Pusan Feb 4 6 discussed submitted tasks selected 17 candidate tasks International Committee Mee
35. evaluation facilities trying to harmfully interfere with the running of the competition in any way or trying to communicate in any way during a competition round with anyone other than the competition staff will be disqualified from the competition The competition computers are connected via a local area network for submitting solutions running test executions making backups and printing Contestants are not allowed to access the network for any other purpose or with any tools other than the tools provided by the organizers Even sending a single ping command is strictly prohibited The competition staff should be contacted for help with any suspected network problems Also contestants are not allowed to make any material accessible to the network from their computers The competition facilities are provided over secure connections The network traffic is monitored and logged during the competition a contestant breaking these rules will be disqualified Submitted programs are not allowed to access the network are not allowed to fork are not allowed to create files other than those required in the task definition are not allowed to attack the system security or the grader are not allowed to attempt to execute other programs are not allowed to change file system permissions and are not allowed to read file system information other than the input file given in the task description A contestant whose program attempts any of the abo
36. exectime end do This facility is only available for test executions and submission executions Measuring the intermediate CPU usage of a program C C users Page 119 of 142 IOI 2002 Yong In Korea The grading system will observe your program s execution time from outside If you want to check intermediate execution times during test execution or submission execution you may use the exectime function which returns the number of milliseconds your program has used so far Here is a sample program to demonstrate its use main k 0 for 1 07 1 lt 100 i for 3507 j lt 1000000 j k J k n exectime This facility is only available for test executions and submission executions Page 120 of 142 IOI 2002 Yong In Korea APPENDIX V List of Contestants Gold Medalists 23 CNTRID Name Dayl Day2 Score KOR KORCO3 Wanyeong JUNG 260 250 510 POL POLCOI Pawel PARYS 263 195 458 BGR BGRCO Velin TZANOV 213 235 448 USA USACO3 Tiankai LIU 220 195 415 ROM ROMCO Radu BERINDE 158 240 398 KOR KORCO2 Kyung Yoon OH 200 190 390 RUS RUSCOI Petr MITRITCHEV 130 255 385 TPE TPECO01 Yin WANG 168 210 378 ROM ROMC02 Daniel Octavian DUMITRAN 152 220 372 LVA LVACOI Aleksandrs BELOVS 186 175 361 RUS RUSCO2 Petr KALININ 156 200 356 CHN CHNCO1 Yifei ZHANG 180 170 350 EST ESTCO1 Martin PETTAI 92 255 347 CHN CHNC02 Qiming HOU 111 235 346 CHN CHNC03 Wei YU 140 200 340 SVK SVKCOI Peter BEL
37. int cl int r2 int c2 int pl int ql int p2 int q2 Instructions To compile your rods c use fin in the gcc g clude crectlib h source code and compile it as 02 static rods c crectlib o 1m 02 static rods cpp crectlib o 1m The program crodstool c gives an example of using this GNU C C library Page 69 of 142 IOI 2002 Yong In Korea For C C in the RHIDE environment Be sure that you set the Option gt Linker configuration to crectlib o EXPERIMENTATION To experiment with the library you must create a text file rods in The file must contain three lines The first line contains one integer N the size of the grid The second line contains the coordinates of RODI r c r2 c where ri ci is the left end cell of RODI The third line contains the coordinates of ROD2 p q p2 q2 Where p q1 is the top end cell of ROD2 After running your program which calls report you will get the output file rods out This file contains the number of rect function calls and the coordinates of the ends of the rods you submitted in your call to report If there are any errors or violations of the requirements during library calls then rods out will contain the corresponding error messages The dialogue between your program and the library is recorded in the file rods log This log file rods 109 shows the sequence of function calls your program made in the form of k rect a b c d
38. m th row of the large picture is a specified row thus there are n m specified rows in the large picture If a specified row of the large picture contains a row of the small picture then check whether there is an occurrence of the small picture This gives an optimal expected time algorithm See Karkkainen and Ukkonen b Pretty good solution Determine a fingerprint of the small picture A simple fingerprint can be the first row of the small picture Search the large picture for fingerprints here one needs to use a fast algorithm such as Horspool For each fingerprint check whether it is an occurrence of the small picture c Naive algorithm For each position of the large picture check whether it is an occurrence of the small picture B Problem Type Reactive problem Page 94 of 142 IOI 2002 Yong In Korea C References 1 Karkkainen and Ukkonen Two and higher dimensional pattern matching in optimal expected time SIAM J Comput 29 2 1999 571 589 2 Horspool Practical fast searching in strings Software Practice and Experience 10 1980 501 506 Page 95 of 142 IOI 2002 Yong In Korea Submitted Task 3 BRIDGE Chong Dae Park Bridge Construction PROBLEM A long time ago in an ocean far far away there was a small kingdom with 101 islands The king of the kingdom wanted to build bridges to connect the islands A large project is initiated to connect these islands by 100 bridges As a chief engineer
39. of a GA meeting where tasks for a competition day are presented and approved and ending on the following competition day after the start of the competition During the curfew the contestants are not allowed to communicate by any means direct or indirect with any people who attend this meeting The contestants and the GA meeting participants must obey any instructions which limit the area where they are allowed to be The GA meeting participants are not allowed to communicate task related information to anyone not at the meeting before the end of the curfew Any contestant breaking the curfew may be disqualified If some other person associated with a national delegation breaks this rule then all contestants of that delegation may be disqualified Competition Time Procedures Page 100 of 142 IOI 2002 Yong In Korea Starting the competition Contestants will be taken to the competition hall before the competition starts A randomly chosen computer is designated to each contestant with a different assignment each time The computer will be powered up and will display a menu from which the contestant may choose to boot either Linux or Windows The competition envelope containing the task definitions and other necessary information will be in front of the computer Contestants are not allowed to touch the keyboard or open the envelope until the start signal is given At the starting whistle contestants may open their envelopes and use their
40. of the construction post you had to make an arrangement plan There were some restrictions for the arrangement A bridge had to be straight and not to cross one another Moreover the direction of a bridge should be orthogonal i e it should lie from south to north or from east to west You would get the awards if your attempt was a success but you might be punished if you were failed Unfortunately it is not possible to obtain such an arrangement in any case I wish you a good luck INPUT The input file name is bridge in The first line contains one integer the number of islands in the kingdom M 2 x M x 200 The following M lines contain information about the positions x y of M islands 1 lt x y lt 1000 OUTPUT The output file name is bridge out The output file contains M 1 lines Each of these lines contains two integers the pair of islands to connect The islands are numbered from 1 to M If such an arrangement is not possible the output should be just a single line that contains 0 EXAMPLE INPUTS AND OUTPUTS Examplel bridge in bridge out OPAFOUOWEHE O1 0 C0 OO iO Oy LN 3 3 5 5 6 6 8 9 9 Page 96 of 142 IOI 2002 Yong In Korea Example 2 bridge in bridge out A Comment This problem belongs to NP hard Given a set P of n grid points in the plane deciding whether P possesses a crossingfree spanning tree with only axis parallel edges is NP complete 1 And given
41. practice competition round on Monday August 19 All contestants MUST take part in the practice competition round Competition Equipment The specification is a PC with a 1 7 GHz Pentium 4 processor 256 MB RAM a standard US keyboard a mouse and a color screen If the model information is changed this section will be updated and announcements will be made on the web site and the IOI mailing list Blank paper and writing utensils will be provided Contestants may NOT take any material such as computing equipment including calculators organizers PDAs computers books manuals written or printed materials diskettes CD ROMs or communication devices into the competition area A contestant who is in possession of this type of material in the competition room may be disqualified Programming Environment The computers have a dual boot installation of Debian GNU Linux 3 0 woody and Windows XP In both the Linux and Windows environments the programs installed for the competition are set up in such a way that they can be found in the users path i e no extra setup is needed to use the tools Both the Linux and Windows platforms include GCC compiler version 2 95 3 and Freepascal fpc compiler version 1 0 6 These are the official compilers for IOI 2002 Newer versions of software may be installed as necessary to resolve hardware problems and or software compatibility bug patch issues If so the changes will be ann
42. rn r coc c break p ct p c rn void init ct initializing corner table inb 3 J for i 1 i lt n 1 i ct 0 i rn n 2 Page 39 of 142 IOI 2002 Yong In Korea void add_to_sol ct 0 i cn itl ct i 0 rn itl ct i 0 cn n 2 cor i 0 coc i 0 for i 1 i lt n 1 i for j 1 j lt n 1 j if b i count 0 solution int int int int int void dfs flip corner flip corner r2 flip corner flip corner i jJ flip corner r2 if cl gt c2 LE rl r2 G2 tS sols count sols count sols count sols count counttt links MAXN4 int c1 c2 int c2 int ri cl c2 2cl 2c2 rIs r2 r nr 2 match MAXN4 r2 link MAXN 2 MAXN 2 islinked MAXN 2 traveled MAXN 2 path MAXN 2 found int X vj int k pathlen for i 0 i lt links k 1i v link k i if traveled v else match v 1 path pathlen v pathlen found 1 return pa pa tr pa pa df if uU ct ct Q amp ct ct a a V a n n lentt eled v Lenrr found len 2 pathlen pathlen v 1 l match v Gaon TS return j b 4 1 3 b 4 3 1 b i 1 j 1 2 int r2 adding a rectangl maximal Page 40 of 142 to th matching algorithm IOI 2002 Yon
43. s is known to be a substring of the hidden string Append each character to s to have four strings sA sC sG and sT Call the oracle with each of the four strings If any of the four calls gets an answer yes them we have succeeded in incrementing the length by one We may repeat If every one gets an answer no then we can say that s is a suffix of the hidden string We prefix each character to s having As Cs Gs Ts Again call the oracle with each of these four strings If any one is answered yes the length of the string known to be a substring of the hidden string can be incremented by one If none is answered yes then s itself is the hidden string Initially s A or C or G or T Four calls to the oracle to determine the initial single character s Four calls to determine each character of the hidden string Four calls to determine the end of the string and another four to determine the start c A more complicated solution A more sophisticate method with 3 N sqrt N is possible See the reference 1 B Test Data Information Test data sequences can be obtained from a real E coli or C elegance whose whole DNA sequence multi mega bytes can be downloaded via several bioinformatics related web sites C Background This is an important problem in computational molecular biology especially in genome sequencing Genome sequencing is to read the DNA sequences of an organism such as human mouse
44. the minimum length of the longest bus route for the input Page 59 of 142 IOI 2002 Yong In Korea EXAMPLE INPUTS AND OUTPUTS Example 1 input output Example 2 input output The following figures show the bus networks for the inputs given above If in Example 1 bus stops 3 and 4 are selected as hubs then the longest route is either between bus stops 2 and 5 or between bus stops 2 and 1 There is no better choice for the hubs and the answer is 20 For the bus network in Example 2 if bus stops 5 and 6 are selected as hubs then the longest route is obtained between bus stops 2 and 7 There is no better choice for the hubs and the answer is 25 5 10 x 5 10 15 l Bus network for Example 1 Bus network for Example 2 SCORING If your program outputs the correct answer for a test case within the time limit then you get full points for that test case and otherwise you get 0 points for that case Page 60 of 142 IOI 2002 Yong In Korea A Solution a Algorithm Description The solution is based on the algorithm running in O N time presented in 1 Recently it is slightly improved in 2 but its implementation is too complicated to accept for the competition so we use the algorithm in 1 as a solution The diameter of a bus network is the longest length of the route between any two bus stops in the bus network Our goal is to find the minimum value of the diameters over all possible choices of
45. very easy to observe the following lemma Lemma 1 An image is all white if and only if there are no imagecorners We may now try to find a solution by working from the input image backward to an all white image by doing XOR operations The following lemma is the base of our solution Lemma 2 Suppose we perform XOR L R T B Let Q be the rectangle affected by XOR L R T B and let the grid point at left top corner of Q be a at left bottom of Q be b at right bottom corner of Q be c and at right top corner of Q be d Then XOR L R T B will change the ic value for a b c and d and the ic values for all other grid points will remain unchanged Proof Exactly one pixel adjacent to each of a b c and d will change their color It follows that the ic values will change for these points Now consider the other grid points at the edge of Q For all of these grid points exactly two pixels adjacent to them the ones inside Q will change their color Therefore the number of odd pixels around those grid points does not change Page 34 of 142 IOI 2002 Yong In Korea Finally consider the grid points inside Q For all of these grid points all four pixels adjacent to them will change their color Thus the ic values of these grid points will not change and this completes our proof When trying to reduce the number of corners we would like to reduce them maximally with each XOR call However it may not always be possible to choose an X
46. 0 25 0 45 5 RODS 2 0 5 2 15 20 4 19 4 5 0 11 496 4 5 34 1 45 5 Page 137 of 142 IOI 2002 Yong In Korea Task Understandability No 1 2 3 4 5 Average answer Easy Hard FROG 2 15 15 10 2 0 1 98 4 5 34 1 34 1 22 8 4 5 0 UTOPIA 2 15 12 7 7 1 2 21 4 5 34 1 27 3 15 9 15 9 2 3 XOR 2 20 15 4 0 3 1 83 4 5 45 5 34 1 9 1 0 6 8 BATCH 2 10 12 6 10 4 2 67 4 6 22 7 27 3 13 6 22 7 9 1 BUS 3 17 14 5 2 3 2 02 6 8 38 6 31 8 11 4 4 6 6 8 RODS 3 17 12 5 6 1 2 07 6 8 38 6 27 3 11 4 13 6 2 3 Task Translatability No 1 2 3 4 5 Average answer Easy Hard FROG 6 15 9 9 4 1 2 13 13 7 34 1 20 4 20 4 9 1 2 3 UTOPIA 6 12 13 9 4 0 2 13 13 6 27 3 29 5 20 5 9 1 0 XOR 6 17 9 8 4 0 1 97 13 6 38 6 20 5 18 2 9 1 0 BATCH 6 10 13 7 6 2 2 39 13 6 22 7 29 6 15 9 13 6 4 6 BUS 6 13 10 12 1 2 2 18 13 6 29 6 22 7 27 3 2 3 4 5 RODS 6 16 6 4 9 3 2 39 13 6 36 4 13 6 9 1 20 5 6 8 Preferring Tasks No mark FROG UTOPIA XOR BATCH BUS RODS Best 2 9 5 7 5 5 5 5 10 4 5 21
47. 0 HUN HUNCO3 Gabor PELLADI 170 79 249 IRN IRNC04 Mohammad MOHARRAMI 133 115 248 LTU LTUCOI Viktor MEDVEDEV 148 100 248 CHN CHNC04 Decheng DAI 90 157 247 EST ESTC04 Andres LUUK 226 20 246 TUR TURC04 Semsi Cihan YUCEL 144 100 244 IRN IRNCOI Hamed AHMADI NEJAD 62 177 239 TPE TPECO3 Shu Chun WENG 128 110 238 DNK DNKCO Bjarke ROUNE 104 132 236 SGP SGPC02 Jiquan NGIAM 131 104 235 EST ESTC03 Mihkel KREE 109 125 234 SGP SGPCOI Heng Ping Christopher MOH 152 80 232 SVK SVKCO2 Jozef TVAROZEK 96 135 231 COL COLCO3 Oscar RODRIGUEZ 145 85 230 HRV HRVCO1 Ivan SIKIRIC 100 130 230 FIN FINC03 Markus OJALA 98 131 229 GBR GBRC01 Paul JEFFERYS 103 125 228 AUT AUTCO2 Lukas STADLER 127 100 227 BLR BLRCO1 Maksim OSIPAU 132 94 226 Bronze Medalists 68 CNTRID Name Dayl Day2 Score SVK SVKC04 Radovan BAUER 79 145 224 SWE SWECO Erik BERNHARDSSON 98 124 222 POL POLC04 Marcin MICHALSKI 110 110 220 THA THAC04 Wittawat TANTISIRIROJ 145 75 220 DEU DEUCO1 Benjamin DITTES 135 84 219 ZAF ZAFCOI David Jacques CONRADIE 113 106 219 HRV HRVC02 Lovro PUZAR 100 116 216 KOR KORCO4 Heon JEONG 169 45 214 UKR UKRC04 Andriy STASYUK 71 143 214 FIN FINCO0O1 Veli PELTOLA 68 140 208 FIN FINC04 Olli Pekka KAHILAKOSKI 145 60 205 THA THACOI Piyawat LAMSAM 88 117 205 Page 122 of 142 IOI 2002 Yong In Korea MDA NLD GBR BGR BRA DEU LTU ARG CAN ITA VNM EST ESP HUN LKA SVN CUB BLR IRL FIN IRN CHE TPE UKR ARG BRA HKG LUX THA HKG ARM BLR ARG SWE GBR
48. 000 separated by single spaces The last line contains a sequence of N region numbers each of which is 1 2 3 or 4 OUTPUT Your program is to write to standard output The output consists of N lines each containing a pair of code numbers each preceded by a sign character These are codes pairs that will direct the teleporter to the given region sequence Note that there must be no blank following a sign but there must be a single space after the first code number If there are several solutions your program can output any one of them If there are no solutions your program should output the single integer 0 EXAMPLE INPUTS AND OUTPUTS Example 1 input Example 2 input SCORING If your program outputs a correct answer for a test case within the time limit then you get full points for that test and otherwise you get 0 points for the test case Page 24 of 142 IOI 2002 Yong In Korea A Solution Jung Heum Park Ian Munro The problem is two dimensional but is most easily solved as two one dimensional problems solved independently Let us first concentrate on the one dimensional problem The one dimensional problem is Given N code numbers and a sequence of N region signs each of which is or produce a sequence of N signed code values x so that the sign of X x matches the i region sign The basic approach is quite intuitive though seeing that it works requires som
49. 002 By the end of IOI 2002 we had received 44 completed forms almost 56 All tasks are considered to suitable for the IOI competition FROG is considered most suitable and UTOPIA is least BATCH is considered hardest to understand followed by UTOPIA XOR and FROG are easy to understand BATCH and RODS are rated harder to translate XOR is easiest RODS and FROGS are likable most by 2 9 XOR and UTOPIA are dislikable most by 2 9 The preferences are spitted evenly Over 3 4 of respondents supports the idea of output only tasks Over 5 6 of respondents supports the idea of the relative scoring The majority think the grading system of IOI 2002 easy and fast The respondents definitely think that it is useful to receive the contents of students home directories The respondents think that 1 page solution handout is useful and just right Some people think that it is not detailed enough More than 1 4 of respondents were not subscribed to the IOI LIST Task Suitability No 1 2 3 4 5 Average answer Less Much FROG 2 0 1 7 9 25 4 38 4 5 2 3 15 9 20 5 56 8 UTOPIA 2 6 4 5 14 13 3 57 4 5 13 6 9 1 11 4 31 8 29 6 XOR 3 1 6 11 j 16 3 76 6 8 2 396 13 6 25 0 15 9 36 4 BATCH 2 3 7 3 13 16 3 76 4 5 6 8 15 9 6 8 29 6 36 4 BUS 2 2 2 7 11 20 4 07 4 5 4 5 4 5 16
50. 2 amp p2 swi amp cl amp q1 Swi amp c2 amp q2 if cl gt c2 correcting the order of output Swi amp cl amp c2 if pl gt p2 swi amp pl amp p2 report rl ely X24 C2 Dl aly B27 q2 4 int r1 int r2 in th int area by rl int spac int center if rl r2 E143 while rl r2 center r1 r2 1 2 if pseudo rect r1 1 rl center return r2 center else r2 center 1 return r2 bottom to top int bottom to top search int r1 int int center if rl r2 r2tt while rl r2 center rl r2 2 if pseudo rect center r2 center return r1 r2 1 else rl center l return r1 left to right int left to right search int r1 int int center if cl gt c2 Cl while cl c2 center c1l c2 1 2 if pseudo rect rl cl center else c2 center 1 return c2 r2 C111 return c2 right to left int right to left search int r1 int int center if cl gt c2 Che return cl imt e2 7 function with virtual coordinates int cl binary searching top to bottom r2 int cl el I2 Ant c1 el r2 int c1 center r2 int cl Page 76 of 142 int c2 int c2 int c2 int c2 IOI 2002 Yong In Korea while cl c2 center cl c2 2 if pseudo rect rl r2 center c2 1 0 c2 center else ci centert1 return cl
51. 2 1 pr2 1 pc2 pc2 0 rk bottom to top search prl 2 pr2 2 pc2 pc2 1 pseudo output pri pc2 rk pc2 pr2 pci pr2 pc2 else ck right to left search pr2 pr2 pcl 2 pc2 1 1 if ck pc2 1 ck pc2 pseudo output pri pc2 pr2 pc2 pr2 pel pr2 ck if 114 12 134 14 2 if 11 1 amp amp 12 1 12 1 amp amp 14 1 112 1 amp amp 13 1 13 1 amp amp 14 1 dece de de dece KKK if 122 21 amp amp 14 1 v flip 1 d flip 1 if 11 1 amp amp 13 1 d flip 1 if 13 1 amp amp 14 1 h flip 1 pseudo init 0 Page 79 of 142 IOI 2002 Yong In Korea rk top to bottom search prl 1 pr2 2 pc2 pc2 1 if pc2 pcl 1 pseudo output prl pcl pr2 pcl rk pcl rk pc2 ck left to right search rk rk pcltl pc2 2 1 if ck pcl41 ck pcl pseudo output prl pcl pr2 pcl rk ck rk pc2 else if 11 220 v flip 1 pseudo init TY KKKKK if pseudo rect pri pri pcl l pcl 1 0 rk bottom to top search prl 2 pr2 1 pcl pcl 1 cl left to right search pr2 pr2 pcit1 pc2 1 1 pseudo output pri pcl rk pcl pr2 cl pr2 pc2 else ck right to left search prl prip pcl 2 pc2 1 1 rl top to bottom search prl41 pr2 2 pc2 pc2 1 pseudo output rl pc2 pr2 pc2 pri pci pri ck int main boundary search find_shape
52. 6 176 114 153 88 74 110 151 91 138 118 72 124 98 108 126 126 95 98 124 88 142 121 141 85 70 130 87 137 126 115 79 102 60 111 61 102 90 86 78 110 81 40 15 73 105 70 80 85 10 80 10 70 30 93 105 68 26 86 35 55 98 45 70 59 40 40 70 66 40 75 20 40 20 75 90 30 73 20 30 40 75 50 92 40 90 46 39 204 202 200 199 199 197 197 196 192 192 192 187 186 186 184 183 181 179 178 177 177 173 173 170 169 168 167 166 166 165 164 164 163 162 161 161 160 160 160 160 157 156 155 154 152 152 151 151 148 145 IOI 2002 Yong In Korea ISR TUR MDA MDA PRT BLR ISRCO1 TURC02 MDAC02 MDAC01 PRTC01 BLRC04 Ariel GUTMAN 34 110 Osman CELEP 58 85 Constantin JUCOVSCHI 60 81 Dumitru CODREANU 74 66 David RODRIGUES 104 35 Raman DZVINKOUSKI 115 20 Other Participants 137 sorted by ID CNTRID ALB ARG AUS AUS AUS AUT AUT AUT AZE AZE AZE AZE BIH BIH BIH BIH BRA BRA CAN CHE CHE CHE COL COL COL CUB CUB CYP CYP CYP CYP CZE CZE DEU DEU DNK DNK DNK EGY ALBCOI ARGC04 AUSCOI AUSC02 AUSC03 AUTC01 AUTC03 AUTC04 AZECOI AZEC02 AZEC03 AZEC04 BIHCOI BIHC02 BIHC03 BIHC04 BRACOI BRAC04 CANC02 CHECOI CHEC02 CHEC04 COLCOI COLCO2 COLC04 CUBC02 CUBC04 CYPC01 CYPC02 CYPC03 CYPC04 CZEC03 CZEC04 DEUC02 DEUC04 DNKC02 DNKC03 DNKC04 EGYCOI Name Ariel APOSTOLI Martin VALDES DE LEON
53. 7 use C and 1 6 use C B For Linux users about 3 7 use C 1 3 use C and 1 5 use Pascal Very few use both or switch the OS and the compiler between competition days The FreePascal IDE and RHIDE are used by more than 1 3 of respondents Emacs and vim are used by about 1 7 Notepad is about 1 9 About 2 3 use debuggers integrated with IDE Almost 1 2 use extra printf writeln statements in the program code About 1 8 use external debuggers such as gdb Calculators and editors are mentioned as other tools used The majority think the grading system of IOI 2002 easy and fast to use BATCH is somewhat hard to understand FROG and RODS are easier to understand About 1 2 of respondents rate UTOPIA and BUS as very hard to find algorithm XOR and BATCH are considered slightly harder FROG and RODS slightly easier RODS is hardest to write program though it is one of easier tasks to find algorithm BUS is considered slightly harder FROG is slightly easier Other tasks are around the middle FROG is likable most by 1 3 RODS by 2 9 Other tasks are about 1 10 Page 128 of 142 IOI 2002 Yong In Korea UTOPIA XOR and BUS are dislikable most by 2 9 More than 3 4 think that it is useful to receive the contents of the home directory Less than 1 4 of respondents were subscribed to the IOI LIST OS Linux Windows XP B
54. DEs do not recognize mouse actions in console mode Solution Use the Alt lt KEY gt hot keys to access the menus or run RHIDE from X Windows Page 110 of 142 IOI 2002 Yong In Korea APPENDIX IV IOI 2002 Contest System Users Manual Version 1 03 INTRODUCTION The IOI 2002 Contest System is a group of server applications and modules designed to support International Olympiad in Informatics 2002 Its main functions are to support the contest by providing submit test print backup restore facilities during the contest and to support automated grading of participants submissions after the contest The participants of the contest are given web interfaced contest supporting facilities during the contest This manual is to provide contest participants with information about how to use the IOI 2002 Contest System during the contest This manual does not contain information to setup and maintain the IOI 2002 Contest System for administering the contest USER INTERFACE The user interface of the IOI2002 Contest System is web based A user can connect to the system with a web browser Microsoft Internet Explorer or Mozilla using the URL provided The IOI 2002 Contest System s user interface consists of three Web pages login page main page and restore page Login Page When a user first connects to the IOI 2002 Contest System a login screen with input boxes for Login ID and Password will be shown Type in login id and passw
55. IOI 2002 Yong In Korea FOREWORD The materials in this booklet were used at IOI2002 held August 18 25 2002 in Yong In Korea The IOI venue was the central library building at Kyung Hee University More than 270 contestants from 77 countries took part in the competition In Korea the national programming contest for secondary school students was first held in 1984 Korea first participated as an Observer at the 3rd IOI held in Greece This year we confidently hosted IOI2002 in Korea The Scientific Committee of IOI2002 consisted of three subcommittees Task Evaluation and Technical Creating an excellent set of competition tasks is the key to the success of IOI while ensuring continuity Computing environments remain almost the same as in IOI2001 A new grading system was designed and implemented to fit the IOI2002 competition rules A new evaluation policy for an output only task was used In this evaluation policy the score of each contestant s solution depends on the best solution from among all contestants submissions This policy allows for the possibility of partial credit and the output only nature of the tasks also avoids the problem of imprecision and other errors in timing program execution We hope that this booklet helps in preparing future IOI competitions Kyung Yong Chwa Chair of Scientific Committee of IOI2002 Yong In city August 18 2002 Page 1 of 142 IOI 2002 Yong In Korea TABLE OF CONTENTS P
56. Korea Result of Day1 Competition A Summary scores 7 HO NE NE Average 51 97 16 21 25 43 propia 39 7 Standard deviation 30 97 21 56 18 96 Note The averages and standard deviations are calculated from submitted solutions only B Contestants Scores sorted to X axis frog Submit 251 Average 51 97 Full Score 24 120 100 PN PRE lar 80 s quem 60 que ae 40 m deu 20 lg qe m 0 T T T T e 0 50 100 150 200 250 300 Page 49 of 142 IOI 2002 Yong In Korea utopia submit 209 Average 16 21 Full Score 7 120 100 80 60 40 20 0 50 100 150 200 250 xor Submit 257 Average 25 43 Full Score 1 120 100 80 60 40 20 Page 50 of 142 IOI 2002 Yong In Korea DAY 2 TASK OVERVIEW SHEET DAY 2 TASK BATCH RODS material Time limit per test 32 MB 32 MB 32 MB C il C and O2 static O2 static 02 static uA e C 1m 1m m gps Pascal So 02 xs So 02 XS So 02 XS Maximum points per 5 5 test Program header comment when using C Program header rods rM using PASCAL a PASCAL LENG PASCAL asca TA is accepted puse l is PE 1 is UY is solved solved processed Page 51 of 142 IOI 2002 Yong In Korea Task 1 BATCH Hee Chul Kim Jyrki Nummenmaa Batch Scheduling PROBLEM There is a sequence of N jobs t
57. LA 139 200 339 IRN IRNCO3 Mohammadhossein BATENI 172 160 332 LVA LVACO3 Andrejs IVANOVS 144 185 329 KOR KORCO Hyung Sul KIM 170 140 310 CZE CZEC01 Josef CIBULKA 82 225 307 ISR ISRCO2 Yair CHUCHEM 176 121 297 SWE SWECO2 Daniel ANDERSSON 131 165 296 VNM VNMCO1 Khai TRAN QUANG 126 170 296 Silver Medalists 47 CNTRID Name Dayl Day2 Score USA USACOI Jacob BURNIM 102 191 293 RUS RUSC04 Dmitri PAVLOV 91 200 291 IDN IDNCOI Widagdo SETIAWAN 156 134 290 UKR UKRCO2 Petro LUFERENKO 143 146 289 FRA FRAC04 Benjamin GAILLARD 248 40 288 SVK SVKC03 Tomas DZETKULIC 195 91 286 CAN CANCOA David ZHANG 68 215 283 VNM VNMCO2 Hieu NGUYEN VAN 108 172 280 HUN HUNCO2 Peter PALLOS 103 175 278 ROM ROMC04 Marius Victor COSTAN 123 155 278 TUR TURCOI Sedat GOKALP 192 80 272 USA USACO2 Adam D ANGELO 72 200 272 CUB CUBCO3 Ronny L PEZ TRUJILLO 163 105 268 YUG YUGCO Dejan KOLUNDZIJA 78 190 268 Page 121 of 142 IOI 2002 Yong In Korea BGR BGRC04 Nikolay NIKOLOV 105 160 265 HRV HRVC03 Luka KALINOVCIC 148 115 263 POL POLCO2 Bartosz WALCZAK 167 95 262 YUG YUGCO3 Aleksandar ZLATESKI 68 193 261 AUS AUSC04 David GREENAWAY 140 120 260 GEO GEOCO01 Nicholas JIMSHELEISHVILI 93 165 258 CAN CANCO3 Matei ZAHARIA 84 173 257 NLD NLDCO3 Tijmen TIELEMAN 142 115 257 BGR BGRC03 Georgi TSANKOV 167 86 253 NOR NORCO3 Geir ENGDAHL 123 130 253 POL POLC03 Karol CWALINA 49 204 253 TPE TPEC02 Cheng Yu LEE 111 141 252 RUS RUSCO3 Pavel MAVRIN 122 129 251 USA USAC04 Alex SCHWENDNER 80 170 25
58. MORAGAS Guillaume RYDER Chargueraud ARTHUR Cl ment GENZMER Adam LANGLEY Giorgi BOCHORISHVILI Zviad METREVELI Theocharis ATHANASAKIS Milos TZIOTAS Xaralampos TSIMPOURIS Christos SAVVOPOULOS Siu Man CHAN Jozsef MARTON Ilham Winata KURNIA Felix HALIM Rahil ALI Anubhav GUPTA Vivek KAPOOR Adnan RAJA Eamon PHELAN Robert CUNNINGHAM Daniel IRVINE Michael KARASIK Paolo CODENOTTI Alessio ORLANDI Maurizio SAMBATI Nurzhan BAKIBAYEV Khairosh YERZHAN Anton NIKOLAYEV Zhanibek DATBAYEV Kirill BARYSHNIKOV Stanislav VASHUK Abdimital PAZYLOV Ali MUBARAK Ibrahim ALMAYAS Saleh ALSAFFAR Harshana DANTANARAYANA Amila DE SILVA Dainius KUNIGAUSKAS Jean Marc HENGEN Sidhath MYSORE Karlis GANGIS Sergejs KOZLOVICS Chi Hou HO Chon Kit WONG IOI 2002 Yong In Korea MAC MACC03 MAC MACC04 MDA MDAC04 MEX MEXCO2 MEX MEXC03 MEX MEXC04 MKD MKDCOI MKD MKDC02 MKD MKDC03 MKD MKDC04 MLT MLTCOI MLT MLTCO2 MNG MNGCOI MNG MNGC02 MNG MNGCO03 MNG MNGCO04 MOZ MOZCOI MOZ MOZC02 MOZ MOZCO03 MUS MUSCOI MUS MUSC02 MUS MUSC03 MUS MUSC04 NLD NLDCOI NOR NORCOI NOR NORC02 NOR NORC04 PRT PRTCO2 PRT PRTCO3 PRT PRTC04 ROM ROMC03 SGP SGPC03 SGP SGPC04 SVN SVNCOI SVN SVNCO2 SVN SVNCOA SWE SWEC03 THA THACO2 TKM TKMC02 TKM TKMC03 TKM TKMC04 UKR UKRCOI VEN VENCOI VEN VENCO02 VEN VENCO3 VNM VNMC04 ZAF ZAFCO3 ZAF ZAFC04 Cheng Chun NG lat Man IEONG Eugen SORBALO Eduardo LOPEZ Jesus PUENTE Manuel TORRES Aleksovs
59. OR call in such a way that it changes the ic value of all of the corners of the area affected by the XOR call Lemma 3 If the image is not all white it is always possible to choose such an XOR call that the number of imagecorners is reduced by either two or four Proof First observe that at least two of the imagecorners are on the same line For this examine the pixels in the topmost row which contains black pixels There is an imagecorner at the right top corner of the rightmost of these pixels and at the left top corner of the leftmost of these pixels These imagecorners can not be the same and they are on the same line Next observe that the imagecorners can not all be on the same line This can be done by first examining the topmost and bottommost imagecorners as above and finding out that the topmost imagecorners are higher up than the bottommost imagecorners Then examine the leftmost and rightmost imagecorners and find out that they can not be on the same vertical line It follows that not all imagecorners can be on the same line We can now choose such a rectangle that three of its corners are imagecorners as follows We first choose the rightmost of the topmost imagecorners and then some other imagecorner of the rightmost imagecorners The third imagecorner can be found as follows We start from the rightmost of the topmost imagecorners Only the adjacent pixel left and down from it is black and the other adjacent pixels are white We
60. ORE WORD 2a AA ANA NU ie caus R A deanna ee ee 1 TABLE OF CONFENT Siac tion quiste acte ttes MM iad da EE aaa 2 INTRODUCTION 2225 sete nee ase deat ta adi e eae aes 3 DAYO Practice Session oop me pee Et Pu pedet to dte a bets 6 Practice Task E NUMBER soos ata EROR ede Ves el rns Mais 6 Practice Task 2 STRING iniba anan a du eei dahila ad taie das a Practice T sk 3 AA nm ene aa RGR 10 Evaluation Results of Internet Practice Session aa 13 DAY AA 14 TASK OVERVIEW SHEET DAY laga aha eaan ia AA As aaa 14 Tasks PROGA S uA aem o eM EC E M ORS ana lagi LI S t 15 Task 2 MEO PU it fa oic itte ite Dedi iHa diu PAULA ONG itae E HN ka a 25 TSS SX ORR eset sass ces kas AA 32 Result ot Dayl E ORNS mile AANI LNAG AN NAA 49 DAY er AN AA AA AA ER 51 TASK OVERVIEW SHEET DAY 22 wz namna UU ord 51 Task le BATCH a ees NGA ANG ANA e t 52 qas AA AA AG AA 59 qTascs RODSS sr AA AA PA AA AA AA eT a 68 Result of Day2 Competitions eate edere e es ig BILAY ee 81 BACKUP MAAN AA AA 83 Back Up Task 1 NETWORK cscs inte asa wees 83 Back Up Task 2 DIAMOND 5 a na NAAN Gat 86 SUBMITEED TASKS uer aa An Na kakalasan nkaka Bana atas tate katas bun Ka Pedes quuin 89 Submitted Task 1 ROBOT Ulam tie tos i uaria eno nina EI ten edv onda 89 Submitted bas PICTURE et paan dese autas oe da dione aee 93 Submitted Task 3 BRIDGE neo Io d n RITE bs 96 APPENDIX I IOI 2002 Competition Rules sess 98 APPENDIX IE Programming Enyirontment
61. S 1 9 2 9 13 6 27 2 17 5 36 9 37 Preferring Tasks No mark FROG UTOPIA XOR BATCH BUS RODS Best 3 34 13 8 10 12 23 2 9 33 0 12 6 7 8 9 7 11 7 22 3 Least 5 4 23 23 17 22 9 4 9 3 9 22 3 22 3 16 5 21 4 8 7 Receiving Contents of Students Home Directories No answer Useful Not useful 6 79 18 5 8 76 7 17 5 IOI LIST YES NO Are you subscribed to the 23 80 IOI LIST 22 3 77 7 Page 132 of 142 IOI 2002 Yong In Korea Written Comments Linux Environment 1 Install RHIDE s help on Linux Whenever I accidentally pressed the right mouse button I got a segmentation fault Fix the mouse on the Linux shell 8 ZSH was not installed under Linux 14 Four Manager is very good shell and it is free 15 text mode 80x50 18 Configure RHIDE problem 23 Create shortcuts on desktop 35 KDM maybe Need FTE 42 The compiler options for g specified on the task summary sheet worked under Windows but under Linux only a out file was generated no exe so I could not make use of Linux because I had never used g before 43 FTE editor Nvidia drivers 1600X1200 resoltion 45 GPERF was missing for generating perfect hash functions 46 Privileged 72 User screen feature of RHIDE RHIDE Help files RHIDE doesn t work in X Mouse in console mode RHIDE had a few crashes 82 RHIDE 1 5 i
62. Sd n msols i 2 msols i 3 msols i I 1 printf Sd n mcount int main int argc char argv read_data 0 delete min row or col delete on by one print argv 1 return 0 Page 46 of 142 msols i 0 IOI 2002 Yong In Korea E Source code for XOR SensQ Award Winner The contestant Tiankai Liu gets 100 points 99 7 pts exactly in Task XOR His solution is the best except the test case 3 his solution uses 29 XORs The best one uses 28 XORs Tiankai LIU USACO3 include lt stdio h gt include lt assert h gt int N K 0 Waas 0 int color 2000 2000 int needy 2001 2001 0 FILE fin fout void get needy int i int 3 if i gt 0 LE 0 needy i j color i 1 j 1 if lt N needy i j color i 1 j if i lt N if j gt 0 needy i j color i 3 1 if j3 lt N needy i j color i j needy i j amp 1 void use rect int i int j int ii int jj fprintf fout d sd Sd dWMn j l jj itl ii notice the tricky 1 and lack of 1 K needy i j 1 needy i jj 1 needy ii j 1 needy ii jj 1 1 1 int main int argc char argv ine iy cy tir du Er G int ninrow nincol int inrow 2000 incol 2000 bool found get input and figure out what is needy fin fopen argv 1 r assert fin fscan
63. The x coordinates of the screen start from the left and the y coordinates from the top as shown in the figures For the application you need various images which are not all of the same size Instead of storing the images you want to create the images using the phone s graphics library You may assume that at the start of drawing an image all pixels of the screen are white The only graphics operation in the phone s library is XOR L R T B which will reverse the pixel values in the rectangle with top left coordinate L T and bottom right coordinate R B where L stands for the left T for the top R for the right and B for the bottom coordinate Note that in some other graphics libraries the order of the arguments is different As an example consider the image in Figure 3 Applying XOR 2 4 2 6 to an all white image gives the image in Figure 1 Applying XOR 3 6 4 7 to the image of Figure 1 gives the image in Figure 2 and applying XOR 1 3 3 5 to the image in Figure 2 finally gives the image in Figure 3 1 2 34567 1 2 3 4 4 5 6 7 7 Figure 1 Figure 2 Figure 3 Given a set of black and white pictures your task is to generate each picture from an initially white screen using as few XOR calls as you can You are given the input files describing the images and you are to submit files including the required XOR call parameters not a program t
64. Xx n grid of equal sized cells Cells have row numbers counted from top to bottom and column numbers counted from left to right top left corner has row number 1 and column number 1 In the grid B cells are black and the rest is white A digital diamond of size k k 21 is a square such that its diagonals are horizontal and vertical and the sides of the square have k cells placed diagonally see example Figure 1 a A digital diamond of size 1 b A digital diamond of size 2 c A digital diamond of size 3 There is an n X m grid and some grids are filled with black as shown in Figure 2 Figure 2 A digital diamond of size 6 This problem is to find a largest digital diamond which contains at most one black grid INPUT The first line contains two integers m and n 1 lt m n lt 100000 first m the number of rows and then n the number of columns in the grid The second line contains one integer B Page 86 of 142 IOI 2002 Yong In Korea 0 x B x 5000 the number of black cells The following B lines contain two positive each the row number and the column number of the black cell separated by one blank OUTPUT The output file contains the size of the digital diamond and the coordinate of the center of the digital diamond EXAMPLE INPUTS AND OUTPUTS Examplel diamond in diamond out 6 11 7 VID tO ON OY O1 Oi 4 WN 10 11 12 14 15 1 15 151 16 1 16 16 16 17 181 181
65. YCALLS exit 0 if De sr2 gt a amp amp De srl b amp amp De sc2 gt c amp amp De scl lt d result 1 lse if De sp2 gt a amp amp De spl lt b amp amp De sq2 gt c amp amp De sq1 d result 1 else result 0 fprintf lgfile Sd n result return result void report int rl int cl int r2 int c2 int pl int ql int p2 int q2 if De rectlib initialized fprintf lgfile report d ql p2 q2 fclose lgfile if De count 0 H oo H Q ct o ar ZA Sd Sd Bd hn rl cl r2 c2 pl erroroutput ERRNORECTCALL exit 0 oufile fopen OUTFILE w fprintf oufile Sd n d d 3d Sd n d Sd d d n count En rl1 En cl En r2 En c2 En pl En q1 En p2 En q2 fclose oufile exit 0 D Source code for RODS Solution1 in C Jung Gun Lim TASK RODS LANG C x include stdio h include crectlib h int n void swi int a int b swapping two integers int t a a b b t correcting and submit output void soutput int rl int cl int r2 int c2 int pl int ql int p2 int q2 if cl c2 the first rod should be horizontal Page 75 of 142 IOI 2002 Yong In Korea getting result of the rect int pseudo rect finding whit int top to bottom search swi amp rl amp pl swi amp r
66. ams and input output files of tasks 10 I felt that this Olympiad was too easy to score a lot of points with a bad solution One of my students made a really inefficient N solution for FROG which took more than 2 minutes to run for the last case and still he got 44 points I fell that it s unfair for other contestants that such a bad solution earns so many points Its ok to give points to all solutions Just don t give so many 31 To improve the security of all systems Page 142 of 142
67. ary with details of the implementation Depending on the details of the implementation such an approach could also gain credit in several of the larger examples in which the rods are small and near a corner Page 71 of 142 IOI 2002 Yong In Korea B Test Data Information Jung Gun Lim Testing Data Timing Description for RODS P tooo st 0 00 50 00 e 3 4 soo FT f oo f 7 oo 832 3 Al 7000 5 00 16 boo 82 10000 14 700 79 0 00 76 15 1000 79 000 77 6 10 16 000 15 A 1000 52 000 Sa GO jis 500 56 000 c61 000 8 L19 7000 65 0006 4 00G 82 20 1000 70 000 70 000 88 C Source code for Library LINUX Jung Gun Lim include crectlib h define errmsgs 10 static const char errmsg errmsgs Cannot open the input file Invalid input file N is out of range should be 5 10000 One of the coordinates is out of range ROD1 is not valid ROD2 is not valid Cannot create the log file Invalid library function call Too many rect calls No rect call RINVCALL 7 RTOOMANYCALLS 8 define define define ERROPENINPUTFILE O define ERRINVINPUTFILE 1 define ERRNOUTOFRANGE 2 define ERRCOORDINATEOUT 3 define ERRFIRSTROD 4 define ERRSECONDROD 5 define ERRCREATELOGFILE 6 R R Page 72 of 142 IOI 2002
68. ase is as good as the best submission gets full marks and other students get partial credit according to how close to that answer their submission was XOR was chosen to be scored in this manner and it was also decided that it be phrased as an output only task This means that all 10 test data input sets are given to contestants at the beginning of competition and instead of submitting source code as in a typical IOI task contestants to submit only the output files corresponding to the given data sets Grading using relative scoring is performed in two steps first we evaluate the absolute performance of each solution and second we compare the performance of contestant s solution to the performance of others The final score given for each test case is the relative ratio of Contestant s result Best result among submitted solutions It is worth noting that the ISC and HSC weighed the fact that ROBOT is of a type of task new to the IOI However ROBOT was in the end rejected since IOI2002 did not seem to be the right moment to introduce it in view of the other changes which were considered more immediately workable We include that task in this IOI2002 book with one solution and we hope this innovative type of task will be accepted in future IOIs to broaden the IOI task repertoire even further One difficulty in preparing tasks and solutions is the difference between C C and Pascal much effort has been put into examining and un
69. ases scoring 40 of the points Testing Data Description FROG 6 300 30 30 modified random pointset 15 8 500 100 100 Specialcasefornosoluion 0 9 1000 100 100 Several Lines random points 34 Several Lines random points Page 19 of 142 IOI 2002 Yong In Korea Several Lines random points C Background The problem The Troublesome Frog is related to the problem for detecting spatial regularity in images Spatial regularity detection is an important problem in a number of domains such as computer vision scene analysis and landmine detection from infrared terrain images The AMESCS AII Maximum Equally Spaced Collinear Subset problem is defined as follows Given a set P of N points in E find all maximal equally spaced collinear subset of points Kahng and Robins 1 present an optimal quadratic time algorithm for solving the AMESCS problem D REFERENCE 1 A B Kahng and G Robins Optimal algorithms extracting spatial regularity in images Pattern Recognition Letters 12 757 764 1991 E Source Code for FROG Sungjoon Choi TASK frog LANG C kJ include stdio h define Max 5000 int p Max 2 1 Max Max PME Ay PCy my dod void ReadInput int i scanf d d amp r amp C scanf Sd amp n for i 0 i lt n itt scanf d d amp p i 0 amp pli 1 Page 20 of 142 IOI 2002 Yong In Korea
70. cations SIAM J Computing 0 200 211 1980 Page 88 of 142 IOI 2002 Yong In Korea SUBMITTED TASKS Submitted Task 1 ROBOT Sam Myo Kim Robot PROBLEM There is a robot on a checkerboard see Figure 1 which is divided into cells The robot can read and write a symbol on the current cell 1 e the cell where it is positioned and move to its neighboring cell Maneuvering this robot with a sequence of commands we want to draw a figure 8 of 8 s as shown in Figure 2 Each command should be expressed in one of the following three forms where T and T can be either R L U D or S respectively denoting a move to the right left up down and stop i a b T Reading symbol a on the current cell rewrite it with b and move to the next neighboring cell in direction T For example lt B 8 R gt denotes the command for Reading B for the blank symbol on the current cell rewrite it with 8 and move to the right ii a b T lt c d T gt While reading a keep moving to direction T after rewriting the symbol a with b until you read c Then rewrite c with d and move to direction T This command should satisfy the condition that a z c For example 8 8 U lt B 8 L gt denotes the command for While reading 8 on the current cell keep moving up rewriting the 8 with 8 until you read B Then rewrite the B with 8 and move on to the left cell ii i j Repeat previous i th command through up to j th c
71. ces and end of line characters separate items The format of the input data will be given in the task specification The output data files should be formatted strictly according to the task specific instructions However the grading system scores output files using C streams in such a way that extra white space spaces and end of line characters between or around items is ignored Directories In both Windows and Linux the environment will be provided with a directory created for each task Each directory will be named after its task and will contain any required task related materials As an example consider a competition round with three tasks named number string and red In Linux each contestant s home directory will have the three subdirectories number string and red and in Windows each computer will have the folders C ioi number C ioi string and C ioi red All provided files relating to the string task will be contained in the string subdirectory in Linux and in the C ioi string subdirectory in Windows Practicing The competition computers will be available for practice during hours that will be announced at the competition All contestants must take part in the practice competition round on Monday August 19 Before each competition round the computers will be assigned randomly to the contestants with a different assignment each time Curfew A curfew will be in effect beginning with the start
72. d Sd Sd amp srl amp scl amp sr2 amp sc2 amp spl amp sql amp sp2 amp sq2 8 erroroutput ERRINVINPUTFILE exit 0 N De N if De srl1 1 De scl 1 De sr2 1 De sc2 1 De sp1 1 De sq1 lt 1 De sp2 1 De sq2 1 De srl N De scl gt N De sr2 gt N De sc2 gt N De sp1 N De sql gt N De sp2 gt N De sq2 gt N erroroutput ERRCOORDINATEOUT exit 0 N En N if De scl gt De sc2 De sr1 De sr2 erroroutput ERRFIRSTROD exit 0 if De spl gt De sp2 De sql De sq2 erroroutput ERRSECONDROD exit 0 fclose f lgfile fopen LOGFILE w if lgfile 0 erroroutput ERRCREATELOGFILE exit 0 int gridsize if De rectlib initialized init fprintf lgfile gridsize d n De N return De N int rect int a int b int c int d int result if De rectlib initialized init count En De count 1 fprintf lgfile d rect d d d d De count a b c d if a 1 a gt De N b 1 b De N c 1 c De N d 1 d gt De N a gt b c gt d Page 74 of 142 IOI 2002 Yong In Korea fprintf lgfile Ss n errmsg ERRINVCALL fclose lgfile erroroutput ERRINVCALL exit 0 if De count gt upperbound fprintf lgfile Ss n errmsg ERRTOOMANYCALLS fclose lgfile erroroutput ERRTOOMAN
73. dard output The output contains one line with a single integer the number of plants flattened along a frog path which did the most damage if there exists at least one frog path otherwise 0 Page 16 of 142 IOI 2002 Yong In Korea EXAMPLE INPUTS AND OUTPUTS Example 1 input output the example of Figure 4 6 7 7 14 2 1 6 6 4 2 2 5 2 6 2 1 3 4 6 1 6 2 2 3 6 3 6 4 6 5 6 7 Example 2 input the example of Figure 5 6 7 18 ty 22 cx JA ki 1 6 2 3 5 dae 3 4 7 4 12 14 5 1 6 6 L Figure 5 21 2 3 2 6 4 2 4 4 4 5 5 4 579 6 6 output Figure 6 The maximum number of 4 plants flattened by a frog is 4 Page 17 of 142 IOI 2002 Yong In Korea SCORING If your program outputs the correct answer for a test case within the time limit then you get full points for the test case and otherwise you get 0 points A Solution A naive O N time algorithm for the problem iterates through all O N line segments induced by the point set S and determines how far each segment spacing can be extended to either direction within the point set O landings O N An efficient O N time algorithm for the problem is based on an algorithm for finding an equally spaced collinear subset of a set The algorithm works by overlapping all equally spaced triples in order to determine all maximal equally spaced collinear subsets The overlappin
74. deliver the printouts to the contestants there might be a small delay before printouts are delivered Contestants should not leave their computer to find printouts Backups Contestants will be able to make and retrieve backups through a facility provided in the competition environment Page 101 of 142 IOI 2002 Yong In Korea Test execution For tasks that require programs as solutions a contestant will be able to submit a solution along with an input file for test execution The test execution system will compile and execute the program under Linux enforcing the resource limitations for the particular task The program output the execution time and possibly error messages will be displayed A contestant can have at most one test execution in progress at a time until a test execution has completed further submissions will be blocked The test execution facility will not be available during the last 5 minutes of the competition Submitting Contestants will be able to submit their solutions through a facility provided in the competition environment For tasks which require output files as solutions the submission facility will validate the format of the output file submitted accepting the output file for grading if it passes For tasks that require programs as solutions the submission facility will verify that the program compiles and obeys the stated limits on source code size and compile time and will run the program on a simp
75. derstanding the differences and Page 4 of 142 IOI 2002 Yong In Korea their impact on an IOI Generally we find C C to be faster than Pascal on one occasion up to 4 times faster for equivalent code Of course this depends on the programming style used in both languages However the relative performance also varies by task we were surprised to find that in some of the backup tasks our optimized Pascal programs ran faster than our optimized C C programs We found little performance difference between Linux and Windows XP although developing two different contest environments for the two operating systems while trying to keep them as identical as possible proved to be extremely difficult We hope this two OS problem will be eliminated in future IOIs We hope the material presented here will be helpful to the IOI2003 Scientific Committee and will be instructive to IOI2002 leaders and contestants Page 5 of 142 IOI 2002 Yong In Korea DAYO Practice Session Practice Task 1 NUMBER Hwan Gue Cho Number of Distinct Values PROBLEM You are to write a program which given N positive integer values Xi X5 Xy compute the number of distinct values in those N integer values INPUT Your program reads input from standard input The first line contains one integer the number N 2 lt N lt 1000 The following N lines represent the values Xi X5 Xy and each of these lines contains one integer a value X 1
76. e care We start by sorting the N input code numbers into increasing order and then assigning alternating signs to them so that x gt v though x gt 0 iff x lt 0 The sign of x and so all the others is yet to be determined We then start at an appropriate place in the middle of this sequence and move outward using large numbers to change the sign of the sum from that of the current situation and small values to keep it the same A few definitions and lemmas make things much clearer Definition A sequence of non zero integers X x x Xp a b is an alternating acl sequence if i x K xta K x45 I amp 77 qx and ii for all i a i b the sign of x is different from the sign of x _ Here x is the absolute value of x Lemma 1 Let X x x X be an alternating sequence The sign of x is equal adl to the sign of x the total sum of elements in X 85 7 sigh 1 Proof We assume without loss of generality that x is a positive integer When the number b a 1 of elements in X is even resp odd the partial sums x x acl Xo PN dace Xa cb ESPs Hs Xu PA atl a 2 X44 FX are positive and thus the total sum 2 x is positive sisb Example 1 The total sum of elements in an alternating sequence X 1 42 5 4 6 is 1 2 5 6 2 42 which is positive Example 2 For an alternating sequence X 3 4 5 6 7 the
77. e o The C C library has the following three functions void start string The call to start It should be called only once at the beginning int oracle call char S If S is a substring of the hidden string this function returns 1 Otherwise this function returns 0 The query string S should not be an empty string and the length of S should be equal or less than 255 void answer string char S This function will terminate your program Your program passes the string S as an answer This should be called only once at the end of the program Page 7 of 142 IOI 2002 Yong In Korea Instruction To compile your string c or string cpp use the include statement include oracle h in the source code and compile it as gcc 02 static string c oracle o lm g O2 static string cpp oracle o 1m lib test c shows how to use the GNU C C library FreePascal Library oracle ppu oracle o The corresponding pascal library functions are procedure start string function oracle Call Ss string integer procedure answer string S string Instruction To compile your string pas include the import statement uses oracle in the source code and compile it as fpc So 02 XS string pas lib test pas shows how to use the FreePascal library The library generates a file named string out automatically in a call to answer string The file string out has two lines The integer in the first line shows
78. ecurity reasons The test facility checks for program headers Thus to test a simple test program say Windows vs Linux differences one has to include a valid program header and be limited by that task s memory and the limits There could be an accept submission regardless of whether it passes the sample input checkbox on the submission page Grading on a curve needs to be revised It is unfair in its current form 10 If a program e g FROG uses too much memory over 64Mb the error message was something like Bad memory reference I think it should have been something more informative I think the XOR format checker should have been stricter The current checker didn t notice trivial format errors such as missing number of rectangles on second line Also for the sake of similarity the submit program could have tested that the given rectangles really are a solution at least for the first input 29 Make the results show times and answers on each test case as on IOI 2001 43 Make it so you don t have to press reload 44 Use something that works in lynx 50 The grading system should be available from command line Using X web browser and mouse is very uncomfortable 72 The header format was too strict It should allow extra spaces 83 It must work no crashes Should work with more than I serves 85 The response time of your grader was far from being good It took quite some time for my requests to be processed
79. exit code is non zero All programs should have return code of 0 Put return 0 of exit 0 at the end of your code in case it is written in C or C For Pascal the return code is always 0 unless you specified in the code differently Execution error invalid memory reference Segmentation fault possibly due to resource limitations submission Accepted Submission Failed The submitted file could not pass all submission tests and was not accepted The submission is not added to accepted submission list of the user In case there was a pervious accepted submission for the task the previous submission is not overwritten and is still valid accepted submission APPENDIX B MEASURING THE CPU USAGE OF A PROGRAM Measuring the intermediate CPU usage of a program Pascal users The grading system will observe your program s execution time from outside If you want to check intermediate execution times during test execution or submission execution you may include this line in your code Si extime inc to include the execution function called exectime This function has no parameters and looks just like a scalar Its value is the number of milliseconds of execution used so far Here s a sample program to demonstrate its use program timetest i extime inc var i j k longint begin k 0 for i 1 to 100 do begin for j 1 to 1000000 begin le sedo JE des end end writeln
80. f fin Sd amp N for i 0 i N itt for j 07 j lt N jtt fscanf fin Sd amp color il j get needy i j get_needy i N for j 0 j lt N j get_needy N j fclose fin Page 47 of 142 IOI 2002 Yong In Korea fout fopen argv 2 w assert fout try to do stuff for i 0 i lt N itt for j 0 j lt N j if needy i j continue assert i lt N assert j N ninrow 0 for jj 3417 jj lt N JJe if needy i 33 inrow ninrowtt jj assert ninrow amp 1 should be odd nincol 0 for ii itl ii lt N iit t if needy ii j incol nincolt ii assert nincol amp 1 found 0 for c 0 found amp amp c lt nincol c for r 0 found amp amp r lt ninrow r if needy incol c inrow r found the perfect rectangl found 1 use rect i j incol c inrow r if found no perfect rectangle go for inferior stuff printf Waa Waastt use rect i j incol 0 inrow 0 sanity check ifndef NDEBUG for i 0 i lt N it for 3 07 3 assert needy endif fclose fout give some feedback printf Number of rectangles used d Number of Waas 3d Score gt Sg n n K Waas 1 9 double K 4 Waas return 0 Page 48 of 142 K 4 IOI 2002 Yong In
81. fy the input and output data format and value ranges the resource limitations for the computations e g cpu time memory any other constraints on the program behavior and the comment tags required in the source code so that the grading system can identify the task and programming language The submitted source program must be smaller than 1 MB and the evaluation server computer must be able to compile it in less than 30 seconds Submitted programs which do not meet these constraints will be rejected by the submission system and the contestant will be notified 2 Tasks for which output data files are requested as a solution There may be tasks for which input data is given to the contestant and the contestant is required to produce only the output data as an answer If the contestant writes programs to help determine the output data the programs should not be submitted with the solution The input data will be provided in ASCII text files For these tasks the task documentation will specify the structure of the input and output files and the full set of official input files Input and output data Page 99 of 142 IOI 2002 Yong In Korea In all tasks input and output data consists of a sequence of items An item is a string of printable non white space characters ASCII code from 33 through 126 An item may represent an integer or a general string the meaning of each item will be given in the task specification Spa
82. g is performed by constructing an undirected graph where for each equally spaced triple pa Pp Pc We create nodes lt A B gt and lt B C gt and the edge lt A B gt lt B C gt connected components in this graph correspond to maximal equally spaced collinear subsets in the original set Observe that a frog path is simply a linear chain of connected nodes with at least one edge and two nodes meaning at least 3 flattened plants in this graph Each node in this graph has degree at most two so the edge set and vertex set both have size O N Hence we can find all maximal equally space collinear subsets in O N time from the graph The only detail here is how to efficiently find the equally spaced triples from which the graph is created The obvious method of iterating over all triples of flattened plants would worsen the complexity to O N If instead the field is stored as a two dimensional array every plant has an entry giving the identity of the landing on that plant e g if the 100 flattened plant were at 10 12 then the array value at 10 12 is 100 you can loop over pairs of flattened plants pa and pp and then look up pc from the array in constant time since you know what the location of pc must be if it exists This strategy takes O N time but uses O field size memory in particular it needs 500045000 entries of a short integer each or 50MB Because the above graph also needs O N space to store it this st
83. g In Korea Task 2 UTOPIA Sergey Melnik Jung Heum Park Chong Dae Park Kee Moon Song Ian Munro Utopia Divided PROBLEM The beautiful land of Utopia was once ravaged by war When the hostilities subsided the country was divided into four regions by a longitude north south line and a latitude east west line The intersection of these lines became known as the point 0 0 All four parts claimed the name Utopia but as time went by they generally became known as Utopia 1 northeast 2 northwest 3 southwest and 4 southeast A point in any of the regions was identified by its distance east and its distance north of 0 0 These distances could be negative hence a point in Utopia 2 was designated by a negative positive pair in Utopia 3 by a negative negative pair in Utopia 4 by positive negative and in Utopia 1 by a pair of positive numbers Utopia 2 Utopia 1 0 0 E G Utopia 3 Utopia 4 A major problem was that citizens were not permitted to cross borders Fortunately some ingenious IOI contestants from Utopia developed a safe means of teleportation The machine requires code numbers each of which can only be used once Now the challenge facing the team and you is to guide the teleporter from its initial position of 0 0 to the regions of Utopia in the order requested You don t care where in a region you land but you will have a sequence of N region numbers that specify the regions in w
84. g In Korea void matching int elems int i flag last for i 0 i lt elems i match i 1 for i 0 i lt elems i traveled i 0 flag 0 for i 0 i lt elems i if match i 1 amp amp traveled i found 0 traveled i 1 path 0 i pathlen 1 dfs i if found f for i 0 i lt pathlen it t if i 2 0 match path i path i 1 else match path i path i 1 while flag last 1 for i 0 i lt elems i if match i 1 islinked i 1 else islinked i 0 if last 1 last i else match last i match i last last 1 void destroy row int r removing all corners in the row int int int int p 0 cols col MAXN 2 p qd i Ji min minp Page 41 of 142 IOI 2002 Yong In Korea cols 0 while ct r p cn lt nt2 p ct r p cn col cols p colst t for i 0 i lt cols i t links i 0 for i 0 i lt cols 1 i t t Could the pair of columns be 4 for j itl j lt cols j p ct 0 col i rn q ct 0 col j rn while p n 2 amp amp q n4 if p gt q q ct q col else if p lt q p ct p col else if p r ink i inks i ink j inks j break p ct p col q ct q col matching cols Maximum for i 0 i lt cols itt if match i gt i if islinked i
85. g system evaluates the submitted tasks after the competition round For tasks that require programs as solutions the submitted source files will be re compiled under Linux enforcing the source file size and compilation time constraints The compiler options for Pascal programs are O2 So XS and the compiler options for C and C programs are 02 static lm Page 102 of 142 IOI 2002 Yong In Korea The grading system will then execute the compiled program under Linux enforcing the task specific run time resource constraints Typically there will be a CPU run time limit and a limit on total memory use Every limit applies independently for each test case if any limit is exceeded no points will be awarded for that test case The actual limits will be specified in the task materials If the submission facility accepts a program that only means that the compilation was successful and the program correctly solved the simple test case within the resource constraints but no more In particular it does not mean that the program would obey the resource constraints when given different input The IOI 2002 schedule will specify the times when the grading results and evaluation data used for grading will be made available to the delegations and when grading appeals are to be submitted to the Scientific Committee Other Information A contestant trying to interfere with other contestants activities trying to break the installations or
86. good rectangles in a row For a row there are even numbers of comer points Ci C5 C3 Ck where k 2N Then we construct a complete weighted graph G V E from Cj Let v of V be Cj And edge e v vj is given for every pair of v vj The weight of each edge w e is given w v vj 1 if there is a rectangle 4 corners with v v Otherwise w v vj 0 In the following figure circle denotes the corner point of given image There are 6 corner points vertices namely vi V2 V3 V4 Vs Ve in the first row Since there is a rectangle with four corner points with v1 v4 edge four corners 1 1 1 4 3 1 3 4 gives a rectangle thus w vi v4 1 In a similar way we can set W vi v3 0 w vi vo 1 w vi vz 0 W V3 V7 0 l lalao Jaalan 1 1 1 3 1 4 1 6 1 7 ee Then we compute the maximal matching of G V E and remove all rectangles corresponding to edges contained in maximal matching This gives a better solution compared to the performance of Solution 1 and Solution 2 Page 37 of 142 IOI 2002 Yong In Korea B Test Data and 3 Solutions Jung Gun Lim Testing Data Description for XOR 2 optimal a ES IOI 2002 Pio ane apa sagana 8 3 3 25 random boxes DEE endom bores 18 98 E D ve siens nu m ae 1 a Ls pus west sos ost isi 500 random boxes e eoo 306 patente ahas 22 19 9 1500 Two kinds of 500 boxes 526 3732
87. gt 3 lt B 8 R gt 4 lt B 8 R gt 5 lt B 8 U gt 6 i7 8 9 lt B 8 U gt lt B 8 L gt lt B 8 L gt 8 8 D lt B 8 D gt 10 3 6 11 lt 8 8 S gt Figure 5 An intelligent motion planning Figure 6 An intelligent answer for question a for question a start Figure 7 A Cleaver motion planning B 8 L lt B D gt start ee lt B D gt Nay 8 S lt B 8 R gt 8 D SB 8 R gt BJ D B 8 U DELE lt B 8 U gt 1B 8 L lt 8 D gt D 8 8 D lt B 8 D gt 8 8 D l 2 Ban B 8 U aa 0 lt 8 8 S gt dues T Figure 8 Motion planning using one Figure 9 An answer for question b additional symbol i e flag for question Robot program with 10 commands using b one additional symbol Page 91 of 142 IOI 2002 Yong In Korea Figures 10 and 11 show another motion plan and an answer for part b I designed this problem out of one of homework assignments given to my automata class The original problem is to design a 2 D automaton with smallest possible number of states There are more solutions than the ones shown here However as I commented before with the set of 3 commands given in this problem small automaton does not necessarily give small program It is easy to see that with command ii a b T lt c d T we can implement command 1 because if current symbol is c which is not equal to a then the iteration pa
88. hich the teleporter is to land You may be asked to land in the same region in two or more consecutive stops After leaving the initial 0 0 point you must never land on a border You will receive as input a sequence of 2N code numbers and are to write them as a sequence of N code pairs placing a plus or a minus sign before each number If you are currently at the point x y and use the code pair u v you will be teleported to the point x u y v You have the 2N numbers and you can use them in any order you like each with a plus or a minus sign Suppose you have code numbers 7 5 6 1 3 2 4 8 and are to guide the teleporter according to the sequence of region numbers 4 1 2 1 The sequence of code pairs 7 1 5 2 4 3 8 6 achieves this as it teleports you from 0 0 to the locations 7 1 2 1 2 4 and 6 10 in that order These points are located in Utopia 4 Utopia 1 Utopia 2 and Utopia 1 respectively Page 23 of 142 IOI 2002 Yong In Korea TASK You are given 2N distinct code numbers and a sequence of N region numbers indicating where the teleporter is to land Construct a sequence of code pairs from the given numbers that guide the teleporter to go through the given region sequence INPUT Your program is to read from standard input The first line contains a positive integer N 1 lt N lt 10000 The second line contains the 2N distinct integer code numbers 1x code number lt 100
89. i and head i satisfying the following properties i lt i1 lt lt i lt i and gi l1 gt g 1 2 sanag gt gil ij Seats 1 When C is calculated 1 Using fi remove unnecessary element at head of Q If fi g i i1 delete i from Q since for all A lt i Ah fi g iz i1 and Ch in lt Cn 1 by Property 1 Continue this procedure until for some gt 1 g i i1 gt g ij3 i2 gt gt gie i gt f Then by Property 1 Ci i 1 gt Ciy for v t 7 1 or r t and Q contains only i Therefore C i is equal to min C K k i 1 N 1 2 When inserting i at the tail of Q maintain Q for the condition 1 to be satisfied If g i i g i i 1 delete i from Q by Property 2 Continue this procedure until g i iy gt g i i 1 Append i as a new tail of Q Analysis Each i is inserted into Q and deleted from Q at most once In each insertion and deletion it takes a constant time Therefore the time complexity is O N Page 54 of 142 IOI 2002 Yong In Korea B Test Data Information and Grading Kee Moon Song In total 20 test cases are prepared and tested Each test case is of 5 credits Among them 19 test cases are randomly generated so that negative integer by overflow does not occur during computing F The remaining 1 test case is that setup time and all processing times and cost factors are 1 The test case is mainly prepared to distinguish whether
90. ill pass both two hubs H and H2 5 10 15 20 X Figure 1 In Figure 1 it shows a distribution of 7 bus stops in Yong In We consider all pairs of bus stops of the input as possible two hubs H and A and select the pair of the bus stops that gives a minimum diameter Let at the beginning D be sufficiently large e g maxint Consider now fixed two hubs H and H Each of the remaining N 2 points will be initially connected to one of two hubs say H Sort the remaining N 2 points in the array Page 61 of 142 IOI 2002 Yong In Korea P in non decreasing order according to the distance from the hub Figure 2 Figure 2 Denote by ry d H P N 3 r2 d Ho P n 2 and d2 dM H If ri dj2 1 lt D then the point P N 2 is connected to the hub H and set D to the new value D r di r5 Figure 3 represents this step 7 d H P N 3 d H P 4 10 r2 d H P N 2 Ad P 5 3 di dM H s 12 SO D F F di2 F 1977 10 12 3 25 y Figure 3 Now we repeat the same procedure with r d H P N 4 r2 d H P N 3 same di2 d H FA and get ri di2 r d H P 3 td d Ho P 4 7 12 8 27 Since we got the new distance which is greater than the previous diameter the value D remains unchanged so D still has value 25 If 25 is turned out to be the minimum of D at the end of the procedure the point P 4 shall be connected to H although its distance to H is sma
91. in the time limit 22 The idea of relative scoring seems to be natural for output only tasks We suggest to add source file management tool to the default installation 25 Start to have problem in area of parallel algorithms 28 Need to constantly refresh web page to get status of test run is annoying though not critical Suggest an applet would improve this situation 20 Whole system should be more stable 37 Format checkers for all batch library and output only tasks are an excellent idea and should be continued Other Comments 5 Pascal and C compiler also installed on the translator s machines It would be nice to assume that people are fair and let them use internet while translating tasks More time for discussion on GA meetings Less security restrictions like forcing students to stay in their rooms on the night before competition extime library for measure execution times should be provided to students as well 6 I d like we could be used Delphi second IDE for Pascal programmer in windows 7 Tasks made in windows checked up in Linux This caused mistakes All optimization problems such as BATCH BUS RODS must be made with relative scoring But a formula may vary I suggest to include continuous non discrete problems on Page 141 of 142 IOI 2002 Yong In Korea optimization approximate solving of equations etc Relative scoring makes such problems to be correct 9 In fact we need only the student s progr
92. j bp if k gt 2 if mm lt dis i p k 1 dis il p k 2 mm dis i p k 1 dis i p k 2 if bq 99 if mm lt dis j bp dis j bq mm dis j bp dis j bq if min gt mm min mm if dis j bp dis j pf1 bq bp bp pI 1 if bq 99 dis j bq dis j P 111 if p 1 bp bq p 1 if min gt dis j bq dis j bp min dis j bq void output printf Sd n min int main void input preprocess process output return 0 dis j bp Page 67 of 142 IOI 2002 Yong In Korea Task 3 RODS Hwan Gue Cho Ian Munro Two Rods PROBLEM A rod is either a horizontal or a vertical sequence of at least 2 consecutive grid cells Two rods one horizontal and the other vertical are placed on an N by N grid In Figure 1 the two rods are shown by X s The rods may or may not be the same length furthermore they may share a cell If from a diagram such as Figure 1 it is possible to interpret a cell e g 4 4 as being in just one rod or in both rods we make the interpretation that the cell is in both Hence the top cell of the vertical rod is 4 4 rather than 5 4 Figure 1 c d i 1 2 3 4 5 6 7 8 9 T 2 a3 4 Dearne X X 5 X 6 X 7 X b gt 8 X 9 X Initially we do not know where the two rods are and so your task is t
93. ki DARKO Stojanovska VESNA Atanasov VASIL Mihajlovski NIKOLCE Joel AZZOPARDI Christian COLOMBO Tulga TUMENDALAI Gansukh BATKHUYAG Dorjnamjil CHANDMANI Otgontugs MIIMAA Sonia RAITHATHA Decio MACAMO Bachir BACHIR Vishwaduthsingh GUNGA Mohammad Zyaad JAUNNOO Dominique Francois ADOLPHE Rowan Rishi JUGERNAUTH Cynthia KOP Dag SELJEBOTN Tormod LANDET Daniel LOKSHTANOV Nuno PEREIRA Pedro PEREIRA Andre COIMBRA Cosmin RAIANU Junjie LIANG Kee Tee Lawrence TAN Ruben SIPOS Ivo LIST Tomaz GREGOREC Carl NETTELBLAD Pitchaya SITTHI AMORN Gurbannazar REJEPOV Nagmat NAZAROV Serdar MUHAMMETBERDIYEV Oleksiy HLUKHOVSKIY Alfredo Enrique ROMAN REYES Alicson RUBIO Johan VIVAS Son NGO THANH Graham Leslie POULTER Harry Zondberg WIGGINS Page 126 of 142 IOI 2002 Yong In Korea APPENDIX VI Contestant Questionnaire Questions for Contestants about IOI 2002 Competition Which Operation System s did you use Dayl Linux LE Windows XP Day2 L Linux Windows XP Which programming language s did you use Dayl Lk Pascal C LEC Day2 Ci Pascal C C Which programming editor s did you use FreePascal IDE RHIDE LE Emacs CE vi vim LI notepad win joe Linux Other Which debugger s did you use Lk FreePascal IDE LCERHIDE Cf using extra printf writeln statements LE gdb Lk ddd LE Other What other tools did you use during the competition days Please grade the Grading System and the Web ser
94. l void delete min row or col destroying the row or the column that contains least corners int mins minp i isrow init ct 1 while 1 mins n 1 for i 1 i lt n 1l itt if mins gt cor i amp amp cor i mins cor i minp i isrow 1 if mins gt coc i amp amp coc il mins coc i minp i isrow 0 if mins n 1 break if isrow destroy row minp else destroy col minp update sol void delete one by one int i init ct for i l i lt n 1l it destroying the top row first if cor i 0 destroy row i update sol Page 45 of 142 IOI 2002 Yong In Korea init ct for i 1 i lt n 1l it the bottom row if coc i 0 destroy col i update sol init ct for i ntl 1i gt 1 i the left column if cor i 0 destroy row i update sol init ct for i n 1 i gt 1 i the right column if coc i 0 destroy col i update sol void read data Ine ud Jo scanf d amp n void print for i 0 i lt n it for j20 j n j scanf d amp b i 1 j 1 for i1 0 i lt n 1 i b i 0 0 b i nt 1 0 b 0 i 0 b n 1 i 0 mcount 0x7fffffff1 int 1 char ID printf FILE xor s n ID printf Sd n count for i 0 i lt mcount i t printf Sd d d
95. lation debugging a graphical front end ddd to debugging Option 3 is targeted primarily for Linux although it is possible to use Windows Edit and command line compilation Hardware The specification is a PC with a 1 7 GHz Pentium 4 processor 256 MB RAM a standard US keyboard a mouse and a 19 inch CRT Linux For Linux we are using Debian release 3 0 woody You can get more information from Debian s home pages at http www debian org The tasks are chosen by tasksel with the following choices X window system Page 104 of 142 IOI 2002 Yong In Korea desktop environment C and C And additional packages are chosen by dselect ddd The Data Display Debugger a graphical debugger frontend mc Midnight Commander A powerful file manager normal version mozilla Mozilla Web Browser dummy package vim Vi IMproved enhanced vi editor vim gtk Vi IMproved GTK version exuberant ctags multi language reimplementation of ctags emacs21 The GNU Emacs editor emacs21 el GNU Emacs LISP el files joe user friendly full screen text editor GCC on Linux We use gcc 2 95 which is installed as a part of the Linux Debian woody You can learn about the availability of various GCC versions through http gcc gnu org If you install a Linux version and include development tools then you are extremely likely to get a GCC version Pascal on Linux You can get the Freepascal software th
96. le test case that is given in the task description enforcing the relevant run time resource constraints If the submission produces the correct output then the submission is accepted for grading Contestants may submit any number of times for each task each accepted submission replaces any other submissions of that task by that contestant The last accepted submission by a contestant for a task is officially graded in a separate process and contestants will not be informed about the results until after the competition Ending the competition round Warnings will be given with 15 minutes remaining in the round 3 short whistles and a verbal announcement 15 minutes 5 minutes remaining 2 short whistles and a verbal announcement 5 minutes and 1 minute remaining 1 short whistle and a verbal announcement 1 minute and the end of the round will be announced 3 long whistles and a verbal announcement end of competition round At the announcement ending the round contestants must immediately stop working and put their keyboards on top of their terminals without switching off their computers Contestants should then wait at their desks without operating their computers or touching anything on their desks an additional announcement will be made instructing them to leave their tables and exit the competition hall At this point contestants may take with them the contents of their competition envelope Grading The gradin
97. left end cell of the horizontal rod RODI Cell pi q1 is the top end cell of ROD2 Hence m r2 c1 C2 p lt pa and q qo If your report parameters do not meet these constraints then you will get error messages on standard output CONSTRAINTS You can access input only by using the library functions gridsize and rect N the maximum row column size of input satisfies 5 lt N x 10000 The number of rect calls should be at most 400 for every test case If your program calls rect more than 400 times this will terminate your program Your program must call rect more than once and call report exactly once Ifa rect call is not valid e g the query range exceeds the grid space it will terminate your program Your program must not read or write any files and must not use any standard input output LIBRARY You are given a library in the following FreePascal Library prectlib ppu prectlib o func func proc tion gridsize LongInt tion rect a b c d LongInt LongInt edure report rl cl r2 c2 pl qi p2 92 LongInt Instructions To compile your rods pas include the import statement use in the fpc S prectlib source code and compile it as So 02 XS rods pas The program prodstool pas gives an example of using this FreePascal library GNU int int void C C Library crectlib h crectlib o gridsize rect int a int b int c int d report int rl
98. ller than the distance from Hj This situation is represented in Figure 4 where the point P 4 is connected with a thin line to H7 which is shorter than the distance from Hj to P 4 5 10 i3 20 x Figure 4 This procedure is repeated by decreasing the index of the array P one by one until the index 1 is reached For the example the minimum value of D is 25 after the procedure and the corresponding network is shown in Figure5 below Page 62 of 142 IOI 2002 Yong In Korea Figure 5 b Seemingly nice heuristic but wrong approach The correct and the nearly best algorithm by Ho et al considers all O N pairs of points as two bus hubs Let D Hi H2 be the longest length between two bus stops for fixed two hubs H and H The main difficulty in this problem is how well contestants compute D Hi H2 for each pair Hi H2 Many contestants will try to take a seemingly natural and intuitive heuristic approach to connect each of N 2 points to the nearest one of two hubs But this is wrong because there is a counter example shown in Figure 6 Of course this approach can produce correct answers for some inputs The following two images are caught from the screen shots of the optimal network produced by the correct algorithm and the non optimal network produced by the heuristic for the same input of 100 points The left one has diameter 167 and the right one has diameter 168 The longest path defining the diameter is represented
99. lready examined Assuming the table is filled up to row A row A 1 is filled by considering all O N flattened plants B before pa and if there is a flattened plant C such that A B and C are equally spaced look up in the array the number of landings in the candidate frog path through B from C increment by 1 and store as the B entry in the row for A If C would be outside the field then enter it as having 2 flattenings At the same time check to see if the next flattened plant D would be outside the graph and if so you have a completed frog path To efficiently determine C the same 50MB array as above is needed a hash table can again be used with no increase in average case time complexity but an increase in worst case time complexity B Testing Sungjoon Choi The test data contains 25 test cases Most of data are initially generated by random function then they are modified by manual work Each test case has size N the number of points in the range between 10 and 5000 Among 25 test cases 10 test cases have size N lt 1000 The remaining 15 test cases have size N 2 2000 The detail on the test data is summarized in the following table Each test case is worth 4 points A program which implements a cubic time algorithm can solve the test cases within time limit such that their size N lt 1000 An implementation of this algorithm should be able to get the first 10 test cases correct but will likely run out of time on all other c
100. ly The total cost for a partitioning is the sum of the costs of all jobs The total cost for the example partitioning above is 153 You are to write a program which given the batch setup time and a sequence of jobs with their processing times and cost factors computes the minimum possible total cost INPUT Your program reads from standard input The first line contains the number of jobs N 1 lt N 10000 The second line contains the batch setup time S which is an integer O lt S x 50 The following N lines contain information about the jobs 1 2 N in that order as follows First on each of these lines is an integer 7 1 lt 7 100 the processing time of the job Following that there is an integer F 1 lt F 100 the cost factor of the job OUTPUT Your program writes to standard output The output contains one line which contains one integer the minimum possible total cost Page 52 of 142 IOI 2002 Yong In Korea EXAMPLE INPUTS AND OUTPUTS Example 1 input output 45000 Example 2 input output 153 Example 2 is the example in the text REMARK For each test case the total cost for any partitioning does not exceed 2 1 SCORING If your program outputs the correct answer for a test case within the time limit then you get full points for the test case and otherwise you get 0 points A Solutions This problem can be solved using dynamic programming Let C
101. me A user should wait for his or her current submission process to finish before attempting to initiate another submission process Note that logging out or turning off a user s machine will not cancel an ongoing submission process A submission is accepted only if it satisfies all the requirements for the task The maximum size of a source file or an output file that can be submitted is 1M bytes 1048576 bytes If the size exceeds an error message will be immediately displayed and the submission process will not start at all Other requirements for the task will be examined in the submission process Failing to meet all the requirements will result in a submission failure The table below contains common requirements for a submission to be accepted Note that a user program must return exit code of 0 In C or C the user program should do return 0 or exit 0 at the end of the execution In Pascal the default return code is 0 unless specified otherwise in the source code Requirements for user programs Program exit code 0 Maximum source file size 1M bytes Maximum output file size output only tasks 1M bytes Header format Specified per task Stdout size limit 200k bytes Stderr size limit 200k bytes Compile time limit 30 seconds Execution time limit Specified per task Memory usage limit Specified per task Stack size limit Default 8M bytes Test The test facility is si
102. milar to the submit facility The main difference is that a user must provide his or her own input file The test facility is not available for an output only task The input file is fed to the user program as stdin and the user program is expected to use stdout and stderr for outputs The user program s stdout and stderr will be shown in the Test Output window along with other information All requirements for the task are examined as in the submission facility A test process might take more time than a submission process as submission processes are given much higher priority by the server Only one test process is possible at a time However it is possible to proceed with one submission process and one test process at the same time Page 115 of 142 IOI 2002 Yong In Korea Print Select a file to be printed into Print File box and press Print button Print Successful will be displayed if printing is successful and the printing job is fed to the printer spool which means that it can still take some time before actual printing Print Failed means the printing subsystem of the IOI 2002 Contest System is not available at the time and the user should try again some other time or consult with an assisting personnel It may take some time before the main screen is displayed with either Print Successful or Print Failed when the file is big or there are many simultaneous printing requests from the users This is due to a system design to suppress e
103. ms TROUBLES There are some inconveniences for programming in the competition environment You can avoid these problems RHIDE and debugging problem in Windows XP Trouble If you set breakpoints and the program terminates without reaching any of the breakpoints the DOS box will be terminated without even a message Solution Set any breakpoints on the first or last line to reach in any case RHIDE and black screen in Windows XP Trouble If you launch RHIDE in full screen mode and you choose DOS shell or execute the program or exit RHIDE you may see only a black screen Solution Change to the window mode by pressing Alt Enter You may avoid this problem by launching RHIDE with S option Page 108 of 142 IOI 2002 Yong In Korea Freepascal IDE in Linux Trouble The function of viewing user screen in FP IDE has some trouble It breaks the IDE editing screen Solution Returning of editing mode makes the screen clean again You may avoid this problem by using console compilation and debugging FORBIDDEN A contestant trying to interfere with other contestants activities trying to break the installations or evaluation facilities trying to harmfully interfere with the running of the competition in any way or trying to communicate in any way during a competition round with anyone other than the competition staff will be disqualified from the competition Submitted programs are not allowed to access
104. nd there is no restriction on the scheduled sequence of jobs then the problem can be solved in O N log N time 3 If all jobs have the same processing time and there is no restriction on the scheduled sequence of jobs then the problem can be solved in O N log N time D References 1 P Brucker Efficient algorithm for some path problems Discrete Applied Mathematics 62 pp 77 85 1995 2 S Albers and P Brucker The complexity of one machine batching problems Discrete Applied Mathematics 47 pp 87 107 1993 Page 56 of 142 IOI 2002 Yong In Korea E Source Code for BATCH Kee Moon Song TASK Batch LANG C Optimal solution O N with Dynamic programming x7 include lt stdio h gt define MAX 10000 int num stime answer of Jobs Setup Time answer int data MAX 2 processing time amp priority int queue MAX 1 table MAX 1 tables for DP void getdata In scanf d d amp num amp stime for i 0 ix num itt scanf 3d Sd amp data i 0 amp data i 1 void preprocessing ING iz for i 1 i lt num i data i 0 datali 1 0 data i 1 datali 1 1 int func int k return data num 1 1 k data k 1 1 0 int cost int i int j return func i stime data j 1 0 i data i 1 0 0 int delta int i int j return table i table j data j 1 0
105. network robust to a single failure EXAMPLE INPUT AND OUTPUT output 5 2 3234 0 1 00 50 100 100 100 O 100 100 100 50 100 0 20 100 100 100 20 O 80 100 100 80 O SCORING For each test case if the program outputs the minimum cost full points are awarded else no points are awarded for that test case A Comment The Weighted Biconnectivity Augmentation problem is NP hard 1 The computer network can be modeled by a graph G V E We let H V E be the graph obtained by removing the vertex representing the main computer and its associated edges from G It holds true that G V E U X is biconnected if and only if H V E U X is connected for any set X of pairs of computers in local branches To find a minimum cost connected graph of H employing a minimum cost spanning tree algorithm is sufficient Page 84 of 142 IOI 2002 Yong In Korea B Test Data Information The test data consists of 25 test cases each generated mainly at random C Grading If a contestant s program outputs the correct answer for a test case in the time limit then he she will get 4 points for that test and otherwise he she get 0 points for the test case D References 1 M R Garey and D S Johnson Computers and Intractability A Guide to the Theory of NP Completeness Freeman 1979 Page 85 of 142 IOI 2002 Yong In Korea Back Up Task 2 DIAMOND Tae Cheon Yang Digital Diamond PROBLEM Given is an m
106. no corners intersect rods intersect rods intersect rods intersect rods This leads to a 6 lg N 4 solution The maximum value of lg N in the test data is 14 so we have a solution that takes at most 88 calls to rect With care this can be reduced to 6 1g N 1 Notice that the queries we ask of the data have only two possible answers As there are N N 1 4 possible placements of the rods ig N N 1 l6 lg N 2 calls are necessary on average for any algorithm We do not claim our testing is exhaustive so we simply take this as a worst case lower bound We implemented two versions of the general approach suggested There are a number of variations on this approach For example one could try to finding the bounding rectangle more quickly when it is large Approaches of this type tend to double the number of calls to rect and will lead to full marks on the 4 small cases and 3 marks on each of the larger cases The most naive approach involves scanning individual cells to find some portion of a rod then looking around for the rest of the rod This can clearly lead to an M solution or even slightly worse if one is careless The approach receives full marks in the four cases of size 10 Another exhaustive approach involves taking entire rows or columns as query rectangles to find the bounding rectangle then applying a similar approach to find the rods inside this rectangle This will require O N calls though the constant will v
107. o be processed on one machine The jobs are numbered from 1 to N so that the sequence is 1 2 N The sequence of jobs must be partitioned into one or more batches where each batch consists of consecutive jobs in the sequence The processing starts at time 0 The batches are handled one by one starting from the first batch as follows If a batch b contains jobs with smaller numbers than batch c then batch b is handled before batch c The jobs in a batch are processed successively on the machine Immediately after all the jobs in a batch are processed the machine outputs the results of all the jobs in that batch The output time of a job 7 is the time when the batch containing finishes A setup time S is needed to set up the machine for each batch For each job i we know its cost factor F and the time T required to process it If a batch contains the jobs x x41 x k and starts at time f then the output time of every job in that batch is t S T Ty Tu Note that the machine outputs the results of all jobs in a batch at the same time If the output time of job i is O its cost is O x F For example assume that there are 5 jobs the setup time S 1 T To T T4 T5 1 3 4 2 1 and Fi F5 F F4 F5 3 2 3 3 4 If the jobs are partitioned into three batches 1 2 3 4 5 then the output times Oi O2 Os O4 Os 5 5 10 14 14 and the costs of the jobs are 15 10 30 42 56 respective
108. o create these files INPUT You are given 10 problem instances in the text files named xor1 in to xor10 in Each input file is organized as follows The first line of an input file contains one integer N 5 lt N lt 2000 meaning that there are N rows and N columns in the image The Page 32 of 142 IOI 2002 Yong In Korea remaining lines represent the rows of the image from top to bottom Each line contains N integers the pixel values in the row from left to right Each of these integers is either a 0 or a 1 where 0 represents a white pixel and 1 represents a black pixel OUTPUT You are to submit 10 output files corresponding to the given input files The first line contains the text FILE xor I where integer I is the number of the respective input file The second line contains an integer K the number of XOR calls specified in the file The following K lines represent these calls from the first call to the last call to be executed Each of these K lines contains four integers the XOR call parameters L R T B in that order EXAMPLE INPUT AND OUTPUT Example xor0 in xor0 out SCORING If the XOR calls specified in your output file do not generate the required image or the number of XOR calls specified in your output file is not K or in your output file K gt 40000 or your output file contains such an XOR call that L gt R or T gt B or your output file
109. o get the current time display updated 2 Reload button Reload the main page from the web server and get the page updated Users should manually reload the main page to see their submit or test operations in progress to see the reports on submit or test operations when they are finished or to update the current time and announcement window displayed Pressing F5 button on the keyboard is equivalent to pressing the Reload button 3 Accepted submission table The accepted submission table shows the task name a filename and the time the file is submitted for each of all the tasks of the currently running contest Initially only the task names are shown for the tasks of the day and filenames and submission times are left blank Filenames and submission times are filled only after a successful submission A user can follow the HTML link at the filename to display its content or download the file A new successful submission will overwrite the previous submission There is no way for a user to recover an overwritten submission except for starting a new submission process with the old file kept in his computer Note that when a user initiates a submission process that will turn out to be successful and the user never updates his main screen to see the updated submission table the previous submission is still overwritten There are two kinds of tasks One accepts a single file program and the other output only task accepts multiple file
110. o write a program to determine their locations We call the horizontal rod RODI and the vertical rod ROD2 Each grid cell is represented by a row column pair r c and the top left corner of the grid is taken to be location 1 1 Each rod is represented as two cells ri ci 72 c2 In Figure 1 RODI is lt 4 3 4 8 gt and ROD2 is lt 4 4 9 4 gt This task involves the use of library functions for input for determining the solution and for output The length of a side of the square grid is given by the library function gridsize which your program is to call at the beginning of each test case To locate the rods you can only use the library function rect a b c d which examines the rectangular region a b x c d shaded region in Figure 1 where a lt b and c lt d Note carefully the order of these parameters If at least one grid cell of either rod falls inside the query rectangle a 5 x c d rect returns 1 otherwise it returns 0 So in the example rect 3 8 3 6 returns 1 Your task is to write a program to discover the exact location of the rods using a limited number of rect calls Page 68 of 142 IOI 2 002 Yong In Korea You produce output by calling another library function report ri ci 2 Co Pi di P2 q2 Where RODI is ri 1 72 C2 gt and ROD2 is pi q1 p2 g2 gt Calling report terminates your program Recall that RODI is horizontal and ROD is vertical and ri C1 is the
111. ommand For example 4 9 is the command Repeat previous fourth command through ninth command Using this command we have the following restriction the first entry of the next command if any to this one and the first entry of j 1 command should be different In other words suppose that a b c is the next command to this repeat command and d e f gt is jt command Then it must beazd It is possible to have a b or c d in the above commands which means that the robot does not change the symbol The robot executes one command at a time Robot Figure 1 Figure 2 Page 89 of 142 IOI 2002 Yong In Korea Assume that all the board cells are initially written with blanks and the robot can draw the figure positioned at any location on the board Now we have the following questions Question a Under the restriction that the robot can only read and write two symbols B for blank and 8 what sequence of commands 1 e program will you send to the robot to draw the figure The robot should stop when it is done with the work Your answer will be evaluated according to the correctness and brevity i e in terms of the number of your program Question b Now suppose that the robot is allowed to read and write an extra symbol say in addition to B and 8 How can you reduce the length of your commands Again your answer will be evaluated according to the correctness and brevity of your program A Solu
112. onal communication links between pairs of computers in local branches to achieve this goal but each new link has an associated construction cost Your task is to figure out the minimum total cost of any set of new links you could add to your communication network which would make the network robust to a single failure either of a computer or of a link though not necessarily both Page 83 of 142 IOI 2002 Yong In Korea INPUT The first line contains the two integers n and m where N is the number of computers in the network 3 lt N lt 1000 and m is the number of existing direct communication links between computers in local branches The second line contains m pairs of integers a1 b1 a2 b2 Gmsbm describing those direct links where each pair apb indicates that there is a bidirectional communication link between computer a and computer bx in local branches Recall that every branch office has a link to the head office those links are not listed here The following n lines contain the costs of building communication links line i 2 in the input file contains N integers between 0 and 1000 inclusive which are the costs of building a link between computer i and each computer 1 2 N respectively Note that since the communication links are all bidirectional this table of costs will be symmetric that is cost costji OUTPUT The output contains a single integer on one line the minimum cost to make the communication
113. ord and press Login button to open a new session with the IOI 2002 Contest System Then the main screen will be displayed Contest is not running When a contest is not running which means that it is before or after the contest period Contest is not running is displayed on the main screen and users cannot use submit or test facilities Print and backup restore facilities however are available even when a contest is not running Viewing and downloading submitted files is also available when a contest is not running Page 111 of 142 IOI 2002 Yong In Korea Main Page 1 3 Login ID sllee Tine 2002 07 29 17 35 12 Relbad 5 NUMBER Submit File Submit File number c Time 4 11 22 STRING Time 6 red in 1 15 10 01 Test Source File Test N Test Input File red in 4 15 33 20 Announcement 14 11 56 8 1012002 Contest System Print File Print Demonstration Backup File Backup Restore File Restore 1 Login and time information The login ID of the user and the current time are shown The current time is obtained from the system clock of the hardware where the IOI 2002 Contest System is running Therefore the time shown is uniform among all participants regardless of their local machines system clocks Note that the main page should be reloaded manually t
114. orea Evaluation Results of Internet Practice Session We have announced three practice tasks to all contestants to help them understand the procedure of submission evaluation system and task styles for IOI2002 On line practice session was conducted by Internet in August 6 We received several solutions and output files for RED and evaluated those materials of contestants Number of Number of Full Average score of Task name a aa solutions a NUMBER 9407 07 Page 13 of 142 IOI 2002 Yong In Korea DAY1 TASK OVERVIEW SHEET DAY 1 TASK FROG 3 directory Time limit per test Memory limit 64 MB C and 02 static Pascal So 02 XS per test DEE C points Program header comment when using C Compiler options Program header comment when using C Program header comment when using Pascal Submission is ramp l is accepted if solved PASCAL UTOPIA 32 MB So 02 XS in EN nos PASCAL Fam 1 is The file format is solved correct Page 14 of 142 IOI 2002 Yong In Korea Task 1 FROG Soo Hwan Kim Greg Galperin The Troublesome Frog PROBLEM In Korea the naughtiness of the cheonggaeguri a small frog is legendary This is a well deserved reputation because the frogs jump through your rice paddy at night flattening rice plants In the morning after noting which plants have been flattened you want to identify the path of the frog which did the mos
115. oth Day 1 40 60 3 y 38 896 58 3 2 9 Dav 2 40 62 1 y 38 896 60 2 1 0 Language Pascal C CH Pascal amp C C e C Dav 1 44 23 34 1 1 ii 42 794 22 394 33 0 1 0 1 0 Dav 2 44 24 34 0 1 uy 42 7 23 3 33 0 0 1 0 OS amp Language Pascal C Cae Linux 9 13 18 Windows XP 35 10 17 Editor multiple selections 39 FreePascal IDE 37 996 37 RHIDE 35 9 13 Emacs 12 6 Nu 16 Vi vim 15 594 Notepad win Ls DE 11 7 8 1 Joe Linux 1 0 5 Other 4 996 Page 129 of 142 IOI 2002 Yong In Korea other editors edit 2 wordpad kate mcedit Debugger multiple selections FreePascal IDE Tum RHIDE aio Extra printf writeln statements mon gdb T ddd um Other Tools Used bash script 4 bc 10 cat 2 diff gnome calculator 4 gprof grep EUIS joe kate kedit less make 2 mc 7 nano perl 2 ps time xcalc Windows users debug com edit com 2 notepad 8 windows calculator 20 Grading System Usability No 1 S answer Easy 2 2 a Hard aes 3 77 16 4 2 1 Submit 050 74 8 15 5 3 9 1 9 a o 134 Testin 6 63 21 n 2 2 1 56 5 896 61 1 20 4 7 8 2 9 1 0 i E 0o ij a o A 1 39 8 14 6 67 0 6 8 6 8 1 9 1 9 i m 12 74 10 4 1 2 35 P 11 7 71 8 9 7
116. ounced on the competition web site and the IOI mailing list Page 98 of 142 IOI 2002 Yong In Korea The contestant should be familiar with the programming package of his her choice including the use of libraries or units The contestant should be able to execute programs change the working directory and manage files and use a web browser Similar installations will be used for the computers in the translation computer room Windows installations include MS Word with some multi lingual support and PowerPoint In the Linux environment TeX will be provided Competition Tasks All of the tasks in IOI2002 are designed to be algorithmic in nature There are two types of tasks 1 tasks for which a solution comprises a single source file of a computer program and 2 tasks for which a solution comprises a set of output data files Efficiency plays an important role in some tasks Whenever efficiency of algorithmic computations is important there will be at least one grading input for which some correct but inefficient programs can also score some points It is important therefore for contestants to attempt a task even if the contestant does not know how to solve the hardest possible test cases 1 Tasks for which a program source file is requested as a solution When a program source file is required as a solution the program source provided by the contestant must be contained in a single source file The task documentation will speci
117. output of your program is wrong you will get 0 If your output is correct your score depends on the number of queries The query is implemented as a library We assume that the pictures are squares LIBRARY You are given a library with the following single operation query x1 y1 x2 y2 x1 y1 is the position of a pixel in the small picture x2 y2 is the position of a pixel in the large picture if the two pixels are the same query x1 y1 x2 y2 returns 1 Otherwise it returns 0 INPUT The input file name is PICTURE IN The first line of the input file contains two integers m and n The size of the small picture is m m and that of the large picture is nn The following m lines of the input file contain rows of the small picture OUTPUT The output file name is PICTURE OUT The output file contains one line that consists of two integers x and y The position x y in the large picture should be an occurrence of the small picture Page 93 of 142 IOI 2002 Yong In Korea EXAMPLE INPUT AND OUTPUT If the large picture is the following the answer should be 1 2 or 2 3 Example 1 picture in large picture 2 5 ab aa A Solution and testing data There can be three levels of solutions a Very hard to get this solution Consider the small picture as a set of its rows Build a trie that represents the set of rows Ask queries to see if some specified rows of the large picture contain a row of the small picture Every
118. p cl n 1 c1 c2 nt 1 c2 ql n 1 ql q2 n 1 q2 soutput l cl F2 C2 pl gl p2y g2 finding two rods in the boundary found void find_shape lnt Ll 12 l3 14 Ck Ck rl cl ll pseudo rect brl bri bcl bcl 12 pseudo rect br2 br2 bcl bcl l3 pseudo rect brl bri bc2 bc2 watching 3 corners if 11 12 13 0 cross shape rk top to bottom search br1t1 br2 2 bcl bel ck left to right search brl bri betl bc2 2 soutput rkt1 bel rkt1 bc2 brl ckt1 br2 ck 1 0 or 1 or 3 of 4 corners could be filled if 114 12 13 1 14 1 else if 114 12 13 3 14 0 else l4 pseudo rect br2 br2 bc2 bc2 if 11 12 13 14 3 if br2 brl 1 amp amp bc2 bcl 1 if 11220 soutput br2 bel br2 bc2 bri Page 78 of 142 bc2 br2 in 2 by 2 square bc2 int p2 int IOI 2002 Yong In Korea if 12 0 soutput brl bel br1 bc2 bri bc2 br2 bc2 if 13 0 soutput brl bel br2 bel br2 bel br2 bc2 if 14 0 Soutput brl bel br2 bel rl bol bri BEz if 12 0 14 0 v_flip 1 if 13 0 14 0 h_flip 1 if br2 brl 1 d flip 1 pseudo init i ei FF mi doce dede eee if pc2 pcl 1 rk bottom to top search pr142 pr2 1 pc2 pc2 1 if rk pr2 1 rk pr2 pseudo output prl pc2 rk pc2 pr2 pcl pr2 pc2 if pseudo rect pr
119. peration Try again after some time If the problem persists consult administrator Unknown error Try pressing reload button Submit test output window messages These messages are displayed inside the submit output window or the test output window Other task specific messages are also displayed in the submit output window or the test output window See the task description for each task for information on task specific messages Error Message Explanation The system failed to process the Check your program and consult administrator job Please consult administrator HEADER CHECK OK HEADER CHECK ERROR COMPILE OK SAMPLE DATA TEST OK SAMPLE DATA TEST ERROR output only task need no testing Test facility is not provided for the output only tasks Use the submit facility for format checking of output only tasks header format error Check header format task name is invalid Check task name field in the header execution time limit exceeded User s program did not terminate within the execution time limit per task output size limit exceeded Output size limitation of 200k bytes for each of stdout and stderr is exceeded and execution of the program is stopped wrong answer Failed to produce correct output with sample Page 118 of 142 IOI 2002 Yong In Korea test data This error message is shown in the submit output window only
120. pixels in the image it is possible to find the required imagecorners in Step 1 of the algorithm Since each of the executions of Step 1 reduces the number of imagecorners Algorithm 1 will eventually halt and the image will be all white It follows that Algorithm 1 works correctly O a 2 optimal solution Solution 1 For each row i For each column j If point i j is corner Let k be the nearest corner right to the point 7 in row i Let be the nearest corner below to the point 7 in column j XOR j k 1 i l 1 j b Randomized 2 optimal solution Repeat Load initial data While there are corner points Choose a corner point i j randomly Let k be a random corner in row i Let be a random corner in column j XOR j k 1 i l 1 until there are no improvements This randomized algorithm gives a chance of best solutions If this algorithm runs several times we can choose the best among the solutions c Simple greedy algorithm Solution 2 For each row i For each column j If pixel i j is black Find the horizontally maximal black run from i Assume pixels in i j to k 1 are all black Find the vertically and maximal black run from i Assume pixels in i j to j 1 are all black so rectangle region i k 1 x 1 is a black rectangle XOR j k 1 i l 1 Page 36 of 142 IOI 2002 Yong In Korea d Algorithm using Maximal Matching Solution 3 Solution 3 finds a set of
121. r Message Explanation Submission failed Already The user attempted to start a new submit processing process before the previous submit process is finished Submission failed No file No file is selected into the Submit File box selected The file path specified is inadequate retry after copying the file to some other place Submission failed Contest not The contest is over and the user is not allowed running to start a new submission process Test failed Already processing The user attempted to start a new test process Page 117 of 142 IOI 2002 Yong In Korea before the previous test process is finished Test failed Select two files Not both files are present in the Test File box and Test Input box The file path specified is inadequate retry after copying the file to some other place Test failed Contest not running The contest will be over in less than 5 minutes and the user is not allowed to start a new test process Source code display failed Please Fail to follow the HTML link in the accepted retry or consult administrator submissions table Check if the filename of the file submitted follows UNIX filename conventions and retry File upload interrupted Please The user canceled a file upload possibly by retry pressing cancel button on the web browser or a network error occurred Print Successful A printing job is successfully spooled Print Failed The printing subsystem is not in o
122. rategy unfortunately would exceed the memory limit of 64MB However as this array is very sparse it may be stored in memory as a hash table which in the expected case does not affect the time complexity but which in the worst case does The third and best option is to construct the graph in linear time and constant memory by sorting the locations e g row major column minor and keeping 3 pointers into the list A B and C for pointing to PA Pp and pc A lt B lt C as follows loop A over all values and for each A march B and C down the list moving either B or C forward at each step so as to try to maintain as close to equal spacing as possible when exactly equal spacing is found enter the nodes and edge into the graph There is also an O N dynamic programming algorithm to solve this problem which is plagued by the same memory problems as illustrated above In addition to storing the identity matrix described above store another O N matrix containing whose rows are indexed by pa along the row are N entries one per plant pp giving the number of landings Page 18 of 142 IOI 2002 Yong In Korea in a candidate frog path which goes through pa and pa but which only uses points which sort before pa in the ordered list i e pretend the field ends at pa and look for frog paths of any length in that smaller field the idea is to find partial frog paths which violate none of the frog path conditions in the region of the field a
123. re is 5 20 x DistanceInBestAnswer DistanceInYourAnswer The score is rounded off to the first decimal place for each case The total score is rounded off to the nearest integer Suppose that you submit the tour 1 53 52 55 54 51 The length of your tour is 26 If the best of submitted solutions is a tour 1 52 53 54 55 51 whose length is 18 your score becomes 5 20x18 26 18 846 which will be rounded off to 18 8 Page 11 of 142 IOI 2002 Yong In Korea A Solution This is a famous Traveling Sales Person TSP problem which is one of typical NP hard problem There are lots of heuristics for this problem It is easy to find useful references and books ftp ftp zib de pub Packages mp testdata tsp tsplib tsp index html gives traveling sales person problem instances and solutions http www math princeton edu tsp is one of TSP Home Page According to this site Mathematical problems related to the traveling salesman problem were treated in the 1800s by the Irish mathematician Sir William Rowan Hamilton and by the British mathematician Thomas Penyngton Kirkman A nice discussion of the early work of Hamilton and Kirkman can be found in the book Graph Theory 1736 1936 by N L Biggs E K Lloyd and R J Wilson Clarendon Press Oxford 1976 The general form of the TSP appears to be have been first studied by mathematicians starting in the 1930s by Karl Menger in Vienna and Harvard A detailed treatment of the connec
124. resh 68 Install games and mp3s on the computers 69 Provide contestants with free music and headphones 70 Would be preferable if knowledge of specialized algorithms and especially important insights e g O n for BATCH solution for BUS not be required as this unfairly benefits certain algorithms over others It is better if questions asked for tricky applications of general algorithms as in IOI 2002 CEOI 2002 rather than direct applications of more obscure algorithms which competitors can hardly expect to derive and prove correctness within 5 hours e g minimum diameter spanning tree 72 More question time an hour is too few Time limit for tasks more permissive 75 Make less mathematical and more algorithmic tasks and at least one easy task per day 81 The problems were so hard Make it easy next time 82 I should be able to see the sources I have submitted I should also be able to test the sources I submitted without having to select the file on my hard disk which might be different from the one submitted I think a just submitted program option should be added 85 Scores were reported pretty late I think that due to the nature of the graders you could have shown us our scores on the screens of our Woojungwon stations might after the end of the competition Page 135 of 142 IOI 2002 Yong In Korea Appendix VII Delegation Questionnaire Questions about IOI 2002 Competition What do you think about the
125. rough http www freepascal org which shows a number of mirror sites We have installed the binary version of freepascal 1 0 6 You can download fpc 1 0 6 ELF tar 14 3 MB file which contains a standard tar archive with an installation script After untarring the archive you can run the installation script in the created directory by issuing the command sh install sh RHIDE for Linux The debian woody doesn t contain the RHIDE package You can download the tarball file from http www rhide com Pascal IDE for Linux You can download the snapshot version of Linux IDE with debugging support You should be able to download it at the development section from http www freepascal org Linux and Cygwin You may want to learn about using Linux and do not want to install it The GNU tools are in the core of the Linux facilities and you can obtain a much larger collection of them from the DJGPP package see Windows gcc A collection of GNU facilities can also be obtained from http www cygwin com This Cygwin package has even more of the feel of Linux as they are being used through the bash shell which is common in Linux systems Page 105 of 142 IOI 2002 Yong In Korea Note that the Cygwin is not a part of the competition environment Windows We are using Windows XP We expect support for the hardware to be available in Windows XP You can get information about Windows from http www microsoft com windows
126. rt fa b T would not be executed I kept the command 1 for convenience start 8 L dodo B 8 R S R 8 L 1 2 3 4 5 6 7 8 B 8 U p Figure 10 Another motion planning with flag 11 lt B L gt lt 8 D gt lt B B D gt lt B 8 D gt lt B B D gt lt B 8 L gt lt B R gt 10 lt 8 8 R gt B 8 U lt 8 Figure 11 Another answer for part b with 14 commands Page 92 of 142 IOI 2002 Yong In Korea Submitted Task 2 PICTURE Kunsoo Park Picture PROBLEM You are given a small picture You can carefully look at the given picture and remember every detail of the picture Then you are supposed to go into a dark room A large picture is hung on a wall of the dark room Inside the large picture there is at least one occurrence of the small picture given to you You are to find any one occurrence of the small picture in the large picture The problem is that you cannot see the large picture because you are in a dark room You know only the size of the large picture The only way you can access the large picture is by asking queries You can ask a query to test whether or not a pixel of the small picture is the same as a pixel of the large picture The answer will be either yes or no You are to write a program that given a small picture and the size of a large picture finds an occurrence of the small picture in the large one If the
127. s output files In the figure above NUMBER and Page 112 of 142 IOI 2002 Yong In Korea STRING are examples of single file tasks and RED is an example of an output only task which accepts 4 output files 4 Announcement window The announcement window displays announcement messages from the administrator of the system The time of announcement is also displayed Every user sees the same message When the administrator puts up a new announcement message users must reload the main screen manually to display the new message Thus it is advised that the announcement message does not contain any critical information 5 Submit facility It is used to initiate a submission process Select a file to be submitted into Submit File box and press Submit button During the submission process the submit window is replaced by Submission Progress 0 message A user should reload the main screen manually to check the submission process progress and get submission results displayed 6 Test facility It is used to initiate a test process Select a source file to be tested into Test Source File box and its input file into Test Input File box and press Test button During the test process the test window is replaced by Test Progress 0 message A user should reload the main screen manually to check the test process progress and get test results displayed 7 Print facility A user may use Print File box and Print
128. s x yi and x2 y2 is x x y y If bus stops 4 and B are connected to the same hub 71i then the length of the route from A to B is the sum of the distances from A to H and from H to B If bus stops A and B are connected to different hubs e g A to H and B to Mh then the length of the route from A to B is the sum of the distances from 4 to Hi from H to H5 and from M gt to B The planning authority of Yong In city would like to make sure that every citizen can reach every point within the city as quickly as possible Therefore city planners want to choose two bus stops to be hubs in such a way that in the resulting bus network the length of the longest route between any two bus stops is as short as possible One choice P of two hubs and assignments of bus stops to those hubs is better than another choice Q if the length of the longest bus route is shorter in P than in Q Your task is to write a program to compute the length of this longest route for the best choice P INPUT Your program is to read from standard input The first line contains one positive integer N 2 N lt 500 the number of bus stops Each of the remaining N lines contains the x coordinate followed by the y coordinate of a bus stop The x and y coordinates are positive integers 5000 No two bus stops are at the same location OUTPUT Your program is to write to standard output The output contains one line with a single positive integer
129. s unstable 85 The tools used on Linux are a little bit unstable The best example is RHIDE Having the newest version is not the same as having the best version Also RHIDE would have worked much better if you gave us root access which I think is not impossible 87 Linux was not properly configured Improve configuration 99 More usable version of RHIDE 101 Use VESA VGA console mode for better console resolutions Windows Environment 1 Choose a windows version on which RHIDE works 10 I don t like RHIDE very mush The amount of code I can see on screen is small and the program is unstable It would be nice to have a Windows not Dos based IDE though I don t if it s possible 14 Borland C is very good thing 15 File Manager Any 16 The FP crashes if memory limits exceeds Can this be fixed 19 The RHIDE didn t work with FPC compiler Although it was said before competition that it wound That s not fair There should have been file manager provided for example windows commander for Win XP users 21 There should be windows commander available 29 Use Windows 98se instead of WinXP because RHIDE halts very often 31 Make them stable 33 I missed some file manager like Norton Commander 34 RHIDE is very unstable with Win XP Use Win 98 37 RHIDE is not stable enough and it s quite old and looks very stupid so new IDE would be nice 38 File manager like FAR WC Shortcuts on Desktop
130. t 30 credits A brute force program running in O N time will be successful only for the first six test data within the time limit For the other test data its running time will exceed the time limit so it gets at most 30 credits The detail on the test data is summarized in the following table The time limit is 4 second The largest running time is 3 343 second for the last test data Testing Data Description for BUS Size Range of Correct Heuristic s mia mE ES 1 2 10 Exremecase ae S Mem row c 16 100 20 Random 35 36 8 180 1000 Random 1845 1849 9 300 650 Dumbbell 45 degree 911 m Page 64 of 142 IOI 2002 Yong In Korea Timing Test for BUS sec Optimal in Optimal in Brute force Brute force C C Pascal in C C in Pascal aaa REN ERIT end Ll o0 O f o o eE o 6 29 E30 P Ee 4 o 0 0 O J 5 0 00 00 007 6 00 004 097 2098 8 oo 016 56 100 9 03x o9 366 638 o 11 0 83 1 95 gt 50 gt 50 13 0 33 0 76 gt 50 gt 50 15 0 51 1 2 gt 50 gt 50 17 0 52 1 18 gt 50 gt 50 18 08 oo 18 B69 Bgy 19 0 77 1 75 gt 50 gt 50 C References 1 J M Ho D T Lee C H Chang C K Wong Minimum Diameter Spanning Trees and Related Problems SIAM J on Computing 20 5 987 997 1991 2 T Chan Semi online maintenance of geometric optima and measures 73th ACM SODA 474 483
131. t a user submitted is run under resource limitations Process memory and output file size limitations are enforced by the resource limitations set on the user s executable file Page 116 of 142 IOI 2002 Yong In Korea File accessibility The running environment of a user program is set up so that the user program cannot access other files Moreover the hardware on which a user program is run is a separate system from the rest of the hardware including the server and it contains only a sample input file and a checker for the sample input Network security The hardware where a user program is run is set up in a private network where it can only access the central system server Any attempt to connect to the central system server is monitored from the server side The private network itself is also packet monitored Logging All user programs submitted or tested to the server are kept with their output and activity log The activity log of the system is kept in three different parts of the system and the three recordings are cross checked after the contest CONTACT INFORMATION The IOI 2002 Contest System is developed and maintained by Computer Theory amp Cryptography Lab School of Computer Science and Engineering Seoul National University Seoul Korea Email to sllee snu ac kr for technical information APPENDIX A ERROR MESSAGES Web server messages These messages are displayed in the main page Erro
132. t damage A frog always jumps through the paddy in a straight line with every hop the same length eo 9 09 09 09 Different frogs can jump with different hop lengths And in different directions 00060006000 99 Your rice paddy has plants arranged on the intersection points of a grid as shown in Figure 1 and the troublesome frogs hop completely through your paddy starting outside the paddy on one side and ending outside the paddy on the other side as shown in Figure 2 RC WEE Hn Figure 1 Figure 2 Nn BW NY mn Many frogs can jump through the paddy hopping from rice plant to rice plant Every hop lands on a plant and flattens it as in Figure 3 Note that some plants may be landed on by more than one frog during the night Of course you can not see the lines showing the paths of the frogs or any of their hops outside of your paddy for the situation in Figure 3 what e can see is shown in Figure 4 2 3p 5 6 7 TO O 2 3 4 5 6 Figure 3 Figure 4 Page 15 of 142 IOI 2002 Yong In Korea From Figure 4 you can reconstruct all the possible paths which the frogs may have followed across your paddy You are only interested in frogs which have landed on at least 3 of your rice plants in their voyage through the paddy Such a path is said to be a frog path In this case that means that the three paths shown in Figure 3 are frog paths there are also other possible frog paths The vertical path down column
133. t last visit plane 3 C Grading If a contestant s program outputs the correct answer for a test case in the time limit then he she receive 4 points for that test and otherwise he she gets 0 points for the test case 4 4 4 I Uy il w UI oj Z Z d nln Z Z Il E Z Z I ERE PERPE Z E ES Ka EAE pa NI CA D Remark The original one dimensional problem entitled Sign Representation was proposed by Sergey Melnik It was extended to the two dimensional problem by the Host Scientific Committee Page 29 of 142 IOI 2002 Yong In Korea E Source Code for UTOPIA Kee Moon Song TASK Utopia LANG C Optimal solution O N af include lt stdio h gt include lt stdlib h gt define MAX 10000 int num N int data 2 MAX dest MAX int answer MAX 2 void getdata int i scanf d amp num for i 0 i lt num i scanf Sd Sd amp data 0 i amp data 1 i for i 0 i lt num i scanf d amp dest i int compare const void a const void b subroutine for qsort return int a gt int b 1 1 void preprocessing Sort input values qsort data 0 num sizeof int qsort data 1 num sizeof int r compare r compare int check int plane int axis if axis 0 return xx0 if axis 1 return y 0 if axis 0 return plane 2 amp amp
134. task Suitability To Understand It To Translate It No 9 Much Easy Hard Easy Hard FROG O 0 0 0 0 O 0 0 0 0 O O O O O UTOPIA L1 LI L1 L1 LI L1 LI L1 L1 L1 L1 LI L1 LI1 L1 XOR O O O O O O O O O O O O O O O BATCH O O O O O O O O O O O O O O O BUS O O O O O O O O O O O O O O 0O RODS L1 LI L1 L1 LI L1 LI L1 L1 LI L1 L1 L1 DI Which task did you like BEST of all Which task did you like LEAST of all Do you like the idea of output only tasks Yes No Do you like the idea of the relative scoring LE Yes No Please grade the Grading System and the Web services Usability Response Time Do You Like It Easy Hard Slow Fast No Much Submit LI LI LI LI L1 0 0 0 0 0 0 0 0 Testing 0 0 0 0 0 0 0 0 0 0 0 0 Print O O O O O O O O O O O O O O O Backup LI LI L1 LI L1 LI LI LI LI L LI LI LI LI LI Do you find it useful to receive the contents of the students home directories after the contest LE Yes LE No What is your opinion of the 1 page solution explanation handout Useful LE Not useful Too detailed Ck Just right Li Not detailed enough Are you subscribed to the IOI LIST mailing list Yes No Suggestions for improving the Linux competition environment Suggestions for improving the Windows competition environment Suggestions for improving the Grading System competition environment Any other comments Page 136 of 142 IOI 2002 Yong In Korea Brief Summary There were 78 delegations at IOI 2
135. that d 7 0 for any city 7 Given the distance between cities you are to find a Red Devil s tour with the shortest possible length You are given the input files describing the distances You must submit files describing the tours not a program to find the tours INPUT Page 10 of 142 IOI 2002 Yong In Korea You are given 4 problem instances in the text files named red1 in to red4 in Each input file is organized as follows The first line contains one integer the number of cities N 5 lt N lt 50 The following N lines represent the distance d J where for each d J we have 0 lt d 1 J 50 These N lines are organized in such a way that the K of these M lines contains N integers the distance d K 1 d K 2 d K N This way the input is organized in the following form N d 1 1 d 1 2 d 1 N d 2 1 d 2 2 d 2 N d N 1 AN2 d N N OUTPUT You are to submit 4 output files corresponding to the given input files You do not need to submit your solution program source The first line contains the text FILE red I where integer I is the number of the respective input file The second line contains N 1 integers which represent the cities in the order in which they are visited in the tour of your solution EXAMPLE INPUTS AND OUTPUTS Examplel red0 in red0 out FILE red 0 132541 SCORING If the output is not a valid tour your score is zero Otherwise your sco
136. the competitors design an efficient algorithm or not Among 20 test cases algorithm by enumeration may solve for three ones within the given time limit and an O N time algorithm may solve for 14 test cases within the given time limit If the competitors submit a correct O time algorithm they will get 100 credits Timing Test for BATCH No C C Pascal C C Pascal 10 T 12 3 4 001 lt ooi 003 006 5 16 7 Page 55 of 142 IOI 2002 Yong In Korea Testing Data Description for BATCH M 1 Example 2 153 15 Randomly generated data 322305 LL Nc Randonee any e N 30 Randomly generated data 1414590 NE N 50 Randomly generated data 3900980 7 N 100 Randomly generated data 12636575 8 N 200 Randomly generated data 50649757 9 N 300 Randomly generated data 124220878 11 E 700 Randomly sand data 635041453 2 331524426 Ur 1500 Randomly ae data 744367663 Randomly generated data Randomly generated data Randomly generated data Randomly generated data ir 9000 Randomly generated data 1042629359 9500 Randomly generated data 925702728 10000 Randomly generated data 1025371921 C Variations There are other several variations of the batch problem 2 1 If there is no restriction on the scheduled sequence of jobs that is a batch consists of arbitrary set of jobs then the problem is NP hard 2 1f the cost factor of all jobs are all 1 a
137. the hubs and assignments of bus stops As did in 1 we consider two cases separately For it we need some notations Let D be the minimum value of the longest length between two bus stops which are connected through only one hub over all possible choice of one hub and let D be the minimum value of the longest length between two bus stops which are connected through both two hubs over all possible choice of two hubs and the corresponding assignments of bus stops We can now find the diameter in the following way presented in 1 First compute D and D Next output the minimum of D and D as the minimum diameter of the entire network First we will explain the computation of D If a point p will be served as the hub through which the longest route passes the longest length is d p q d p r where the points q and r is the farthest and the second farthest ones from p respectively Then D min dp q d p r over all points p of the input This can be obtained in O N time because the farthest and second farthest bus stops for each point p are easily found in O N time Of course we can reduce the time complexity to O N log N by using the second order farthest Voronoi diagram But we simply implement the O N time algorithm because the complexity does not affect the total complexity of O N Second we will explain how to compute D with a simple example Note that in this case the longest route between two bus stops w
138. the network are not allowed to fork are not allowed to read or create files directly are not allowed to attack the system security or the grader are not allowed to attempt to execute other programs are not allowed to change file system permissions and are not allowed to read file system information A contestant whose program attempts any of the above will be disqualified User Manual Addendum Timing Library will be provided To measure the CPU usage of the program we will provide a function called exectime See Contest System Users Manual Appendix B for detail Online Help C C including STL manual and Pascal help file will be available at the competition web page Linux and Web Browser Trouble A large amount of output causes mozilla to freeze for several minutes Solution When this happens run the web browser opera and perform an action which replaces the contents of the box with the large amount of output e g submit a different test program which produces less output Note The contest system has not been tested with opera use mozilla when possible Page 109 of 142 IOI 2002 Yong In Korea Linux and FreePascal Trouble Running the Freepascal IDE from X Windows the terminal does not display correctly Solution Switch to console mode via Ctrl Alt Fl before running the FreePascal IDE You should log in again Ctrl Alt F7 switches back to X Windows Linux Trouble The RHIDE and FreePascal I
139. the number of calls to oracle call made by your program and the second line contains the hidden string your program has given as a solution EXAMPLE INPUTS AND OUTPUTS The length L of the hidden string satisfies 1 L 255 You can experiment with the library by creating a text file string in with a single line which contains the hidden DNA string Note that the string out in the following example is not necessarily optimal It merely shows the file format of input and output Examplel string in ATTGCGCGATCG string out 41 ATTGCGCGATCG SCORING If your program violates one of constraints e g calling too many function calls then you get 0 point Page 8 of 142 IOI 2002 Yong In Korea If your solution is not correct then the score is 0 When the output solution is correct then your score depends on the number of library function calls for each testing data For each data if the number of function calls is less than a bound B that is fixed independently for each data then you get full score Otherwise you will get 0 points A Solutions a simple solution A simple solution is to try each of 4 strings from k 1 2 Stop when there is no string of length k 1 with answer yes The string of length k with a yes is the hidden string In case of English strings replace 4 by 26 b Suggested solution 4 N 2 oracle calls are sufficient 26 N42 in case of English strings Assume that a string
140. ting in Seoul Feb 17 reported the current state of the tasks to IC 3rd HSC meeting at KAIST Mar 29 30 reviewed the first draft of candidate tasks programmed solutions 4th HSC meeting at KAIST Apr 26 28 reviewed solution programs and test data tested solution programs for timing 5th HSC meeting at KAIST May 4 ISC meeting at KAIST May 11 18 HSC and ISC reviewed and discussed the first draft of tasks Prof Kunsoo Park explained our evaluation system and discussed with ISC ISC selected 7 competition tasks out of 16 tasks ISC improved the presentation style of 7 selected tasks 6th HSC meeting at KAIST Jul 3 5 7th HSC meeting at KAIST Jul 22 23 demonstrated task evaluation system loaded and tested solution programs and task library on the evaluation server Evaluation system was tested on line and off line Jul 25 Internet Practice Session Opened Aug 6 8th HSC meeting at KAIST Aug 7 finalized tasks and solutions Page 3 of 142 IOI 2002 Yong In Korea TASK SUMMARY pre Reject Typical Heures NETWORK mieu seep Reject Rede UTOPIA Typical DAYI TASK2 XOR Output only DAY1 TASK3 IOI2002 used a new evaluation method namely relative scoring initially called tournament scoring In this scoring policy the number of points awarded to each competitor s solution depends on the best solution submitted by any competitor a competitor whose answer on a test c
141. tion between Menger and Whitney and the growth of the TSP as a topic of study can be found in Alexander Schrijver s paper On the history of combinatorial optimization till 1960 Most recent result on this problem is work done by D Applegate R Bixby V Chvatal and W Cook who solved 15 112 cities instance D15112 this is one of the larger TSP instances in TSPLIB It contains 15 112 cities in Germany D Deutschland The data set was contributed to TSPLIB by Andre Rohe See http www math princeton edu tsp d15112 d15112 info html for D15112 B Relative Scoring Other issue in RED is the relative scoring policy which was first proposed and implemented in IOI 2002 Relative scoring gives scores according to the relative quality of the solution This is an open ended competition which means better solution will receive more scores and any valid answer receives some points It is suitable for NP hard class or real world problems Score will be given by a function of submitted solution A and the best solution BEST Scoring function base proportional x BEST A For example Task RED if the submitted tour length is 26 and the shortest submitted tour length is 18 score 5 20 x 18 26 18 846 rounded to 18 8 So best solution earns full score 5 20 x 18 18 25 If the best solution is changed by an appeal then grading will be performed again This might affect the others score Page 12 of 142 IOI 2002 Yong In K
142. tions print files and backup files Readers are expected to have a good understanding of IOI contest rules Readers who do not have sufficient knowledge are advised to read IOI 2002 Competition Rules first Submit A user may submit a source file or an output file using the submit facility on the main page Note that the main screen is not automatically updated as the submission process progresses The user must manually reload the main screen Either by pressing Reload button or FS button on the keyboard to get submission results However once the user starts a submission the submission process is internally processed Page 114 of 142 IOI 2002 Yong In Korea regardless of user s updating his or her main screen output Thus even if the user does not check submission results i e he she never updates the main page or he she immediately closes the browser after initiating a submission process or the user s computer is powered off immediately after initiating a submission process the submission is processed unhindered and if the submission is accepted it will replace the last submission Also reloading the main page frequently will not speed up the submission process The number displayed during a submission process as Submission Progress 0 indicates the percentage of progression When the number hits 90 the submission process is actually started on the server side A user can have only one submission being processed at a ti
143. tions and Remarks We can find a naive answer by drawing a graph having edges correspond to the commands given to the robot as shown in Figure 3 below Obviously the sequence of 15 commands i e edges is as show in Figure 4 Actually the graph represents a finite state automaton that draws the figure So the problem can be interpreted as a robot motion planning as well as designing a finite state automaton Assuming that the participating students do not understand the automata theory I wrote the problem in terms of robot motion planning which can be dealt with their bright common sense Notice that the number of states does not necessarily match to the length of the program lt B 8 R gt lt B 8 R gt lt B 8 D gt B8 Ds B 8 D gt lt B 8 D gt lt B 8 D gt lt B 8 D gt lt B 8 L gt lt B 8 L gt B 8 D gt 9 lt B 8 U gt 10 lt B 8 U gt 11 lt B 8 R gt B 8 D gt 12 lt B 8 L gt 13 lt 8 8 U gt lt B 8 L gt lt B 8 L gt 14 lt B 8 U gt 15 lt 8 8 S gt start lt B 8 U gt lt 8 8 U gt lt B 8 U gt lt B 8 U gt Figure 3 A naive motion planning Figure 4 A naive answer for part a Page 90 of 142 IOI 2002 Yong In Korea Notice that the following cleaver answer utilizes symmetric property of the figure See Figure 7 on the following page for the robot motion profile 1 lt B 8 D gt 2 lt B 8 D
144. total sum of elements in X is equal to 3 4 5 6 7 5 which is also positive We let S s 5 15 seta Xe a lt b is valid with respect to S if the sign of gt 4 a b be a sequence of signs plus and minus A i sequence X x 3x eto S equal to s foreach k a lt k lt b Page 25 of 142 IOI 2002 Yong In Korea Theorem 1 Let X x x X5 a b be an alternating sequence and let S s 8 there exists a sequence X x x 45 a amp b be a sequence of signs If the sign of x is equal tos then 3X such that adl aa i 1x 3X eX m DX and ii X is valid with respect to S Proof The proof is by induction on the number k of elements in X Whenk 1 it is easy to see that X X is a valid sequence with respect to S Now we assume that k 2 2 We let S S s that is S 5 415 555 1 Case 1 The sign of x is equal tos Let X X x that is X x x x and let t x Case 2 The sign of x is equal tos Let X X x that is X x x 4 x and let t x Note that X is an alternating sequence and S is a sequence of signs such that the sign of the last element in X is equal to s the last element in S Thus by induction hypothesis there exits a valid sequence X with respect to S Therefore X 2 X f isa valid sequence with respect to S Example 3 For an alternating sequence X
145. travel the gridpoints to the left one by one At some point either the black pixels below end or black pixels above start If both of these happen at the same time we find no imagecorner yet and the situation is reversed and we continue When as we go left the pixel color changes only above or below this must eventually happen as at least we must eventually come to a situation where pixels both above and below are white we encounter an imagecorner which we choose These three imagecorners specify a valid rectangle Therefore it is always possible to choose the XOR call in such a way that either four or three of the grid points at the corners of the rectangle affected by the XOR are imagecorners Now if all four of these corners are imagecorners then by Lemma 2 we reduce the number of imagecorners by 4 and if exactly three of these corners are imagecorners then by Lemma 2 we reduce the number of imagecorners by 2 we remove three imagecorners and create one This completes the proof We now get the following 2 optimal method for solving XOR Algorithm 1 Two optimal XOR 1 If there are black pixels in the image find three imagecorners that can be used to specify a rectangle and use the respective XOR call Go to 1 2 Halt Page 35 of 142 IOI 2002 Yong In Korea Theorem 1 Algorithm 1 is correct and 2 optimal Proof We will first show the correctness of Algorithm 1 From Lemma 3 it follows that as long as there are black
146. u just first unzip the file and run install exe You can use Freepascal with its own IDE Page 106 of 142 IOI 2002 Yong In Korea APPENDIX III User Manual for IOI 2002 GENERAL Contestant materials Contestants will get the competition materials in the competition envelope The envelope will contain a sheet for a user id and password for the web services You need them to access the services Selecting operating system You can select Linux or Windows XP at booting Competition computers are configured for dual booting Use the cursor key to highlight your choice and type Enter key Login You do not need to login to Windows XP You can login to Linux with username ioi password ioi Restarting your computer In Windows XP click Start and Turn off computer From the menu that appears choose Restart In Linux you may press Ctrl Alt Fl to change console mode You can return to X Windows mode by pressing Ctrl Alt F7 Then you may press Ctrl Alt Del to restart If you need help If you need any assistance system trouble go to toilet whatever please just raise your hand and wait for help PROGRAMMING Comment tags for grading Your program or output file for output only tasks must have certain tags in comments for the grading system to identify the task and the programming languages for source code file For the source code submission the syntax will be TASK taskname LANG LANGUAGE
147. ve will be disqualified Page 103 of 142 IOI 2002 Yong In Korea APPENDIX II Programming Environment General Please first check the general information about the competition programming environment from the Competition Rules The main environment for the contest is Linux Linux is available as a programming environment specifications below and also the servers and evaluation grading runs on Linux However we provide the contestants with dual boot computers where you can program either in Linux or in Windows environment The evaluation is based on source code submission and the evaluation system compiles the submitted source code As a consequence also the programs written in the Windows environment are re compiled for evaluation in Linux using the same compiler This is something that all contestants using Windows must be aware of For example uninitialized variables may cause undefined behavior when executing for the evaluation We favor fairly standard operating system installations But we may modify the installations for hardware support and security fix The compilers used in the competition are GCC for C and C programs and Freepascal for Pascal programs Generally the installations are designed for the following main alternatives 1 Pascal as the programming language Freepascal compiler Freepascal IDE 2 C C as the programming language GCC compiler RHIDE IDE 3 Editors emacs vim command line compi
148. vices Usability Response Time Do You Like It Easy Hard Slow Fast No Much Submit O O O O O O O O O O O O O O O Testing O O O O O O O O O O O O O O O Print O O O O O O O O O O O O O O O Backup O O O O O O O O O O O O O O O Please rank the six tasks Understand It Find Algorithm Write Program Easy Hard Easy Hard Easy Hard FROG O0 0 0 0 0 O0 0 0 0 0 O O O O O UTOPIA O O O O O O O O O O O O O O O XOR O O O O O O O O O O O O O O O BATCH O O O O O O O O O O O O O O O BUS O O O O O O O O O O O O O O O RODS O O O O O O O O O O O O O O O Which task did you like BEST of all Which task did you like LEAST of all Was it useful to receive the contents of your home directory after the contest Li Yes No Page 127 of 142 IOI 2002 Yong In Korea Are you subscribed to the IOI LIST mailing list Ci Yes No Suggestions for improving the Linux competition environment Suggestions for improving the Windows competition environment Suggestions for improving the Grading System competition environment Any other comments Brief Summary There were 276 contestants in IOI 2002 By end of IOI 2002 we had received 103 completed forms about 37 About 3 5 of the respondents use Windows XP and 2 5 of them use Linux E About 4 5 of Pascal users use Windows XP About 5 9 of C C users use Linux About 2 5 of the respondents use Pascal 1 3 use C and 1 5 use C E For Windows XP users about 3 5 use Pascal 2
149. where LANGUAGE is one of C C or PASCAL For the output only tasks the syntax will be FILE taskname data See the task overviews and task descriptions for detail Page 107 of 142 IOI 2002 Yong In Korea Range of integer variable The ordinary type integer in freepascal has the range of 32768 to 32767 In some tasks this may not be enough Use 32bit variant Longint type which has the range of 2147483648 to 2147483647 Exit value For C and C programmers make sure that your program terminates with exit 0 or return O in main Exiting with any other value is considered as an incorrect termination A normally terminated Pascal program returns a 0 when it terminates Differences between Linux and Windows XP A program submitted for grading or testing will be compiled using the options given in the overview sheet The compiled program will be executed on Linux Running programs on a Linux machine differs slightly from running programs on a Windows machine If you access a pointer variable that points the memory outside your allocation your program may stop abnormally If you access outside the boundary of an array your program may stop abnormally Linux does not initialize local variables to any predictable value These differences mean that your program might work fine on Windows XP and fail on Linux Be careful when using pointers arrays and uninitialized variables to avoid these proble
150. with thick lines In the left image some of pairs of edges are crossing but this does not affect to the minimality a Optimal network by Ho et al s algorithm b Non optimal network by heuristic Figure 6 Page 63 of 142 IOI 2002 Yong In Korea c Brute force approach We can make a brute force algorithm running in O N time It considers all pairs of points as hubs H and Ap and computes D H H gt for each pair in O N time B Test Data Information Kyung Young Lim In total 20 data will be tested and each data is of 5 credits All data are made with parameters n the number of bus stops in the range between 2 and 500 and the range of x y coordinates between 10 and 5 000 Among them 15 data are randomly generated The remaining ones are designed to test the special cases The data of test no 1 consists of only two points and the data of test no 12 is 20 x 20 grid with a regular shape with easy solution Three data from test no 9 to 11 have dumbbell shape distributions two points are lying on 45 degree 45 degree 0 degree line with fixed positions and the other points are randomly generated evenly around those two points The test data is mainly prepared to distinguish the heuristic and brute force programs with the correct one Among 20 test data only six ones have the same answers by both of the correct and heuristic programs Hence if competitors submit the heuristic program they will get at mos
151. xcessive printing requests The maximum size of the file to be printed is 1M bytes Backup The backup restore facility can be used to store user s files on the server The files can be as large as 1M bytes and each user is guaranteed to use space for at least 10 files Select a file to backup into Backup File box and press Backup button The restore page will be displayed with the list of backup files on the server on a successful backup An error message will be displayed on the main page on a failure Press Restore button to display the restore page A user may display or download backup files or delete one or all backup files Press Reload button on the restore page or backspace key on the keyboard to go back to the main page SECURITY MEASURES According to 1012002 Competition Rules submitted programs are not allowed to access the network are not allowed to fork are not allowed to read or create files directly are not allowed to attack the system security or the grader are not allowed to attempt to execute other programs are not allowed to change file system permissions and are not allowed to read file system information The IOI 2002 Contest System has features to enforce above rules The competition rules can be enforced at the time a user tries to break the rules or afterwards by examining log files The IOI 2002 Contest System supports both ways of enforcing the competition rules Resource limitations A program tha

Final Report on the IOI 2002 Competition

Contents

Download Pdf Manuals

Related Search

Related Contents