Programming Contest Sample Problems

These are the 6 problems from the 2021 CMIMC Programming Contest. Starter code and input files for the optimization round can be found here. AI Round starter code can be found here.

Given natural numbers $N$ and $M$, you must construct $N$ sets $$A_1, A_2, A_3, \dots, A_N \subseteq \{1, 2, 3, \dots, M\}$$ such that all possible products $a_1\, a_2\, a_3 \cdots a_N$ are distinct, where $a_i \in A_i$ for all $i$.

The sets $A_1, A_2, \dots, A_N$ must have equal size, and do not need to be distinct.

The first line of each input file contains two integers: $N$, the total number of subsets, and $M$, the maximum allowed value in any subset.

You will output $N$ lines. On the $i^\text{th}$ line, output $k$ space-separated positive integers denoting the values in $A_i$. All integers should be in the interval $[1, M]$, and $k$ (the size of each set $A_i$) should be the same for each line.

Your score on each task will be the value of $k$ you achieved, i.e. the size of each of your subsets. Your goal is to maximize this value.

`2 7`

```
1 2 3 4
1 5 6 7
```

Since all $16$ products $1\cdot 1, 1\cdot 5, 1\cdot 6, 1\cdot 7, 2\cdot 1, 2 \cdot 5, \dots, 4 \cdot 7$ are distinct, and all numbers are between $1$ and $7$, these sets are valid. The common size of each set is $4$, so this sample output gets $4$ points.

- $N = 2, M = 400$
- $N = 2, M = 4,000$
- $N = 2, M = 40,000$
- $N = 3, M = 4,000$
- $N = 4, M = 1,000$
- $N = 8, M = 200$

Aliens, aka CMIMC Programming Organizers, are trying to abduct the contestants of CMIMC Programming! As you are all socially distancing, from the point of view of the aliens, you are just points in a plane. To abduct the contestants, the aliens will drop crop circles of varying radii on groups of you.

Given $N$ points on a 2D plane, and $M$ lengths denoting the radii of circles, your goal is to place these $M$ circles on the plane in a way that maximizes the number of points covered by some circle.

The first line contains a single integer $N$, denoting the number of points.

$N$ lines of input follow, each containing a space-separated pair of integers `x y`

denoting the coordinates of each point.

The next line contains a single integer $M$, denoting the number of circles.

$M$ lines of input follow, each containing a single positive integer denoting the radius of each circle.

Output $M$ lines, each containing a pair of floats `x y`

denoting the center of the indexed circles. The $i^\text{th}$ line of your output should correspond to the $i^\text{th}$ circle of the input.

Your score is the number of points covered by the $M$ circles. Your goal is to maximize this value.

```
6
0 1
4 4
2 2
6 4
1 0
3 3
2
1
2
```

```
5.0 4.0
1.6 1.6
```

This sample output gets a score of $6$ points, since the two circles centered at $(5.0, 4.0)$ and $(1.6, 1.6)$ will cover all $6$ points.

- $N \le 100, M = 10$
- $N \le 100, M = 20$
- $N \le 11,000, M = 20$
- $N \le 11,000, M = 100$
- $N \le 210,000, M = 60$
- $N \le 210,000, M = 15$

As another side project besides CMIMC, Carnegie the Mellon was able to build a robot army of $N$ robots, for his plan of world domination. Unfortunately on his way to CMIMC he lost them in a rectangular maze of $R$ by $C$ cells. The maze consists of cells that are either walls or empty rooms, and has one entrance. The robots quickly spread themselves out, occupying $N$ distinct rooms.

Carnegie the Mellon is afraid of mazes and waits anxiously at the entrance, hoping for his robot’s safety. Luckily, Carnegie the Mellon has built a remote to control his robot army, but it only has $4$ buttons, `U`

, `D`

, `L`

, `R`

. These buttons command all $N$ robots to move one cell up, down, left, or right, respectively. The robots have advanced pathing, so if the direction would cause a robot to hit a wall, it chooses to stay in place. Two or more robots may occupy the same cell simultaneously.

Carnegie the Mellon would like to move all $N$ robots to the maze's entrance, so he can regroup with them. Once a robot reaches the entrance, Carnegie the Mellon can deactivate it, so it no longer listens to the remote’s command. Find the shortest sequence of commands so that all $N$ robots reach the entrance of the maze.

The first line contains $3$ integers: $R$, $C$, and $N$.

The next $R$ lines contain a string of $C$ characters. The characters will either be `.`

, `X`

, `R`

, or `E`

, which correspond to an empty room, a wall, a room with a robot in it, and the entrance.

There are guaranteed to be exactly $N$ `R`

s, and exactly one `E`

. Each robot can reach the entrance from their starting position, and no robot will start at the entrance.

Print a string consisting of the characters `U`

, `D`

, `L`

, `R`

, corresponding to the sequence of commands Carnegie the Mellon should use.

Your score is the number of commands used to move all robots to the entrance. Your goal is to minimize this value.

```
3 4 2
..XE
XXRR
....
```

`RU`

After the `R`

command, both robots will occupy the cell directly below the entrance. The next `U`

command moves both robots to the entrance. This output gets a score of $2$, because $2$ commands were used.

- $N = 1, 1 \le R,C \le 100$
- $N = 3, 1 \le R,C \le 100$
- $1 \le N \le 200, 1 \le R,C \le 200$
- $1 \le N \le 200, 1 \le R,C \le 200$
- $1 \le N \le 200, 1 \le R,C \le 1000$
- $1 \le N \le 200, 1 \le R,C \le 1000$

This is a 3-player game. Initially, each of the 3 players holds 13 bidding cards worth 2 through 14 (i.e. a suit of cards with ace-high). There is also a face-down pile that contains 13 shuffled cards with point values from 2 to 14.

On each turn, one card from the face-down pile is revealed. All three players simultaneously bid on the revealed card by using one of their remaining bidding cards. If there is a unique highest bidder, that player receives points equal to the value of the card. If there is a tie for first, no player receives points. This repeats 13 times until all cards are used.

You must define the function `bet_bot.move(hand, others, card, scores)`

in the starter file, where:

`hand`

is your current hand (a list of integers from 2 to 14)`others`

is a list of the 2 other players' hands (the players appear in a fixed order)`card`

is the card currently being bet on (an integer from 2 to 14)`scores`

is a list of current scores for all 3 players in a fixed order. Your score is displayed as the first value, and the scores of the 2 other players appear in the same order as in`others`

The function `bet_bot.move`

should return an integer from 2 to 14, representing the value of a card in your hand.

Invalid outputs will result in your lowest card being played by default.

Your program is allotted 1 second of total runtime during a game, and 32 MB of memory. If you exceed those limits, the default move above will be used instead.

```
hand = [2, 4, 14]
others = [[6, 8, 9], [5, 11, 13]]
card = 9
scores = [34, 21, 18]
```

`14`

In each game, you will receive $5$ points for coming 1st, $2$ points for 2nd, and $1$ point for 3rd. If there are ties, all tied players will be treated as having the lower scoring rank, i.e. if 1st and 2nd tie, both will be treated as 2nd. Additionally, $1\%$ of the numerical sum of the cards you won during the game will be added to your score. For example, if you came 1st in a game with a total of $49$ points won from bids, you would receive $5.49$ points for that game.

In each match, your bot will play against the same 2 opponents for a total of 5 games, and your match score will be the average over these 5 games. You are allowed (and encouraged) to store any information you want about previous games in the match.

This is a 2-player asymmetric game. The two players are Scotty and the Trapper.

Initially, Scotty is at the center cell of a $15 \times 15$ grid, called the game board. On each turn, the Trapper can place a barrier on any empty cell of the board, then Scotty can either move to one of the 8 cells adjacent to it's current cell (like a chess king), or stay in it's current cell. Scotty's goal is to move off the edge of the board, while the Trapper's goal is to stop this from happenning.

The game ends when Scotty moves off the board (and Scotty wins), or Scotty is unable to make any legal move besides staying still (and the Trapper wins). If no player has won after 200 moves, the game is considered a draw.

To help out the Trapper, some cells will start with barriers. In particular, the board will be randomly initialized with barriers in 20-40% of its cells. It is guaranteed that the center cell never contains a barrier, and Scotty will always have a path to escape.

You must define the functions `scotty_bot.move(board)`

and `trapper_bot.move(board)`

in the starter file, where `board`

is a $15 \times 15$ 2D array of integers.

`board[y][x]`

represents the cell at coordinates $(x,y)$, **not** $(y,x)$. It has 4 possible values:

`board[y][x] = 0`

if the cell $(x,y)$ is empty`board[y][x] = 1`

if Scotty is currently at $(x,y)$`board[y][x] = 2`

if there is a naturally generated barrier at $(x,y)$`board[y][x] = 3`

if the Trapper placed a barrier at $(x,y)$

**Scotty**

The function `scotty_bot.move`

should return a list of integers`[dx, dy]`

, designating the direction for Scotty to move in. Your output must satisfy $$-1 \le dx, dy \le 1$$ and one of

- $\max(x+dx, y+dy) \ge 15$ (moving off the board)
- $\min(x+dx, y+dy) \le 0$ (moving off the board)
`board[y+dy][x+dx]`

$< 2$ (moving to an empty cell or staying still)

where $(x,y)$ is Scotty's current position. Any invalid output will result in Scotty staying still as the default move.

**Trapper**

The function `trapper_bot.move`

should return a list of integers `[x, y]`

, designating the location of a new barrier to construct. Your output must satisfy $$0 \le x, y \le 14,$$ and $(x,y)$ must be an empty cell, i.e. `board[y][x] = 0`

.

Any invalid output will result in no barrier being placed by default.

Your program is allotted 1 second of total runtime during a game, and 32 MB of memory. If you exceed those limits, the default move above will be used instead.

In each game, the winner receives $1$ point and the loser receives $0$ points. In the case of a draw, both players receive $0.5$ points.

This is an $n$-player game. Each player controls a spaceship that starts at some integer coordinates $(x,y)$. On each turn, all spaceships move simultaneously to a new position. Spaceships move in the same L-shaped pattern of a chess knight, so there are 8 possible moves to choose from.

If two or more spaceships move to the same position at the same turn, they will crash. This is bad for all spaceships involved, and should be avoided at all costs. Additionally, the sun occupies a $5 \times 5$ square of cells centered at $(0,0)$, and any spaceships moving into this region will also crash.

Each player is given a direction to move their spaceship: either clockwise or counterclockwise. The goal is to make the maximum number of orbits around the sun, in the given direction.

The starting positions $(x,y)$ are such that $x + y \pmod 2$ is the same for all players. Moreover, $(x,y)$ is chosen to be a distance of approximately $n$ away from the sun, i.e. $x^2 + y^2 \approx n^2$, where $n$ is the number of players.

The game will last for $500$ turns, but any crashed spaceships will immediately stop moving.

You must define the function `spaceship_bot.move(ship, others)`

in the starter file, where:

`ship`

is a list of 4 numbers`[x, y, status, score]`

, such that- $(x,y)$ are the current integer coordinates of your spaceships
`status`

is 1 if you should move counterclockwise, -1 if you should move clockwise, and 0 if you have crashed`score`

is the number of times your spaceship has orbited around the origin (represented as a float, not an integer)

`others`

is a list of all other players' ships, in a fixed order. Each ship is given in the same format as your ship, i.e. a list of 4 numbers

The function `spaceship_bot.move`

should return a list of two integers `[dx, dy]`

, satisfying $dx^2 + dy^2 = 5$. Your spaceship will move to the square $(x+dx, y+dy)$.

Invalid outputs result in your spaceship moving in the same direction as your previous move by default (or a randomly chosen move, if this occurs on the first turn when there is no previous move to use).

Your program is allotted 5 seconds of total runtime during a game, and 32 MB of memory. If you exceed those limits, the default move above will be used instead.

```
ship = [3, 5, -1, 1.1]
others = [[4, 4, 1, -1.3], [4, 6, 0, 0.1], [4, 6, 0, -0.3]]
```

`[-1, 2]`

At the end of the game, your score will be calculated as your winding number - the total number of times your spaceship has orbited around the origin. If you are going in the wrong direction (e.g. moving counterclockwise when you are supposed to move clockwise), your score will be 0 (despite the starter file's local tester showing a negative winding number)