Codeforces 451 Div2

Rounds 451 and 452 were genuinely quite easy, but I made foolish mistakes.

Here are notes on the problems I caught up on. The rest were very straightforward.

For Problem D, use greediness: scan left to right and remove the rightmost element whenever the condition is violated. I somehow wrote a Fenwick tree, then missed one case in the check and got WA.

For Problem E, simply split into cases and greedily move the part that exceeds $n/2$.

Problem F is worth discussing. Given a string of length around $10^6$, write it in the form X + Y = Z.

First, of course, enumerate the split position of the first number. After that, I did not know what to do.

For X + Y = Z, the length of Z is either equal to the length of X, one more than the length of X, equal to the length of Y, or one more than the length of Y. There are only these four cases. That is enough.

How do we check the addition? Use prefix hashing. I still got through with a trick and some luck; in a contest, two independent hashes should be used. A painful lesson.

int len;
char val[maxn];
ll inv[maxn], pre[maxn], f[maxn];

bool check(int st, int en)
{

	int len1 = st;
	int len2 = en - st;
	int len3 = len - en;
	if (len1 > len3 || len2 > len3)return false;
	if (len1 <= 0 || len2 <= 0 || len3 <= 0)return false;

	if (len1>1 && val[1] == '0')return false;
	if (len2>1 && val[st + 1] == '0')return false;
	if (len3>1 && val[en + 1] == '0')return false;

	ll sum1 = pre[st];
	ll sum2 = (pre[en] - pre[st] * f[en - st] % mod) % mod;
	sum2 = (sum2%mod + mod) % mod;
	ll sum3 = (pre[len] - pre[en] * f[len - en] % mod) % mod;
	sum3 = (sum3%mod + mod) % mod;
	if ((sum1 + sum2)%mod != sum3)return false;
	for (int i = 1; i <= len; i++)
	{
		printf("%c", val[i]);
		if (i == st)printf("+");
		if (i == en)printf("=");
	}
	return true;
}

void solve()
{
	scanf("%s", val + 1);
	len = strlen(val + 1);
	inv[0] = 1;
	f[0] = 1;
	int up = 1e6;
	repp(i, 1, up)
	{
		f[i] = f[i-1] * 10 % mod;
	}
	repp(i, 1, len)
	{
		pre[i] = pre[i - 1] * 10 + val[i] - '0';
		pre[i] %= mod;
	}

	repp(i, 1, len)
	{
		if (check(i, len - i))
		{
			return;
		}
		if (check(i, len - i - 1))
		{
			return;
		}
		if (check(len - i - i, len - i))
		{
			return;
		}
		if (check(len - i - i - 1, len - i - 1))
		{
			return;
		}
	}
}