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:
First notice that the number of integers on the spinner is very large (), but the actual range of values each integer can take on is very small (). 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:
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.
Make the observation that any value cannot be moved until is before in order to have the minimal amount of movements. Then iterate starting from and only move value if it occurs after .
Time complexity: , or 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 and where and . Then we checked if point 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.