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.

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

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:

$W_T \times T + W_A \times A + W_P \times P + W_Q \times Q >= 50\%$Time complexity: $O(N)$

First notice that the number of integers on the spinner is very large ($1 <= N <= 5000$), but the actual range of values each integer can take on is very small ($1 <= 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:

$\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(S^3)$

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(N^2 + TN)$

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

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

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 $X$ and $Y$ where $C_x - 50 <= X <= C_x + 50$ and $C_y - 50 <= Y <= C_y + 50$. Then we checked if point $(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.

Previous Post

CCOQR 2016 Analysis

Next Post

Personal Website Redesign