Find the number of positive integers that are $$$\le n$$$ and is coprime to $$$\text{lcm}(1, 2, 3, \dots, x)$$$ where $$$n$$$ and $$$x$$$ are positive integers. Maybe have $$$n\le 10^{15}$$$ and $$$x\le 10^{12}$$$.

Prove that for any $$$a, b, c\in \mathbb{R}^+$$$ the following inequality is true: \begin{align*} \left(\frac{a+b+c}{3}\right)\left(\frac{b^{3/2}}{\sqrt{a}}+\frac{c^{3/2}}{\sqrt{b}}+\frac{a^{3/2}}{\sqrt{c}}\right) \ \ge a(2b-a)+b(2c-b)+c(2a-c) \end{align*}

Inspired by AoPS's Marathon Threads, I decided to create one on CF! The only rule of this forum is that you have post an interesting theorem, or trick related to CP or math, with a brief description and provide a source for extra research.

To start things off, I think that Proizvolov's identity is very interesting (but doesn't appear much in math problems :( ) and states if you have the numbers from $$$1-2n$$$ and split the numbers into 2 sets $$$A, B$$$ such that $$$A$$$ is in increasing order and $$$B$$$ is in decreasing order, the sum $$$|A_1-B_1|+|A_2-B_2|+\dots+|A_n-B_n|$$$ is always equal to $$$n^2$$$. Source: https://en.wikipedia.org/wiki/Proizvolov%27s_identity

There was some problem with the validator on problems A and G in the recent Div 3 and invalid hacks were considered valid and a lot of solutions got "hacked" because of that. After fixing the issue, the solutions have been rejudged and some AC solutions on G got TLE after being rejudged. But apparently, its not only happening with the submissions to the problems on the recent Div 3, its happening everywhere.

This has been brought to my attention by magnus.hegdahl who submitted 2 submissions https://codeforces.net/contest/1512/submission/112567753 https://codeforces.net/contest/1512/submission/112578347
Now if you compare these two codes, the only difference is that the second submission has this line

#pragma Voodoo magic("superfast")

which obviously does nothing. Now look at the execution time. One is TLE, the other is AC with 160 ms to spare. This is very weird. Usually if you submit the same code, the difference is at most 60 ms not this drastic from TLE to AC.

Second case is form Nika_Tamliani who also has the same case. https://codeforces.net/contest/1512/submission/112584737 https://codeforces.net/contest/1512/submission/112502297 these two submissions. First one is AC in 1731 ms and second is again TLE. Like before, the submissions are the same except for a comment which obviously shouldn't change the execution time by this much.

Now another case from galen_colin who has these 3 submissions which are also exactly the same https://codeforces.net/contest/1512/submission/112578130 https://codeforces.net/contest/1512/submission/112578058 https://codeforces.net/contest/1512/submission/112503702. First one is AC in 1357 ms, second one is AC in 1840 ms, and third is TLE. All are EXACT same, maybe some comment changes or something but everything is the same. The difference is HUGE, 1357 to 2000 ms TLE? C'mon what is this? Can anyone explain this? It seems very peculiar and strange.

Last case is yet again galen_colin who took TripleM5da's solution after contest and resubmitted it, adding a comment at the top. https://codeforces.net/contest/1512/submission/112585380 galen_colin's submission https://codeforces.net/contest/1512/submission/112482209 and TripleM5da's submission. Galen's submission was out of contest while DeadPillow's submission was in contest. Again, the execution time is drastically different. Around 600 ms different.

But it seems like that this error doesn't only occur on the recent Div 3. Again we look at galen_colin's submissions https://codeforces.net/contest/286/submission/112584630 https://codeforces.net/contest/286/submission/112584865. As you can see, these problems aren't from the recent Div 3 and were from Round 176 Div 1. The difference is also very drastic, more than 400 ms.

MikeMirzayanov please take a look into this issue.

Thanks to SlavicG for helping me develop the introduction!

If you look at the top left corner, the badges are not pictures, but rather are text. Also, if you look at your favorited blogs, the button "Remove from favourites" is now in text format and not in picture format.

MikeMirzayanov please fix this.

Also sorry for pinging my followers :D

UPD: Fixed, thanks Mike!

With pllk introducing 100 more problems to the CSES problemset, the race for shortest code is on. Here in this blog, I talk about the many different ways of shortening code to get that shortest code.

std::any_of

This is a very useful function that returns true iff any of the elements in the range [first, last) satisfies some condition. Let's say you want to figure out if an array contains at least one 9. You could just write the naive loop and waste time in contest.

bool ok = 0;
for(int i = 0; i < (int)(a).size(); ++i) {
	if(a[i] == 9) {
		ok = 1;
		break;
	}
}

but you could be smart and write this all in one line.

bool ok = any_of(a.begin(), a.end(), [](int x) { return x == 9; });

Time Complexity

This is linear aka $$$O(n)$$$.

std::all_of

This is another useful function that functions similar to std::any_of. The difference is that it returns true iff all the elements in the range [first, last) follow some condition.

Let's say you want to find if the array consists of all 9's.

bool ok = 1;
for(int i = 0; i < (int)(a).size(); ++i) {
	if(a[i] != 9) {
		ok = 0;
	}
}

Now this method saves a couple of lines which means that you'll get the fastest submit time. Guaranteed or I will give you your money back. :D

bool ok = all_of(a.begin(), a.end(), [](int x) { return x == 9; });

Time Complexity

Like the function that I mentioned, this is also $$$O(n)$$$.

std::none_of

This is yet another function that is close relatives of the two mentioned above. This function returns true iff all the elements does not follow some condition.

Let's say you want to find if the array doesn't contain 9.

Noobs will do:

bool ok = 1;
for(int i = 0; i < (int)(a).size(); ++i) {
	if(a[i] == 9) {
		ok = 0;
	}
}

Pros would do:

bool ok = none_of(a.begin(), a.end(), [](int x) { return x == 9; });

This next one is very useful and it appears quite frequently in problems on various judges.

Time Complexity

Linear, $$$O(n)$$$.

std::for_each

Thanks to Ta180m for pointing this out in the comments. This function applies a function hld to all of the elements in the range of [first, last).

Lets say that you want to increase all the elements in some vector by 5.

Naive way:

for(int i = 0; i < (int)(a).size(); ++i) {
	a[i] += 5;
}

A shorter way to write it would be:

auto change = [&](int& x) {
	x += 5;
};
for_each(a.begin(), a.end(), change);

As mentionted by purplesyringa, if you want to iterate from begin ... end it is better to use range-based for loops. std::for_each is only really useful when your iterating from something else other than begin ... end.

Time Complexity

$$$O(n \cdot X)$$$ where $$$X$$$ is the complexity of applying the function hld once.

std::count

This functions counts the number of elements in the range [first, last) that are equal to some variable val.

Noobinho:

int cnt = 0;
for(int i = 0; i < (int)(a).size(); ++i) {
	cnt += (a[i] == x);
}

Proinho:

int cnt = count(a.begin(), a.end(), x);

Time Complexity

$$$O(n)$$$.

std::find

This function returns the first iterator that compares equal to val.

Thanks to _rey for pointing this out to me. :)

NOTE: if using std::find on sets, use set::find instead. This guarantees it to be $$$O(\log n)$$$ where $$$n$$$ is the size of the set.

Nubs:

int hld = -1;
for(int i = 0; i < (int)(a).size(); ++i) {
	if(a[i] == x) {
		hld = i;
		break;
	}
}

Prubs:

int hld = find(a.begin(), a.end(), x) - a.begin();

Time Complexity

Linear, $$$O(n)$$$.

std::accumulate

Many coders use this function but I am still going to include it just in case you don't know the uses of it. This function returns the sum of init and all the elements from [first, last).

Let's say that you want to find the sum of all the elements in the vector. Beginners would do:

int sum = 0;
for(int i = 0; i < (int)(a).size(); ++i) {
	sum += a[i];
}

Now, we can use std::accumulate to do this in 1 line.

Thanks for N8LnR2Nqf8Q4FN for pointing this out to me.

NOTE: Be mindful for overflow when using std::accumulate. If you know that the sum will overflow, use 0LL otherwise use 0. If your not sure using 0LL won't hurt that much anyways.

int sum = accumulate(all(a), 0LL);

Time Complexity

$$$O(n)$$$

std::binary_search

This function is pretty useful in finding if the element val appears in the sorted range [first, last).

Let's say that you want to find if the element val appears in the sorted array. Standard binary search looks something like this.

bool ok = 0;
int l = 0, r = (int)(a).size(), target = val;
while(l < r) {
	int mid = (l + r) / 2;
	if(a[mid] < target) {
		l = mid + 1;
	} else if(a[mid] == target) {
		ok = 1;
		break;
	} else {
		r = mid;
	}
}

bool ok = binary_search(a.begin(), a.end(), val);

Time Complexity

$$$O(\log n)$$$

std::max_element

This function returns the max element in the range [first, last).

int cur = -INF;
for(int i = 0; i < (int)(a).size(); ++i) {
	cur = max(cur, a[i]);
}

Better way to do it is:

int cur = *max_element(a.begin(), a.end());

Time Complexity

$$$O(n)$$$

std::min_element

This is basically the same as std::max_element but returns the min element in the range [first, last).

int cur = INF;
for(int i = 0; i < (int)(a).size(); ++i) {
	cur = min(cur, a[i]);
}

int cur = *min_element(a.begin(), a.end());

Time Complexity

Linear in time, $$$O(n)$$$.

std::is_sorted

This function is for checking if the range [first, last) is sorted. Its pretty self-explanatory.

bool ok = 1;
for(int i = 1; i < (int)(a).begin(); ++i) {
	if(a[i] < a[i - 1]) {
		ok = 0;
	}
}

bool ok = is_sorted(a.begin(), a.end());

Alternatively, if you want to check if the range is sorted but in reverse order, you can first reverse the sequence and then check if it's sorted.

reverse(a.begin(), a.end());
bool ok = is_sorted(a.begin(), a.end());

Time Complexity

$$$O(n)$$$

std::lexicographical_compare

This function is used in many problems that compares two containers and checks which one is lexicographically first.

bool ok = lexigraphical_compare(a.begin(), a.end(), b.begin(), b.end());

Time Complexity

$$$O(n)$$$.

std::partial_sum

Thanks to Kavaliro for pointing this out to me. Imagine doing a prefix sum problem. You want to obviously compute the prefix sums. Naive way to do it would be

for(int i = 1; i < (int)(a).size(); ++i) {
	a[i] += a[i - 1];
}

Now, as Kavaliro pointed out, this could be done in 1 line.

partial_sum(a.begin(), a.end(), a.begin());

Suffix sums are much the same thing

partial_sum(a.rbegin(), a.rend(), a.rbegin());

Time Complexity

Both are linear, $$$O(n)$$$.

std::adjacent_difference

Thanks to elsantodel90 for pointing this out to me. Since I already included the std function for prefix sum, it "only natural to mention adjacent_difference too" — elsantode190. So here it is.

vector<int> hld = a;
for(int i = 1; i < si(hld); ++i) {
	hld[i] -= a[i - 1];
}

This takes 4 lines and much more characters than this:

adjacent_difference(a.begin(), a.end(), a.begin());

Saves a good amount of characters and shorter to type out.

Time Complexity

$$$O(n)$$$

std::iota

Thanks to purplesyringa for pointing this out to me! This function assigns every value from [first, last) successive values of val where val is the argument to the function. A useful scenario is when you have a DSU and you want to initialize it by setting each node's parent to itself. Now this can be done naively

for(int i = 0; i < n; ++i) {
    par[i] = i;
}

or it can be done in a much shorter way

iota(par.begin(), par.end(), 0);

Time Complexity

$$$O(n)$$$

Thats all for now, as I have school work to do. But I'll continue to update this blog with other useful functions. :D

Ever since I reached cyan, people have been asking me "How to get better at CP like you?". I have the answer. This answer may surprise you.

I am asking this question for another person btw.

I know how to find LIS in $$$O(n \log n)$$$ with binary search and is pretty well known. I am trying to find the Maximum Sum Increasing Subsequence in $$$O(n \log n)$$$. This can be solved using a BIT or a segtree, but is there an approach with binary search like LIS? https://www.geeksforgeeks.org/maximum-sum-increasing-subsequence-dp-14/.

Disclaimer: Make sure to get yourself comfortable before reading this comment. I was intrigued by the earlier discussion on sieves and decided to benchmark some sieves. There are 2 that I benchmarked with surprising differences in running time. One of them can be found here. https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html. Under the "Different optimizations of the Sieve of Eratosthenes". The optimization is sieving to the root. Another one is Nisiyama_Suzune's https://codeforces.net/blog/entry/54090. Under the section "Linear sieve". It is a direct copy-paste from the CodeForces blog. Now, here comes the surprising part. https://cp-algorithms.com/algebra/prime-sieve-linear.html. Under the section "Runtime and Memory" it says "and the optimized versions of the sieve run as fast as the algorithm given here." Note: the optimized versions is the one that I used in my benchmarking. This states that the optimized sieve is also linear. Okay, now it really comes the surprising part. When I benchmarked both functions, the optimized sieve or the CP-Algorithm's Optimized Sieve ran more than 2x faster than the linear sieve in the CF blog. Why is this true? Both sieves are linear yet one is more than 2x faster than the other. This is pretty weird. Here you can find the benchmark. https://ideone.com/MfaJCF. In this code N = 1e8 which is pretty big. Now if I try on smaller N like N = 1e7 or N = 1e5, the differences are even larger. For N = 1e7, the sieve in CP Algo's is more than 3x faster than the CF blog implementation. https://ideone.com/b7jjyO. As you can see, the only difference between the two benchmarks is the value of N. Now if I try N = 1e6, the sieve from CP algos is 4.56x faster than the other implementation. Now, I haven't tried it yet but I imagine when N = 1e5 or smaller, the difference is massive. I know this is pretty long, happy reading.

Using the other implementation that is not improved in the same CP Algorithms article produces surprising results. The CF blog and the $$$O(n \log \log n)$$$ implementation of sieve from CP algos have basically the same execution time when running it. Now this makes me think, "Is the CF implementation of linear sieve linear?"

What are your thoughts about this?

As you all know, the winter theme has come. But, if you look at the top left corner and you hover your mouse over the logo it says "Header:: Happy New Year". It would be awesome if somebody removes the "Header::" part so it looks better. Thanks.

Edit: Thanks to MikeMirzayanov for fixing the problem.

I was solving this problem and I got AC. While I was solving the problem, I had some cerr's and I commented them out when submitting. After getting AC, I wanted to experiment if uncommenting those cerr's would have a difference in runtime. Lo and behold! The difference was huge. Take a look at these two submissions. 100116835 is the AC and 100116299 is the TLE. The AC runs in 62 ms and the TLE is over 1000 ms. Now I have questions. Does Codeforces use the standard error stream? Why does this affect my runtime? All the comments are print statements and even if they were outputted to standard output stream, this wouldn't cause TLE. Why, why, why?

Recently, I stumbled upon Rascal's Triangle. You can read more about it here. Basically it is very like Pascal's Triangle but a bit different. I know that there is a $$$O(n)$$$ solution for Pascal's Triangle. I would want to calculate the $$$nth$$$ row in $$$O(n)$$$ mod $$$998244353$$$. Help?

NOTE: This problem is NOT interactive
I was doing some problems of SlavicG and mesanu's Unofficial Div 4 round. This problem was causing me with some weird Idleness Limit Exceeded. 99582268. After being Sherlock Holmes for a few minutes, I fixed the problem and 99582838 is AC. The weird thing is the $$$dbg$$$ macro. After commenting all of the dbg's out, it got AC. I am wondering why is this. Shouldn't it be outputted to the standard error stream? Why am I getting this idleness limit exceeded?

With school starting around the world, that means less time to participate in contests! The weekends are the best time for us students to participate and many times the time slots are left blank! Contest writers should consider moving contests to weekends where more people could participate and have fun! I could point to many contests where Sunday has a contest but Saturday doesn't or vice versa. Contest writers, if you see this, please consider moving contests to the weekends.

What is the relation between ABC's and ARC's. Like ARC's problem A is idk ABC's problem D. Help is appreciated.

Here is the problem.

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

#define int long long
#define ll long long

int modmul(int a, int b, int M) {
	long long ret = a * b - M * (int)(1.L / M * a * b);
	return ret + M * (ret < 0) - M * (ret >= (ll)M);
}
int modpow(int b, int e, int mod) {
	int ans = 1;
	for (; e; b = modmul(b, b, mod), e /= 2)
		if (e & 1) ans = modmul(ans, b, mod);
	return ans;
}
bool prime(int n) {
	if (n < 2 || n % 6 % 4 != 1) return (n | 1) == 3;
	int A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022},
	    s = __builtin_ctzll(n-1), d = n >> s;
	for (int a : A) {   // ^ count trailing zeroes
		int p = modpow(a%n, d, n), i = s;
		while (p != 1 && p != n - 1 && a % n && i--)
			p = modmul(p, p, n);
		if (p != n-1 && i != s) return 0;
	}
	return 1;
}
int pollard(int n) {
	auto f = [n](int x) { return modmul(x, x, n) + 1; };
	int x = 0, y = 0, t = 30, prd = 2, i = 1, q;
	while (t++ % 40 || __gcd(prd, n) == 1) {
		if (x == y) x = ++i, y = f(x);
		if ((q = modmul(prd, max(x,y) - min(x,y), n))) prd = q;
		x = f(x), y = f(f(y));
	}
	return __gcd(prd, n);
}
vector<int> factor(int n) {
	if (n == 1) return {};
	if (prime(n)) return {n};
	int x = pollard(n);
	auto l = factor(x), r = factor(n / x);
	l.insert(l.end(), begin(r), end(r));
	return l;
}
struct custom_hash { // Credits: https://codeforces.net/blog/entry/62393
	static uint64_t splitmix64(uint64_t x) {
		// http://xorshift.di.unimi.it/splitmix64.c
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}
	size_t operator()(uint64_t a) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(a + FIXED_RANDOM);
	}
	template<class T> size_t operator()(T a) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		hash<T> x;
		return splitmix64(x(a) + FIXED_RANDOM);
	}
	template<class T, class H> size_t operator()(pair<T, H> a) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		hash<T> x;
		hash<H> y;
		return splitmix64(x(a.f) * 37 + y(a.s) + FIXED_RANDOM);
	}
};
template<class T, class H> using umap = unordered_map<T, H, custom_hash>;
template<class T> using uset = unordered_set<T, custom_hash>;

 
int n;
vector<pair<int, int>> a;
vector<set<int>> hld;
umap<int, int> cnt;
 
int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	a.resize(n);
	for(auto& i: a) {
		cin >> i.first >> i.second;
	}
	for(int i = 0; i < n; ++i) {
		vector<int> hld1, hld2;
		hld1 = factor(a[i].first);
		hld2 = factor(a[i].second);
		set<int> se;
		for(auto& j: hld1) {
			se.insert(j);
		}
		for(auto& j: hld2) {
			se.insert(j);
		}
		hld.emplace_back(se);
	}
	for(auto& i: hld) {
		for(auto& j: i) {
			++cnt[j];
		}
	}
	for(auto& i: cnt) {
		if(i.second == n) {
			cout << i.first << "\n";
			return 0;
		}
	}
	cout << -1 << "\n";
}

The factorization algorithm is taken from KACTL, same with the Miller-Rabin and the modmul and the modpow.

My thought process:

If we take each pair and then prime factorize each of the numbers in the pair. Then take the union of those prime factors and then for each union, we count the number of primes and if there are $$$n$$$ of those primes in the pairs then, at least one number from each pair will be divisible by that number.

Complexity

Since the prime factorization is $$$O(n^{\frac{1}{4}})$$$, and we are doing $$$O(n)$$$ of them and there are at most 30 prime factors for a number $$$\le 2 \cdot 10^{9}$$$, the complexity is about $$$O(n \cdot n^{\frac{1}{4}})$$$ or $$$O(n^{\frac{5}{4}})$$$. Also, I didn't add in the set's insert which works in $$$O(log(n))$$$, but I don't think that that would matter much. This complexity should suffice for $$$n \le 150,000$$$

Please let me know if there is a section where it is not clear. Thanks for reading the blog.

The title prolly ain't clear at all. You are given a string $$$s$$$ and a string $$$t$$$. For every substring $$$s$$$ of length $$$|t|$$$, you are to find the number of different characters between the substring of $$$s$$$ and $$$t$$$ in $$$O(n \cdot log(n))$$$ or less. It is guaranteed that $$$|t| \le |s|$$$.

Example: s: abac t: ag output: [1, 2, 1]

s: adfjaasd t: asdf output: [3, 4, 4, 4, 3]

Don't just downvote, tell me where I should improve or what the answer to my question is. Pls, my contribution is already too low (-75).

Problem statement: 1196D2 - RGB Substring (hard version)

Note: Factors and prime factorization are two different things. The factors of a number are the numbers that are divisible by it. Example: 12: {1, 2, 3, 4, 6, 12}.

When I urgently need help with a question that I am having, this message appears frequently when I try to write more than 1 comment in 10 minutes. Although I understand that this rule is put in place to stop spammers from spamming too much comments, I do believe that it could help many people if we change the time of this feature. Maybe we could reduce from 10 minutes to 5 or even 3. Thoughts?

I know that using Manacher's algorithm, we can find all pairs ($$$i$$$, $$$j$$$) such that s[i $$$\dots$$$ j] is a palindrome. This article on cp-algorithms uses 2 vectors, one in which the $$$i$$$ is the center of an odd length palindrome, the other in which the $$$i$$$ is the latter of the 2 middle elements of an even length palindrome. But how do we convert this information into a vector<pair<int, int>> where the pair represents the boundaries of the palindrome substring?

I want a data structure(range maximum query with lazy updates) that supports 2 queries. One of them is an update in which we update all the elements from position $$$l$$$ to $$$r$$$ to be equal to $$$k$$$. The second query is getting the index of the maximum element in the range $$$[l, r]$$$. For the second query, if there are 2 elements with the same value and that value is the maximum, output the minimal index. Examples: Initial array = [5, 4, 3, 9]. Do first query $$$2, 3, 3$$$. array = [5, 4, 3, 3]. Do second query(0, 3). Answer = 0. Do first query $$$0, 1, 100$$$. array = [100, 100, 3, 3]. Do first query $$$3, 3, 1000$$$. array = [100, 100, 3, 1000]. Do second query(0, 1). Answer = 0.

I have been seeing this used in people's codes and wondered what are the uses of this in Competitive Programming? I am genuinely curious.

I very much like $$$cin » $$$ but want to have this fast reading integers function. How to do it? For example, I want to input multiple integers in this $$$cin » a » b » c;$$$ but the reading of integers is using the comment above.

I tried this but it didn't work.

istream & operator >> (istream& os, int x) {
	bool minus = false;
	int result = 0;
	char ch;
	ch = getchar();
	while (true) {
		if (ch == '-') break;
		if (ch >= '0' && ch <= '9') break;
		ch = getchar();
	}
	if (ch == '-') minus = true; else result = ch-'0';
	while (true) {
		ch = getchar();
		if (ch < '0' || ch > '9') break;
		result = result*10 + (ch - '0');
	}
	if (minus)
		os >> -result;
	else
		os >> result;
	return os;
}

But I got this error

 error: ambiguous overload for 'operator>>' (operand types are 'std::istream' {aka 'std::basic_istream<char>'} and 'int')
  124 |   os >> result;
      |   ~~ ^~ ~~~~~~
      |   |     |
      |   |     int

I want a data structure that keeps elements in the way that you inserted them and allows erases in $$$O(log(n))$$$ or less. For example, if the initial array is empty and you insert 5, 2, 4, then the array would be [5, 2, 4]. Erase 4 and it is [5, 2]. Insert a 3 and it is [5, 2, 3]. I know that set allows erases in $$$O(log(n))$$$ and insertions but it keeps the elements in sorted order, not in the way that I inserted them.

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?