Block Art – IEEEXtreme 9.0

Problem Statement

The NeoCubist artistic movement has a very distinctive approach to art. It starts with a rectangle which is divided into a number of squares. Then multiple rounds of layering and scraping occur. In a layering round, a rectangular region of this canvas is selected and a layer of cubes, 1 cube deep, is added to the region. In a scraping round, a rectangular region of the canvas is selected, and a layer of cubes, again 1 cube deep, is removed.

The famous artist I.M. Blockhead seeks your help during the creation of this artwork. As he is creating his art, he is curious to know how many blocks are in different regions of the canvas.

Your task is to write a program that tracks the creation of a work of Pseudo-Cubist art, and answers I.M.’s periodic queries about the number of blocks that are on the canvas. Consider, for example, the following artwork created on a canvas with 5 rows and 15 columns or squares. The canvas starts without any blocks, like in the figure below. We label cells in the canvas based on the tuple (row,column), with the upper left corner being designated (1,1). The numbers in each cell represent the height of the blocks in that cell.

Continue reading “Block Art – IEEEXtreme 9.0”

Advertisements

Digit Fun! – IEEEXtreme 9.0

Problem Statement

Recurrence relations are an important tool for the computer scientist. Many algorithms, particularly those that use divide and conquer, have time complexities best modeled by recurrence relations. A recurrence relation allows us to recursively define a sequence of values by defining the nth value in terms of certain of its predecessors.

Many natural functions, such as factorials and the Fibonacci sequence, can easily be expressed as recurrences. The function of interest for this problem is described below.

Let |An| denote the number of digits in the decimal representation of An. Given any numberA0, we define a sequence using the following recurrence:

Ai = |Ai-1| for i > 0

The goal of this problem is to determine the smallest positive i such that Ai = Ai-1.

Continue reading “Digit Fun! – IEEEXtreme 9.0”