KöMaL Problems in Informatics, April 2009
Please read the rules of the competition.
Show/hide problems of signs:
Problems with sign 'I'
Deadline expired on May 15, 2009.
I. 211. Wire frames can be used to give simpler description of objects of an image. The main idea is to find a one-pixel-wide ``middle line'' of the object: this way less information is needed, and objects can be compared more easily. Frames are useful, for example, in character recognition.
Given a black and white image, your program should find and display the frame of the black components. Each frame should be one pixel wide, should preserve the connectedness of the original object and should keep the endpoints.
The algorithm for creating frames is described in the following. Black pixels are encoded by 1 and white pixels by 0. When creating the frame by narrowing, only contour points of the object can be changed. (A point is said to be contour point if it has value 1, and there is at least one 0 value among its 8 neighbours.) Neighbouring pixels are denoted as can be seen in the first table.
First step. Pixel s0 is deleted, if each of the following four conditions are satisfied:
Here #Neighbours (s0) is the number of neighbours of pixel s0 with value 1, while Changes (s0) is the number of changes of 0s into 1s (or vice versa) in the sequence s1,s2,...,s7,s8,s1.
In the example, Átmenet ( means Changes (.
Second step. Conditions i. and ii. are unchanged, and instead of iii. and iv., consider
and delete pixels according to these rules.
In the first step, all contour points of the object are scanned, then pixels satisfying the 4 conditions are marked as ``to be deleted''. You should delete pixels only after the scanning process has been finished. Then, in the second step, you repeat the same process, but with the second set of conditions.
Step 1 and 2 should be repeated until there is no change in the resulting figure. The frame is now complete.
The command line argument of your program is the name of a black and white BMP image. The output should be the original image together with its frame displayed on the screen. If you prefer, you can use a different image format (e.g. RAW) as well, but then the command line argument of your program should consist of the vertical and horizontal dimensions of the image and the name of the image file.
The source code of your program (i211.pas, i211.cpp, ...) and a short documentation (i211.txt, i211.pdf, ...) should be submitted, also describing your solution and specifying the name of the developer environment to use for compiling, further, the possible parameters of your program.
I. 212. There are at most 8 contestants in a certain chess competition. Each person plays against everybody else twice: once with white and again with black. A player gets 1 point for a win, 0.5 point for a draw and 0 points for a loss.
A spreadsheet application is used to keep track of the outcome of the matches. Worksheet ``Party'' contains the results from the viewpoint of the player with white. For example, if C is with white, A is with black and C has won, then ``1'' should appear in the row of C and column of A (see the first table).
You should work out that only values 0, 0.5 and 1 can be entered into the results field on worksheet Party. The name of the contestants can be entered in the first column, after which the first row is automatically filled with the same data. (You do not have to disable entering results into columns and rows of non-existent matches.)
Worksheet ``Actual'' should contain the current results of the contest. Players should be ordered according to their points in descending order. (If two players have the same score, their order is irrelevant, however, they should have the same place.) In the example, ``gy'' abbreviates victory, ``d'' is for draw, ``v'' denotes a lost party, and ``pont'' is points (see the second table).
The sheet (i212.xls, i212.ods, ...) together with a short documentation (i212.txt, i212.pdf, ...) should be submitted, also containing a brief description of your solution and the name and version number of the spreadsheet application.
I. 213. After some brilliant investigation, Poirot yesterday arrested Mr Colston, the director of a well-known company. Poirot also found a strange document in Colston's office, and he is sure that this document is not related to the ``primary'' job of the suspect.
The title of this document is ``Yearly account''. Then three instructions follow, finally there is a table: the first column of the table is numbered from 1 onwards, the second column contains some strange words, while the third column again contains certain numbers.
Poirot now asks you to decipher the document by using your knowledge in algorithmic theory and decoding. Poirot believes that the document describes the hierarchy of Colston's secret criminal organization. Poirot knows that-with the exception of the boss - everybody has exactly one superior in such an organization, moreover, everybody - for his or her own sake - must have followed the instructions of the document carefully, and finally, the name of Colston's secretary, Ms Hartsell, is likely to appear on the list.
The document can be downloaded from our homepage (i213.doc) . You will be awarded 5 points if you decode the hierarchy, and get additional 5 points for decoding the names. Exactly one name should appear in each line of your solution, and names of subordinates of a member should be indented. Your solution in plain text (i213.txt) should be submitted together with a short description of the decoding process (i213mo.txt, i213mo.pdf, ...), further, the source code of your programs (if any) that you have used during the solution.
Problems with sign 'S'
Deadline expired on May 15, 2009.
S. 44. A tram competition is organized on the longest tram line of the city. The goal is to travel the whole line in the shortest possible time, but at the same time there should be only one competitor on the line. During the contest trams do not carry passengers, but the organizers do not want to restrict car traffic in the city, so there is a second rule for competitors saying that a tram must stop if they encounter a red traffic lamp at a crossing.
Your program should compute the minimal time to travel the whole line. The input file (as the first command line argument to your program) contains the description of the tram line, while your result should be written in the output file (with name given as the second command line argument).
The front of the tram is located at x=0 in the coordinate system at time t=0. At the beginning of each time unit, the tram can change its speed instantaneously by -1, 0 or +1 unit. Then the tram travels uniformly at this speed for one time unit along the x-axis. The tram can stop but can not travel in the reverse direction. Its maximal speed is limited by a given constant M.
The front part of the tram can pass through a crossing only if the lamp shows green. State of the lamps are described by left-open and right-closed intervals, meaning that a tram can still cross if the lamp has just turned red, but the tram should not cross if the lamp has just turned green. A tram has completed the line if the x-coordinate of its front is equal to the length L of the line.
The first three rows of the input file contain three numbers separated by a space: the length 10L5000 of the line, the number 0N1000 of traffic lamps and the maximal allowed speed 1M30 of the tram. Then each of the following N lines contains the description of the actual lamp: the position 1XiL of the lamp, the number 1Ci100 of changing its state (but altogether at most 1000 changes), then Ci numbers, separated by a space, describing the time instants when the lamp changes between red and green. Initially, all lamps show green.
The output should contain only one number: the shortest time in which a tram can travel through the line. The number should be given in integer part-fractional part form, , where c is the speed of the tram at the last instant.
In the example, ``Példa.be'' is the name of the sample input file, ``Példa.ki'' is the output file, and ``Út-idő grafikon'' is ``path--time diagram''.
In order to get maximal points, the running time of your program should be within a few minutes on a modern PC even for larger data sets. The task can be solved in 64 kB of memory, and the above time limit also refers to such solutions, so we do not recommend using temporary files in any cases.
The source code of your program (s44.pas, s44.cpp, ...) and a short documentation (s44.txt, s44.pdf, ...) should be submitted, also describing your solution and specifying the name of the developer environment to use for compiling, further, the possible parameters of your program.
Clarification: In case the tram comes to a halt at a crossing, it is considered "passing through" that respective crossing momentarily so long as it stands still (including the moment it stopped and will start).
Upload your solutions above