Uol 2025 Wk2 Solutions

Recount

Problem

The recent schoolboard elections were hotly contested: a proposal to swap school start times for elementary and high school students, a controversial new dress code proposal that bans athletic clothes in school, and a proposal to raise real-estate taxes to pay for a new football practice facility, and the list goes on and on. It is now hours after the polls have closed and a winner has yet to emerge!

In their desperation, the election officials turn to you and ask you to write a program to count the vote!

Input

The input consists of a single test case, which is a list of votes cast. Each line in the input contains the name of a candidate for whom a vote was cast. A name may consist of multiple words, separated by spaces. Words contain letters or hyphens, but no other punctuation characters. There will be at least 2 votes on the list. The list of votes ends with a single line containing the characters ***. This line should not be counted. There can be up to 100 000 valid votes.

Output

If a candidate obtained a simple or absolute majority of all votes cast (that is, more than any other candidate), output the name of this candidate! If no candidate obtained a simple majority, output: “Runoff!” (don’t forget to include the exclamation mark!)

Code

##include <iostream>
##include <string>
##include <unordered_map>
##include <algorithm>

// using namespace std; // For brevity in a single file solution

namespace recount {
    int main(istream &cin, ostream &cout) {
        // Use an unordered_map to store vote counts for each candidate.
        // The key is the candidate's name (string), and the value is their vote count (unsigned long).
        std::unordered_map<std::string, unsigned long> m = std::unordered_map<std::string, unsigned long>();
        std::string line;

        // Read votes line by line until the sentinel value "***" is encountered.
        while(std::getline(cin, line)) {
            if(line == "***") {
                break;
            }
            // Increment the vote count for the candidate named in the current line.
            // If the candidate is not yet in the map, they are added with a count of 1.
            m[line]++;
        }

        // Initialize a string to hold the winner's name and a variable for the maximum vote count.
        std::string ans             = "***"; // Sentinel value to check for ties.
        unsigned long max_vote = 0;

        // First pass: find the highest vote count among all candidates.
        for(const auto &[k, v]: m) {
            max_vote = std::max(max_vote, v);
        }

        // Second pass: find the candidate(s) who achieved the maximum vote count.
        for(const auto &[k, v]: m) {
            if(v == max_vote) {
                // If 'ans' is no longer the sentinel value, it means we have already found
                // one winner. Finding another one means there is a tie.
                if(ans != "***") {
                    cout << "Runoff!";
                    return 0; // Exit after printing the result for a tie.
                }
                // This is the first candidate found with the maximum vote count.
                ans = k;
            }
        }
        // If the loop completes and 'ans' has been updated exactly once, print the winner's name.
        cout << ans;

        return 0;
    }
}

Solution

This problem asks us to process a list of votes, where each vote is a string representing a candidate’s name. We need to find the candidate with the most votes. If there is a single candidate with the highest vote count, we print their name. If two or more candidates are tied for the highest count, we must declare a “Runoff!”. The list of votes is terminated by a special string, ***.

To solve this, we need an efficient way to store and count votes for potentially many different candidates. A hash map ( or dictionary) is the ideal data structure for this task. In C++, this is implemented as std::unordered_map. We can map each candidate’s name (a std::string) to their total vote count (an integer type like unsigned long).

The overall algorithm proceeds in three main stages:

First, we read the input and count the votes. We iterate through each line of the input. For each line, which represents a single vote, we check if it is the terminator string ***. If it is, we stop reading. Otherwise, we use the candidate’s name as a key in our unordered_map and increment the corresponding value. The [] operator of std::unordered_map is very convenient here: if the key (the name) doesn’t exist in the map, it is automatically inserted with a default-constructed value (0 for integers), and then the increment operation ++ brings it to 1. If the key already exists, its value is simply incremented.

Second, after processing all votes, we need to determine the highest number of votes received by any candidate. We can achieve this by iterating through all the key-value pairs in our map and keeping track of the maximum value (vote count) seen so far. Let’s call this maximum value max_vote.

Third, we must identify the winner or detect a tie. A single pass through the map is not sufficient to do this reliably while also finding the maximum value. Therefore, a second pass through the map is the simplest and clearest approach. In this second iteration, we compare each candidate’s vote count with the max_vote we found in the previous step. We use a string variable, say winner_name, initialized to a special sentinel value (like the *** from the input, as it cannot be a valid candidate name). When we find the first candidate whose vote count equals max_vote, we store their name in winner_name. If we then encounter another candidate whose vote count also equals max_vote, we know there is a tie. At this point, we can immediately print “Runoff!” and terminate the program. If the second loop completes without finding a second candidate with max_vote, it means there is a unique winner, whose name is now stored in our winner_name variable. We then print this name.

Complexity Analysis

Let N be the total number of votes cast, and C be the number of unique candidates. Let L be the maximum length of a candidate’s name.

Time Complexity

The process can be broken down into three parts.

Reading votes and populating the map: We loop N times. Inside the loop, std::getline takes O(L) time. Accessing the unordered_map with a string key involves hashing the string, which takes O(L) time on average. Therefore, this phase has an average-case time complexity of O(N * L).
Finding the maximum vote count: We iterate through the C unique candidates stored in the map. This takes O(C) time.
Identifying the winner or a tie: We again iterate through the C unique candidates, which takes O(C) time.

The total time complexity is the sum of these parts: O(N * L + C + C) = O(N * L + C). Since the number of unique candidates C cannot exceed the total number of votes N (i.e., C ≤ N), the complexity is dominated by the first phase, resulting in a final average-case time complexity of O(N * L).

Space Complexity

The primary space usage comes from the unordered_map. In the worst-case scenario, every vote is for a different candidate, meaning we would store N unique names. The space required for the map is proportional to the number of unique candidates (C) and the sum of the lengths of their names. In the worst case, this is O(N * L), where we store N names of average length L. Thus, the space complexity is O(N * L).

Set

Problem

Set is a card game designed by Marsha Falco in 1974 which is marketed by Set Enterprises, Inc. It also appears in syndicated form on the website of the New York Times. The player is shown 12 cards, each of which contains 1, 2, or 3 symbols. The symbols are either diamonds, squiggles, or ovals. Symbols are drawn using either a solid, striped, or open fill style. Each symbol’s color is either red, green, or purple. On a given card, all symbols are of the same type, same color, and have the same fill style.

To make a set, you must select three cards for which all 4 characteristics are either the same or pairwise different. For instance, 3 cards where the first shows 2 striped red ovals, the second shows 3 striped green squiggles, and the third shows 1 striped purple diamond form a set. They show 2, 3, and 1 symbols (each has a different number); they show ovals, squiggles, and diamonds (each shows a different shape); they use colors red, green, and purple (3 different colors); and lastly, they all share the same fill style: striped.

Write a program that finds all sets for 12 provided cards!

Input

The input to your program will consist of 4 lines, each containing 3 strings representing 3 cards, each consisting of four characters ABCD where

A ∈ {1, 2, 3}, corresponding to the number of symbols.

B ∈ {D, S, O}, corresponding to diamonds (D), squiggles (S), and ovals (O).

C ∈ {S, T, O}, corresponding to solid (S), striped (T), and open (O) fill styles.

D ∈ {R, G, P}, corresponding to red (R), green (G), and purple (P).

Think of the cards as being arranged in the input as follows:

+———-+ | 1 2 3 | | 4 5 6 | | 7 8 9 | | 10 11 12 | +———-+

Output

Output all sets you can find, one per line. For each set, output the numbers of the card in the set in sorted order. The sets should be listed in sorted order using the number of their first card, breaking ties using the numbers of the second and third card in the set. If no sets can be formed, output “no sets”.

Code

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <unordered_set>

namespace set {
    std::vector<std::vector<int>> ans = {};

    class card {
    public:
        int id;
        char f[4];
        card(int id, std::string s);
    };

    class cardset {
    public:
        unsigned short mask = -1;
        int cnt             = 0;
        std::unordered_set<card *> cards{};
        cardset() = default;
        cardset(card *c);
        void insert(card *c);
    };

    cardset::cardset(card *c) {
        this->cards.insert(c);
        this->cnt = 1;
    }

    unsigned short calc_mask(card *c1, card *c2) {
        unsigned short mask = 0;
        for(int i = 0; i < 4; i++) {
            mask <<= 1;
            mask |= c1->f[i] == c2->f[i];
        }
        return mask;
    }

    card::card(int id, std::string s) {
        this->id = id;
        std::istringstream iss(s);
        iss >> this->f[0] >> this->f[1] >> this->f[2] >> this->f[3];
    }

    void cardset::insert(card *c) {
        if(this->mask == (unsigned short) (-1)) {
            this->mask = calc_mask(c, *this->cards.begin());
        }
        this->cards.insert(c);
        this->cnt++;
        if(this->cnt == 3) {
            std::vector<int> vec = {};
            for(auto &card_ptr: this->cards) {
                vec.emplace_back(card_ptr->id);
            }
            std::sort(vec.begin(), vec.end());
            ans.emplace_back(vec);
        }
    }

    bool fit(card *c, const cardset *s) {
        if(s->mask == (unsigned short) (-1)) {
            return true;
        }
        for(auto &sc: s->cards) {
            if(calc_mask(sc, c) != s->mask) {
                return false;
            }
        }
        return true;
    }

    int main(std::istream &cin, std::ostream &cout) {
        cardset sets[1 << 10] = {};
        int sets_cnt          = 0;
        std::string input;
        for(int i = 1; i <= 12; i++) {
            cin >> input;
            card *newcard = new card(i, input);
            for(int j = 0; j < sets_cnt; j++) {
                if(fit(newcard, &sets[j])) {
                    cardset newset = sets[j];
                    newset.insert(newcard);
                    sets[sets_cnt++] = (newset);
                }
            }
            cardset newset   = cardset(newcard);
            sets[sets_cnt++] = (newset);
        }
        if(ans.size() == 0) {
            cout << "no sets";
            return 0;
        }
        std::sort(ans.begin(), ans.end(), [](const std::vector<int> &a, const std::vector<int> &b) {
            if(a[0] != b[0]) {
                return a[0] < b[0];
            } else if(a[1] != b[1]) {
                return a[1] < b[1];
            } else {
                return a[2] < b[2];
            }
        });
        for(const auto &s: ans) {
            cout << s[0] << ' ' << s[1] << ' ' << s[2] << std::endl;
        }
        return 0;
    }
}

Solution

The problem asks us to find all valid “sets” from a given collection of 12 cards. A set consists of three cards where for each of their four features, the feature values are either all identical or all pairwise different.

The provided C++ code implements a constructive or incremental algorithm to find these sets. Instead of checking every possible combination of three cards (brute-force), it builds up potential sets by adding one card at a time.

The core logic revolves around a clever use of bitmasking to represent the relationship between two cards. The function calc_mask(card *c1, card *c2) generates a 4-bit integer. Each bit corresponds to one of the four features. The bit is set to 1 if the feature is the same on both cards, and 0 if it’s different. This “similarity mask” compactly describes how two cards relate to each other.

The rule for a set of three cards (A, B, C) can be rephrased using this mask: the similarity mask between A and B must be identical to the similarity mask between A and C, and also identical to the similarity mask between B and C. This ensures the “all same or all different” property for every feature.

The main algorithm proceeds as follows:

It processes cards one by one, from card 1 to card 12. It maintains an array, sets, which stores cardset objects. A cardset is a potential set, which can contain one or two cards.

For each new card newcard that is read:

It iterates through all cardset objects already created (sets[j]). A cardset can be of size 1 (a single card) or size 2 (a pair of cards).
The function fit(newcard, &sets[j]) checks if newcard can be validly added to the existing cardset.
If sets[j] contains only one card, any newcard can “fit” to form a pair. A new cardset of size 2 is created from this pair. Its mask member is now calculated and stored, representing the similarity between these two cards.
If sets[j] contains two cards, fit checks if newcard’s similarity mask with both cards in sets[j] matches the mask already stored in sets[j]. If it does, a valid set of three has been found. A new cardset of size 3 is created, and its card IDs are added to the global ans vector.
After attempting to extend all existing cardsets, a new cardset containing only the newcard is created and added to the list. This allows newcard to start new potential sets with subsequently processed cards.

After all 12 cards have been processed, the ans vector contains all found sets. The code then checks if any sets were found. If not, it prints “no sets”. Otherwise, it sorts the list of sets lexicographically as required by the problem statement and prints each set on a new line.

Complexity Analysis:

Let N be the number of cards (N=12).

Time Complexity

The outer loop runs N times. The inner loop iterates through sets_cnt, which is the number of existing cardsets. After processing i cards, the number of cardsets of size 1 is i and the number of size 2 is i*(i-1)/2. So, sets_cnt grows quadratically, O(i^2). The total work is approximately the sum of i^2 from i=1 to N-1, which results in a time complexity of O(N^3). For N=12, this is very efficient.

Space Complexity

The sets array stores all cardset objects. The number of these objects is O(N^2). Each cardset stores pointers, so the space is dominated by the array itself, leading to O(N^2) space complexity.

Planting Trees

Problem

Farmer Jon has recently bought n tree seedlings that he wants to plant in his yard. It takes 1 day for Jon to plant a seedling, and for each tree Jon knows exactly in how many days after planting it grows to full maturity. Jon would also like to throw a party for his farmer friends, but in order to impress them he would like to organize the party only after all the trees have grown. More precisely, the party can be organized at earliest on the next day after the last tree has grown up.

Help Jon to find out when is the earliest day when the party can take place. Jon can choose the order of planting the trees as he likes, so he wants to plant the trees in such a way that the party will be as soon as possible.

Input

The input consists of two lines. The first line contains a single integer N (1 ≤ N ≤ 100 000) denoting the number of seedlings. Then a line with N integers t_i follows (1 ≤ t_i ≤ 1 000 000), where t_i denotes the number of days it takes for the i-th tree to grow.

Output

You program should output exactly one line containing one integer, denoting the earliest day when the party can be organized. The days are numbered 1, 2, 3, … beginning from the current moment.

Code

##include <iostream>
##include <vector>
##include <algorithm>

namespace plantingtrees {
    int main(std::istream &cin, std::ostream &cout) {
        int n;
        cin >> n;
        std::vector<int> vec(n);
        for(int i = 0; i < n; i++) {
            cin >> vec[i];
        }

        // Sort the tree growth times in descending order.
        // The rbegin() and rend() iterators are used for reverse sorting.
        std::sort(vec.rbegin(), vec.rend());

        int ans = 0;
        // Iterate through the trees in the chosen planting order.
        // The tree at index 'i' is planted on day 'i + 1'.
        for(int i = 0; i < n; i++) {
            // Day of planting: i + 1
            // Growth time: vec[i]
            // Maturity day: (i + 1) + vec[i]
            // Party day must be after all trees mature, so we find the maximum maturity day.
            // The party is on the day AFTER the last tree matures.
            // The value `i + vec[i] + 2` corresponds to `(i + 1) + vec[i] + 1`, which is the earliest possible party day
            // if this tree is the last one to mature.
            ans = std::max(ans, i + vec[i] + 2);
        }
        cout << ans;

        return 0;
    }
}

Solution

The problem asks for the earliest possible day to hold a party, which must be the day after all planted trees have matured. We have N seedlings, and we know the time t_i each seedling takes to mature after being planted. Planting one seedling takes one day. We can decide the order of planting. The goal is to find a planting order that minimizes the final party day.

Let’s analyze the timeline. If we decide on a planting order, the first tree is planted on day 1, the second on day 2, and so on, with the i-th tree in the sequence being planted on day i. If this i-th tree has a maturity time of t_i, it will be fully grown on day i + t_i. The party can only happen after all trees are mature. This means we need to find the latest maturity day among all trees. The party can be held on the day immediately following this latest maturity day. So, for a given planting sequence p_1, p_2, ..., p_N with corresponding growth times t_{p_1}, t_{p_2}, ..., t_{p_N}, the party day will be 1 + max(1 + t_{p_1}, 2 + t_{p_2}, ..., N + t_{p_N}). Our task is to find an ordering (a permutation p) of the trees that minimizes this value.

This problem can be solved using a greedy approach. The intuition is that trees requiring a longer time to grow should be planted as early as possible. This gives them a “head start” on their long maturation period. Conversely, trees that grow quickly can be planted later without significantly pushing back the final completion date.

Let’s prove this greedy strategy is optimal. The strategy is: sort the trees in descending order of their growth times ( t_i) and plant them in that order. Consider any optimal planting schedule. If this schedule is not sorted by growth time in descending order, there must be at least one pair of adjacent trees in the planting sequence, say at day i and i+1, where the tree planted on day i (let’s call it tree A with growth time t_A) has a shorter growth time than the tree planted on day i+1 (tree B with growth time t_B). So, t_A < t_B.

The maturity days for these two trees in this schedule are:

Maturity of A: i + t_A

Maturity of B: (i + 1) + t_B

All other trees in the sequence are unaffected by what we do with A and B. The latest maturity day for the schedule is max(..., i + t_A, (i + 1) + t_B, ...).

Now, let’s swap the planting order of A and B. We plant B on day i and A on day i+1. The new maturity days are:

New Maturity of B: i + t_B

New Maturity of A: (i + 1) + t_A

Let’s compare the latest maturity day of just this pair before and after the swap. Before swap, the latest is max(i + t_A, i + 1 + t_B). Since t_A < t_B, it implies t_A <= t_B - 1. So, i + t_A < i + t_B - 1 < i + 1 + t_B. The maximum is i + 1 + t_B. After swap, the latest is max(i + t_B, i + 1 + t_A). Since t_A < t_B, it implies i + 1 + t_A < i + 1 + t_B. And also i + t_B is greater than i + 1 + t_A if t_B - t_A > 1. Regardless, the maximum is i + t_B.

Comparing the maximums: (i + t_B) (after swap) vs. (i + 1 + t_B) (before swap). Clearly, i + t_B < i + 1 + t_B. The swap has reduced the latest maturity day for this pair. Since all other trees' maturity days remain unchanged, the overall latest maturity day for the entire schedule can only decrease or stay the same. It cannot increase. This “exchange argument” shows that we can always improve or maintain an unsorted schedule by moving longer-growth-time trees earlier. By repeatedly applying this logic, we can transform any optimal schedule into one that is sorted by growth time descending, without making the result worse. Therefore, the greedy strategy of planting trees with longer growth times first is indeed optimal.

The implementation is straightforward:

Read N and all the growth times t_i into a vector.
Sort the vector in descending order.
Initialize a variable max_party_day to 0.
Iterate through the sorted vector from i = 0 to N-1. The tree t_i is planted on day i+1. Its maturity day is (i+1) + t_i. The earliest party day considering this tree would be (i+1) + t_i + 1. We update our max_party_day with the maximum of its current value and this new calculated day.
After the loop, max_party_day will hold the final answer.

Complexity Analysis

Let N be the number of seedlings.

Time Complexity

The dominant operation is sorting the growth times. Standard sorting algorithms take O(N log N) time. Reading the input takes O(N), and the final loop to calculate the maximum party day also takes O(N). Therefore, the total time complexity is O(N log N).

Space Complexity

We need to store the N growth times in a vector, which requires O(N) space.

Recount#

Problem#

Input#

Output#

Code#

Solution#

Complexity Analysis#

Time Complexity#

Space Complexity#

Set#

Problem#

Input#

Output#

Code#

Solution#

Complexity Analysis:#

Time Complexity#

Space Complexity#

Planting Trees#

Problem#

Input#

Output#

Code#

Solution#

Complexity Analysis#

Time Complexity#

Space Complexity#

Recount

Problem

Input

Output

Code

Solution

Complexity Analysis

Time Complexity

Space Complexity

Set

Problem

Input

Output

Code

Solution

Complexity Analysis:

Time Complexity

Space Complexity

Planting Trees

Problem

Input

Output

Code

Solution

Complexity Analysis

Time Complexity

Space Complexity