Programming Contest Problems
1.Design and implement an algorithm that fills a table n x m in the following way:
A[0][0] to a[0][m-1] = 1
A[n-1][0] to a[n-1][m-1] = 1
A[0][0] to a[n-1][0] = 1
A[0][m-1] to a[n-1][m-1] = 1
A[1][1] to a[1][m-2] = 2 (if the row exists and is not filled with 1)
A[n-2][1] to a[n-2][m-2] = 2 (if the row exists and is not filled with 1)
A[1][1] to a[n-2][1] = 2 (if the column exists and is not filled with 1)
A[1][m-2] to a[n-2][m-2] = 2 (if the column exists and is not filled with 1)
Etc
Example:
5 x 7 6 x 77 x 74 x 3
1 1 1 1 1 1 11 1 1 1 1 1 11 1 1 1 1 1 11 1 1
1 2 2 2 2 2 11 2 2 2 2 2 11 2 2 2 2 2 11 2 1
1 2 3 3 3 2 11 2 3 3 3 2 11 2 3 3 3 2 11 2 1
1 2 2 2 2 2 11 2 3 3 3 2 11 2 3 4 3 2 11 11
1 1 1 1 1 11 1 2 2 2 2 2 11 2 3 3 3 2 1
1 1 1 1 1 11 1 2 2 2 2 2 1
1 1 1 1 1 1 1
2.Door in a wall. You are facing a wall that stretches infinitely in both directions. There is a door in the wall, but you know neither how far away nor in which direction. You can see the door only when you are right next to it. Design an algorithm that enables you to reach the door by walking at most O(n) steps where n is the (unknown to you) number of steps between your initial position and the door. Implement the algorithm
3.Let A[1::n] be a strictly sorted vector of integers. Find any k such that A[k] = k in O(log n) time. For example:
4.Let A[1::n][1::n] be a two-dimensional array of real numbers that is sortedboth row-wise (A[x][y] < A[x][y + 1] for all x and y) and column-wise(A[x][y] < A[x + 1][y] for all x and y). How can you find a given numberk in this array in O(n log n) time? How can you do it in O(n) time? Forexample (k = 5):
5.Given a vector A[1::n] of integers find in O(n) time two indices i and j such that A[i] _ A[j] is the greatest possible. Then, solve a more difficultversion of this problem, in which i > j. For example, this is the formerversion
and this is the latter one
5 / 7 / 9 / 4 / 2 / 6 / 3 / 8 / 3 / 1 / 4j i
6.Let A[1::n] be a vector of real numbers. Explain how to implement afunction Sum(i; j) that computes the sum A[i] + A[i + 1] + ….. + A[j] inconstant time. Assume that you can do some preprocessing of A, i.e.,before the first invocation of Sum, you can create an auxiliary vector Band use it inside Sum.
7.Let A[1::n] be a vector of integers (some of them may be negative). Findi and j such that the value of A[i] + A[i + 1] + …. + A[j] is the greatestpossible. Can you do it in O(n3) time? In O(n2) time? In O(n) time?
8.Let A be an array of N integers not necessarily sorted. An element x of A is said to be a majority element if the number of elements of A that are equal to X is at least (n+1)/2. Design and implement an algorithm that determines whether A has a majority element or not, and outputs such an element when A does have a majority element. The worst-case running time of your algorithm must be O(n).
9.You are given a vector A[1::n] of natural numbers. Design an O(n) algorithmthat would compute another vector B[1::n] such that for everyi > 1, B[i] is the biggest number smaller than i for which A[B[i]] > A[i].We assume that A[1] is the biggest element in A so B always exists. Forthe following vector A
the correct vector B is
10.Let A[1::n] be a vector of natural numbers such that 1 A[i] m for everyi. Find the length k of the longest sequence of indices i1 < i2… < iksuch that A[i1] > A[i2] > … > A[ik]. We call it a descending sequence.
An example is shown below.
11.A department has n research students. Consider one day, in which the i-thstudent starts working at time A[i][1] and stops working at time A[i][2].Determine the greatest number of students that are working simultaneously.
In the example below, the answer is 7.
12.Let A[1::n][1::n] be a two-dimensional array of 0's and 1's. Find the greatest
rectangle, which contains only 0's. In other words, find x1, y1, x2,y2, with A[x][y] = 0 for all x1 x < x2 and y1 y < y2, such that(x2 - x1)(y2 - y1) is maximum. Can you do it in O(n6) time? In O(n4)time? In O(n3) time? In O(n2) time? For example:
13.Let c1, c2, . . . , ck be natural numbers such that 1 ci n for each i that represents denominations of coins (in pence). You have an infinitenumber of coins of each of the denominations. For each k : 0 k n find the smallest number of coins A[k] using which you can pay exactly kpence. For example, when c1 = 1, c2 = 4, c3 = 6, c4 = 9 you the answer is
Note that even if we are interested only in A[15] we have to compute thewhole vector. Augment the algorithm such that you should be able to findout which coins you have to use to obtain a particular sum (e.g., to findout that 15 = c3 + c4).
14.Let modify the previous question by assuming that we have only one coinof each denomination. Show how to compute an array A[0::k][0::n] suchthat paying j pounds using only coins c1, . . . , ci requires using A[i][j]coins. For the same example as in the previous exercise we get:
Again note that if we are interested only in calculating the value of A[4][15](i.e., the smallest numbers of coins necessary to obtain 15, assuming thatwe can use all 4 coins), we have to compute the whole array. However, anoptimization is possible, because we do not need to have access to eachrow of the array at the same time. Show how to compute the last rowusing only two vectors: B[0::n] and C[0::n]. Then, show how to do thesame with only one such a vector available.
15.Design an algorithm to find all natural numbers that can be expressed asthe sum of two cubes in two essentially different ways. In other words, find all k's for which there exist four different natural numbers a, b, c, d,all smaller than n, such that k = a3 + b3 = c3 + d3. For example:
13 + 123 = 1729 = 93 + 103:
Can you do this in O(n4)? In O(n3)? In O(n2 log n)?
16.You have a machine that can cut a rectangle into two smaller rectanglesalong the line that is parallel to one of the sides. There is a furtherrestriction: the lengths of all sides of all the rectangles involved (both theoriginal one and the two smaller ones) are natural numbers. You can usethis machine as many times as you want. Given two natural numbers: nand m, determine the smallest number of cuts necessary to cut a single rectangle n _m into squares. For example, if n = 6 and m = 5, you need4 cuts:
17.A combination lock with master combination consists of ndials, each of which can be set in one of k positions. Each lock can be opened in (at least) two ways: setting each dial to the correct setting of the individual combination (different for each lock) or setting each dial to the correct setting of the master combination (the same for each lock). For example, suppose there are 3 dials, each with 10 positions (0 through 9), five locks with the following individual combinations:
lock A: 9,5,8
lock B: 6,5,7
lock C: 5,9,3
lock D: 4,8,6
lock E: 3,9,2
and all also open with the master combination 8,4,5. Now suppose there is a “flaw” in the lock design, so that a given lock will open if each individual dial is set either to the individual combination setting or to the master combination setting e.g., lock D will open on setting 4,4,5. Describe how, given one lock and only the individual combination to that lock, one can rapidly determine (in O(nk) time rather than O(nk/2)time) the master combination, and hence the way to open any lock.
18.There are n bacteria and 1 virus in a Petri dish. Within the first minute, the virus kills one bacterium and produces another copy of itself, and all of the remaining bacteria reproduce, making 2 viruses and 2*(n-1) bacteria.
In the second minute, each of the viruses kills a bacterium and produces a new copy of itself (resulting in 4 viruses and 2*(2*(n-1) -2) = 4*n – 8 bacteria; again, the remaining bacteria reproduces. This process continues every minute. Will the viruses eventually kill all the bacteria?
19.Given a list of positive integers, and another integer representing a goal, find a subset of the list of integers with a sum as close as possible to the goal.
20.You are given 8 x 8 table of natural numbers. In any step you can either double each of the numbers in any one row, or subtract 1 from each of the numbers in any one column. Devise an algorithm that transforms the original table into a table of all zeros. What is the running time of your algorithm?
21.A very large department has a mix of 100 professors: some are honest and hard-working, while others are deceitful and do not like students. The honest professors always tell the truth, but the deceitful ones sometimes tell the truth and sometimes lie. You can ask any professor the following question about any other professor: “Professor Y, is professor X honest?” Professor Y will answer either with “yes” or “no”. Design an algorithm that, with no more than 198 questions, would allow you to figure out which of the 100 professors are honest. It is known that there are more honest than dishonest professors
1