Reason for wrongness of Code Jam submission

I'm attempting to solve this CodeJam problem in Rust. My algorithm is sound in my mind, and I don't believe the implementation has any mistakes either.

But I keep getting wrong answer for every submission. Please help me if there's something obviously wrong with my Rust code.

I'd also like to clarify that the read() function used here is the most idiomatic way to read and return a single line from stdin. I can't use external crates as the code has to be submitted to code jam.

use std::{
    collections::{HashMap, HashSet},
    io::BufRead,
    usize,
};

fn read() -> String {
    std::io::stdin()
        .lock()
        .lines()
        .next()
        .unwrap()
        .unwrap()
        .trim()
        .to_string()
}

fn main() {
    // number of cases
    let n: u32 = read().parse().unwrap();

    for i in 0..n {
        let mut stored: HashMap<String, bool> = HashMap::new();
        let mut switch_count: u32 = 0;
        let s: u32 = read().parse().unwrap();

        // read and discard engine names
        for _ in 0..s {
            read();
        }

        // read queries
        let mut queries: Vec<String> = Vec::with_capacity(1000);
        for _ in 0..read().parse().unwrap() {
            queries.push(read());
        }


        // increment switch_count if every engine has already been encountered.
        for query in queries {
            if stored.len() == s as usize {
                stored.clear();
                switch_count += 1;
            }
            stored.insert(query, true);
        }
        println!("Case #{}: {}", i + 1, switch_count);
    }
}

For this input you must switch three times:

1
2
Foo
Bar
4
Foo
Bar
Foo
Bar
2 Likes

Thank you! Your suggestion was sound. It's odd, but it really bugs me that I hadn't thought of that, while simultaneously being dumbfounded on how to think up such cases. I also hadn't considered this:

1
2
Foo
Bar
2
Foo
Foo

Final code:

use std::{collections::HashMap, io::BufRead};

fn read() -> String {
    std::io::stdin()
        .lock()
        .lines()
        .next()
        .unwrap()
        .unwrap()
        .trim()
        .to_string()
}

fn main() {
    let n: u32 = read().parse().unwrap();
    for i in 0..n {
        let mut stored: HashMap<String, bool> = HashMap::new();
        let mut switch_count: u32 = 0;
        let s: u32 = read().parse().unwrap();

        // read and discard engine names
        for _ in 0..s {
            read();
        }

        // read queries
        let mut queries: Vec<String> = Vec::with_capacity(1000);
        for _ in 0..read().parse().unwrap() {
            queries.push(read());
        }

        // increment switch_count if every engine has already been encountered.
        for query in queries {
            if stored.get(&query) == None && stored.len() == (s - 1) as usize {
                stored.clear();
                switch_count += 1;
            }
            stored.insert(query, true);
        }
        println!("Case #{}: {}", i + 1, switch_count);
    }
}

That still doesn't seem right. Consider this input:

1
2
Foo
Bar
5
Foo
Bar
Bar
Foo
Bar

Here, it should only switch three times, but your code says four.

My bad I copied older code. I've edited my reply with the correction.

This instance has solution two (send it to baz every time except for the third time), but your code says five:

1
3
Foo
Bar
Baz
11
Foo
Bar
Baz
Foo
Bar
Foo
Bar
Foo
Bar
Foo
Bar

I updated the reply above with corrected code that prints 2 for that input.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.