reading input takes O(n**2)

Oh, I had the same idea as yours. But during the contest, I used a BIT to calculate the sum... I forgot I could calculate the sum afterwards. So I'm $$$O(nk \log n)$$$. And it passed too.

same too

Same here. I feel so sad bruh =))

ceil is prone to error. Better write your own, like you said, or maybe implement something along these lines:

#define ll long long

ll ceil(const ll &a, const ll &b)
{
    if(a%b == 0)
        return a/b;
    return a/b +1;
}

n=5*10^17, m=10^18. Gcd will be 5*10^17 and it's umportant to keep gcd in long long.

500000000000000000 1000000000000000000 1 2 716004419141796031 1 358002209570898016 Built-in ceil function failed on this query

consider use long long and long double for all varibles

Instead of using ceil I just switched to zero-indexed (subtract 1 from y) and use the default truncated integer division. Since the only thing we want to do with the group index is to compare equality, there is no need to convert back to one-indexed.

sometimes , bruteforce is the best solution, just keep in mind the time complexity for the worst case :)

I'm wrong.

You will most probably encounter precision errors as you have use double data type, because the values are as high as 1e18!!

Firstly #define int long long. There is one big cauldron for you guys :)

But mainly reason is usage of long double. It is always bad thing when you need actually precise comparsion of long long.

For prefix function one usually uses a string formed by:

Where $ is a symbol that doesn't belong to the alphabet just to be sure that we won't be getting an invalid prefix value of $$$pattern$$$. Here we go with some observations:

1) Since $$$\pi[i]$$$ is the length of a prefix of $$$pattern$$$, then $$$\pi[i] \leq |pattern|$$$.

2) In the usual preprocess, we initialize $$$j = \pi[i-1]$$$, but this can be dismissed by using $$$j$$$ as an outside variable and recycling it for the next iteration.

3) Combining 1 and 2, we notice that we just need to compute $$$\pi[i]$$$ for $$$0 \leq i < |pattern|$$$ to get any $$$\pi[i]$$$ needed afterwards (it doesn't even depend on the value of $$$text$$$ :D).

4) Since we already have all that we need to compute any $$$\pi[i]$$$ without any extra data, we don't need to create $$$S$$$ as it is, just use a similar preprocess iteration over $$$text$$$ and take the last $$$j$$$ value (since that would be $$$\pi[|text| - 1]$$$, exactly what we need).

The rest is just the implementation required to solve the problem and some optimizations (like just taking the last $$$min(|ans|,|word|)$$$ characters of $$$ans$$$).

area1 = ((a==1) ? n*(b-1) : m*(b-1));
area2 = ((c==1) ? n*(d-1) : m*(d-1));

It will overflow here.

same problem here https://codeforces.net/contest/1200/submission/58606476

just use long double instead of double. the WA verdict was because of precision error due to division of large values

same happening with me...58621017..Anyone please explain..??

Seems, like in python double comparison is f**ked up.

Since this passes by converting to int.

https://codeforces.net/contest/1200/submission/58622224

You should avoid to use real number when integer can solve

But it seems your solution can be hacked since your hashing is not randomized

Okay three main issues:

• m == 0 should be changed to m < 0
• > in else should be changed to >=
• And you can further decrease by k amount in else even after making them equal.

Here is your modified code that passes:

https://codeforces.net/contest/1200/submission/58624658

Some points why this doesnt work:

• You are incrementing LP and never looking back
• When your match fails, LP never goes to original LP+1, it continues from where it failed.
• You are missing to check all potential candidates which might have matched.

This part of your code works in linear time of current string's length, because you mark all suffixes of string:

int term = last;
while (term > 0)
    terminal[term] = 1, term = st[term].link;

Total complexity is $$$O(W^2)$$$, where $$$W$$$ is sum of strings length. So, tests are weak.

I believe the problem is in the way you are building the string ans with the string's += operator. According to here, time complexity could be as much as linear in the length of the resulting string, even if you are adding one character on the end at a time. Try push_back instead, which should be constant time amortized.

for(10**5) ret(A[i+1]);

And in ret() you copy the original string string a = ans;

Copy can take 10**6 . So, in total 10**10

Denote a wall by its clockwise angle from the 12 o'clock position, out of the full $$$360^\circ$$$. So the inner walls occur at $$$\frac{0}{n},\frac{1}{n},\dots,\frac{n-1}{n}$$$ and the outer walls occur at $$$\frac{0}{m},\dots,\frac{m-1}{m}$$$. An inner wall and outer wall coincide when there is a pair $$$(x,y)$$$ such that $$$0\le x< n,\ 0\le y< m$$$, and $$$\frac{x}{n}=\frac{y}{m}$$$. That is, $$$xm=yn$$$. So, $$$xm=yn$$$ is a common multiple of $$$m$$$ and $$$n$$$, so it is divisible by $$$\mathrm{lcm}(m,n)=\frac{mn}{\gcd(m,n)}$$$. So we write

and simplify to

The restrictions $0\le x<n,\ 0\le y<m$ require that $$$0\le k<\gcd(m,n)$$$. The dual walls correspond exactly with each integer $$$k$$$ in this range, therefore the number of dual walls is $$$\gcd(m,n).$$$

Basically, suppose that you have currently formed the string $$$ans$$$ and you will add the string $$$word$$$. Then, to minimize the letters added, we need the longest string such that is a suffix of $$$ans$$$ and also a prefix of $$$word$$$ (we won't need to add this string since it's already formed in $$$ans$$$). Fortunately, prefix function computes exactly that if we use $$$word$$$ as pattern and $$$ans$$$ as text (so the answer would be $$$\pi[|ans|-1]$$$ with $$$\pi$$$ applied to the text).

However, this method would be a TLE since $$$ans$$$ might be very long, so we use the following optimization: Since the string wanted is a prefix of $$$word$$$, then it's size is at most $$$|word|$$$. Thus, we just need to use the last $$$min(|ans|,|word|)$$$ characters of $$$ans$$$ to use as the text for the prefix function (since any more characters would be unused in the possible prefix).

We finally end up with a complexity of $$$O\left(\sum\limits_{i=1}^{n}|word_{i}|\right)$$$ since each run of prefix function is linear respect to the length of $$$word$$$.

I hope this helped :D

can u please explain how u have solved D que??

The prime must be at least the number of characters we need to take care of. We have letters 'a' to 'z', letters 'A' to 'Z', and numbers '0' to '9' — a total of 62 characters. Thus, it's best to have a prime > 62

For rolling hash you need your $$$p1$$$ to be greater than the maximum possible integral value of the characters you'll use. Since we have an alphabet of size $$$62$$$, your $$$p1$$$ must be at least $$$62$$$ (considering that you mapped the characters to the range $$$[0,61]$$$).

The culprit is ans = ans + s[i][j]; Concatenation and string copying takes linear time, and you do this operation for each character, making your solution quadratic. Try ans.push_back(s[i][j]); instead, which is constant amortized.

I solved E by KMP following the editorial. https://codeforces.net/contest/1200/submission/58665108

I think the key point is to reset the longest border value in the center of c which is defined by editorial.

Try this test: "3 abc def cdef". Answer should be abcdef, but your program outputs abcdefcdef. Did you found your misunderstanding? :v

They are both YES. What made you think the answer is NO?

You need to, optimize the string you use for your prefix function, since ans can be really long. Your just need to take the last $$$min(|ans|,|s|)$$$ characters of $$$ans$$$ since your common string cannot exceed that length. Also try not to use too much the $$$+$$$ operator for strings, it's faster to push_back the characters :D

Here's one of the correct solutions.

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

const int MAX_N = 2000;

string s[MAX_N], t[MAX_N];

int row_first[MAX_N], row_last[MAX_N];
int col_first[MAX_N], col_last[MAX_N];

int row_ans[MAX_N][MAX_N], col_ans[MAX_N][MAX_N];
int base = 0;
int n, k;

void find_first_last(int *first, int *last, string *board)
{
	int i, j;
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
			if (board[i][j] == 'B')
				first[i] = min(first[i], j), last[i] = max(last[i], j);
		if (last[i] == -1)
			base++;
	}
}

void solve(int *first, int *last, int ans[][MAX_N])
{
	int cur, i, j;
	for (i = 0; i < n - k + 1; i++)
	{
		cur = 0;
		for (j = 0; j < k; j++)
			if (last[j] != -1 && i <= first[j] && last[j] <= i + k - 1)
				cur++;
		ans[0][i] = cur;
		for (; j < n; j++)
		{
			if (last[j] != -1 && i <= first[j] && last[j] <= i + k - 1)
				cur++;
			if (last[j - k] != -1 && i <= first[j - k] && last[j - k] <= i + k - 1)
				cur--;
			ans[j - k + 1][i] = cur;
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	int i, j;
	cin >> n >> k;
	for (i = 0; i < n; i++)
		cin >> s[i];
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			t[i] += s[j][i];

	fill(row_first, row_first + MAX_N, MAX_N);
	fill(row_last, row_last + MAX_N, -1);
	fill(col_first, col_first + MAX_N, MAX_N);
	fill(col_last, col_last + MAX_N, -1);

	find_first_last(row_first, row_last, s);
	find_first_last(col_first, col_last, t);

	solve(row_first, row_last, row_ans);
	solve(col_first, col_last, col_ans);

	int ans = 0;
	for (i = 0; i < n - k + 1; i++)
		for (j = 0; j < n - k + 1; j++)
			ans = max(ans, row_ans[i][j] + col_ans[j][i]);
	cout << ans + base << '\n';
}

2520 is the lowest common multiple of 1,2,...,10 — all possible numbers of outgoing edges.

So (v, 2521) is essentially the same state as (v, 1) because they have the same remainder modulo 1,2,...,10

it's not O(n*n)... it's O(n*n*k). in the last loops you are calling a function func which works in O(k) time.

Did you find the problem?

You are right. I fixed editorial. thank you!

i found my problem

https://codeforces.net/blog/entry/69035?#comment-534568 this might help.

Some testers thought so, too. But the official result shows that it was a good decision to put it this way. D is just about some ideas and implementations, while E requires some pre-knowledge about some specific algorithms.

Every state is visited at most once. If you're about to re-visit a particular state, then that means you already know the answer for that state (the loop that it'll end on) — so you can just use it without re-visiting it.

Well it's not that kind of timestamp I mentioned. What I referred to is that you use different timestamp for different travels. This way you can look through all the vertices you visited in the loop (i.e. you can backtrack what states you have visited), and only increase the answer if the visited time is not same as this travel, and update the timestamp for that vertex.

Anyways the time complexity for that submission is actually O(min(2520n, q)*n), since it requires at most one run of the loop per query. It should be fast enough since the loop barely does any work.

Maybe I could make a case where that makes a lot of cache misses, but I don't know.