Kattis lektira rust solution

Solving the "Lektira" Problem from Kattis

The "Lektira" problem, as presented on Kattis, is an intriguing challenge that involves string manipulation and lexicographical ordering. The essence of the problem is to find the lexicographically smallest word possible by splitting a given word into three parts, reversing each part, and then reassembling them. This article provides a detailed walkthrough of an efficient solution to this problem, emphasizing performance.

Solution Strategy

The solution is structured around two nested loops to try all possible pairs of cutting points. Additionally, a function is used for reversing the sub-words and reassembling them to form the final word.

github full rust solution

Main Function

use std::io::{self, Read};

fn main() {
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).unwrap();
    let word = input.trim_end();
    let word_chars: Vec<char> = word.chars().collect();

    let mut best_i = 0;
    let mut best_j = 1;
    for i in 0..word_chars.len() - 2 {
        for j in i + 1..word_chars.len() - 1 {
            if compare_ijs(&word_chars, i, j, best_i, best_j) < 0 {
                best_i = i;
                best_j = j;
            }
        }
    }
    let result = reverse(&word_chars, best_i, best_j);
    println!("{}", result.iter().collect::<String>());
}

This function reads the input word, converts it into a vector of characters, and initializes the cutting points best_i and best_j. The nested loops iterate over all possible pairs of cutting points.

Comparison Function

fn compare_ijs(word: &[char], i1: usize, j1: usize, i2: usize, j2: usize) -> i32 {
    let li = word.len() - 1;
    let mut cp = if i1 == i2 { i1 } else { 0 };
    let rp = if j1 == j2 { j1 } else { li };
    while cp <= rp {
        let c1 = word[char_position(li, i1, j1, cp)];
        let c2 = word[char_position(li, i2, j2, cp)];
        if c1 != c2 {
            return c1 as i32 - c2 as i32;
        }
        cp += 1;
    }
    0
}

This function compares two possible splits of the word. It determines which of the two results in a lexicographically smaller word.

Character Position Calculation

fn char_position(li: usize, i: usize, j: usize, cp: usize) -> usize {
    if i >= cp {
        i - cp
    } else if j >= cp {
        j - (cp - i - 1)
    } else {
        li - (cp - j - 1)
    }
}

This function calculates the position of a character in the reversed sub-word.

Reversal and Reassembly Function

fn reverse(word: &[char], i: usize, j: usize) -> Vec<char> {
    let li = word.len() - 1;
    (0..word.len())
        .map(|cp| word[char_position(li, i, j, cp)])
        .collect()
}

This function reverses the sub-words and reassembles them into the final word. It uses the char_position function to place each character in its new position.

Conclusion

This solution efficiently solves the "Lektira" problem by exploring all possible splitting points and selecting the one that yields the lexicographically smallest result. The use of nested loops for iteration and a dedicated function for comparison ensures the performance is optimized for competitive programming standards. This approach effectively demonstrates the power of algorithmic thinking and the practical application of string manipulation techniques in solving complex problems.