UVa _11456 _ Trainsorting

 #include <iostream>

#include <vector>

using namespace std;

int findLongestSymmetricSubsequence(int sequenceLength) {

    // Create mirrored train sequence

    vector<int> symmetricSequence(sequenceLength * 2);

    // Track length of increasing subsequence for each position

    vector<int> subsequenceLengths(sequenceLength * 2, 1);

    int maxSubsequenceLength = 0;

    // Read and mirror the sequence

    for (int i = 0; i < sequenceLength; ++i) {

        int trainCarValue;

        cin >> trainCarValue;

        symmetricSequence[sequenceLength + i] = symmetricSequence[sequenceLength - i - 1] = trainCarValue;

    }

    // Find longest increasing subsequence

    for (int currentIndex = 0; currentIndex < sequenceLength * 2; ++currentIndex) {

        for (int prevIndex = 0; prevIndex < currentIndex; ++prevIndex) {

            // If current element is larger than previous, update subsequence length

            if (symmetricSequence[currentIndex] > symmetricSequence[prevIndex]) {

                subsequenceLengths[currentIndex] = max(

                    subsequenceLengths[currentIndex], 

                    subsequenceLengths[prevIndex] + 1

                );

            }

            // Track maximum subsequence length

            maxSubsequenceLength = max(maxSubsequenceLength, subsequenceLengths[currentIndex]);

        }

    }

    return maxSubsequenceLength;

}

int main() {

    // Optimize input/output performance

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    cout.tie(nullptr);

    int numberOfTestCases;

    cin >> numberOfTestCases;

    // Process each test case

    while (numberOfTestCases--) {

        int trainLength;

        cin >> trainLength;

        // Solve and output result for current test case

        cout << findLongestSymmetricSubsequence(trainLength) << "\n";

    }

    return 0;

}

UVa _ 10336 _ Rank the Languages

 import sys

# Constants

MX = 10000

class Type:

    def __init__(self, id=None, value=0):

        self.id = id

        self.value = value

def comp(a):

    # Comparison function for sorting ranks

    # Primary sort: descending order of value (using negative to achieve descending)

    # Secondary sort: ascending order of id (in case of equal values)

    # Useful for ranking components by size and then by identifier

    return (-a.value, a.id)

def init(h, w):

    # Initialize a list of Type objects with default values

    # Creates an empty data structure of specified dimensions

    # Useful for pre-allocating space for graph-related data structures

    return [Type() for _ in range(h * w)]

def set_rank(ranks, c, r):

    for rank in ranks:

        if rank.id == c:

            rank.value += r

            return    

    new_rank = Type(id=c, value=r)

    ranks.append(new_rank)

def dfs_visit(graph, a, b, h, w):

    # Capturing the original color/type of the current cell before modification

    temp_c = graph[a][b]

    # label v as discovered

    # Mark the current cell as 'visited' to prevent re-exploration and avoid infinite recursion

    graph[a][b] = 'G'

    

    # Directional movements represent the possible traversal directions

    # These coordinates allow checking adjacent cells (left, up, right, down)

    dr = [0, -1, 0, 1]

    dc = [-1, 0, 1, 0]

    # for all directed edges from v to w that are in G.adjacentEdges(v) do

    # Iterate through all four possible adjacent directions

    for i in range(4):

        r = dr[i] + a

        c = dc[i] + b

        # if vertex w is not labeled as discovered then

        # Check if the adjacent cell is within graph boundaries and of the same color/type

        if (0 <= r < h and 0 <= c < w and 

            graph[r][c] == temp_c):

            # recursively call DFS(G, w)

            # Explore the connected component by recursively visiting adjacent cells

            dfs_visit(graph, r, c, h, w)

    # Mark the cell as completely explored to distinguish from undiscovered cells

    graph[a][b] = 'B'

def dfs(graph, h, w):

    # Initialize a list to store ranked components

    ranks = []

    # for all directed edges from v to w that are in G.adjacentEdges(v) do

    # Traverse through entire graph to find and explore connected components

    for i in range(h):

        for j in range(w): 

            # if vertex w is not labeled as discovered then

            # Check if the current cell hasn't been explored in previous DFS calls

            if graph[i][j] not in ['G', 'B']: 

                # Assign initial rank to the newly discovered component

                set_rank(ranks, graph[i][j], 1)  

                # recursively call DFS(G, w)

                # Start DFS from this undiscovered cell to explore its entire component

                dfs_visit(graph, i, j, h, w)

    return ranks

def process_world(h, w, graph_input):

    # Convert input to 2D list for easier manipulation

    graph = [list(row) for row in graph_input]

    # Perform depth-first search to identify and rank components

    ranks = dfs(graph, h, w)

    # Sort ranks in descending order of component size, with secondary sorting by component ID

    ranks.sort(key=comp)

    return ranks

test_cases = int(input())

cases = 0

for _ in range(test_cases):

    h, w = map(int, input().split())

    graph_input = [input() for _ in range(h)]

    cases += 1

    ranks = process_world(h, w, graph_input)

    print(f"World #{cases}")

    for rank in ranks:

        print(f"{rank.id}: {rank.value}")