It will be hilarious when Jiangly gets Tourist title :D

During Codeforces Round 934 (Div. 2) I submitted problem D hoping to get the green AC but unfortunately got the red WA (submission 251770538). I spent the rest of the time in the contest trying to figure out the problem in vain. After the contest, I checked the accepted solutions and found that they were exactly like mine which made me more confused.

I stress-tested my solution using a brute-force approach during the contest and using AC solutions after the contest time but couldn't find a single test case. Even after a million random test cases, my solution is still steadfast. I know that a few hundred test cases are enough.

My implementation of string hashing is inspired by Usaco.guide, which uses random bases and a fixed modulus (1LL << 61) -1). I used multiple bases to make sure no collisions happen, but this also didn't help.

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

// BeginCodeSnip{HashedString}
class HashedString {
  public:
	// change M and B if you want
	static const ll M = (1LL << 61) - 1;
	static const ll B;
	static __int128 mul(ll a, ll b) { return (__int128)a * b; }
	static ll mod_mul(ll a, ll b) { return mul(a, b) % M; }

  private:
	// pow[i] contains P^i % M
	static vector<ll> pow;

	// p_hash[i] is the hash of the first i characters of the given string
	vector<ll> p_hash;

  public:
	HashedString(const string &s) : p_hash(s.size() + 1) {
		while (pow.size() < s.size()) { pow.push_back(mod_mul(pow.back(), B)); }
		p_hash[0] = 0;
		for (int i = 0; i < s.size(); i++) {
			p_hash[i + 1] = (mul(p_hash[i], B) + s[i]) % M;
		}
	}

	ll get_hash(int start, int end) {
		ll raw_val =
		    p_hash[end + 1] - mod_mul(p_hash[start], pow[end - start + 1]);
		return (raw_val + M) % M;
	}
};
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
vector<ll> HashedString::pow = {1};
const ll HashedString::B = uniform_int_distribution<ll>(0, M - 1)(rng);
// EndCodeSnip

const auto M = HashedString::M;
const auto B = HashedString::B;
const auto mul = HashedString::mul;
const auto mod_mul = HashedString::mod_mul;
ll inv(ll base, ll MOD) {
	ll ans = 1, expo = MOD - 2;
	while (expo) {
		if (expo & 1) { ans = mod_mul(ans, base); }
		expo >>= 1;
		base = mod_mul(base, base);
	}
	return ans;
}

string n, h;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> h;
	if (n.size() > h.size()) return cout << 0, 0;
	HashedString hs(h);

	set<ll> good;
	ll h_hsh = 1, n_hsh = 1;
	for (int i = 0; i < n.size(); i++) {
		// Compute product hashes
		h_hsh = mod_mul(h_hsh, B + h[i] - 'a');
		n_hsh = mod_mul(n_hsh, B + n[i] - 'a');
	}

	for (int i = n.size() - 1; i < h.size(); i++) {
		if (i >= n.size()) {
			// Update product hashes using modular inverse
			h_hsh = mod_mul(h_hsh, inv(B + h[i - n.size()] - 'a', M));
			h_hsh = mod_mul(h_hsh, B + h[i] - 'a');
		}
		if (n_hsh == h_hsh) { good.insert(hs.get_hash(i + 1 - n.size(), i)); }
	}

	cout << good.size() << '\n';
}

Unfortunately, I couldn't get AC during the contest but now I'm curious about this weird behavior of string hashing. Why using many random bases doesn't help and the solution is to use a prime modulus (i.e. $$$10^9 + 7$$$)?

Now the situation is more complex, I tried to submit a solution (submission 252010026) with only one base and $$$10^9 + 7$$$ as a modulus and got AC. Isn't the collision probability high for such a case?

Another thing to note is the inability to use GNU C++20 compiler caused all of this chaos because I couldn't use __int128 and (1LL << 61) - 1 as a modulus which I think will get AC.

Problem: 1868B2 - Candy Party (Hard Version)

The easy version wants every person to send and receive, we can model the problem to be a graph problem where powers of $$$2$$$ are the nodes, and persons are the directed edges between the required power of $$$2$$$ to send and the required power of $$$2$$$ to receive. So, we can always have the cycles of persons by the fact that Eulerian circuits exit.

Here is a comment on the editorial that explains it more precisely.

But in the hard version, what is the proof that we can always have cycles or paths of persons when some will only send or receive?!

If you have more channels please leave a comment and I will update it. I hope it is helpful for you!

I'm trying to list all the YT channels of the Codeforces competitors, not necessarily mean that the channel is active or has many videos. The channel should be mainly for competitive stuff. (sorted by title as appeared in July 2023)

Let's welcome the Codeforcers YouTubers:

Non-English Channels

Unkown handles

In the recent Div 3, I was rushing to submit fast to reduce the penalty so I miss-typed this part of the code:

            if (j + tochange[i])
                dp[i + 1][j + tochange[i]] = dp[i + 1][j + tochange[i]] | dp[i][j];

It should be:

            if (j + tochange[i] <= n)
                dp[i + 1][j + tochange[i]] = dp[i + 1][j + tochange[i]] | dp[i][j];

Can you hack my submission, please?: 203309510

Update:

Solution verdict: Wrong answer

Congratulations Yousef-Elwan!

But why my solution didn't get RTE?

In the last round Codeforces Round 838 (Div. 2) I managed to solve A, B, and C in about 45 minutes even faster than a friend of mine who is a master and faster than lots of experts. I was left with about 1:45:00 to solve D but in vain. This happens many times in recent rounds, solving the first 3 problems so quickly and D is the big obstacle that seems impossible to approach.

If anyone can give me some advice to attack D more efficiently I'll be thankful.

What can really cause such a runtime error with this version of the GNU C++ compiler? The only thing I thought about was a bug in this version, which was fixed later in GNU C++17.

• My accepted submission with GNU C++17: https://codeforces.me/contest/1696/submission/169228991
• The submission with the same code but with GNU C++14: https://codeforces.me/contest/1696/submission/169229016

This is my first time submitting an answer with python. I tried PyPy 3-64 but got runtime error, I thought it was my fault to submit with PyPy as the language which I don't know anything about it. Then I tried to submit again with Python 3 in no vain.

These are my submissions:

1. https://codeforces.me/contest/1690/submission/160147330
2. https://codeforces.me/contest/1690/submission/160147403

Can anyone help?!