Hope you enjoyed our contest! The editorial is below:
Author: porkchops
We can use distance formula to calculate the distance from each point in the map to your current location. We return the point with minimum distance. If there are multiple points at the same minimum distance, keep the point with the smallest x-coordinate, and if there is still a tie, keep the point with the smallest y-coordinate (as stated in the problem description).
Author: B-1168
The specific mixtures of 0, 1, and 2s are not as significant as the length of contiguous blocks of 0s and 1s (those "contiguous blocks" can have length 0, when between consecutive instances of 2). For example, we can parse the $$$1201012200120012$$$ sample into 0-1 blocks of lengths [1, 4, 0, 3, 3, 0]. Then, use a "sliding window" to get the greatest $$$k+1$$$ consecutive values from the list, and add $$$k$$$ to calculate the final answer.
Author: isaac18b
This problem can be solved with a prefix sum and a binary search. First, turn the input array of students in buildings to a prefix sum array, such that index $$$i$$$ stores the number of all students in or to the left of building $$$i$$$. Then, for each number Freddy is curious about, conduct a binary search on the prefix sum array. There are a few edge cases to be aware of, like the case where Freddy's number is greater than the total number of students and the case where the number is 0.
Author: GhOsT16790
We only have two cases for the problem. We will either flip all the lanterns to 0, or 1. Therefore, we can try to compute the cost for both methods, and then take the minimum of that at the end. Essentially, we are just counting the number of consecutive segments of 0 and 1, which is the minimum number of moves needed to make all the lanterns either 0 or 1 respectively.
Authors: mwen, DylanSmith
First let's observe that only at most $$$k$$$ of each candy may be eaten (which would happen in the case that Charlie eats one such candy every day), so we can set each $$$k_i$$$ to $$$\min(k_i, d)$$$. Now, if we ignore the "all candy eaten each day must be unique" constraint, the optimal solution would be to greedily eat the tastiest $$$d \cdot x$$$ candies. Notice that we can actually achieve this by choosing a candy to eat on day $$$1, 2, ... d$$$, repeating $$$x$$$ times. If we choose candies in this order, then we know that if two chosen candies are less than a distance of $$$d$$$ from each other, then they must be eaten on different days. Since there are (now) at most $$$d$$$ candies that share a common tastiness, the maximum distance between any two is $$$d - 1$$$, so we know that the "uniqueness" condition is satisfied. Thus a simple solution is to simply choose the $$$d \cdot x$$$ tastiest candies after doing the initial reduction.
Author: Daveeed
Assuming the ghosts move optimally, we realize that Harry can only guarantee that he can exit if Harry can get to the exit faster than every ghost. That is, an exit is good if the shortest path from it to Harry is shorter than the shortest path from any ghost to the exit.
To find the shortest path from each exit to Harry, we can run a BFS starting at Harry. To find the shortest path from an exit to any ghost, we can run a multi-source BFS from all the ghosts. Then, we simply loop over exits and count the ones that are closer to Harry than a ghost.
Author: ericpenguin
When two students meet, we can assume nothing happens, because we can say they swapped identities (and stayed moving in the same direction) rather than swapping directions. For each query, our answer increases by 1 for each student that must move in a specific direction, but becomes -1 if a student will have exited in either direction. We can store prefix and suffix sums of students at each position and store the minimum $$$t$$$ for which some student will exit no matter what.
Author: zekigurbuz
This problem boils down to running a breadth-first search (BFS) with extra state, specifically which candy corns we have picked up and how many we haven't yet used to pass through jack-o'-lanterns. One straightforward approach is to assign a power of two to each of the candy corns (since there can only be a few of them) and then store a bitmask as part of the BFS state (to keep track of the set of distinct candy corns that have been visited). Then, if the BFS encounters a jack-o'-lantern, it may decrement its candy corn counter (aborting if it is negative), and if it instead encounters a candy corn, it may increment its counter only if the candy corn has not yet been visited. Otherwise, the problem is a simple BFS.
Author: tn757
Let's consider the structure of this problem. There will be some left and right bound of the array that Alice has explored, and a direction that she is heading in. Then the state can be defined in terms of $$$l, r, dir$$$. Let's use Dijkstra's Algorithm to find the earliest moment that Alice can have explored $$$[l, r]$$$ and be facing $$$dir$$$. We can push $$$[d, l, r, dir]$$$ into a priority queue, and push the two choices of continuing in the same direction, or turning to the other direction. If we continue right, we push $$$[d+1, l, r+1, dir]$$$. If we turn left, we push $$$[d+r-l+1, l-1, r+1, dir]$$$, and vice versa. If $$$d$$$ is ever $$$>=$$$ the house that we are at, then we just pop from the queue. By Dijkstra's algorithm, the first time we explore the segment $$$[0, n-1]$$$ will have the minimum amount of time taken to reach it. If we never explore it, then it is impossible.
Authors: bridgeminion, fishy15
This problem looks like a range queries problem, so an approach like segment tree seems to be the right approach. We just need to figure out what state we store in the segtree and how to merge states together. Instead of just storing the number of ways to make $$$5 \bmod 13$$$, we can store the number of ways to make all possible remainders $$$\bmod 13$$$. For an interval of size 1 with element $$$v$$$ inside we can either keep the element in the product or not keep it. This means that we can make a product of 1 or a product of $$$v$$$ using this single element.
To merge two different states together, we can take the number of ways to make $$$i \bmod 13$$$ on one side and the number of ways to make $$$j \bmod 13$$$ on the other side and add it to the number of ways to make $$$ij \bmod 13$$$. We can easily verify that this operation is associative, so we can implement a segment tree using it. To answer type 2 queries, we just need to query the range and output the number of combinations for $$$5 \bmod 13$$$.