Magic Square – IEEXtreme 8.0

Problem

Johnny designed a magic square (square of numbers with the same sum for all rows, columns and diagonals i.e. both the main diagonal – meaning the diagonal that leads from the top-left corner towards bottom-right corner – and the antidiagonal – meaning the diagonal that leads from top-right corner towards bottom-left corner). Write a program to test it.

Task
Write a program that will check if the given square is magic (i.e. has the same sum for all rows, columns and diagonals).

Continue reading “Magic Square – IEEXtreme 8.0”

Sum It Up – IEEXtreme 8.0

Problem

Minka is very smart kid who recently started learning computer programming.
His coach gave him a cyclic array A having N numbers, and he has to perform Q operations on this array.
In each operation the coach would provide him with a number X. After each operation, every element of the cyclic array would be replaced by the sum of itself and the element lying X positions behind it in the cyclic array. All these replacements take place simultaneously.
For example, if the cyclic array was [a, b, c, d], then after the operation with X = 1, the new array would be [a+d, b+a, c+b, d+c].
He needs to output the sum of the elements of the final array modulus 10^9+7.
He made a program for it but it’s not very efficient. You know he is a beginner, so he wants you to make an efficient program for this task because he doesn’t want to disappoint his coach.

Continue reading “Sum It Up – IEEXtreme 8.0”

Back to Square 1 – IEEEXtreme 8.0

The game “Back to Square 1” is played on a board that has n squares in a row and n-1 probabilities. Players take turns playing. On their first turn, a player advances to square 1.After the first turn, if a player is on square i , the player advances to square i + 1 with probability p(i) , and returns to square 1 with probability 1-p(i) .The player is finished upon reaching square n .

Task


Write a program that determines the expected number of turns needed for a player to reach the final square.For example, consider the board below with n = 3 and p(1) = 0.5 and p(2) = 0.25. A player moves to square 1 on their first turn. With probability p(1) , they move to square 2 on their second turn, but with probability 1- p(1) , they remain on square 1. If they were lucky and made it to square 2 on their second turn, they advance to square 3 on their third turn with probability p(2) , but they would go back to square 1 with probability 1- p(2) . Thus, a really lucky player could finish is 3 turns. However, on average, it would take 13 turns for a player to make it to square 3.

IMAGE 1

Continue reading “Back to Square 1 – IEEEXtreme 8.0”

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”

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”