jeffreyxiao
Hi! I'm a student at the University of Waterloo studying software engineering. I have an interest in large scale distributed algorithms and infrastructure for data analytics. I also enjoy working with low level systems.

ECOO Round 1 Analysis

Friday, April 8, 2016

ProgrammingCompetition

Introduction

The first round of the provincial ECOO competition happened on Wednesday. You can access the problems here.

Problem 1: Pass or Fail

This problem simply asks whether the weighted average of a student's test, assignment, project, and quiz scores are above or equal to 50%.

A student passes the course if the following inequality holds true:

WT×T+WA×A+WP×P+WQ×Q>=50%W_T \times T + W_A \times A + W_P \times P + W_Q \times Q >= 50\%

Time complexity: O(N)O(N)

Problem 2: Spindie

Solution 1

First notice that the number of integers on the spinner is very large (1<=N<=50001 <= N <= 5000), but the actual range of values each integer can take on is very small (1<=Si<=1001 <= S_i <= 100). Additionally, the number of occurrences of each value does not matter. Thus we can have three loops that iterate through all possible values and check the following four cases to see if a value is possible:

1. (A×B)×C2. (A+B)×C3. (A×B)+C4. (A+B)+C\begin{aligned} &1.\ (A \times B) \times C \\ &2.\ (A + B) \times C \\ &3.\ (A \times B) + C \\ &4.\ (A + B) + C \\ \end{aligned}

Time complexity: O(S3)O(S^3)

Solution 2

Generate pairs of spinner values and store it in a map. Then work backwards from the target values and check if it exists in the map.

Time complexity: O(N2+TN)O(N^2 + TN)

Problem 3: Railway Sort

Make the observation that any value XX cannot be moved until X+1X + 1 is before X+2X + 2 in order to have the minimal amount of movements. Then iterate starting from NN and only move value XX if it occurs after X+1X + 1.

Time complexity: O(N2)O(N^2), or O(N)O(N) if you are smart about the implementation.

Problem 4: Kayenne

Store the houses in a set to check if your current position is already occupied by a house. Then you can just brute force and check all possible values that is in the radius. My team checked all XX and YY where Cx50<=X<=Cx+50C_x - 50 <= X <= C_x + 50 and Cy50<=Y<=Cy+50C_y - 50 <= Y <= C_y + 50. Then we checked if point (X,Y)(X, Y) was in the radius or on a house. Finally, we inserted all the houses in a priority queue and determined if it was democratic or republican.

Introduction
Problem 1: Pass or Fail
Problem 2: Spindie
Solution 1
Solution 2
Problem 3: Railway Sort
Problem 4: Kayenne
Previous Post
CCOQR 2016 Analysis
Next Post
Personal Website Redesign