m.cpp's blog

Switching from C++ to Rust gave me MLE.
By m.cpp, 9 months ago, In English

Hi!

I'm practicing coding in the new Rust language and today I'm struggling while solving this problem: 557E - Аня и полупалиндром. The main idea is to build a trie that contains all the suffixes of a binary string $$$s$$$ having a maximum length of $$$5000$$$.

I was able to code in C++ and get an AC, but when I switched to Rust, I got MLE verdict on test 9. Though both solutions have the same approach.

I think the main issue is that my $$$trie$$$ array contains too many elements and there are differences in the data storage mechanisms between C++ and Rust.

I'm new to this language anyway so any suggestions are appreciated. Thanks in advance!

  • Vote: I like it
  • +20
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it +16 Vote: I do not like it

int in C++ takes 4 bytes, while usize in Rust takes 8 bytes. So if your C++ solution already uses around 400MB of memory, the Rust version with usize shouldn't fit into 512MB limit.

Easy (but ugly) fix — use i32 or u32 instead of usize. One downside is that you can't index the array by i32, so you will need to add some casts like as usize in some places. To make it more clean, you can store things in Trie as u32, but also add a wrapper function like:

impl Trie {
  fn next(&self, ch: usize) -> usize {
    self.next[ch] as usize
  }
}

and just call next(0) instead of directly using next[0] everywhere.

→ Reply