C++ is an excellent language for competitive programming, and most of the top performers use it. However, it has many flaws. Lately, Rust is getting increasingly more popular on CodeForces. I haven't yet written a single program in Rust in my entire life, however from what I have heard about it, I feel like there is actually a possibility that in 15 years it will be the most popular CP programming language as now is C++ and as 15 years ago was Pascal (don't quote me on that).
So this Saturday, January 21st at 11:00 AM UTC I will be streaming and trying to solve a CodeForces round using Rust, learning it along the way and seeking help from viewers. Additionally, we will be raising money for a great non-profit organization that helps Ukraine. More details at the beginning of the stream.
Rust is a great language, but not for competitive programming. It may increase in popularity as competitive programmers who also have real jobs switch to it for work and will be more inclined to keep it as their primary language for competitive programming, but even if Rust completely replaces C++ in the real world, I seriously doubt it will ever reach a double-digit share on platforms like CodeForces because the barrier of entry is so much higher compared to C++ and most other languages,
I'd argue the barrier of entry is not that high, but even knowing Rust relatively well, I don't use it for competitive programming, mostly because CP requires you to write lots of code fast, and even if the code has UB, you don't care about that as long as the particular compiler you're using does what you expect it to. Rust is neither fast to write in, nor lets you say "I don't care about UB" (clearly, even wrapping everything in
unsafeis not quite enough).That's an interesting take.
tbh I think this is matter of habit more than anything. Of course you probably would be slower first month after switch, but benefits of having language that does not try to kill you on every corner outweights time spent to learn it
I don't think writing lots of code fast is really important. It saves little time. I think problems of C++ eat much more time on average.
Can you elaborate which problems do you mean? I definitely know a few aspects where Rust is better than C++, but I don't see how they are really applicable for CP, especially, having in mind that a huge part of even high-rated community prefers
printfover debugger in all cases and text editors over IDEs.Don't get me wrong, I like to upsolve problems on Rust, but on more important contests I still stick to C++, because with enough discipline you can write C++ code as you do it in Rust (i.e. always having either one mutable reference or any number of immutable, etc.), but when you need to do something tricky to make your life a little bit easier, you almost always can do that in C++ and in Rust it is often not as easy.
One of such things is that in C++ you can wrap any short, but complex piece of code into a lambda and then use it, but Rust has some obstacles on this path. For example, if you are writing some dp, you may want to write a lambda "please, make sure that this state is computed", but it is impossible in Rust, because it captures dp as mutable. Obviously, you can make a function and pass everything to it, but then it probably would not be short anymore (e.g. if you need to compute sum of products of values from three different dp's as in problem F from the last contest). I also have similar issues when I need to compute a lot of simple things in dfs. Mutable y-combinator is easy in C++, but I simply don't know how to do it in Rust. Another problem is that C++ templates are superior, so for metaprogramming in Rust you have to go to macros earlier and macros code is undebuggable.
forin Rust is much nicer, thoughRecursive lambda in Rust
Yes, it is formally undefined behavior, but I use it extensively and had not had any problems yet
Well, it definitely is a solution, and it is cool that it exists and works, but the fact that it looks messy even to C++ standards just drains all the happiness
But, honestly, I was wondering if it is doable in safe Rust without unreasonable overhead
"Recursive closures" are definitely possible in safe Rust, here's an example: https://pastebin.com/QJ7bJbu5 (snipped from my submission to an AtCoder problem: https://atcoder.jp/contests/abc231/submissions/27948026)
I do admit it can be a tad unwieldy to code on-the-fly though (hence why for most DFS problems, I simply continued using the iterative DFS tricks I picked up from Kotlin to prevent StackOverflowException), but I haven't yet learned how to do a similar thing in C++, so I can't compare.
pastebin is somehow down for me, so I read the AtCoder submission, and, as far as I understood, you use
RefCellto deal with mutability. Although, it is not too much, it is still unreasonable overhead I mentioned.In C++ and for immutable case in Rust you can simply write y-combinator and it will be fine. You can find an implementation for Rust here, for example.
Similar code for C++ works both for mutable and immutable case because C++ does not care, but in Rust replacing
FnwithFnMutdoes not seem at least straightforward (you can read this as "I failed to do that"). Your code overcomes these problems withRefCellthat does all the checks in runtime which is probably still fine, but still carries some overhead with the sole purpose of shutting the compiler up.Oh thanks, I didn't know about Y-combinator, that makes things much cleaner (well, except for the need for either RefCell or pointer-hacks, but it shouldn't be too much of a problem for the majority of the problems I'd use it for)
Not sure I have the ability to actually understand it, but at least it's pretty copy-pastable
What do you mean by "look messy"? Because usage site is not really messy, and why do you care about messiness of your library code during contest? And I do not think there's any real performance overhead
Usage and performance are great, I agree. I meant the implementation. It has
unsafe, UB, macros and some boilerplate all in one place. I don't use prewritten code during a contest except for short (about 70 lines long) template for reading input and multitests, so at the end of the day, I indeed write my library code. It makes a lot of sense when you are mostly competing under ICPC rules, although, now I probably can start building a library.In general, I don't mind the complexity of the solution. I even don't really mind
unsafe, but I don't see any fundamental reasons for its necessity in this case. However, when you have to put up with UB, with things that completely avoidable in C++, like macros killing all the assistance from your IDE and boilerplate, and also withunsafeas the cherry on top of that in return for checks for rare occasions that you messed your references up, it kills all the fun of using Rust.It is necessary here because we need to pass lambda as argument at the same time as we invoke it, hence we have more than 1 mutable reference (which is theoretically UB)
As for other things — macros is not that black of a box for clion now, and c++ templates have same problem. Also we are not only talking about memory safety as applied to CP — amount of sugar that rust gives that is very relevant to CP is staggering
Yes, I agree that this exact solution would not work. However, in fact, what we are trying to achieve is to create an anonymous object that has references to whatever we want to capture and also is able to call itself. Again, I see no fundamental reasons for it to be impossible for mutable references.
Maybe I missed some specific extension for CLion that helps with macros specifically, but currently the way I write macros when I need them looks like
Implement needed functionality for some particular case.
Wrap into macros and generalize using search and replace.
Fix errors that you can't even locate.
Cry if you need to add something later.
C++ template are much more debuggable in that sense. At least, you can read compiler errors and understand them. Errors even in normal Rust are sometimes misleading, but with macros it gets even worse. In general, I believe that in terms of debuggability Rust generics $$$\gg$$$ C++ templates $$$\gg$$$ Rust macros $$$\gg$$$ C++ defines. But in C++ you can do everything you need using only templates, while in Rust you have to occasionally use macros.
And yes, I agree that whenever you don't need anything too complex, using Rust is much more comfortable, except for a few very annoying things like using only
usizeand notisizefor indexing, but, even to this day, C++ offers considerably more capabilitiesThey've added recursive expand which makes stuff way easier to write. But thing is I never needed to write something like that during the contest, and time is not that much of constraint when writing library. I'm not sure if rust or c++ better to use without library, but I do not have this alternative, I have libraries in both of them
why not atcoder-style where you pass one mutable struct?
https://github.com/rust-lang-ja/ac-library-rs/blob/master/src/internal_scc.rs#L60-L79
January 21st is Saturday though
Thanks! I am bad at math. Fixed.
Rust is getting increasingly more popular on CodeForces13 people in #844, 6 in #843 — the same as 7 months ago...
I mean the bigger scale picture. Compared to 5 years ago. And I did not look at the statistics, but just submissions of people I befriend on codeforces.
Well, I had a hard time reading input in Rust without having a prewritten scanner. If the contest doesn't go well, I suggest you to do first several projecteuler.net problems (the rules of PE allow streaming and spoiling first 100 problems wherever you want); or maybe even start the stream earlier and practice them prior to the codeforces contest, as it seems more logical to do it in this order (basic stuff first, reading input second).
I am not a rustacean and speak from the position of somebody who also tried to take a glance at Rust in the recent past.
Great suggestion. Will probably do that. Thanks!
You may want to look into this
Well, it is definitely easier to do competitive programming in Rust when you already have prewritten IO code.
I'd suggest abstracting out all the parsing logic to a separate struct/function, otherwise, there will be too many
unwraps in the code, and it will be very hard to write and read.I solved the same task as you — see the submission 189675119. I have a
Scanner, which has just one methodnext, which returns the next token and parses it to whatever type you want. So if you want to readi32, you can just writelet x:i32 = scanner.next()orscanner.next::<i32>().I'd recommend peltorator to just copy
Scannercode from my submission, and spend time on more interesting parts of Rust instead of parsing :)Your Scanner has a problem, being unusable for interactive problems
Here is a much better one, modified version of which I use all the time and had no problems with.
Though it uses some unsafe, so I did my best to create a better one without unsafe: https://pastebin.com/qRsQwBQe
Also, if you were using clippy, you would notice that
nextis definetly not the best name choice for the method, because it's usually used by iterators and they return a predefined type instead of generic oneYeah, I know my version doesn't work for interactive problems.
The idea was to show a very short implementation, which works in most cases and is understandable even for people, who use Rust for the first time. I definitely can't say the same about the unsafe version you suggested :)
Though the unoptimized version from your first link is pretty good.
I do agree using Clippy is a good practice in general, but in this specific case, it is not so important.
Note: Sorry for being odd one out among all red coders.
Peltora stream about to begin. This stream is going to make or break my Saturday. But very much excited for this. Hope to see some cool stuffs.
Hi,
I certainly agree that Rust is gaining popularity very fast. Here is good resource to start competitive programming in Rust.
Competitive Programming in Rust
It has basic functions at least start Competitive Programming in Rust.
Thank You
bro, you really wanna deal with borrow checker when you're a power user in CP? yeah no, I reckon python is the future.
why this code is failing to solve the problem https://codeforces.net/problemset/problem/1883/C 1883 C. Raspberries
use std::{ collections::VecDeque, fmt, io::{self, BufRead}, str::FromStr, };
struct Scanner { tokens: VecDeque, }
impl Scanner { pub fn new() -> Self { let stdin = io::stdin(); let mut tokens = VecDeque::new(); for line in stdin.lock().lines() { for token in line.unwrap().split_ascii_whitespace() { tokens.push_back(token.to_owned()); } } Self { tokens } }
pub fn next<T: FromStr>(&mut self) -> T where <T as FromStr>::Err: fmt::Debug, { T::from_str(&self.tokens.pop_front().unwrap()).unwrap() }}
fn main() { let mut input = Scanner::new(); let tests: i32 = input.next();
for _ in 0..tests { let n: i32 = input.next(); let k: i32 = input.next(); let mut myvec: Vec<i32> = Vec::new(); let mut mysecondvec: Vec<i32> = Vec::new(); let mut x: i32 = 0; for _ in 0..n { let num: i32 = input.next(); myvec.push(-num % k); } if k == 4 { for i in 0..n { mysecondvec.push(myvec[i as usize] % 2); } mysecondvec.sort(); x = mysecondvec[0] + mysecondvec[1]; myvec.push(x); } let mut min_value = myvec.iter().min().unwrap(); // Added this line to print the minimum value for each test case println!("{}", min_value); }}
I am not sure modulo for negative numbers works the way you think it works
well it did worked for python see R = lambda: map(int, input().split()) t, = R() while t: t -= 1 n, k = R() a = [-x % k for x in R()] print(min(a + [sum(sorted(x % 2 for x in a)[:2])] * (k == 4)))
i think the logic of mod should not change for rust . now see the code and tell me why it is failing i am not able to understand that how the same logic is working for one language could not work for other language .
Python uses different logic for modulo for negative numbers. For python -13 % 5 = 2. For c++, rust, java, etc, -13 % 5 = -3
Thank you , it finally got accepted. I used k — num % k when num % k != 0, and when it was equal to zero, I pushed 0 inside the vector. It got accepted. Thanks
you are funny
it seems like it until you gotta
as usizeas i64andas i321 million timesIf you have a lot of primitive type conversions you likely write non-idiomatic code