UW-Madison ICPC Team Tryout Contest: Solutions

Here we would like to share our solutions to the '18 Fall Tryout Contest problems. The problem set is entirely designed and implemented by Ziyi^[1]. Jinman^[2] helped redesigning problem A, D and F. Congratulations to the top contestants: Bud^[3], Bryan^[4], Aditya^[5], Zeyuan^[6], Yuhan^[7] and Vibhor^[8]! And many thanks to them for providing their killing solutions!

Contents Summary

Problem	Solutions
A. Alpine Path	@bryan: DP, DAG @vibhor: [solution key]
B. Balanced Number	@zeyuan: brute force @yuhan: binary search
C. Champion and Candies	@zeyuan: 0/1 rucksack, dp @yuhan: knapsack, dp
D. Donuts for free!	@aditya: [solution key] @bud: implementation, data structures
E. E-mail Distribution	@bryan: ad-hoc, simulation @vibhor: [solution key]
F. Forbidden Spell	@jinman: case-by-case, greedy @aditya: [solution key] @bud: dynamic programming

A. Alpine Path

@bryan: dp, dag

We can use a weighted graph to model this problem, with the vertices being the joints, the edges being the trails, and the weights being the lengths of the trails.

A key observation is that we are actually working with a directed graph (despite the fact that trails are bidirectional), because the path we are looking for must be descending, meaning we can only move from a joint with greater height to a joint with smaller height. For example, suppose there is a trail from joint 1 to joint 2, and joint 1 has height 100 while joint 2 has height 10. Then in our graph, we will have a directed edge from joint 1 to joint 2, but no edge from joint 2 to joint 1.

Taking this further, we realize that the directed graph is in fact acyclic, because a path starting at a vertex $v$ and ending at $v$ would imply that the joint represented by $v$ has lower height than itself, which is impossible.

So formally, the problem is to find the longest path in a weighted DAG (directed acyclic graph), where the length of a path is the sum of the weights of each edge in the path.

We can use dynamic programming to solve this problem. Specifically, let $dp$ be an int array where $dp[u]$ is the length of the longest path starting at vertex $u$ . We can compute $dp[u]$ by looking at all the neighbors of $u$ (here a vertex $v$ is a neighbor of $u$ if there is an edge from $u$ to $v$ ). As an example, suppose $u$ has 3 neighbors: $v_1, v_2, v_3.$ Let $w_1$ denote the weight of the edge from $u$ to $v_1,$ and similarly for $w_2$ and $w_3.$ Then $dp[u]$ is the maximum of the values $w_1 + dp[v_1], w_2 + dp[v_2], w_3 + dp[v_3].$ We find $dp[v_1], dp[v_2], dp[v_3]$ recursively.

The base cases for our recursion is the vertices with no neighbors (i.e. out-degree is 0) - the longest path starting at these vertices have 0 length. Because we are using memorization, the recursive method is fast and runs in $\theta(V + E)$ time.

Some implementation details: I represented the DAG with adjacecy lists. I have heard (but not personally verified) that using an adjacency matrix will cause too much memory to be used. Furthermore, I think using an adjacency matrix will cause the time complexity of our recursive method to become $\theta(V^2)$ .

Due to the nature of the input (we first get the trails, then we get the heights of each joint), I first maintained an edge list. After storing all the heights into an array, I built the adjancency lists from my edge list.

As for the recursive method: I first set up the $dp$ array and initialized it to all -1s (a sentinel value). Then I looped through the array, and if $dp[i] = -1$ , I called the recursive method to compute $dp[i].$ Finally, the answer was the maximum value in $dp$ .

Note that this DP solution is top-down. At the time of the competition, I wasn’t able to find a bottom-up DP solution. I believe a bottom-up solution can be done by sorting the vertices in reverse topological order, which can be done using depth-first search in $\theta(V + E)$ time. Specifically, a valid reverse topological order is the order by which DFS finishes visiting the vertices (post order). After sorting the vertices, we can compute $dp[u]$ in the same way as before, only now we are guaranteed that if there is an edge from $u$ to $v,$ $dp[v]$ has already been computed by the time we get to $u$ .

@vibhor: …

B. Balanced Number

@jinman: behind the scene
We set the input size so that a $O(n^2)$ would not pass due to time limit constraint.

@zeyuan: brute force

To solve this problem, we may simply calculate the balance value for each of the digits as the pivot.
To do this, we need to calculate two arrays, pre[] and suf[] for each of the positions, containing the prefix and suffix sum to that digit (inclusive). The balance value of the first position, 0, equals suf[1] + suf[2] + ... + suf[len - 1] while len equals the length of the number (if we take the right side as positive). Then for position i, the balance value when selecting it as the pivot, bal[i] = bal[i - 1] - suf[i] - pre[i - 1]. The answer is the absolute value of the minimum of bal[] array.

@yuhan: Binary Search

As the difference between the torques is monotonic as the pivot moves, we could use binary search to search the optimal pivot and boost our algorithm:

1. Start with search area from $0$ to $n-1$ , and set $pivot$ of $x[n/2]$ ,
1. Calculate the torques.
- if the left side has larger torque, we set the lower boundary of the search area to $pivot$ .
- If the right side has larger torque, we set the right boundary of the search area to $pivot$ .
- If two torques equal, end the algorithm.
- Set $pivot$ = themedian of the search area
1. Repeat procedure 2, end until the search area only contains 1 element.

The time complexity is $O(nlogn)$ . If we need to calculate torques with each pivot in $O(n)$ time, then the utilization of binary search is necessary, as n is $10^5$ and a $O(n^2)$ algorithm may exceed the time limit (but not the case for this problem as the tests are not that extreme).

However, unfortunately, this problem has a $O(1)$ method to calculate the torques during each iteration. If we use the linear method, the final time complexity of the algorithm using binary search would still be $O(n)$ , which is the time to pre-calculate the prefix sum.

@sichao: observation










#include <stdio.h>
#include <stdint.h>
#define min(a, b) a < b ? a : b

int main() {
    int64_t s = 0, l = 0;
    char c;
    while ((c = getchar()) != '\n') s += l += c -= '0';
    printf("%d", min(s % l, l - s % l));
}

Whenever the pivot moves by one step, the difference changes by a constant value. So binary search is not needed for this problem and we can calculate the zero point through direct division.

C. Champion and Candies

@zeyuan: 0/1 rucksack, dp

This is a classic 0/1 rucksack problem and can be easily solved by applying dynamic programming techniques.
Because once the sum of pleasure for one of the students is given, the other one can be determined by subtracting the sum of the first one from the sum of all candies, we may consider this problem as finding a way of taking candies that the sum of pleasure is closest to 1/2 of the total pleasure, which is a 0/1 rucksack problem.
let lim = 1/2 total pleasure, x[i] = candie i’s pleasure.

Basically:

dp[i][j] means the highest possible number of pleasure one may achieve while only taking from first i candies and leaving j number of space. (dp[i][j] = lim - j)
dp[i][j] = dp[i - 1][j] if j < x[i]
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - x[i]] + x[i])

The maximum of dp array is the closest value to lim that is possible to take. 2 * abs(lim - maximum) is the answer.

@yuhan: 1-dimensional knapsack (dp)

In terms of Zeyuan’s definition of ‘space’, we are considering the degree of pleasure as the ‘space’ of the knapsack.

Furthermore, as we iterate i from 0 to n-1, we always calculate $dp[i][]$ after $dp[i-1][]$ . Therefore, the first dimension of the array is redundant. In order to save memory and simplify the code, we could omit the first dimension. Instead, we could use $dp'[j]$ to save the highest possible degree of pleasure one may achieve leaving $i$ degree of space (We conside). The recursive formula would be:

$dp[j] = dp[j - x[i]] + x[i]$ if $dp[j] < dp[j - x[i]] + x[i]$

This could be considered as $dp[]$ is automatically inheriting the value from previous iterations of $i$ .

The final answer will still be $2 * abs(lim - maximum)$ where $maximum = dp[lim]$ .

The time complexity of the algorithm would be $O(n*maxsum) = O(n^2*max(x_i))$ , which is about $10^6$ in extreme case.

D. Donuts for free!

@jinamn: Behind the scene
In the first version of the problem, Tommy had to line for donuts on his own, which means there would only be only one type-2 input, making the problem rather simple.

@aditya: Maintain when the bots would join the queue

For this problem, a queue can be used to store when (point in time, say T) Tommy’s bots would join the line and how many bots would join with together. Thus a queue of pair of time, count would suffice.
Then at each point in time,

Update total number of people. Remove elements from queue if the time had already passed.
if there are Tommy’s bots ready to join the line, add pair of <current time + total number of people already in queue, Number of bots> to the end of queue.
Update total number of people
If asked when the next bot would get the donut, just check the difference from the data stored in queue and current time.

@bud: implementation and choosing the right data structure

We can see that the maximum number of seconds (i.e the maximum number of event) is $2 \times 10^5$ , and in one event, the maximum number of Tommy’s bots that join the line is $20$ . As a result, there are at most $20 \times 2 \times 10^5 = 4 \times 10^6 < 10^7$ bots, which means it is possible store all these bots in a data structure of C++ STL or Java Collections and simulate the process.

=> We need to find a clever way to mark the bots and insert these bots in an appropriate data structure (I will temporarily call it “bag”) so that we can calculate the result when Tommy wants to know when is his next donut.

=> We keep a variable cur that store the second that the last thing in line get the donut (and also use it to mark the bots).

When we add $x$ things (students or Tommy’s bots) to the line, the first thing of these $x$ things will get the donut at second cur+1, the second one will get the donut at second cur+2, and so on. If these things are bots, we also need to mark them by the second they get a donut and insert them into the bag. After adding all these things, we also need to increase cur by $x$ .

(Then, I realized that there is a case that there is nothing in the line, so if there is nothing in the line at the begining of second $i$ (i.e cur<=i-1), I assume the last thing get the donut at second $i-1$ and set cur=i-1)

With the idea of using variable cur, we can easily come up with this algorithm:

Set cur = 0

For each second i:
    if there is nothing in the line (cur<=i-1)
        set cur=i-1;
    
    if x students join the line
        set cur=cur+x 
    (since we don't need to store the students)
    
    if x bots join the line
        for each bot j (1<=j<=x)
            insert cur+j into bag
        set cut=cur+x
    
    if Tommy wants to know when is his next donut
        set tmp=(the smallest number in the bag that is not smaller than i)
        print out tmp-i

The last problem is choose the right data structure for our “bag”. We can see that we need a method/ function that return (the smallest number in the bag that is not smaller than a number), so that’s mean that we can use a set (which is a balanced binary search tree in C++) as our “bag”.

Since the numbers inserted into the bag are already increasing, we can also a simple array to store them and perform binary search, but I didn’t have time to think about that.

Complexity: Because we need to process one thing in the line at a time, and we need $O(\log_2(Tx))$ to insert or find something in the set, the total complexity is $O(Tx\log_2(Tx))$ with $T$ can be as large as $2 \times 10^5$ and $x$ can be as large as $20$ .

In worst case, this algorithm takes $\frac{20 \times 2 \times 10^5 \times \log_2(20 \times 2 \times 10^5)}{10^8} \approx 0.8773 < 1$ seconds to run.

@sichao: sparse and dense storage

You can implement a queue in 2 ways: 1,1,1,1,0,0,0,1,1,0,0,0,… or {4,1},{3,0},{2,1},{3,0},… The first one is easier to write but wastes more space and time that may result in a MLE or TLE in harder questions.

E. E-mail Distribution

@bryan: ad-hoc, simulation

Use an array to keep track of each friend, i.e. arr[i] is the number of spam emails that the ith friend has received.
Initially, let arr be an int array of length n with all 0s. Then read in each integer in the second line of input. Upon reading in the integer i, increment arr[i - 1] (the minus 1 comes from zero-based indexing, you could make an n + 1 length array to use 1-based indexing instead).
Finally, print each entry of the array.

@vibhor: …

F. Forbidden Spell

@jinman: trivia

Forbidden spell is a song by Touhou Project fan circle SPACELECTRO. I like more of the later mAoA9 Remix version.
Hymmnos is a language created by Akira Tsuchiya for Ar tonelico, a video game series. The vowels, plus ‘n’, are “emotional” elements in the language.

@jinman: case-by-case, greedy

Note that:

If there are odd number of consonants, there is no way to split.
Else if there are odd number of vowels, the entire string is a valid phrase.
Else we have an even number of consonants and an even number of vowels. If there exist a way of split, there must be a split of two [more explanation]. So we can go from left to right, accumulate the counts for vowels and consonants, and output the first valid split we found.

[more explanation]: Say we can split the string into many phrases, each of which contains odd number of vowels and even number of consonants. Note that any three adjacent phrases can be combined together to form a larger phrase which also contains odd number of vowels and even number of consonants. Repeat this process, you will finally arrive at one or two phrases. One phrase case is forbidden by the condition.

Oh, don’t forget to check if the second phrase is valid.

@aditya: Case by case checking

Same as above solution.
Only one case needs to be analyzed

Count of vowels = even
Count of consonants = odd
If there exists a solution, then for the first part of the split, the number of vowels would be odd and consonants even. This would make the number of vowels in second half also odd and consonants even. So iterate over the string one and find the point of split if it satisfies the constraints.

@dung: dynamic programming

One rule of thumb of competitive programming: When your greedy algorithm is wrong, use dynamic programming.

First, I used a greedy solution similar to the one of @jinman, but because I forget to check if the second phrase is valid, my solution failed. As a result, I decided to come up with a dynamic programming solution for this problem.

I defined a function dp[x] that return true if there is a legal way to split the string from somewhere before $x$ to $N$ (the length of the string) and return false otherwise. There is a problem though: it is impossible to calculate dp[x] directly from dp[x+1] (I can only use dp[x+1] because if I use dp[x+2], dp[x+3], …, the complexity will be $O(N^2)$ , and with $N \leq 10^5$ , I will definitely receive Time Lime Exceeded).

=> I decided to add several parameters to keep track the last phrase of the string from 1 to $x$ .

I defined dp[x][y][z][t] that return true if there is a legal way to split the string from somewhere before $x$ to $N$ and the first phrase (which starts at that "somewhere before $x$ " and can end at $x$ or somewhere else after $x$ ) is having odd vowels iff $y=1$ , even consonants iff $z=0$ , and at least 1 consonant iff $t=1$ .

If I have time, I will add my dynamic programming formula here.

Complexity: We can see that $0 \leq x \leq N$ , $0 \leq y \leq 1$ , $0 \leq z \leq 1$ , $0 \leq t \leq 1$ , so the number of states is $\approx N \times 2 \times 2 \times 2 = 8N$ . Since it takes $O(1)$ to make transitions between states, the total complexity is $O(8N)$ (i.e. $O(N)$ ).

This solution is much longer than the greedy one, but it has some advantages:

It can be modified to solve other versions of this problem (such as the problem of splitting the string to as many valid phrases as possible)
If $N$ is bigger (say, $N \leq 10^8$ ), we can generate some small tests with correct answers to make an important observation: The initial greedy solution is correct, and there is just a small bug in our first code.

Ziyi Zhang, CF: RobeZH ↩︎
Jinman Zhao, jz(a)cs.wisc.edu ↩︎
Dung Viet Bui (Bud), CF: bvd ↩︎
Bryan Jin, CF: divide_by_zero ↩︎
Aditya Akash, CF: adityaakash ↩︎
Zeyuan He, CF: Assancious ↩︎
Yuhan Xie, CF: Scorpion_XZ ↩︎
Vibhor Goel, CF: goelvibhor ↩︎