Selected Problems - 1st-11nth Year of the CSP

Content

Problems were selected & translated by Mgr. Richard Nemec

  1. Union of Rectangles.
  2. Minimum Absolute Sum.
  3. Strange Permutations.
  4. Contiguos Draw.
  5. Ratios.
  6. Sequence.
  7. Chessboard.
  8. Soldiers.
  9. Labyrinths.
  10. Coding.
  11. Deleting.
  12. Bla-Bla-Bla.
  13. The Digit Powers Problem.
  14. The Parentheses Problem.
  15. Common Element Example.
  16. Fraction Example.
  17. Sum Example.
  18. Average Problem.
  19. Weighing Example.
  20. Fractions (Farey's Series).
  21. Sharp-eyed Points and a Fatty Line.
  22. Array Rotation.
  23. Floor Covering.
  24. Symmetric Numbers.
  25. Army on Move.
  26. Sequence.
  27. Convex Hull.

Union of Rectangles.

A rectangle in a plane having its sides parallel to the coordinate axis, is determined by the coordinates of then leftdown and righttop vertex.

Write a program for computing the area of the union of a given sequence of rectangles A_1,A_2,...,A_N.

Example:

A_1 is given by [1;1],[4;3]
A_2 is given by [0;1],[6;2]
A_3 is given by [2;1],[3;3]
A_4 is given by [7;7],[9;9]

The area of the union is 13.

Minimum Absolute Sum.

Consider a two-dimensional NxN array P containing positive numbers. Write a program for finding a sequence of neighbour elements starting by P[1,1] and finished by P[N,N] such that the sum of absolute values of the differences of the neighbour elements of the chosen sequence is minimal.

Two neighbour elements are those having a common "side" (e.g. P[2,3] and P[2,4], but not P[2,2], P[3,3]).


Strange Permutations.

Let M be a nonempty set of natural numbers containing m pairwise different elements.

Write a program for creating such a permutation of the set M that for no two elements of the permutation their arithmetic mean is situated "inbetween" them.

Example:

M={1,2,3,4,5,6}
One possible output: {1,5,6,3,2,4}

Remark: The element "inbetween" two elements needn't be a neighbour of any of them.


Contiguous Draw.

You may now that any contiguous picture compound of lines can be drawn by a single closed draw (i.e. the draw starts and is finished in the same point) if and only if each crossing point of lines there are an even number of lines coming together. The crossing points will be called vertices, the lines will be called edges.

Write a program that will first read then number N of vertices, some pairs of vertices (i,j), being connected by an edge. Then it will write a sequence of vertices determining how to draw a given picture by a single draw. If the given picture cannot be drawn by a single closed draw then the program has to find it out and announce it. (Be careful, it is case if the picture is not contiguous, as well).


Ratios.

Two positive natural numbers M,N are given.

  1. Find the integer part of the ratio M/N, the shortest periodical part (and its length) and the initial pre-periodical part (and its length) of the fraction part of M/N.
  2. Solve the problem of 1) if the following limitation is required: The program can use 10 simple integer variables only, no arrays or structured data can be used.

Example:

In: M=7, N=12
Out: integer part (0), period (3) of length 1,
     pre-period (58) of length 2
     
In: M=125, N=198
Out: integer part (0), period (31) of length 2,
     pre-period (6) of length 1

Sequence.

For a given sequence of natural numbers greater then 2 consider the following operation: take the leading (i.e. the first) element of the sequence, jump over as many elements as the value of the element, and insert it to the obtained position.

Write a program which will determine, for a given element of the sequence, the number of steps necessary for the element to became the leading element the sequence.

Example:

1st step 3 4 5 6 7 8 9 10 ...
2nd step 4 5 6 3 7 8 9 10 ...
3rd step 5 6 3 7 4 8 9 10 ...
4th step 6 3 7 4 8 5 9 10 ...
     
Input: 6

Output: the element 6 becomes leading in the 4th step.

Chessboard.

Assume a chessboard of the size n x n, n being a power of two n=2^m, m -- integer). One field given by its coordinates [x,y] is cut out from the chessboard.

Write a program for cutting the remaining part of the chessboard to L-shaped triminoes (pieces consisting of three chessboard fields each, having the shape of the letter "L").

Think about all the values m and [x,y] such that the problem yields a solution, prove your assumption.

Example:

Input: n=8 (m=3) [x,y]=[1,4]
Output: the solution (drawing)

Soldiers.

There are N soldiers standing a row (i.e. side by side). If they obtain a special command ( ..aoeiu..T FACE !!!), all of them will turn by 90 degrees randomly --- some of them to the left, the others to the right. After 1 second those of them standing face to face to some other soldier will turn by 180 degrees. The same happens after the next second, etc.

Write a program modelling for a given N this action until all the soldiers stop turning. Can you find out (and give your reasons) what is the longest possible duration of this action for a given N ?


Labyrinths.

Write a program which will, for given M and N, fill an MxN array with values 0 and 1 to obtain "the most sophisticated" labyrinth you have ever seen. The labyrinth will be depicted in a graphical way (e.g. on a printer using asterisks), and the entry to the labyrinth and the position of a treasure (or a kidnapped princess) will be given. Write down all your ideas on the "perfect" labyrinth, they will be evaluated. According to the rules, 1 denotes a wall and 0 a free space.

Remark: The result is not specified precisely, it's based on your imagination and fantasy. The main point in this exercise is to design a solution being as close as possible to the intuitive idea of a labyrinth.


Coding.

The Space Research Centre workers are interested in finding highly efficient ways of the transmission of messages by radio. This is their last project for shortening the average length of the message text:
  1. For each symbol in some simple message text its frequency in the text is determined (i.e. the ratio of the number of the occurrences of the text to the total number of symbols).
  2. The symbols used are coded by finite sequences of 0's and 1's, then more frequented symbols having shorter codes.
  3. The coded messages have to be decodable, hence the authors have decided that a code of a symbol mustn't be a prefix (initial part) of a code of any other symbol.
  4. Any messages have to be encoded and decoded using the created code table.

Remark: For the sample text with 8 different symbols BACADAEAFABBAAAGAH the frequencies are as follows:

       A - 9/18   B - 3/18   C - 1/18	D - 1/18
       E - 1/18   F - 1/18   G - 1/18	H - 1/18
If a fixed-length code for symbols is used (at least 3 bits in this case) the satisfying 1)--3) of the project is:
       A -> 0	  B -> 100   C -> 1010	D -> 1011
       E -> 1100  F -> 1101  G -> 1110	H 0> 1111
Using the above code we get 42 bits (symbols 0 or 1)
       100010100101101100011010100100000111001111
Supposing the transmitted messages here similar frequencies of occurrences of symbols, about 20% of bits (and consequently of transmission time) can be saved.

Observe that the code

       A -> 0	  B -> 100   C -> 1001	D -> 1011
       E -> 1100  F -> 1101  G -> 1110	H 0> 1111
doesn't fulfil the requirements of the project as the codes for 1) and 2) don't fulfil 3).

Task: Create a program which for a given sample message builds a frequency table of the symbols used, assigns to them codes fulfilling 2),3),4) and then encodes or decodes some further text.


Deleting.

Let i is a natural number and P an infinite sequence of natural numbers. The operation Delete(i,P) is defined as follows:

The first i elements are left in the sequence, the next i elements are deleted, the next i elements are left, the next i elements deleted, etc.

The result of the operation is again an infinite sequence (not containing the deleted elements). Now we can define a sequence Q of natural numbers being the results of the following process on infinite sequences:

......... .........

This process is an infinite one. Nevertheless, one can determine the first K elements of Q for an arbitrary K after a finite number of steps.

Write a program, for generating the first K elements of the sequence Q, for a given K.

Remark: The result for K=5 is 1,3,9,25,57. A program will be considered to be very good if it is able to generate in reasonable time the first 15 elements of Q.


Bla-Bla-Bla

The Centre for Space Research (SRC) has launched a sonde to an unknown around its position and then to transmit to the Centre the most interesting facts. Since the distance of the planet from the Earth is quite long, different disturbances can change the massage. That's why the sound repeats the message all the way round.

The workers in the Centre here one task only: to obtain from the received (disturbed) text the most probable message. A message is most probable, if when written cyclically bellow the received text, the number of differences in vertical pairs of symbols is minimal.

  1. Help the Centre and write down a program which for a given text and a number K>0 will write all the most probable messages of length K (The length of the text needn't be a multiple of K.)
  2. Find out which interesting thing was discovered by sonde of the planet if the following text was received:
        BLABOLQIALVBPTPVGYWXRKBTAWZXNTCZIAWQFLGBDNPZYKIAWEFHIONIIEYHNSAXH
    EKSEHVWQDEQDYZDYMABFDYIBCVKCNGTRNBDKZPZCSBHICIZIUNFIUGCKMCFKFQIGUNAEP
    IRUKYVSEIIFUBCXFMIUHCBTSBVNGBMDNYDVCORXMDNIGHZPRREGCEQRILDMPBPOBOIXFU
    TEHQNDTDNMNLKEYLSHYZKAFADIAYTAUNVVZEGYQMQXJXVVUTODVKNQCQXCPACAJYVUINK
    ASNGKTDOVJUDTTISPMYAZXIBBHLLWLEJPGNGXDDXEGOXQOENKHKCAAUJRQYXONFPAPRFJ
    QNVLCHRIMOVGGZANYUMDAFXEHQLNXVNNGBVBENICHZQGQNBNKQRNNDNERRCGBSHXZLTGM
    CIHAXFEJXUGFADNGUXVWPYLROEVTFKCWPWGCAVVCPDSOUOKMSMDFHDOHTMYKSPIKDOUNI
    YZTLECVANUHLCNIERUVNQIRGIOHFRLCLUORICNICGHYJAMNMMUXCJCENUVARWOMRNDYNW
    PDNAZECWINYXCMMFKGRTSTBTFHISXANBRYOSYNMQHGYBNJZVEKDEUOVDBWZSGOILRPKWD
    PNQCNIRQUSNIRSKQIOKGTWLAUKHKCMFYYYVIALKALBAYEZAJZUJBWFESQQRACEUEGPWAB
    BEMXPPHNFGKMZHRHKCWFTQNAONUMNTINLRRSLUIVURCQZFEPVHNKNRTUBRHCNWZWNHMAI
    GVRNJZWUNRBIWCZENOGWDOQUFIINPSGDLPAMPETWTSEHICQASRPLMUEPWUDKEBMIAMZPZ
    ZNDHQIMFYPJIFZSBYEMFSMCBEMHNYCSQCMTLRPWVHKHCQEBQMCMOHWWYJBAAIRZTRSEBQ
    NHHKGFCRHCVBWKJBJFVEECETFIEWGIBYNUYROXRDHDRNESIIBVTSDJKLWRCITCLWMISVQ
    KCCWJFQZPUTREVKIFSDRDENCNSJAHQCRXWBIINRIFUTNASWBMNVAMGBUCMNDPNCYWBRPE
    DLCCTABRIPAAKYXDKIQNTJKXZRZDMKBZCYMXXRMVXFIXRSTTVTQQNZBONFKVCLTANHGGC
    KQOLTSHWSJIWLSNUWISYRJJNAMGWVICZIXBIRNLARBIMDYJWUYYCMGJHMMZQKHHDZCGOO
    QRDPOEAIRAWGFKCVHONZHNTITOXBWNYFDYJXHZISDWPEDCHIBGSKLFAUIELPHNJKYDINP
    XYDAIVARCPAAJBEHHWIZOROJTAICMICNDHYXLJDXATEQFCENFRWONHLKUDRTVP
    

Linguistic remark: The word "NIC" means "NOTHING" in Slovak, but "SEMINAR" is the shortened name of this competition.


The Digit Powers Problem.

Take a natural number, carve it up in digits and calculate the sum of their squares.

You obtain a new number, with which you will repeat the same procedure. After the finite repetition of this procedure we will obtain the numbers 1 or 4.

E.g.: If we start with the number 324

Task: Find out the numbers from the interval [1,1000] which, after the application of the presented procedure, will give the result 1.


The parentheses problem.

Every schoolchild knows what correctly parenthesized arithmetical expression are. These are only those which contain to each left parenthesis '(' an correctly parenthesized expression but the expressions ()), )(), (((, ... are not correctly parenthesized.

More precisely:

  1. () is a correctly parenthesized expression.
  2. If the expression X is correctly parenthesized then (X) is a correctly parenthesized expression, too.
  3. If X,Y are the correctly parenthesized expressions then XY is the correctly parenthesized expression.

Task: You dispose of N pairs of the parentheses '(' and ')'. Compose and write out all correctly parenthesized expressions (length 2.N parentheses). E.g.: if N=2 then write up (()), ()().

Remark: Mind the effectiveness of your algorithm.


Common Element Example.

Given is a matrix P of integers with M rows and N columns, each of the rows is sorted in ascending order.

Write a program that finds and reports all the numbers that occur in each row. The program should also report if there is no such number.

Example: for M=4, N=5 and following matrix P:

		     2	 3   5	 7   9
		     4	 6   9	11  13
		     1	 3   7	 8  10
		     3	 3   4	 8   9
Correct answer is "9" because this number occurs in each of the rows.

Fraction Example.

Write a program that, for given real X and E, calculates two relatively prime integer numbers A and B such that |X-A/B|<=E, i.e. we can use fraction A/B instead of real X with precision E.

Print out input values X,E and results, i.e. A and B, respectively.

Example:

  X = 2.718  E=0.01  (*   INPUT   *)
  A = 19     B = 7   (*   OUTPUT  *)

Test your program using input values X=3.1415926 and E=0.001, E=0.0001 respectively.


Sum Example.

Given is a sequence of N integer (both negative and positive) numbers.

Write a program that extracts a subsequence (of length <=N ) of consecutive elements with the maximum possible sum.

Note: Try your best to find the fastest algorithm. The problem is more difficult than one might think at first glance.


Average Problem.

Given is a real number P and a sequence of N (N>0) real numbers. Find the longest subsequence of consecutive elements such that the average of the subsequence is greater or equal to the given P.

Write a program that reads positive integer number N , real number P and a sequence of N real numbers. Program should print the first and last indexes of the required subsequence. The program should also report if there is no such subsequence.

Note: "Average of the sequence" equals the sum of the sequence's elements divided by the number of the elements.


Weighing Example.

Given are N weights of 1kg, 3kgs, 9kgs, ... 3^{N-1} kgs respectively, pair of scales and an object that is to be weighed. The weight of the object is an integer number within range 1..3^{N-1} . Write a program that, for any given object of weight W (within the required range), determines how to distribute the weights in order to achieve balance.

Example: Let's take four weights of 1kg, 3kgs, 9kgs and 27kgs respectively and an object of 5kgs. Obviously, the only solution is the following:

Place weights of 1kg and 3kg on the side of the scales with the object and place weight of 9kg on the other side.

Design the output of the program in the way shown above. Input for your program are two integer numbers: N (N>0) , the number of weights, and H (0<=H<=3^{N-1}) , the weight of the object.

Note: For given N and H (within required range), there is only one correct solution.


Fractions (Farey's Series).

Write a program for outputting for a given N the ascending sequence of all reduced fractions from [0,1] having the denominator not greater than N .

A fraction is reduced if its numerator and denominator are relative primes.

Example: For N=7 the output is:
1/7 , 1/6 , 1/5 , 1/4 , 2/7 , 1/3 , 2/5 , 3/7 , 1/2 , 4/7 , 3/5 , 2/3 , 5/7 , 3/4 , 4/5 , 5/6 , 6/7 , 1/1


Sharp-eyed Points and a Fatty Line.

Assume N sharp-eyed points (given by coordinates) and a fatty line (given by coordinates of its final points).

Write a program which first reads the value N>0 , N pairs of coordinates [x_i,y_i] of the sharp-eyed points and coordinates of the final points [a_x,a_y] , [b_x,b_y] of the fatty line, then it will output the number of pairs of points that cannot see each other because of the fatty line (there is a crossly point of the line connecting the two points with the fatty line).

Don't use any goniometric functions as sin, cos, tan, arctan...


Array Rotation.

Assume an array X of N elements. Write a program which for a given integer K , 1 < K < N , shifts the array cyclically to the right. For a positive value of K this means that the value of X[1] will be shifted to X[K+1] , X[2] to X[K+2] , etc. X[1] will take the original value from X[N-K-1] , X[K] from X[N] .

Example: If N=8 , K=3 and the original array was [ 1 2 3 4 5 6 7 8 ] then the new values after the rotation will be [ 6 7 8 1 2 3 4 5 ]

For K=0 all the values will remain in their positions.

For a negative value of K the values will be shifted cyclically in the opposite direction.


Floor Covering.

The plane is divided to squares of equal size. On this plane the floor of a room is drown containing exactly same number of squares. This floor has to be covered by bricks consisting of two squares each.

Write a program which reads the description of the room floor, and outputs the covering of the floor by bricks or -- a special message, if it is not possible.

The following description of the room floor is recommended: Find a rectangle fully containing the room floor, give the size of the rectangle and then a corresponding matrix containing for each square 0 or 1 depending on whether the square belongs to the room floor or not.

The output has to be a matrix containing in each position a natural number: 0 -- of the square doesn't belong to the room, i (i >= 2) , -- if the square is covered by the brick No (i -1).


Symmetric Numbers.

Write a program for listing for a given k all the odd numbers less then 2^k , having the binary notation symmetric according to its centre.

Example 1: The binary notation of 93 (=1011101_2) is Symmetric, the notation of 67 (=1000011_2) is not.

Example 2: For k=4 the output is '3,5,7,9,15'

Remark: Try to make your program as fast as possible.


Army on Move.

An army unit has to move to some new position. During the move all the soldiers will form a queue. According to the army rules each soldier has always to keep his subordinees in sight. Hence all his subordinees have to move in front of him.

Task: The army unit consist of N soldiers numbered by numbers 1,2,... N . There are given K pairs [commander_i, subordinees_i] (i=1,2,...,K) . Write a program for ordering the soldiers to a queue such that the above rule is fulfilled. If it is not possible the program has to find it out and report it.

Example

N=6, K=5,  commander:  1 4 2 1 2
	   subordinee: 5 5 3 3 4

Output:    1 2 4 6 3 5	   or	 6 2 1 4 5 3.

Remark: One solution is sufficient.


Sequence.

Write a program that for given natural nu