Competitive Programming in Rust

tutorials
1

Hi everyone!

I am new to this forum, but not to the Rust Language. I have been learning rust since 4 months or so.

I also do have interest in Competitive Programming, but I found out that there was no guide for the same in Rust. The most basic guides Solving interactive problems and function to take input were not there in Rust.

So, I created this website, Rust Programming For guiding how to do Competitive Programming in Rust.

I have been actively developing it, and would like to get reviews about this.
I will be adding guides like default data structures, graphs, dynamic programming etc. slowly but surely.
Not to mention this is an open source project, you can visit its Github repo

So, yeah, that should be it. Please review the website, if you are interested!

Any comments, issues and merge requests will be welcome, regarding content as well as overall structure of website.

Thank You

13 Likes
2

Very nice site. Bookmarked.

1 Like
3

Thanks for sharing.

1 Like
4

This is a pretty cool website. I read your "basic programs" section and the template and I have a few points to make (it's rather unidiomatic and inefficient in some places!)

  1. Your functions don't need return -- recall the following are equivalent:

    fn foo() -> usize { 3 }
fn bar() -> usize { return 3; }

  2. When people write their code using your templates, it'll be messy and quickly written. However, when they want to use your functions, they will likely be reading your code to know exact semantics. Hence, make sure to run your template code through something like rustfmt.

  3. You don't need type annotations on local variables, since their types can be inferred.

  4. Your take_string() function doesn't yield a String... it yields a Vec<char>. This takes up 4x the space (for ascii input) and is expensive to actually compute (you need to pull apart utf8 data). It'd be better to provide:

    fn take_string() -> String;
fn to_chars(x: String) -> Vec<char>;

Taking all of this into account, here's the template code:

/*
This template is made by Naman Garg <naman.rustp@gmail.com>
GitHub : https://github.com/namanlp
GitLab : https://gitlab.com/namanlp
Website : https://rustp.org

You can visit https://rustp.org/basic-programs/basic-template/
for understanding the template

Feel free to copy the template, but not the solutions :D
Thank You
 */

#![allow(unused)]

use std::io::stdin;

fn take_int() -> usize {
    let mut input = String::new();
    stdin().read_line(&mut input).unwrap();
    input.trim().parse().unwrap()
}

fn take_vector() -> Vec<usize> {
    let mut input = String::new();
    stdin().read_line(&mut input).unwrap();
    input
        .trim()
        .split_whitespace()
        .map(|x| x.parse().unwrap())
        .collect();
}

fn take_string() -> String {
    let mut input = String::new();
    stdin().read_line(&mut input).unwrap();
    input
}
fn to_chars(x: String) -> Vec<char> {
    x.chars().collect()
}

fn solve() {
    // ======================= Code Here =========================
}

pub fn main() {
    let t = take_int();
    for _ in 0..t {
        solve();
    }
}

Enjoy :slight_smile:

2 Likes
5

Nice website! I skimmed through some pages and one in particular caught my eye: Modular Multiplicative Inverse - Rust Programming.

In that page, as an efficient solution you recommend computing the inverse using exponentiation, thanks to Fermat's little theorem. This in particular requires the modulo to be prime.

A better solution would be to use the extended Euclidean algorithm, which computes the coefficients of the Bézout's identity. This is also recommended by Wikipedia, which says;

  • Modular multiplicative inverse » Extended Euclidean algorithm:

    A modular multiplicative inverse of a modulo m can be found by using the extended Euclidean algorithm.

    In big O notation, this algorithm runs in time O(log2(m)), assuming |a| < m, and is considered to be very fast and generally more efficient than its alternative, exponentiation.

  • Modular multiplicative inverse » Using Euler's theorem

    As an alternative to the extended Euclidean algorithm, Euler's theorem may be used to compute modular inverses.

    This method is generally slower than the extended Euclidean algorithm, but is sometimes used when an implementation for modular exponentiation is already available. Some disadvantages of this method include:

    • [...]
    • The relative cost of exponentiation. [...] the standard binary exponentiation, which requires division mod m at every step, is a slow operation when m is large.
6

Yeah, I know about that, but it might be slightly confusing for people coming from other languages. Most of the languages do use the return statement, so it is good to include return statement.

Ok,

Well, in Competitive Programming, that much space won't matter at all.

Input are often limited to 106 characters, which will make difference of a few MB only(it depends on string obviosuly)

For ASCII, each character takes 1 Bytes, while each char takes 4 Bytes.

So, it is merely a difference of 3 MB, for 106 characters, which is not significant, in my humble opinion.

Plus, using another function to convert String to Vector of characters might be forgotten a lot of times, and might not be realised until compiled. So, I prefer to convert directly to the Vec<char>

Thanks For your opinion. It was really helpful, and is appreciated.
I will make sure to run my code through rustfmt once again.

Regards
Naman

7

Well, in Competitive Programming, that much space won't matter at all.

It is a good habit to cultivate though.

8

Hi there,

To be frank, when I learnt the Modular Multiplicative Inverse, I understood the Fermat's little solution and had not enough time to read and understand the Extended Euclidean Algorithm at all ( I had exam in 3-4 days ).

Plus Fermat's Little Solution works perfectly fine. Like you are almost as good as Extended Euclidean Algorithm when m <= 10^5, differing at max a few milliseconds at max. I have submitted a few CP questions using this, and all went smooth. So I didn't bother.

But I will surely have a look at it now.

Thanks for pointing it out
Regards
Naman

But I will consider it now.

9

Yes, but again,

This will waste at least 1 minute in contest, which, in my humble opinion, is much more important than extra bit of space.

Plus, the user, who might copy without knowing this indexing thing, might be confused a lot by why indexing of characters is not working at all in Rust.

10

I must say, I wonder why one would choose a language with which he is not familiar for a competition...

On top of that, I believe a user might be even more surprised that all String/str methods do not work on the returned value of take_string().

11

Yeah, but well, he might not have gone that deep. It is not mentioned in Rust Book at all, that strings can not be indexed like vector.
( At least I didn't find it. I learnt Rust from the book only)

Which function? General functions like push(), pop(), len(), insert() etc. works as good as in vector.

12

I meant the functions in str - Rust (find, lines, match, parse, split, starts_with, trim, ...)

13

It's described in Storing UTF-8 Encoded Text with Strings - The Rust Programming Language (rust-lang.org).

14

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.