To some extent, from now on, another era of Codeforces starts! :)

*6th

s

maybe 6 hrs.

Don't play ...................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

Wooops, thank you, fixed!

...........................................................................................

Hmm, they do count for now, like we manually delete users from the top-5 table who hack themselves too much. Though, I believe, it's easy to fix the tool to exclude these hacks, I'll check what I can do with it.

They count for the standing page but it seems a pretty fair solution to not count them in top-5, all in all.

Edit: Oh, forget about it) I coded this tool in a most disgusting way possible, too much effort needed to fix it now. Maybe when I finally decide to refactor all of it, I'll take that issue in a consideration.

Read the announcement, please.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Wow, the funniest thing that this link is copy-pasted not by me :D I don't know but I think Mike sends email manually or using some script/this is automatic process

You are an expert. You can not say yourself "Almost Legendary Grandmaster" .

http://mirror.codeforces.com/contest/484/submission/8757420

TBH, I have an opposite opinion. I'm not sure why, but I feel that vovuh usually does fairly easy problem (for me anyways). I'm kinda looking forward to his contest now

Do you have an example of a problem that would be good as Div3A?

It seems to me you are expecting this site to teach you competitive programming from scratch ("scratch" being not knowing how to code, or how to code competitively). Codeforces is not for that. It's for any level, but you have to master trivial problems to even have a level in the first place (I'm not trying to offend you, I'm just saying you need to try studying before competing). Not even Div3A (and definitively not Div2A) is a "trivial educational problem" such as "sum a and b, a,b <=1000", which you imply would make a good Div3A.
And please, don't shake it out on excellent problem setters such as vovuh or awoo because you don't like their style or had a bad day.

Можешь просить других участников взламывать себя)

Я не понимаю, как можно подобное подогнать под формулировку "сдача намеренно неверного решения". К счастью, подобных случаев не очень много, мы вполне можем разобраться, что было сделано специально для попадания в топ-5, а что являлось разумным взломом себя.

You can solve it with dynamic programming approach.

Let's DP(i, j, k) be the number of ways to form a regular bracket, we are at i-th position, degree of a regular bracket is j and we are at k-th position of string s.

Answer is DP(2 * n, 0, s.length()).

Passing state:

Consider the i-th position we want to put a '(', if s[k] == '(' then dp(i, j, k) -> dp(i + 1, j + 1, k + 1)

Otherwise we want to find such position l nearest with i and the part from k-l to k-1 is same as 0 to l-1 (we can precalculate it in O(n^3)). Then dp(i, j, k) -> dp(i + 1, j + 1, l)

Same as ')'.

For detail, you can see my solution: http://mirror.codeforces.com/contest/1015/submission/41048988

Sorry for bad English.

Edit: a problem using a similar technique having the "maximum prefix that is a suffix of the current string we are building" as a dimension for the dp is http://spoj.com/problems/PSTRING/

We will try to count sequences by the first occurrence of s in the sequence.

Pre-compute nxt[i][c='('/')'] which is the maximum prefix of s that is the suffix of (prefix of s of length i + c).

dp1[i][j][k] = we built i letters, the "bracket depth" is j, and the maximum prefix of s that is a suffix of the current string we are building is k

dp2[i][j] = we built i letters and the "bracket depth" is j

Note that we start with dp1[0][0][0]=1, and instead of transitioning to dp1[i][j][s.size()], transition to dp2[i][j]. The answer will be dp2[n][0].

Is there any suloition using inclusion/exclusion?

Have you have taken min distance of each point from the boundaries and naively checked for a mismatch?In this case,the max no of operations are less than 2e8.

Try to close facebook and try again :)

I had same problem. I avoided it by using firefox rather than chrome. Trust me, it'll work.

Print format should be %lld.

Test case 31 is 10 50 450. You can repeatedly move between 1 and 10 (of which the distance is 9) 50 times and reach 450. Not sure what made you think that the answer should be NO.

You wrote in your code:

prefixb[0] = b[0];
if(prefixb[0]>m){
    ans = -1;
}
for(int i=1;i<n;i++){
    prefixb[i] = prefixb[i-1]+b[i];
    if(prefixb[i]>=m){
        ans = -1;
        break;
    }	
}

if(prefixb[i]>=m) ans=-1 means that if sum of elements of array is equal to m then the answer will be -1, but the answer should be n.

Try to add this code:
~~~~~

for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
        b[i][j]=0;

~~~~~

Let call S1[i][j] be the furthest contiguous "1" that can be reach from block (i,j) upwards,S2[i][j] is the same but downwards, S3[i][j] is the same but leftmost,and S4[i][j] is the same but rightmost.

Its easy to see that with each (i,j) we need to greedily choose the longest star that we can create, and the longest one should be min(S1[i][j],S2[i][j],S3[i][j],S4[i][j]) — 1, note that if the min(..) — 1 = 0 then we can't create the star.

After that you're good to go, but in order to check the impossible case efficiently like in O(N*M) time, you need to break the problems down a little bit, say you have N Pairs of [L,R] segments, find which block that is not covered by any original N [L,R] Segments. Then if you solve this problems then you'll be able to check the case in O(N*M)

My solution is O(N^2LogN). I might have overcomplicated some parts of it, would love to know if there can be improvements.

Let the array a[][] be the input matrix, such that a[i][j] = 1 if there is a star on location, 0 otherwise.

For starters, it is easy to see that for each point (x, y), such that the point (x, y) has a star on it, we should make the longest star possible on that node. We need to accomplish this step efficiently.

We first create 2 arrays PrefixRight[][] and PrefixDown[][]. PrefixRight stores the row prefix sum over all (i, j) and PrefixDown stores the column prefix sum. We can do this with the following code —

for(i = 1; i <= n; i++)
    for(j = 1; j <= m; j++) PrefixRight[i][j] = PrefixRight[i][j - 1] + a[i][j];

for(i = 1; i <= m; i++)
    for(j = 1; j <= n; j++) PrefixDown[j][i] = PrefixDown[j - 1][i] + a[j][i];

Now, we have to find the maximum height of the star at some location (i, j). Interestingly, we can binary search over the height and check in O(1) time if it is possible using the prefix arrays we created above. Our condition evaluates to true if some contingencies are met, specifically that the number of stars between our point to a point that is vertically/horizontally at a distance h should be equal to h. These points are (x + h, y), (x — h, y), (x, y + h) and (x, y — h).

The following function check returns true if this condition is met.

int check(int x, int y, int h)
{
	if(x + h > n || x - h < 1 || y + h > m || y - h < 1) return 0;

	if(PrefixRight[x][y + h] - PrefixRight[x][y] != h) return 0;
	if(PrefixRight[x][y] - PrefixRight[x][y - h - 1] != h + 1) return 0;
	if(PrefixDown[x + h][y] - PrefixDown[x][y] != h) return 0;
	if(PrefixDown[x][y] - PrefixDown[x - h - 1][y] != h + 1) return 0;

	return 1;

}

After binary search-ing for the greatest height star we can make at a point, we have to find a way to store this result. We now create two arrays, DPRight[][] and DPDown[][]. We update our vertical results in DPDown and horizontal results in DPRight.

We also store this (x, y, h) result in a vector ans.

DPDown[x + h + 1][y]--;
DPDown[x - h][y]++;

DPRight[x][y + h + 1]--;
DPRight[x][y - h]++;

We can see that this is the prefix sum technique that allows updates in O(1) time. After doing this for all suitable points, we just need to take the row prefix sum for DPRight and column prefix sum for DPDown.

Now we just go over all points (x, y) and check if either DPRight[x][y] or DPDown[x][y] is true. If not, then our answer is no. Otherwise, our answer is yes, and we can just print the contents of our ans vector.

Code here: https://ideone.com/cPp2so

Would love to know a better solution.

Use a generator.

Currently, Codeforces Marathon Round 2 is judging mostly. It requires a lot of judges because of 1000 tests and 15 seconds TL. Sorry about it, but Codeforces Round 501 (Div. 3) is next!

I got 3 Ac . but there are a lot of system testing fails !

And why rating changes just for official differs from standings

Basically, it's just that Trusted participants != Rated participants.

https://en.wikipedia.org/wiki/Zhou_Enlai

Apparently he has been competing on CF in his grave. I wonder who snuck a computer in there for him.

Compete for the rise of China