Home

Challenges

TODO List

Find strong math proofs for solutions of the following problems:

• Timus 1494
• Timus 1725
• Timus 1222
• Timus 2000

Rust notes

Output formatting

Printing floating point numbers with fixed precision:

println!("{:.4}", 0.01); // "0.0100"

Printing numbers with leading zeroes:

println!("{:0>4}", 19); // "0019"

More information on formatting is in the std::fmt docs.

C++ notes

Output formatting

Setting fixed precision for floating point numbers on cout:

#include <iostream>
#include <iomanip>
cout.setf(ios::fixed);
cout.precision(10);
cout << number;
// or
cout << fixed << setprecision(4);
cout << number;

Setting fixed width buffer with filling on cout:

#include <iostream>
#include <iomanip>
cout.width(5);
cout.fill('x');
cout << something;
// or
cout << setw(2) << setfill('0') << something;

Note: The buffer width will be reset to 0 after each output!

Algorithms notes

Arrays

• Majority element can be found in O(n) using Boyer-Moore algo (called MJRTY). See Timus 1510 and its solution.

Graphs

• Shortest cycle can be found in O(n^3) using modification of Floyd-Warshall algo to find all cycles of form ... -> a -> k -> b -> ... where path from a to b is the shortest one consisting of vertices 1 .. k - 1 only. The idea was found in this Quora answer. See my Timus 1004 problem solution for the implementation.