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.

# Unique Products (2021 Optimization 1)

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.

### Input Format

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.

### Output Format

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.

### Scoring

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.

### Sample Input

2 7

### Sample Output

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.

### Tasks

1. $N = 2, M = 400$
2. $N = 2, M = 4,000$
3. $N = 2, M = 40,000$
4. $N = 3, M = 4,000$
5. $N = 4, M = 1,000$
6. $N = 8, M = 200$

# Circle Covers (2021 Optimization 2)

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.

### Input Format

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 Format

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.

### Scoring

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

### Sample Input

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

### Sample Output

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.

### Tasks

1. $N \le 100, M = 10$
2. $N \le 100, M = 20$
3. $N \le 11,000, M = 20$
4. $N \le 11,000, M = 100$
5. $N \le 210,000, M = 60$
6. $N \le 210,000, M = 15$

# Robot Recovery (2021 Optimization 3)

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.

### Input Format

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$ Rs, and exactly one E. Each robot can reach the entrance from their starting position, and no robot will start at the entrance.

### Output Format

Print a string consisting of the characters U, D, L, R, corresponding to the sequence of commands Carnegie the Mellon should use.

### Scoring

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

### Sample Input

3 4 2
..XE
XXRR
....

### Sample Output

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.

### Tasks

1. $N = 1, 1 \le R,C \le 100$
2. $N = 3, 1 \le R,C \le 100$
3. $1 \le N \le 200, 1 \le R,C \le 200$
4. $1 \le N \le 200, 1 \le R,C \le 200$
5. $1 \le N \le 200, 1 \le R,C \le 1000$
6. $1 \le N \le 200, 1 \le R,C \le 1000$

# Bet (2021 AI 1)

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.

### Input Format

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

### Output Format

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.

### Sample Input

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

### Sample Output

14

### Scoring

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.

# Trap the Scotty Dog (2021 AI 2)

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.

### Input Format

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)$

### Output Format

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.

### Scoring

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.

# Spaceships (2021 AI 3)

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.

### Input Format

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

### Output Format

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.

### Sample Input

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

### Sample Output

[-1, 2]

### Scoring

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)