2017 Problems and Solutions

Programming Contest Rules & Questions

The 2017 Hawkeye Challenge Programming Competition will be held Saturday, April 29th, on the University of Iowa campus in Iowa City. Participating teams in two divisions will program solutions to problems on the computers in the Computer Science Labs. The first three teams of each division will be recognized during an awards ceremony following the competition. Any changes, additions, or clarifications to these rules will be announced during the orientation meeting preceding the competition.

Materials

During the competition, team members may use written materials (e.g., textbooks) of any kind. Pencils and scratch paper will be provided. Calculators are permitted. Teams may not bring any storage devices. No Internet use beyond the website of HackerRank is allowed.

Computers

Each team will be assigned one computer to use during the competition. Instructions on computer usage will be given during the orientation meeting preceding the competition. Tables at the back of the room will be available for work away from the computer.

Student Monitors

Student monitors from UI will be available to assist team members. The monitors will answer questions concerning computer usage and competition procedures but will not answer any questions regarding logic, language syntax, or problem interpretation except for anything relating to HackerRank. Questions are to be posted on HackerRank so that everyone can see the answer. Student monitor will also be checking Internet useage. Internet is not allowed except for HackerRank.

Problems

When the competition begins, each team will be given 5 computer problems to solve. Team members may work on these problems in any order and in any manner they choose. There will be 3 hours to work on these solutions.

HackerRank

HackerRank will be used to host the competition. The competition on HackerRank is hosted by the ACM and the questions are also created by the University of Iowa ACM Chapter. HackRank will be the way to submit code and it will automatically judge the problems. Feel free to check out the example competition: www.hackerrank.com/hcpc17-example-competition. During the competition, each team can use their own IDE or program to practice, but the code must work and be submitted in HackerRank. HackerRank supports almost any language.

Testing

Each team may run their program using their own test data files as many times as they wish, there is an option to do this within HackerRank, or teams can try this on their own. We urge you to use the sample provided with each problem statement, but do not assume that because your program works with the sample data that it will work with the actual competition test data. More test cases will be released as "hints" to the problem as the competition goes on if necessary. This will help verify your code; however, test your programs very carefully before submitting them for judging.

Questions

Once the competition begins, all direct or indirect interaction between the teams and judges will be limited to written communication through HackerRank. This includes requests for clarification of problems as well as any other question about a specific problem. These questions, and their answers, will be available under each question in teh Discussions section so that everyone will know the question and answer.

Submitting Code

Submitting code consists of the team entering the code and pressing Submit Code. This will run the code on the sample data and other hidden test cases. Teams may submit as many times as they wish; however, each incorrect judged run adds 10 minutes of time to the eventual problem completion time (see Standings section for more info).

Time of Execution

When the competition judges are executing a program using the official competition data, a solution will be judged to be incorrect if it does not execute in less than 1 minute.

Judging

After submitting code to HackerRank, it will return how many tests are correct or incorrect. HackerRank will tell the teams the errors in their code.

Standings

Teams will be ranked per the number of problems they complete correctly. For example, a team that completes 5 problems correctly will finish ahead of a team that completes 4 problems correctly. There is no penalty for problems that are not solved. In the event of a tie, the teams that tied will be ranked per the total accumulated time taken by each team. All standings will be available on HackerRank's Leaderboard for the competition. Furthermore, 10 minutes per incorrect submission of a problem are added to the total time for that problem.

HackerRank Failure

In the case of failure of HackerRank, the 2016 HCPC Rules will be in effect. Check those out here: https://acm.org.uiowa.edu/article/hcpc-rules

Prizes

First, second, and third places will be awarded to the teams of each division. A complete list of rankings will be posted on the ACM Hawkeye Challenge website.

Division I Questions:

Contest URL:

www.hackerrank.com/hcpc17-div1

Image Compression

A form of image compression goes row by row and checks if any pixels are repeat colors. For example, a picture of a blue sky, sun, and cloud the pixels without compression could look like this:

BBBBBBBBBBBBBBBBSSSSSSSSBBBBBBBBBBBBBBBBBBBBBB

BBBBBBBBBBBBBBBBBBBBBBBBBBBWWWWWWWWWBBBBBBBBBB

With compression the image would be encoded as:

16B8S22B

27B9W10B

Given an image encoding without compression with size n x m, give the compressed image encoding like the example above.

Input Format

BBBBBBBBBBBBBBBBSSSSSSSSBBBBBBBBBBBBBBBBBBBBBB

BBBBBBBBBBBBBBBBBBBBBBBBBBBWWWWWWWWWBBBBBBBBBB

Constraints

The first row of the input is the number of row. The second row is the number of columns (pixles). Each pixel is encoded by a single upper case letter.

Output Format

16B8S22B

27B9W10B

Sample Input 0

BBBBBBBBBBBBBBBBSSSSSSSSBBBBBBBBBBBBBBBBBBBBBB

BBBBBBBBBBBBBBBBBBBBBBBBBBBWWWWWWWWWBBBBBBBBBB

Sample Output 0

16B8S22B

27B9W10B

Explanation 0

There are 16 Bs in the first row, then 8 Ss then 22 Bs There are 27 Bs in the second row, then 9 Ws then 10 Bs

Solution:

#!/bin/python3

import sys

# Write Your Code Here

n = int(input().strip())

m = int(input().strip())

colors = []

text = ""

shift = 0

for i in range(n):

colors.append([])

text = text + str(input().strip())

row = 0

for i in range(len(text)):

row = int(i)//int(m)

if i % m == 0:

shift = 0

colors[row].append(1)

colors[row].append(text[i])

elif i%m > 0:

if text[i] == text[i-1]:

colors[row][shift] +=1

if text[i] != text[i-1]:

shift +=2

colors[row].append(1)

colors[row].append(text[i])

for i in colors:

for j in i:

print(j,end = "")

print("")

TwoSum

Write a program that takes a list of line separated numbers and returns true if the list contains at least one pair of different elements that add up to 0 and returns false otherwise.

Input Format

5 -1 2 1 4 5

Constraints

The first number is the amount of lines that are in the list. The numbers are line separated.

Output Format

true

Sample Input 0

-1

-2

Sample Output 0

false

Explanation 0

No two numbers add up to 0

Sample Input 1

-1

Sample Output 1

true

Explanation 1

-1 + 1 = 0

import java.io.*;

import java.util.*;

import java.text.*;

import java.math.*;

import java.util.regex.*;

public class Solution {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int lines = in.nextInt();

int[] numbers = new int[lines];

for (int i = 0; i < lines; i++) {

numbers[i] = in.nextInt();

}

boolean works = false;

int sum = 111;

for (int i = 0; i < numbers.length; i++) {

for (int j = 0; j < numbers.length; j++) {

if (j <= i || works == true) continue;

sum = numbers[i] + numbers[j];

if (sum == 0) {

System.out.print("true");

works = true;

}

continue;

}

if (works == false) System.out.print("false");

}

Rock Paper Scissors

Today we have a tournament of Rock Paper Scissors! Given an input of players and their random list of options return the result of the tournament following the rules of RPS below. Assume each round the player uses the next option that isn’t used in their list. If there is a tie, then both players move on to their next option. You will not return ties in your tournament results.

Scissors cuts Paper

Paper covers Rock

Rock crushes Scissors

Key: Rock: R, Scissors: S, Paper: P

Input Format

1,R,P,S,R,P,S,R,P,S

2,S,R,S,P,R,S,P,P,S

3,R,S,P,S,S,S,R,P,R

4,R,S,R,R,R,R,S,R,R

5,R,R,R,R,R,R,R,R,R

6,S,S,S,S,S,S,S,S,S

7,P,S,P,S,P,S,P,S,P

8,R,S,P,S,R,P,S,R,P

Constraints

The first line tells you how many players there are in this tournament.

Each line in the output represents a round in the tournament and we want to see every round and the move that the player used for that round. Assume that there are enough players to make an even tournament like below.

To build your bracket, you are to pair up 2 players in numerical order, i.e. 1 and 2, 3 and 4 etc.

Each player is represented by an integer and each game option is represented by a single uppercase letter.

The goal is to end up with one winner, and also show what move he would use in that last round.

Each player has enough options to win.

Output Format

(1R,2S),(3P,4R),(5R,6S),(7P,8R)

(1P,3S),(5R,7S)

(3S,5R)

(5R)

Sample Input 0

1,R,P,S,R,P,S,R,P,S

2,S,R,S,P,R,S,P,P,S

3,R,S,P,S,S,S,R,P,R

4,R,S,R,R,R,R,S,R,R

5,R,R,R,R,R,R,R,R,R

6,S,S,S,S,S,S,S,S,S

7,P,S,P,S,P,S,P,S,P

8,R,S,P,S,R,P,S,R,P

Sample Output 0

(1R,2S),(3P,4R),(5R,6S),(7P,8R)

(1P,3S),(5R,7S)

(3S,5R)

(5R)

Explanation 0

1 beats 2 3 and 4 tie 2 times and then play paper and rock 5 beats 6 7 beat 8

3 beat 1 5 beat 7

5 beat 3

5 wins and played rock again for the last round

import java.io.*;

import java.util.*;

import java.text.*;

import java.math.*;

import java.util.regex.*;

public class Solution {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int n = in.nextInt();

ArrayList<String[]> players = new ArrayList<>();

int[] moves = new int[n];

for(int a0 = 0; a0 < n; a0++){

String playerLine = in.next();

players.add(playerLine.split(","));

}

String winner = "";

String out = "";

for (int i = 0; players.size() > 1; i += 2) {

if (i >= players.size()) {

i = 0;

System.out.println(out.substring(0, out.length() - 1));

out = "";

}

String firstMove = players.get(i)[moves[Integer.parseInt(players.get(i)[0])-1]+1];

String secondMove = players.get(i+1)[moves[Integer.parseInt(players.get(i+1)[0])-1]+1];

while (firstMove.equals(secondMove)) {

moves[Integer.parseInt(players.get(i)[0])-1]++;

moves[Integer.parseInt(players.get(i+1)[0])-1]++;

firstMove = players.get(i)[moves[Integer.parseInt(players.get(i)[0])-1]+1];

secondMove = players.get(i+1)[moves[Integer.parseInt(players.get(i+1)[0])-1]+1];

}

out += "(" + players.get(i)[0] + firstMove + ","

+ players.get(i+1)[0] + secondMove + "),";

if (!firstMove.equals(secondMove)) {

moves[Integer.parseInt(players.get(i)[0])-1]++;

moves[Integer.parseInt(players.get(i+1)[0])-1]++;

if (winner(firstMove, secondMove)) {

players.remove(i+1);

winner = firstMove;

} else {

players.remove(i);

winner = secondMove;

}

i--;

}

System.out.println(out.substring(0, out.length() - 1));

// String move = players.get(0)[moves[Integer.parseInt(players.get(0)[0])-1]+1];

System.out.println("(" + players.get(0)[0] + winner + ")");

}

private static boolean winner(String a, String b) {

if (a.equals("S")) return b.equals("P");

if (a.equals("R")) return b.equals("S");

if (a.equals("P")) return b.equals("R");

return true;

}

Block Caesar Cipher

Block Caesar Cipher: You have a secret message that you need to send to your friend via a public domain. Both you and your friend are big on cryptography and you decide to use a form block Caesar Cipher to encrypt your secret message! Given a string without spaces, you are to encrypt the message as follows.

The block Caesar Cipher: You are to take a message, without spaces and break it up into 4 letter chunks. The first block is encrypted by shifting each letter 3 places. Look at the example below:

First Block Example:

Plaintext (Original text): abcd

Encrypted Text: defg

Knowing that each letter can be encoded as a number, in this case, a = 0, b = 1, c = 2 ...etc. You are to add up the sum of the encrypted letters and then shift the next block with the sum of the previous encrypted block. Note, that if your shifting numbers surpass 25, you must cycle back to the beginning e.g. “26 = a” again.

Final Example:

Plaintext: iowahawkeyes

Encrypted Text: lrzdleaohbhv

Input Format

iowahawkeyes

Constraints

All letters will be lowercase and the first shift if always 3. Assume there won't be any spaces in the input.

Output Format

lrzdleaohbhv

Sample Input 0

iowahawkeyes

Sample Output 0

lrzdleaohbhv

import java.io.*;

import java.util.*;

import java.text.*;

import java.math.*;

import java.util.regex.*;

public class Solution {

String[] alphabet = {"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"};

public static void main(String[] args) {

Solution app = new Solution();

}

public Solution() {

Scanner inp = new Scanner(System.in);

String in = inp.next();

int chunknum = in.length()/4;

int rem = in.length() % 4;

if(rem > 0)

chunknum++;

int index = 0;

String[] result = new String[chunknum];

for(int i=0; i<chunknum; i++) {

String chunk = "";

if(i == chunknum-1)

chunk = in.substring(index);

else

chunk = in.substring(index, index + 4);

result[i] = chunk;

index += 4;

if(index >= in.length()) {

index = in.length() -1;

}

String output = "";

int shiftBy = 3;

for(int i=0; i<result.length; i++) {

output += shift(result[i], shiftBy);

shiftBy = value(shift(result[i], shiftBy));

}

System.out.println(output);

}

private String shift(String shiftee, int shiftBy){

String output = "";

String letter = "";

int len = shiftee.length();

for(int i=0; i<len; i++) {

letter = shiftee.substring(i, i+1);

int index = findIndex(letter);

int temp = (index + shiftBy)% 26;

String newLetter = alphabet[temp];

output += newLetter;

}

return output;

}

private int findIndex(String letter) {

for(int i = 0 ; i < alphabet.length; i++) {

if(letter.equals(alphabet[i])) {

return i;

}

return 0;

}

private int value(String s) {

int length = s.length();

int accum = 0;

for(int i=0; i<length; i++){

String letter = s.substring(i, i+1);

accum += findIndex(letter);

}

return accum;

}

IowaBus API

At Iowa, we take the bus all the time. The Cambus is all over the place! At Stop 0001, the Downtown Interchange, there can be multiple buses sitting at the stop all at once (which is very confusing for a new bus rider).

The Cambus system has an new, and made up, API called IowaBusAPI. From the API we can get a response back with the predicted bus times, this is the input to the problem. Given the response of this API, in the format described below, return a list of bus predictions that contains the buses that are sitting at Stop 0001 at the busiest time of day (find when there are the most busses at the stop and return those buses). Assume that in order to have multiple buses at the stop at the same time, their prediction times should be within 3 minutes of each other. The input and output of your code is shown below.

Input Format

Constraints

The input will be a single line containing a bus name, a colon, a prediction integer in minutes, and a '|' representing the next prediction. Assume there will be no spaces between the colon and the number and the number and the '|'. However, the bus route name might have a space, like "Hawkeye Interdorm".

Return the output in the same format as the input.

You can assume there won't be a tie, there is always a chunk of time where more busses will be at the stop than the rest.

Assume that the bus prediction error is inclusive 3 minutes

Output Format

Pentacrest:5|Interdorm:6|Hawkeye Interdorm:6|10th Street:7

Sample Input 0

Sample Output 0

Pentacrest:5|Interdorm:6|Hawkeye Interdorm:6|10th Street:7

Explanation 0

Pentacrest is in 5 min, Interdorm is in 6, Hawkeye Interdorm is in 6, and 10th is in 7min. All of these are within 3 min of each other and it is the when there will be the most busses sitting at the stop.

import java.io.*;

import java.util.*;

import java.text.*;

import java.math.*;

import java.util.regex.*;

public class Solution {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

String n = in.nextLine();

String[] split = n.split("\\|");

int max = 0;

String maxStr = "";

for (int i = 0; i < split.length; i++) {

String a = split[i];

String temp = a + "|";

int c = 1;

int time = time(a);

for (int j = i+1; j < split.length && Math.abs(time(split[j]) - time) <= 3; j++) {

temp += split[j] + "|";

c++;

}

if (c > max) {

max = c;

maxStr = temp.substring(0, temp.length() - 1);

}

System.out.print(maxStr);

}

private static int time(String a) {

return Integer.parseInt(a.split("\\:")[1]);

}

Programming Contest Rules & Questions

Materials

Computers

Student Monitors

Problems

HackerRank

Testing

Questions

Submitting Code

Time of Execution

When the competition judges are executing a program using the official competition data, a solution will be judged to be incorrect if it does not execute in less than 1 minute.

Judging

After submitting code to HackerRank, it will return how many tests are correct or incorrect. HackerRank will tell the teams the errors in their code.

Standings

HackerRank Failure

In the case of failure of HackerRank, the 2016 HCPC Rules will be in effect. Check those out here: https://acm.org.uiowa.edu/article/hcpc-rules

Prizes

First, second, and third places will be awarded to the teams of each division. A complete list of rankings will be posted on the ACM Hawkeye Challenge website.

Division II Questions

Contest URL:

www.hackerrank.com/hcpc17-div2

Tallest Ladder

On a nice sunny day you are playing disc golf. Unfortunately, you aren't that good and you got your disc stuck in a tree! Luckily, there is a warehouse that has a lot of ladders nearby. Going to the warehouse you notice that the all the ladders are different sizes! Just to be safe you want to find the tallest ladder possible. Given a line separated list of ladder heights, find the maximum ladder height to get your disc out of the tree and return the height of that ladder.

Input Format

5 1 5 2 6 7

Constraints

The first line tells you how many numbers are in the list. The numbers are line separated and are all integers and they are greater than 0.

Output Format

Sample Input 0

Sample Output 0

Explanation 0

7 is the greatest number in the list

Caesar Cipher

You and your friend have a secret message to send to each other. Knowing that you are both big on cryptography, you want to use a Caesar Cipher to encrypt a message. Given a string without spaces, the test answers, encrypt the message. Caesar Cipher: Every letter is advanced three letters to encrypt the message.

Example:

Plaintext (Original text): abcde

Encrypted Text: defgh

Input Format

abcde

Constraints

The string will have no spaces and if the shift surpasses z, it will shift back to the beginning. Assume the string has no spaces and is all lowercase letters.

Output Format

defgh

Sample Input 0

abcd

Sample Output 0

defg

Explanation 0

a -> b -> c -> d

b -> c -> d -> e

c -> d -> e -> f

d -> e -> f -> g

Rock Paper Scissors

Rock Paper Scissors: Given the rules of the game Rock Paper Scissors, and two choices, return which option won! Each option is encoded by a single character.

Rules:

Scissors cuts Paper

Paper covers Rock

Rock crushes Scissors

If it is a tie, return "Tie"

Encoding: Rock: R, Scissors: S, Paper: P

Input Format

S R

Constraints

There will only be 2 letters separated by a line. Encoding: Rock: R, Scissors: S, Paper: P

Output Format

Sample Input 0

Sample Output 0

Image Compression

A form of image compression goes row by row and checks if any pixels are repeat colors. For example, a picture of a blue sky with sun, the pixels without compression would be encoded as:

BBBBBBBBBBBBBBBBYYYYYYYYBBBBBBBBBBBBBBBBBBBBBB

With compression, the image would be encoded as:

16B8Y22B

Given a row of an image, compress the row with the described encoding.

Input Format

BBBBBBBBBBBBBBBBYYYYYYYYBBBBBBBBBBBBBBBBBBBBBB

Constraints

The type of color will be represented by a single letter

Output Format

16B8Y22B

Sample Input 0

BBBBBBBBBBBBBBBBSSSSSSSSBBBBBBBBBBBBBBBBBBBBBB

Sample Output 0

16B8S22B

Explanation 0

First there are 16 Bs Then there are 8 Ss Then there are 22 Bs

TwoSum

Write a program that takes a list of line separated numbers and returns true if the list contains at least one pair of different elements that add up to 0 and returns false otherwise.

Input Format

5 -1 2 1 4 5

Constraints

The first number is the amount of lines that are in the list. The numbers are line separated.

Output Format

true

Sample Input 0

-1

-2

Sample Output 0

false

Explanation 0

No 2 numbers add up to 0

Sample Input 1

-1

Sample Output 1

true

Explanation 1

-1 + 1 = 0

Association for Computing Machinery

University of Iowa Student Chapter

Main Menu