Problem 1: Asian Games Medal Ranking

#include <bits/stdc++.h>
using namespace std;

int main() {
    int entries;
    cin >> entries;
    
    vector<vector<int>> medalCounts(2, vector<int>(4, 0));
    
    for (int i = 0; i < entries; i++) {
        int country, position;
        cin >> country >> position;
        medalCounts[country][position]++;
    }
    
    for (const auto& countryData : medalCounts) {
        for (int pos = 1; pos <= 3; pos++) {
            cout << countryData[pos];
            if (pos != 3) cout << " ";
        }
        cout << endl;
    }
    
    auto originalOrder = medalCounts;
    sort(medalCounts.begin(), medalCounts.end());
    
    if (originalOrder == medalCounts) {
        cout << "The second win!";
    } else {
        cout << "The first win!";
    }
    
    return 0;
}

Key Concepts:

Vector Operations: Dynamic arrays that can automatically resize.

vector<int> container;
vector<int> sizedContainer(10);
vector<int> initializedContainer(10, 1);
vector<int> copiedContainer(container);
vector<int> partialCopy(container.begin(), container.begin()+3);

int array[] = {1, 2, 3, 4, 5};
vector<int> fromArray(array, array+5);
vector<int> rangeCopy(&array[1], &array[4]);

Range-based Loops: Different reference types for various access patterns.

Sorting: Default ascending order comparison.

Problem 2: Hospital Discharge

#include <iostream>
#include <map>
using namespace std;

int main() {
    int knownLevels, queries;
    cin >> knownLevels >> queries;
    
    map<string, string> classification;
    
    for (int i = 0; i < knownLevels; i++) {
        string symptom, level;
        cin >> symptom >> level;
        classification[symptom] = level;
    }
    
    for (int i = 0; i < queries; i++) {
        string querySymptom;
        cin >> querySymptom;
        
        if (classification.count(querySymptom)) {
            cout << classification[querySymptom] << endl;
        } else {
            int matchCount = 0;
            string result;
            
            for (const auto& entry : classification) {
                if (entry.first.size() < querySymptom.size() &&
                    querySymptom.substr(0, entry.first.size()) == entry.first &&
                    classification.count(querySymptom.substr(entry.first.size()))) {
                    matchCount++;
                    result = entry.second + classification[querySymptom.substr(entry.first.size())];
                }
            }
            
            if (matchCount != 1) result = "D";
            cout << result << endl;
        }
    }
    
    return 0;
}

Key Concepts:

Map Data Structure: Key-value pairs with automatic sorting.

String Substrings: Extract portions of strings using position and length parameters.

Problem 4: Relativity

#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>
using namespace std;

const int MAX_NODES = 4010;
int nodeCount = 0, transitionCount;
string nodeName[MAX_NODES];
vector<int> adjacencyList[MAX_NODES];
unordered_map<string, int> nodeId;

vector<int> findShortestPath(int start, int target) {
    queue<int> traversalQueue;
    vector<int> predecessor(nodeCount + 1, 0);
    
    traversalQueue.push(start);
    
    while (!traversalQueue.empty()) {
        int currentNode = traversalQueue.front();
        traversalQueue.pop();
        
        if (currentNode == target) break;
        
        for (int neighbor : adjacencyList[currentNode]) {
            if (predecessor[neighbor] == 0) {
                predecessor[neighbor] = currentNode;
                traversalQueue.push(neighbor);
            }
        }
    }
    
    vector<int> path;
    do {
        path.push_back(target);
        target = predecessor[target];
    } while (target != 0);
    
    return path;
}

void displayNode(int nodeIdValue, bool addSpace) {
    cout << nodeName[nodeIdValue] << " " << nodeIdValue - nodeId[nodeName[nodeIdValue]];
    if (addSpace) cout << " ";
}

int main() {
    cin >> transitionCount;
    
    for (int i = 1; i <= transitionCount; i++) {
        string name1, name2;
        int state1, state2;
        cin >> name1 >> state1 >> name2 >> state2;
        
        if (!nodeId.count(name1)) {
            nodeCount += 2;
            nodeId[name1] = nodeCount - 1;
            nodeName[nodeCount - 1] = nodeName[nodeCount] = name1;
        }
        
        if (!nodeId.count(name2)) {
            nodeCount += 2;
            nodeId[name2] = nodeCount - 1;
            nodeName[nodeCount - 1] = nodeName[nodeCount] = name2;
        }
        
        adjacencyList[nodeId[name1] + state1].push_back(nodeId[name2] + state2);
    }
    
    vector<int> shortestPath(2000);
    
    for (int i = 1; i <= nodeCount; i += 2) {
        auto forwardPath = findShortestPath(i, i + 1);
        auto reversePath = findShortestPath(i + 1, i);
        
        if (shortestPath.size() > forwardPath.size() && forwardPath.size() > 1)
            shortestPath = forwardPath;
        if (shortestPath.size() > reversePath.size() && reversePath.size() > 1)
            shortestPath = reversePath;
    }
    
    for (int i = shortestPath.size() - 1; i >= 1; i--) {
        displayNode(shortestPath[i], true);
        displayNode(shortestPath[i - 1], true);
    }
    
    cout << "= ";
    displayNode(shortestPath.back(), true);
    displayNode(shortestPath[0], false);
    
    return 0;
}

Key Concepts:

Unordered Map: Faster single element access than map, but unsorted.

Queue Operations: FIFO data structure with standard operations.

Breadth-First Search: Graph traversal algorithm for shortest paths.

Problem 5: Relative Succsess and Failure

#include <bits/stdc++.h>
using namespace std;

int main() {
    int testCases;
    cin >> testCases;
    
    for (int caseNum = 1; caseNum <= testCases; caseNum++) {
        int participantCount;
        cin >> participantCount;
        
        vector<int> scores(participantCount + 1, 0);
        
        for (int i = 1; i <= participantCount; i++) {
            int success, failure;
            cin >> success >> failure;
            scores[i] = success + 1 - failure;
        }
        
        vector<int> dynamicProgramming(3, 0);
        int maximumLength = 0;
        
        for (int i = 0; i < participantCount; i++) {
            int participantIndex;
            cin >> participantIndex;
            
            for (int j = scores[participantIndex]; j < 3; j++) {
                dynamicProgramming[scores[participantIndex]] = max(
                    dynamicProgramming[scores[participantIndex]], 
                    dynamicProgramming[j] + 1
                );
            }
            
            maximumLength = max(dynamicProgramming[scores[participantIndex]], maximumLength);
        }
        
        cout << participantCount - maximumLength << endl;
    }
    
    return 0;
}

Key Concepts:

Dynamic Programming: Optimization technique for overlapping subproblems.

This implementation solves the Longest Decreasing Subsequence problem.