Hello Codeforces,

The following is a C++20 user-defined template class modular arithmetics $$$\mod radix$$$, where $$$radix > 1$$$ is a prime number, and all numbers are normalized to the closed interval of non-negative integers $$$[0,radix-1]$$$.

#include <bits/stdc++.h>
using namespace std;
 
template<int radix>
#if __cplusplus > 202002L
requires(radix > 1)
#endif
class mod {
    static inline auto normalize(int64_t num) { 
        const auto r = static_cast<int>(num%radix);
        return r > 0 ? r : r < 0 ? radix+r : 0; }
    int value;
public:
    inline mod(int64_t num = 0): value(normalize(num)) {}
    inline mod(const mod &num) : value(num.value) {}
    inline auto operator()() const { return value; }
    inline auto operator-() const { return mod(radix-value); }
    inline auto operator==(const mod &num) const { return value == num.value; }
    inline auto operator!=(const mod &num) const { return value != num.value; }
    inline auto& operator=(const mod &num) { value = num.value; return *this; }
    inline auto& operator+=(const mod &num) { value = normalize(value+num.value); return *this; }
    inline auto& operator-=(const mod &num) { value = normalize(value-num.value); return *this; }
    inline auto& operator*=(const mod &num) { value = normalize(1ll*value*num.value); return *this; }
    inline auto pow(uint64_t x) const { 
        mod z = 1; 
        for (auto y = *this; x > 0; x >>= 1, y *= y)
            if (x&1) z *= y;
        return z; }
    inline mod& operator++() { value = normalize(value+1); return *this; }
    inline mod& operator--() { value = normalize(value-1); return *this; }
    inline mod operator++(int unused) { const auto previous = *this; ++*this; return previous; }
    inline mod operator--(int unused) { const auto previous = *this; --*this; return previous; }
    inline friend auto operator+(mod a, const mod &b) { return a += b; }
    inline friend auto operator-(mod a, const mod &b) { return a -= b; }
    inline friend auto operator*(mod a, const mod &b) { return a *= b; }
    inline friend auto inv(const mod &num) { return num.pow(radix-2); }
    inline auto& operator/=(const mod &num) { value = normalize(1ll*value*inv(num).value); return *this; }
    inline friend auto operator/(mod a, const mod &b) { return a /= b; }
    inline friend auto& operator>>(istream &stream, mod &num) { 
        int64_t v; stream >> v, num.value = normalize(v); return stream; }
    inline friend auto& operator<<(ostream &stream, const mod &num) { return stream << num.value; } };

The template class can was used successully in 247415519, and can be used as any other shared C++ library template class available in the public domain.

Hello Codeforces,

The following three Kotlin lines:

import java.io.*
val cin = System.`in`.bufferedReader()
val cout = PrintWriter(System.out.bufferedWriter())

along with appropriate function calls were sufficient to achieve significant speed-up to the execution-time of the following problem:

1176D - Recover it!

Check the following accepted submissions:

1. Without fast data input/output 237662785
2. With fast data input/output 237662628

Feel free to use these lines in your Kotlin code, and make sure that cout.flush() is the last statement in your program, unless you are solving an interactive problem in which flushing the data output buffer is required more frequently to interact correctly with the automatic judge.

Best wishes

Hello Codeforces,

I got the following compilation error while using GNU++20 1l.2.0 (64 biy, winlibs) compiler to translate and run a C++ program that contains the following include statement.

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;

|          ^

Has any member of the community encountered this compilation error before and knows how to resolve it?

Thanks in advance for sharing any helpful information.

P.S. The compilation succeeds using GNU++17 7.3.1.

Update

The issue was resolved.

Replacing the statement

#include <bits/extc++.h>

with

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

was accepted by the GNU++20 11.2.0 compiler.

Hello Codeforces,

I am just curious about the reason for the HackerEarth May Circuits '22 to be not held as of today May 31, 2022.

Does anyone know if that is due to some temporary reasons or the HackerEarth team decided to stop organizing this monthly competitive programming event?

Thanks in advance for sharing any information.

Hello Codeforces,

It is sometimes required in competitive programming problems to segment a range defined as [first, last) of indices in a given data container, where first refers to the first element to inspect and last refers to the element past the last element to inspect, into a number of intervals such that all the consecutive elements in any interval have the same value of a particular segmentation function $$$f(x)$$$ whose value depends on the present element $$$x$$$ only, and this value is different from the function value in the intervals before and after such interval if any of them exists.

This blog presents a simple C++ template data structure for such purpose.

The following is the declaration and implementation of the data structure.

template<class ForwardIt, class UnaryFunction>
struct seg: vector<size_t> {
    inline seg(ForwardIt first, ForwardIt last, const UnaryFunction& fun) {
        if (first != last) {
            size_t width = 1; 
            for (auto present_value = fun(*first++); first != last; ++width) {
                const auto next_value = fun(*first++);
                if (next_value != present_value)
                    push_back(width), present_value = next_value, width = 0; }
            push_back(width); } } };

The seg data structure inherits vector<size_t> as a base class to store the range-segmentation results. The data-structure constructor seg(ForwardIt first, ForwardIt last, const UnaryFunction& fun) has three parameters: first and last specify the range [first, last), and fun specifies the segmentation function.

The time-complexity of constructing an object/instance of this data structure should be $$$O((S+T+U).N)$$$, where $$$S$$$, $$$T$$$ and $$$U$$$ are the execution times required to complete the segmentation function call fun(*first), to append an element to the vector using a vector<size_t>::push_back(width) member function call, to increment the iterator first, respectively, and $$$N = last-first$$$ is the range size.

The following are sample applications of this data structure.

1. CodeChef Starter 35: Chef Find XOR Beautiful

2. Codeforces Round #784 (Div. 4): D. Colorful Stamp

Dear Codefoces Members,

I am writing this blog after reading several blogs in this website about events of unfair practices during recent Codeforces contests. I have been fortunate to read a long time ago the following Fairness Charter prepared by the International Fair Play Committee to promote fair practices during sports activities and to keep the spirit of real championship alive.

1. To turn every sports meeting, irrespective of whatever is at stake and its importance, into a privileged moment, a happy event.
2. To conform to the rules and the spirit of the sport I practice.
3. To respect my opponents as I respect myself.
4. To accept the decisions of referees or sports judges well aware that, just like me, they have the right to make mistakes but they do their utmost to avoid them.
5. To avoid malice and aggressiveness in my actions, words and writings.
6. To avoid using tricks or cheating to be successful.
7. To maintain dignity both in case of victory and defeat.
8. To help everyone with my presence, experience and understanding.
9. To assist any sportsman who is injured or whose life is in danger.
10. To be a real sports ambassador, making sure that the above principles are applied in my environment.

I would like to encourage those who have been involved in unfairness acts during the recent contests to read this inspiring Charter carefully, and to strive for abandoning anything which tells them that there is any real gain in unfairness. Let me remind you kindly that there is no real happiness in scoring an offside goal in sports like soccer, even if this unfair goal leads your team to win the world cup.

Please do your best to be patient enough to compete fairly with your fellows, and to use the competitive programming contest event as a good opportunity for improving your skills in problem solving and in computer programming, and as a good opportunity for learning from your fellows and for sharing your experience with them before and after the contest if you are participating in a contest as an individual contestant, not as a team member.

Finally, be sure that real happiness in the pleasant events organized by Codeforces known as competitive programming contests is to solve problems not only as fast as possible, but fairly as well. This can be true for all participants only through your understanding, patience, fruitful cooperation and commitment to fair competition.

Best wishes.

Hello Codeforces Community,

This is an educational blog intended for some newbie and pupil rating members. I assume that members with higher rating and many other members are already aware of its contents. It is well-known that the Time-Limit Exceeded (TLE) Verdict received from the automatic judge in competitive programming contests and practicing using Java language is sometimes not because the computations involved in solving the problem are too time-consuming, but because the data input operations from System.in stream and/or data output operations to System.out stream are not fast enough. The following is a Java 11 simple template for data input-output using InputStreamReader, BufferedReader and BufferedOutputStream library classes.

import java.io.*;
import java.math.*;
import java.util.*;

public final class Main {
	private static final class tokens extends LinkedList<String> {
		tokens(String line) { 
			super(new LinkedList<String>()); 
			for (var token: line.split(" "))
				add(token); } 
		String        nextStr() { return remove(); }
		int           nextInt() { return Integer.parseInt(remove()); } 
		long         nextLong() { return Long.parseLong(remove()); }
		double        nextDbl() { return Double.parseDouble(remove()); } 
		BigInteger nextBigInt() { return new BigInteger(remove()); } }
	private static tokens nextLine(BufferedReader cin) { 
		String line = null;
		try { line = cin.readLine(); }
		catch (IOException e) { e.printStackTrace(); }
		return new tokens(line); }
	private static byte[] to_bytes(String s)           { return s.getBytes(); }
	private static byte[] to_bytes(Integer x)          { return to_bytes(x.toString()); }
	private static byte[] to_bytes(Long x)             { return to_bytes(x.toString()); }
	private static byte[] to_bytes(String f, Double x) { return to_bytes(String.format(f,x)); }
	private static byte[] to_bytes(BigInteger x)       { return to_bytes(x.toString()); }
	private final static byte[] space = to_bytes(" ");
	private final static byte[] endl  = to_bytes("\n");
	public static void main(String[] args) throws IOException {
		final var cin  = new BufferedReader(new InputStreamReader(System.in));
		final var cout = new BufferedOutputStream(System.out);
		cout.flush(); } }

The program declares a queue-based tokens class to parse multiple data items in the same line and push them to the rear of the data queue using LinkedList utility object. The next...() member function, where ... stands for the data-item type, is used to get the next data item from the queue front. Helper functions to_bytes(... x), where ... stands for the data-item type, are declared to convert data item to byte[] array that can be written to the buffered output stream using BufferedOutputStream::write(byte[]) function call. It is always necessary to call the BufferedOutputStream::flush() member function before quitting from the main() function, so as to flush the buffered output stream by sending its contents to System.out.

The following is the main() function has been used for solving 1100C - NN and the Optical Illusion based on this template program.

    public static void main(String[] args) throws IOException {
        final var cin  = new BufferedReader(new InputStreamReader(System.in));
        final var cout = new BufferedOutputStream(System.out);
        final var input = nextLine(cin);
        final var n = input.nextInt();
        final var r = input.nextInt();
        cout.write(to_bytes("%.7f",r/(1.0/Math.sin(Math.PI/n)-1.0)));
        cout.flush(); }

Note that writing floating-point data items requires an additional format string parameter to specify the number of decimal digits after the decimal floating point.

References

1. Fast I/O in Java in Competitive Programming

2. Fast I/O In Java For Competitive Programming

3. Fast Output in Java

A GitHub.com version of this blog can be found in the following link: Fast data input-output for competitive programming in Java 11.

Your constructive comments and feedback are welcome.

Update

The following is another example for the template program: Submissions for 1600J - Robot Factory which use the same code except for the input-output streams.

1. TLE at 1000 ms using Scanner and System.out: 136775503

2. AC with 998 ms using Scanner and BufferedOutputStream: 136775338

3. AC with 405 ms using BufferedReader and BufferedOutputStream: 136742083

Hello Codeforces Community,

In case that some members have not checked yet the new bitwise function templates in C++20 STL bit header, the following are the most relevant to competitive programming.

1. constexpr bool has_single_bit(T x): finds if $$$x$$$ is a positive integer $$$2^p$$$, for some integer $$$p \geq 0$$$.
2. constexpr T bit_ceil(T x): finds the smallest integer $$$2^p \geq x$$$ for some integer $$$p \geq 0$$$.
3. constexpr T bit_floor(T x): finds the largest integer $$$2^p \leq x$$$ for some integer $$$p \geq 0$$$.
4. constexpr T bit_width(T x): finds the smallest number of bits needed to represent $$$x$$$.
5. constexpr T rotl(T x, int s): finds the result of bitwise cyclic left-rotation of $$$x$$$ by $$$s$$$ positions.
6. constexpr T rotr(T x, int s): finds the result of bitwise cyclic right-rotation of $$$x$$$ by $$$s$$$ positions.
7. constexpr int countl_zero(T x): finds the number of consecutive 0 bits in $$$x$$$, starting from the most significant bit.
8. constexpr int countl_one(T x): finds the number of consecutive 1 bits in $$$x$$$, starting from the most significant bit.
9. constexpr int countr_zero(T x): finds the number of consecutive 0 bits in $$$x$$$, starting from the least significant bit.
10. constexpr int countr_one(T x): finds the number of consecutive 1 bits in $$$x$$$, starting from the least significant bit.
11. constexpr int popcount(T x): finds the number of 1 bits in $$$x$$$.

All function declarations are preceded by template<class T>, where T has to be bound at compile-time to unsigned-integer data-type with 8, 16, 32, or 64-bit width. Note that calling any of these functions with signed-integer data-type argument $$$x$$$ produces a compilation error, as it violates the unsigned-integer data-type requirement.

The following is an example program to test the operation of these functions.

#include <bits/stdc++.h>
#define apply1(f,x)   cout << #f << "(x) = " << uint64_t(f(x)) << endl
#define apply2(f,x,s) cout << #f << "(x,s) = " << uint64_t(f(x,s)) << endl
using namespace std;

template<class T>
inline void test_bit(T x, int s) {
    cout << "test_bit: x = " << bitset<sizeof(T)<<3>(x) << ", s = " << s << endl << endl;
    apply1(has_single_bit<T>,x),
    apply1(bit_ceil<T>,x),
    apply1(bit_floor<T>,x),
    apply1(bit_width<T>,x),
    apply2(rotl<T>,x,s),
    apply2(rotr<T>,x,s),
    apply1(countl_zero<T>,x),
    apply1(countl_one<T>,x),
    apply1(countr_zero<T>,x),
    apply1(countr_one<T>,x),
    apply1(popcount<T>,x); }

int main() {
    uint16_t x; int s;
    cin >> x >> s, test_bit(x,s); 
    return 0; }

The following is the test program output for x = 11 and s = 1.

test_bit: x = 0000000000001011, s = 1

has_single_bit<T>(x) = 0
bit_ceil<T>(x) = 16
bit_floor<T>(x) = 8
bit_width<T>(x) = 4
rotl<T>(x,s) = 22
rotr<T>(x,s) = 32773
countl_zero<T>(x) = 12
countl_one<T>(x) = 0
countr_zero<T>(x) = 0
countr_one<T>(x) = 2
popcount<T>(x) = 3

=====
Used: 0 ms, 1188 KB

More details can be found in the C++20 bit header documentation.

Finally, it should be noted that the only difference between interpreting a $$$w$$$-bit word $$$X_w = [x_{w-1},\ldots,x_1,x_0]$$$, where $$$x_i \in \{0,1\}$$$, as an unsigned-integer or as signed-integer is the multiplication factor of the most signification bit $$$x_{w-1}$$$, called the sign-bit when $$$X_w$$$ is interpreted as a signed integer, as it can be proved that $$$X_w < 0$$$ when $$$x_{w-1} = 1$$$ for any positive word-length $$$w \geq 1$$$.

In particular, the value of $$$X_w$$$ as an unsigned-integer can be expressed as:

$$$X_w = x_{w-1} 2^{w-1} + \sum\limits_{i = 0}^{w-2} x_i 2^i$$$

On the other hand, the value of $$$X_w$$$ as a signed-integer can be expressed as:

$$$X_w = -x_{w-1} 2^{w-1} + \sum\limits_{i = 0}^{w-2} x_i 2^i$$$

Therefore, $$$X_w \geq 0$$$ when $$$x_{w-1} = 0$$$, and the value of signed-integer $$$X_w$$$ in this case is equal to the value of the unsigned-integer $$$X_{w-1} = [x_{w-2},\ldots,x_1,x_0]$$$.

Hello Codeforces,

I found this hard practice problem H — Unpredictable Array at CodeChef which has 0 successful submissions!

The following is my C++ map-based solution which got TLE. I tried to run this solution using the Codeforces Custom Test with the maximum data size, and the Codeforces judge reported used time 1170 msec. which is within the 2 sec. time-limit of the problem.

I would be grateful for plausible explanation about this discrepancy.

Hello Codeforces Community,

Congratulations for the installation of C++20 automatic judge. A word of gratitude and appreciation is due to the Codeforces administration team for their endeavors to keep Codeforces up-to-date with the latest developments in C++.

The following program is an example for one of the new features introduced in C++20, __cpp_aggregate_paren_init.

#include <bits/stdc++.h>
using namespace std;

struct FourDPoint {
    int w, x, y, z;
    inline ostream& write(ostream& os) const {
        return os << '(' << w << ',' << x << ',' << y << ',' << z << ')'; }
    inline friend ostream& operator<<(ostream& os, const FourDPoint& p) {
        return p.write(os); } };

template<class value_type, size_t size>
struct Array: array<value_type,size> {
    inline ostream& write(ostream& os) const {
        os << '[' << this->front();
        for (size_t i = 1; i < size; ++i)
            os << ',' << this->at(i);
        return os << ']'; }
    inline friend ostream& operator<<(ostream& os, const Array& p) {
        return p.write(os); } };

int main() {
    const FourDPoint p(1,2,3,4);
    const Array<int,4> q({5,6,7,8});

    cout << "p = " << p << endl << "q = " << q << endl;

    return 0; }

The following is the expected output of this program.

This program produces a compilation error when compiled using GNU++17 9.2.0 compiler, but can be compiled successfully using GNU++20 11.2.0 compiler. The C++20 compiler translates that statement const FourDPoint p(1,2,3,4) into initializing the data members w, x, y, z of the constant object p to 1, 2, 3, and 4, respectively. Similarly, the compiler passes the initialization list {5,6,7,8} to the constructor of the base class array<int,4>, even though both classes FourDPoint and Array<int,4> do not have explicit class constructors.

Hello Codeforces,

It is sometimes required in competitive programming contests, specially in long-time challenges when there is enough time to trace the program execution behavior at run-time before submitting it to the automatic judge, to track the passed arguments and return value of some C++ function(s). This blog presents a simple C++ tracer class for such purpose.

The following is the class declaration and implementation.

#ifdef TRACE
#include <iostream>
#include <sstream>
class tracer_t {
    int trace_depth = 0;
    inline void prefix(int depth, int line, const string& fun) {
        cout << string(depth,' ') << depth << ":LINE " << line << ": " << fun  << "("; }
    inline void suffix() { cout << ") "; }
    template<class Arg, class... Args>
    inline void suffix(const Arg& arg, const Args&... args) {
        if (cout << stringify(arg), sizeof...(Args) > 0)
            cout << ",";
        suffix(args...); }
    inline void pause() { cout << endl, cin.get(); }
public:
    template<class Arg>
    inline string stringify(const Arg& arg) {
        stringstream ss;
        ss << arg;
        const auto s = ss.str();
        return is_same<Arg,string>::value ? "\""+s+"\"": s; }
    template<class... Args>
    inline void begin(int line, const string& fun, const Args&... args) {
        prefix(++trace_depth,line,fun), suffix(args...), cout << "called", pause(); }
    template<class... Args>
    inline void trace(int line, const string& fun, const Args&... args) {
        prefix(trace_depth,line,fun), suffix(args...), pause(); }
    template<class Ans, class... Args>
    inline Ans end(int line, const string& fun, const Ans& ans, const Args&... args) {
        prefix(trace_depth--,line,fun), suffix(args...), cout << "return value = " << ans, pause();
        return ans; } } tracer;
#define db(arg) string(#arg)+" = "+tracer.stringify(arg)
#define tr_begin(...) tracer.begin(__LINE__,__FUNCTION__,__VA_ARGS__)
#define tr(...)       tracer.trace(__LINE__,__FUNCTION__,__VA_ARGS__)
#define tr_end(...)   tracer.end(__LINE__,__FUNCTION__,__VA_ARGS__)
#else
#define tr_begin(...)
#define tr(...)
#define tr_end(ans,...) ans
#define db(arg) arg
#endif // TRACE

If the macro TRACE is defined before this tracer code, the following trace operations are enabled using Variadic Macros and Variadic Function Templates.

1. tr_begin(...) macro call increments the trace depth, and then prints the passed arguments.
2. tr(...) macro call prints the passed arguments without updating the trace depth.
3. tr_end(...) macro call prints the passed arguments, decrements the trace depth, and returns the first argument. This call can be used as the return value of the traced function.

Each traced function should have a tr_begin(...) macro call at the beginning of the function block, a tr_end(...) macro call at the end of the function block, and zero or more tr(...) macro call(s) inside the function block.

If the TRACE macro is undefined before the tracer code, the aforementioned trace operations are disabled.

The following is an example program to test the functionality of the tracer by tracking the execution of the recursive algorithm for computing the factorial function $$$n!$$$.

#define TRACE

// The tracer code should be placed here or included from the header file

#include <bits/stdc++.h>
using namespace std;

int factorial(int);

int factorial(int n) {
    tr_begin(db(n));
    const int ans = n > 1 ? n*factorial(n-1) : 1;
    return tr_end(ans,db(n)); }

inline istream& skip_endl(istream &is) {
    return is.ignore(numeric_limits<streamsize>::max(),'\n'); }

int main() {
    int n;
    cin >> n >> skip_endl, assert(n >= 0), cout << factorial(n);
 	return 0; }

The following is the standard output printed results of the example program when the TRACE macro is defined.

5
 1:LINE 9: factorial("n = 5") called

  2:LINE 9: factorial("n = 4") called

   3:LINE 9: factorial("n = 3") called

    4:LINE 9: factorial("n = 2") called

     5:LINE 9: factorial("n = 1") called

     5:LINE 11: factorial("n = 1") return value = 1

    4:LINE 11: factorial("n = 2") return value = 2

   3:LINE 11: factorial("n = 3") return value = 6

  2:LINE 11: factorial("n = 4") return value = 24

 1:LINE 11: factorial("n = 5") return value = 120

120

Your constructive comments and feedback are evermore welcome.

Update

• The following are interesting related blogs, shared thankfully by other Codeforces members.

  1. darkkcyan, My CP debugging template, shared by jalsol.
  2. rachitiitr, C++ Trick — Easy Debugging / Logging, shared by Manan_shah.

• The trace macros trace_call(...) and trace_ret(...) were renamed to tr_begin(...) and tr_end(...), respectively, and a third macro tr(...) was added. The value of the built-in macro __LINE__ was also passed to each tracer object public member function call so as to identify the location of the trace point inside the traced function.

• The macro db() by darkkcyan was adopted. If the macro TRACE is defined, then db(arg) produces string(arg)+" = "+tracer.stringify(arg). Any variadic argument of the macro calls tr_begin(...), tr(...), or tr_end(ans,...) can be passed as either arg or db(arg)

The following is the GitHub archive of the tracer code.

tracer@GitHub

Hello Codeforces,

I am a 56-year old life-long learner and computer-programming lover with PhD degree in Electronics and Electrical Communications Engineering from Cairo University, Egypt, and with research interest in VLSI CAD algorithms, computer architecture, digital signal and image processing. I joined Codeforces five years ago to encourage my son during his first year in college, and I participate almost regularly in long-time competitive programming challenges as time permits.

I participated last week in HackerEarth September Circuits '21 Long-Time Contest that ended yesterday, and I reached the 4th rank on the Leaderboard of the Contest. The approximate problem in the Contest was a variant to the well-known Traveling Salesman Problem (TSP). To my surprise, the first runner-up commented about four days ago that the checker program of this problem was broken and it accepted invalid solutions. As such, only two contestants managed to write wrong solutions that exploited the incorrectness of the checker in getting the highest possible score, while other contestants including me who wrote correct solutions assuming that the checker program would reject invalid solutions did not reach 1% of the score of the wrong solutions.

I am writing this blog to urge the HackerEarth team whose members announce in Codeforces invitations to regular HackerEarth Contests to review thoroughly the checker programs of the problems posted in its regular contests. The issue of broken checker took place several times in the past few months Circuits long-time Contests without any apology and without any announcement that corrective procedure would be pursued to be more sure that future contests do not include broken checker programs.

Thanks in advance for the constructive feedback and response.

Hello Codeforces,

This is an update to an old blog I wrote 15 months ago about measuring elapsed time between two events in C++ programs on real-time scale such as milliseconds using the std::chrono library classes and functions.

The following is the class declaration and implementation.

using namespace std::chrono;
template<class clock, class units = milliseconds>
class Timer {
    const units T; const time_point<clock> t0; bool stopped = false;
public:
    inline Timer(const units interval) :  T(interval), t0(clock::now()) {}
    inline units elapsed_time() const { return duration_cast<units>(clock::now()-t0); }
    inline bool expired() { return stopped ? true: elapsed_time() < T ? false: (stopped = true); } };

The template has two parameters: clock and units corresponding to the used std::chrono clock and time units of the timer interval, respectively. The value passed to clock should be high_resolution_clock, system_clock, or steady_clock. The default value for units is milliseconds. Other possible values for units include nanoseconds, microseconds, etc. check chrono::duration for more details.

The class has three public member functions:

Timer(const units interval);
units elapsed_time() const;
bool expired();

The first public member function Timer(const units interval) is the class constructor used to create a timer object. The second function elapsed_time() returns the elapsed time since the creation of the object. The third function expired() returns false if such elapsed time has not reached interval yet; otherwise, the function returns true.

The following is an example program to test the functionality of the class by creating a timer object with 1.5 sec interval.

#include <bits/stdc++.h>

// The C++ template class is included here

using namespace std;

int main() {
	const auto T = 1500ms;
	Timer<high_resolution_clock> timer(T); 
	int iterations = 0;
	while (!timer.expired())
		iterations++;
	const double interval = duration_cast<nanoseconds>(T).count();
	cout << "average iteration time = " << interval/iterations << " nsec."; 
	return 0; }

The following is the stdout printed results of the example program.

average iteration time = 19.0212 nsec.

Your constructive comments and feedback are welcome.

Update: The third parameter value_t was removed from the template to make the class declaration more compact.

Hello Codeforces,

I got the following compilation error

Cannot compile file:
In file included from C:/Programs/msys2-mingw64-9/include/c++/9.2.0/pstl/parallel_backend.h:14,
                 from C:/Programs/msys2-mingw64-9/include/c++/9.2.0/pstl/algorithm_impl.h:25,
                 from C:/Programs/msys2-mingw64-9/include/c++/9.2.0/pstl/glue_execution_defs.h:52,
                 from C:/Programs/msys2-mingw64-9/include/c++/9.2.0/execution:32,
                 from program.cpp:2:
C:/Programs/msys2-mingw64-9/include/c++/9.2.0/pstl/parallel_backend_tbb.h:19:10: fatal error: tbb/blocked_range.h: No such file or directory
   19 | #include <tbb/blocked_range.h>

when I added the include command #include <execution> to use the execution::par constant.

128886532

The program compiles successfully on my local computer. Am I missing something that can fix this compilation error?

Hello Codeforces,

I posted this blog in CodeChef Discussion Forum few hours ago. I have just thought about posting it here for those interested in logic programming. CodeChef is distinguished in having Prolog among the available programming languages in its automatic judge system for competitive programming and problem solving.

I am a life-long lover for programming in Prolog, even though Prolog is not commonly used for competitive programming purposes. I noticed that the following sample solution for Prolog code does not identify explicitly the specific requirement for submitted Prolog code.

Prolog Sample Solution

In particular, the automatic judge requires that the entry point of the solution is predicate program/0. The following are sample accepted Prolog solutions.

1. ATM

2. Life, the Universe, and Everything

3. Factorial

Lines 3-22 in these accepted submissions include helper predicates for reading input data from the standard input stream.

CodeChef automatic judge uses presently version 7.2.3 of the free SWI-Prolog compiler, whose documentation is available online. The automatic judge returns a compilation error message if the submitted Prolog code does not include predicate program/0.

Learn Prolog Now is a good source for life-long learners who wish to learn about Prolog.

Hello Codeforces,

It is sometimes required in competetive programming problems to use fast data input/output and/or read and write problem data from and to data files. It is well known that the C++ standard libray functions std::ios_base::sync_with_stdio(), std::basic_io::tie(), and std::freopen() can be used to peform the sought input/output initializtion. The following is a C++ io_init class that simplifies this initialization by encapsulating it inside public class constructors.

#include <bits/stdc++.h>
using namespace std;

class io_init {
    struct fast { fast() { ios_base::sync_with_stdio(false), cin.tie(nullptr); } } io;
    void reopen(const string &file_name, const char *mode, FILE *stream) {
        if (freopen(file_name.c_str(),mode,stream) == nullptr) 
            throw runtime_error("freopen() failed: cannot open file "+file_name); }
public:
    io_init() {}
    io_init(const string &data) { reopen(data+".in","r",stdin), reopen(data+".out","w",stdout); } };
		    
int main() { 
     io_init(); // io_init("data"); 
    // solution
}

The first class constructor without parameter initializes fast input/output by creating the io instance of the private data structure fast. The second class constructor with string data paremeter performs the same operation, and then initializes the data input/output to read data from input file data+".in" and write results to output file data+".out". The private class member function reopen() throws a run-time error exception if the freopen() function call returns nullptr.

Your constructive comments and feedback are welcome and appreciated.

UPDATE

The following alternative to use a fuction call instead of using public class constructors is favored by Actium.

#include <bits/stdc++.h>
using namespace std;

void io_init(const string &data = "") { 
    const auto reopen = [data](const string &ext, const char *mode, FILE *stream) {
        const string file_name = data+"."+ext;
        if (freopen(file_name.c_str(),mode,stream) == nullptr)
            throw runtime_error("freopen() failed: cannot open file "+file_name); };
    if (ios_base::sync_with_stdio(false), cin.tie(nullptr), not data.empty())
        reopen("in","r",stdin), reopen("out","w",stdout); }
		    
int main() {
    io_init(); // io_init("data");
}

A third alterntative (favored by spookywooky) that does not require a function call to be included in the main() function is to declare io_init as a named lambda expression as follows.

#include <bits/stdc++.h>
using namespace std;
     
const auto io_init = [](const string &data = "") {
    const auto reopen = [data](const string &ext, const char *mode, FILE *stream) {
        const string file_name = data+"."+ext;
        if (freopen(file_name.c_str(),mode,stream) == nullptr)
            throw runtime_error("freopen() failed: cannot open file "+file_name); };
    if (ios_base::sync_with_stdio(false), cin.tie(nullptr), not data.empty())
        reopen("in","r",stdin), reopen("out","w",stdout); 
        return 0; } (); // ("data");
    
int main() {
    // solution
}

A fourth alterntative and perhaps the simplest way to initialize data input/output files for read/write is to create std::ifsteam and std::ofstream objects. Names other than cin and cout should be used for the created object if using namespace std; is part of the program so as to avoid name redeclaration errors.

#include <bits/stdc++.h>
using namespace std;
     
ifstream  i_data("data.in");
ofstream  o_data("data.out");

#define cin  i_data
#define cout o_data

int main() {
    
   int a, b; 

   cin >> a >> b;        // read (a) and (b) from file data.in

   cout << a+b << endl;  // write (a+b) to file data.out
}

Hello Codeforces,

It is sometimes required in competitive programming problems at run-time to measure elapsed time between two events on a real-time scale such as milliseconds. It is possible in C++ to do that using the std::chrono library classes and functions. The following is a C++ timer class that simplifies doing this operation.

#include <bits/stdc++.h>
using namespace std;
using namespace chrono;

class timer: high_resolution_clock {
    const time_point start_time;
public:
    timer(): start_time(now()) {}
    rep elapsed_time() const { return duration_cast<milliseconds>(now()-start_time).count(); } };

The timer class inherits the base class std::chrono::high_resolution_clock. A private std::chrono::time_point constant variable start_time is used to store the initial point of time at which the timer object was created using the class constructor function. The class features a constant public member function elapsed_time() whose call returns a non-negative integer which measures the elapsed time in milliseconds since the creation of the timer object.

The following is a sample example for using the timer class.

const int T = 1000;
timer t; // create a timer object

int main() {
    while (t.elapsed_time() < T) {
        // do something
    }
}

Your constructive comments and feedback are welcome and appreciated.

Hello Codeforces,

It is well-known that C++ Input/output manipulators such as fixed, setprecision, endl, etc. are helper functions that serve as user-friendly control commands to input/output streams.

An input-stream command that is necessary but not common in competitive programming is to discard all characters until and including the new-line character. An example for this issue is the following HackerEarth problem. Although the problem is very easy, its data-input invovles a trick that the input string in each line can include a space character as a part of the string.

Using the function call std::getline(cin,s) to read the line which includes space characters right after reading the number of test cases using the input command cin >> t causes the first call of std::getline(cin,s) to read an empty string, as the new-line character at the end of the first line which contains the number of test cases would have not been read yet.

It is possible to use an extra call to std::getline(cin,s) to solve this issue, but a more elegant solution is to declare and use a simple C++ input-stream manipulator whose purpose is to disard the new-line character using a call to the standard function std::istream::ignore.

The followng is the one-line code of the skip_endl input-stream manipulator.

#include <bits/stdc++.h>
using namespace std;

inline istream& skip_endl(istream &is) { return is.ignore(numeric_limits<streamsize>::max(),'\n'); }

And the following is a simple example for using it.

inline string solve(const string &s) {
    string t;
    // code to convert each character in string (s) into its equivalent character(s) 
    // in string (t) should be written here
    return t; }

int main() {
    int t; string s; 
    ios_base::sync_with_stdio(0), cin.tie(0), cin >> t >> skip_endl; 
    while (t--) 
        getline(cin,s), cout << solve(s) << '\n'; }

Your constructive comments and remarks are welcome.

Stay safe, and keep the good work going.

P.S. HackerRank default C++14 code in practice problems often includes the explicit command cin.ignore(numeric_limits<streamsize>::max(),'\n') for the same purpose.

Hello Codeforces,

I have just been practicing during final hour of the open-hacking phase of yesterday's Div. 4 round, when I noticed that someone has just successfully hacked his/her own solution submitted during the contest!

Is there any reasonable explanation for doing that?

Hello Codeforces,

Hope that you are all safe and physically distant enough to avoid COVID-19 infection.

Has anyone seen the strange Verdict of the following submission before?

79000718

Hello Math lovers,

The following is a C++ data structure whose constructor uses arithmetic difference equations of the form $$$f(n+1)-f(n)$$$ to generate all squared integers up to a given upper bound $$$N$$$ without multiplication.

struct squares: std::vector<int64_t> {
    squares(int64_t N) {
        for (int64_t f = 0, g = 1; f <= N; ++g)
            push_back(f), f += g++; } };

It is well known in arithmetics that if $$$f(n) = n^2$$$ and $$$g(n) = 2n+1$$$, then $$$f(n+1) = f(n)+g(n)$$$ and $$$g(n+1) = g(n)+2$$$. The initial state for the iterative algorithm is $$$f(0) = 0$$$ and $$$g(0) = 1$$$.

Alternatively, squared integers up to $$$N$$$ could have been generated using multiplication directly without using difference equations.

struct direct_squares: std::vector<int64_t> {
    direct_squares(int64_t N) {
        for (int64_t f, n = 0; f = n*n, f <= N; ++n)
            push_back(f); } };

The following is the C++ program written to compare the performance of both data structures.

using Clock = std::chrono::high_resolution_clock;
using Time  = std::chrono::time_point<Clock>;
inline Time Now() { return Clock::now(); }
template<class T> 
inline int64_t msec(T t) { 
    return std::chrono::duration_cast<std::chrono::milliseconds>(t).count(); }

inline std::string type_name(const std::string &s) {
    int i = 0; 
    while (isdigit(s[i]))
        ++i;
    return s.substr(i); }
    
template<class T>
void test() {
    const Time initial_time = Now(); 
    const T s(1e14); 
    const int64_t t = msec(Now()-initial_time); 
    const auto name = type_name(std::string(typeid(T).name())); 
    std::cout << "struct " << name << ": elapsed time " << t << " msec.\n"; }
    
int main() { 
    test<squares>(), 
    test<direct_squares>(); }

The following is the results of running the performance evaluation program.

A. Using G++14 6.4.0

struct squares: elapsed time 110 msec.
struct direct_squares: elapsed time 112 msec.

=====
Used: 218 ms, 197032 KB

B. Using G++17 7.3.0 (32-bit)

struct squares: elapsed time 121 msec.
struct direct_squares: elapsed time 93 msec.

=====
Used: 234 ms, 197040 KB

C. Using G++17 9.2.0 (64-bit)

struct squares: elapsed time 121 msec.
struct direct_squares: elapsed time 94 msec.

=====
Used: 218 ms, 198056 KB

Hello Codeforces,

I stopped using Code::Blocks IDE in my local computer recently due to some issue in compilation and debugging. I mostly use Ideone.com online compiler presently. I use the Secret option by default, which should make my code available only to those whom I choose to share the link. I also use the Custom Invocation option in Codeforces sometimes.

My question is: Should I trust that the Secret option in Ideone.com is secure enough to make sure that no one can get the code without permission? If not, what would be the most reliable secure online C++ compiler that you recommend?

Thanks in advance for sharing your knowledge and experience.

Hello C++ learners in Codeforces,

The following is a tutorial C++ class class tutorial_t: vector< T > that illustrates using the standard library function templates std::lower_bound and std::upper_bound.

Tutorial C++ Class

The C++ class inherits the base class vector< T > and generalizes the example given in

1. www.cplusplus.com/reference/algorithm/lower_bound

2. www.cplusplus.com/reference/algorithm/upper_bound

to demonstrate using both function templates for an arbitrary unsorted input array of size n, and an arbitrary value val. The item type T should be instantiated in line 5. For example, typedef double T; allows illustrating the result of searching for the lower-bound and upper-bound in a sorted array of floating-point numbers. Furthermore, standard assert( int expression ) C macro calls are used to illustrate invariant expressions that are guaranteed to be true for any test case.

UPDATE The data item typename parameter T has been removed from the class declaration so as to allow using a single member function example to illustrate both std::lower_bound and std::upper_bound functions. The corresponding function calls are passed to the example function as lambda expressions.

P.S. Downvoters are invited to share their constructive feedback fairly if they can express what they don't like about this blog, and they care to help others and have more time than the time spent to click the dislike voting button. They do not have to create other accounts in Codefores to do that.

In matrix theory, a lower-triangle/upper-triangle matrix is a special n × n square matrix where its items above/below the main diagonal are zeros, and therefore at most of its items are non-zeros. Formally, a lower-triangle matrix A satisfies the condition a_i, j = 0 if i < j, and an upper-triangle matrix A satisfies the condition a_i, j = 0 if i > j, where i is the row index, j is the column index, and 1 ≤ i, j ≤ n.

The following are simple and memory-efficient C++ templates for lower-triangle and upper-triangle matrices that allocate dynamically at run-time using the vector::resize() STL member function the size of each row to store only the non-zero items. This can be useful in saving about half the memory size of the full square matrix when n is large. Individual non-zero items are updated in both templates using set() member function, and the value of an individual zero/non-zero item is read using get() member function.

#include <bits/stdc++.h>

using namespace std;

template< typename T > struct lower_triangle: vector< vector< T > >
{
    lower_triangle( size_t n )
    {
        for( size_t row_size = 1; row_size <= n; row_size++ )
            this->emplace_back(), this->back().resize( row_size );
    }

    void set( size_t i, size_t j, T k )
    {
        assert( i >= j and i >= 1 ), this->at( i - 1 ).at( j - 1 ) = k;
    }

    T get( size_t i, size_t j ) const
    {
        return ( i >= j and i >= 1 ) ? this->at( i - 1 ).at( j - 1 ) : 0;
    }
};

template< typename T > struct upper_triangle: vector< vector< T > >
{
    upper_triangle( size_t n )
    {
        while( n > 0 )
            this->emplace_back(), this->back().resize( n-- );
    }

    void set( size_t i, size_t j, T k )
    {
        assert( j >= i and i >= 1 ), this->at( i - 1 ).at( j - i ) = k;
    }

    T get( size_t i, size_t j ) const
    {
        return ( j >= i and i >= 1 ) ? this->at( i - 1 ).at( j - i ) : 0;
    }
};

The following is a sample program that illustrates using these C++ templates.

int main()
{
    ios_base::sync_with_stdio( false ), cin.tie( nullptr ), cout.tie( nullptr );

    int n; cin >> n; lower_triangle< int > L( n ); upper_triangle< int > U( n );

    for( int i = 1; i <= n; i++ )
    {
        for( int j = 1, k = i; j <= i; j++, k++ )
            L.set( i, j, k );

        for( int j = i, k = 2 * i - 1; j <= n; j++, k++ )
            U.set( i, j, k );
    }

    for( int i = 1; i <= n; i++, cout << endl )
        for( int j = 1; j <= n; j++ )
            cout << L.get( i, j ) << ' ';

    cout << endl;

    for( int i = 1; i <= n; i++, cout << endl )
        for( int j = 1; j <= n; j++ )
            cout << U.get( i, j ) << ' ';
}

UPDATE

The following is an alternative approach for implementing the C++ templates using one-dimensional arrays based on the constructive comment from f2lk6wf90d. Performance analysis should compare the average execution time and memory requirements of both approaches. A word of gratitude is due to tryhard for recommending this modest blog.

inline size_t C2( size_t n ) { return n * ( n - 1 ) / 2; }

template< typename T > struct lower_triangle: vector< T >
{
    lower_triangle( size_t n )
    {
        this->resize( C2( n + 1 ) );
    }

    void set( size_t i, size_t j, T k )
    {
        assert( i >= j and i >= 1 ), this->at( C2( i ) + j - 1 ) = k;
    }

    T get( size_t i, size_t j ) const
    {
        return ( i >= j and i >= 1 ) ? this->at( C2( i ) + j - 1 ) : 0;
    }
};

template< typename T > struct upper_triangle: vector< T >
{
    size_t N, P;

    upper_triangle( size_t n ) : N( n ), P( n + 1 )
    {
        this->resize( C2( P ) );
    }

    void set( size_t i, size_t j, T k )
    {
        assert( j >= i and i >= 1 );  this->at( C2( P - i ) + N - j ) = k;
    }

    T get( size_t i, size_t j ) const
    {
        return ( j >= i and i >= 1 ) ? this->at( C2( P - i ) + N - j ) : 0;
    }
};

The following submission 52361614 contains a user-defind C++ class modulo for () modular arithmetic, where P is a prime number and all numbers are normalized to the interval [0, P - 1]. The modular division operation y / x is performed by means of multiplying the modulo number y times the modular multiplicative inverse of x computed using the modular power operator x^p. The class includes another class modulo::factorial for computing modular factorials n! and modular binomial coefficients m-out-of-n.

The C++ class can be used by Codeforces as any other shared library in the public domain.

Thank you.