KACTL ModMul. It says that it runs around 2x faster than naive

(__int128_t)a * b % M

When I ran my benchmarks with -O2, the results were similar. Am I mistaken?

Take a look at these two submissions

93514862, 93514890

The only difference between these two was that the data types for variables $$$n, k$$$, and vectors $$$a, hld1, hld2$$$. Instead of having them be long doubles, they were int. Now, look at the execution time! The difference is huge! The one with the ints has around 12 times better time than the one with long doubles! I knew that working with floats led to higher constant factors but didn't know that it would be that big.

For a lot of us, when we are introduced to a new concept, trick, or algorithm, it would be easier to learn if the editorialists would provide sample codes using the method explained. This would be very beneficial to us beginners and wouldn't take much effort. Please consider my request.

[](https://imgur.com/a/hACTK4B)

You are given a number $$$n$$$ and a number $$$m$$$ and an array $$$a$$$ of $$$n$$$ numbers and 1 type of query. All of the numbers below are 0 based indexing.

1) Given 3 numbers, $$$l$$$, $$$r$$$ , $$$x$$$. You add all the numbers from l to r(inclusive) by x. For example if the initial array was {5, 4, 3, 9, 2} and the query was {0, 2, 5} then the array would become {10, 9, 8, 9, 2}. Also, print the array.

After each query, store the new array as array $$$a$$$.

At the end print the array a.

m describes the number of queries being asked.

Example:

4 3
1 9 2 2
2 2 3
0 3 5
2
Output:

10
6 14 10 7

Should be less that $$$O(n)$$$

Compare these 2 submissions, 89583867 89743418. There is no difference between them. But one that is submitted today (August 12) has 4200 KB memory improvement. Is there something that I should know?

You are given a number $$$n$$$ and a number $$$m$$$ and an array $$$a$$$ of $$$n$$$ numbers and 2 types of queries. All of the numbers below are 0 based indexing.

1) Given 3 numbers, $$$l, r, x$$$. You add all the numbers from $$$l$$$ to $$$r$$$(inclusive) by $$$x$$$. For example if the initial array was {5, 4, 3, 9, 2} and the query was {0, 2, 5} then the array would become {10, 9, 8, 9, 2}

2) Given 1 number $$$y$$$, output $$$a[y]$$$. This should be self explanatory.

At the end print the array $$$a$$$.

$$$m$$$ describes the number of queries being asked.

Example:

4 3
1 9 2 2
2 2 3
0 3 5
2

Output:

10
6 14 10 7

Should be less that $$$O(n^{2})$$$

I am solving 181B - Number of Triplets. With the constraints being $$$n <= 3000$$$ and my solution supposedly running in $$$O(n^{2})$$$. Am I missing something? 88909110.

Long double holds 22 digits while long long holds 18 digits. Why not use long double over long long? More space, that's for sure.

I see this article and at the bottom, it says that modulus operators are expensive so they implemented a slightly faster version of Euclidean Algorithm. Why not make a more efficient mod?

int mod(int a, int b) { // computes a % b;
	return (a - b * (a / b));
}

I know that set doesn't contain duplicates, but it sorts the elements. I want a data structure that doesn't sort the elements and doesn't contain duplicates.

For example if the data structure contains ints,

Input: 5 4 1 2 5 4 9

Elements in data structure

5 4 1 2 9

Please help.

I was reading up on STL, and I was reading the unordered_set std::count function. It says that worst case is linear and average is constant. Is there a way to make the worst case be constant instead of it being linear?

I am trying to do this 515B - Drazil and His Happy Friends, and I wrote 87470945. It got WA. I am debugging for many hours and still cannot find the bug. My idea was to simply simulate each time the friends meet. If one of the friends are happy, then both are happy. I kept 2 vector of bools, one for boys and one for girls. In the end, I checked if all of the friends were happy. Please help.

Read title... Also, if you generate multiple test cases, how would you do it on a popup window. For example, Dev-C++ has the compile button which if you press it, it opens up a popup window where you can put in data. BTW, I am using GVIM. I saw Errichto's video, but he uses file input and output. Please help. 87387531. This test case consists of 2 strings both of length 1000.

Given an integer $$$n$$$, $$$1 <= n <= 10^5$$$, and an array $$$a$$$ consisting of $$$n$$$ elements, figure out if the array is a good array. A good array is defined to be first increasing, then decreasing. Note that an increasing array or decreasing array is a good array. An increasing array is an array such that every next element of every element(that is not the last) has to be greater than or equal to that element. A decreasing array is an array such that every next element of every element(that is not the last) has to be less than or equal to that element.

Example:

Input:

5 1 2 4 3 1

Output: YES

Input:

3 3 2 1

Output: YES

Input:

5 1 2 3 4 4

Output: YES

Input:

5 5 4 2 1 1

Output: YES

Do it yourself, search up "Is 99999989 a prime number?". Google says "No", and multiple other websites right below it says that it is a prime number. Even this a primality function says that 99999989 is a prime number?

Have you ever used an improved primality test such as Miller-Rabin algorithm? Also can you guys/gals think of any optimizations to this primality test?

bool isprime(ll n) {
    for(int i = 2; i * i <= n; i++) {
        if(n % i == 0) {
            return false;
        }
    }
    return true;
}

I just copied the Miller-Rabin algorithm for primality testing from E-Maxx Algorithms. I wanted to know the time complexity of that function. Here is the link to that article.

Today, I was doing 897B - Chtholly's request. I submitted these two: 86652318 and got RTE, but when I submitted 86652949 it got AC. The only difference between the two submissions was that one of them had stoi and the other had my own stoi. Please check these out.

Run this O(n^2) program in CF custom test

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

long long n;

int main() {
    cin >> n;
    for(long long i = 1; i <= n; i++) {
        for(long long j = 1; j <= n; j++) {
            if((i ^ j) == 0) {
                if(i != j) {
                    cout << "NO!\n";
                    return 0;
                }
            }
        }
    }
    cout << "YES\n";
}

with n = 100000000000

You would expect it to be much longer than 1 second, but it takes

15 ms

screenshot

What are the pros for defining a function to be constexpr. For example the gcd function

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

can be written using constexpr

constexpr ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

Is there any improvement in time it takes to run or execute the program or any other benefits?

I know that there std::unordered_map uses hashing and works 4x faster than std::map. I also know that std::unordered_map has bad hashing which if not using any custom hashing, may result in getting hacked. Credit to blog about ways to prevent getting hacked blog. Is there any way for std::map to work a fast as std::unordered_map so that I can use functionalities such as lower_bound and upper_bound and not getting hacked? Thanks.

In the new CodeForces program EDU, the first problem, linked here Problem here is my below solution. This works in

(credit to .-._._-_.-_.-._-.. for pointing out that it is O(nlog(n)) I originally put O(n) :P)

O(nlog(n))

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

string s;
vector<string> a;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(20);

	cin >> s;
	for(int i = (int)s.size() - 1; i >= 0; i--) {
		string x(1, s[i]);
		a.push_back(x);
	}
	for(int i = 1; i < (int)a.size(); i++) {
		a[i] += a[i - 1];
	}
	sort(a.begin(), a.end());
	cout << (int)s.size() << ' ';
	for(int i = 0; i < (int)a.size(); i++) {
		cout << (int)s.size() + 1 - (int)a.size() - 1 << ' ';
	}
	cout << endl;
}

Help would be greatly appreciated.

My debugging template is:

#define ts to_string
string ts(char c) { return string(1, c); }
string ts(bool b) { return b ? "true" : "false"; }
string ts(const char* s) { return (string)s; }
string ts(string s) { return s; }
template<class A> string ts(complex<A> c) { 
	stringstream ss; ss << c; return ss.str(); }
string ts(vector<bool> v) { 
	string res = "{"; for(int i = 0; i < si(v); ++i) res += char('0' + v[i]);
	res += "}"; return res; }
template<size_t SZ> string ts(bitset<SZ> b) {
	string res = ""; for(int i = 0; i < SZ; ++i) res += char('0' + b[i]);
	return res; }
template<class A, class B> string ts(pair<A,B> p);
template<class T> string ts(T v) {
	bool fst = 1; string res = "{";
	for (const auto& x: v) {
		if (!fst) res += ", ";
		fst = 0; res += ts(x);
	}
	res += "}"; return res;
}
template<class A, class B> string ts(pair<A,B> p) {
	return "(" + ts(p.f) + ", " + ts(p.s) + ")"; }

void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
	cerr << ts(h); if (sizeof...(t)) cerr << ", ";
	DBG(t...); }
#ifdef LOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif

When I type

dbg(a, n)

where 'a' is the vector name and n is the size of the vector. 'a' contains the following {1, 2, 3, 4, 5} and n = 5

it prints

[a, n]: [{1, 2, 3, 4, 5}, 5]

but I want it to print

[a]: [{1, 2, 3, 4, 5}]
[n]: [5]

without having to type

dbg(a);
dbg(n);

Is there any way to do this?

I just noticed that the contest conflicts with my schedule. When I go to the contest page, I go to friends and there is no "x" button to the right of my name. MikeMirzayanov please fix this. Here it is Picture.

UPD: Has been fixed :D