"Everything is possible in ICPC as long as the community decides it should happen" — Bill Poucher.

Hello, community. I want to share my story about how our team got accepted to SEERC(Southeastern Europe Regional Contest) a couple of months ago and suddenly got declined a week ago(our registration was cancelled). I also want to ask some questions.

A little bit about regionals in Ukraine:

There are 2 stages before advancing to SEERC:

1. First stage is held in April(almost in the end of academic year) and all the teams from Ukraine have to attend to this stage in order to go to SEERC(there are also some exceptions)

2. Second stage is held in September(in the start of academic year)

There are also many "rules" for that stages, that are not mentioned anywhere in the official icpc.baylor.edu site.

That already doesn't make any sense because some students entering the university at the start of academic year will not be able to compete in current season, because they weren't participating in April. For example most countries can attend to SEERC without any stages before it.

Organization of first and second stage:

1. First stage is going simultaneously in 20+ different places in Ukraine for the same problemset. There is no any organization at all. Contest can be scheduled to start at 10AM and can start in 11AM. Teams from some places in Ukraine can get statements/login/passwords at 10AM, some of them can get statements/login/passwords at 11AM, although there is only one leaderboard for all the teams from Ukraine. There are always issues with judging system during 1st stage. Almost every year there are some issues like check failed, incorrect constraints, invalid test cases and so on. Most of the problems in the problemset for 1st stage are used from internet. Almost none of them are original.

2. Same issues are applied for second stage, but second stage is going in 5 different places and there is a bit lower percentage of problems from the internet and a bit lower percentage of issues like check failed, incorrect constraints, invalid test cases. Problemset of second stage usually contains 10-15 problems and 75% of them has difficulty  ≤  div2D. And it's always enough to solve this 75% to advance to SEERC.

The part of my story:

This year in July I was invited to enter Lviv National University and enter team to participate in ACM. One of the members of the team was competing in Finals(April 15 — April 20) this year and our first stage before SEERC for season 2019 was held in April 21(amazing, isn't it?). So he was not able to attend this stage because the ticket to Ukraine was booked for April 20 long ago and there was no way he could be in time. That's why he was allowed to create a new team that can attend to second stage or to SEERC. So I was invited to this team and one more person was taken. Here is our team: https://mirror.codeforces.com/team/46799. That's when all this started.

Ukrainian regional director didn't want to accept third member of our team, because he was marked as reserve for another team, that participated in the first stage(it wouldn't happen, if we hadn't that nonsense with stages). He didn't allow our team to participate in second stage with third member, but we had no another options. Regional director even supposed(or joked, I don't know) for us "to take pretty girl as third member, if we have no options".

So our coach decided to get in touch with regional director of SEERC and ask him if it's possible for our team to attend to SEERC. Regional director accepted our team then(it was in July). He said that there will be no problems with it. I relocated to Lviv from my home city and started team trainings. Also I entered Lviv National University in September. We trained for almost 3 months and here we got an information, that our team registration is suddenly rejected.

It appeared, that our ukrainian director wrote to SEERC regional director and him to reject our team registration, because our team was not accepted to stage 2 of ukrainian contest(because of stupid restriction for the third member that would not happen at all if there would be no that nonsense stages). SEERC regional director could still accept our team but he decided to avoid conflict with our ukrainian director and just rejected our team registration. And the point that we wasted 3 months of our time and a lot of resources to train as a team and that we wouldn't do that if he rejected our team registration at July was not an argument for him.

After that I wrote to Bill Poucher with describing this story and asking "Why did it happen?" and just got redirected to some kind of executive manager. And after some talking with him he just finally said to me(it's a quote from the letter): this tough decision is well founded by the regional leadership. I fully understand this is not what you hoped for, but the error is at the level of Lviv teams management. I understood then that it's pointless to talk with them.

I am posting it only after SEERC, because probably they can find a reason to disqualify another teams from our university and I don't really want this to happen.

So the questions are:

1. Why did it happen? It really doesn't make sense that we got approved for SEERC and rejected 2-3 months later.

2. Did somebody have similar problems in ACM? I already saw posts about ACPC multiple times and posts about IOI with similar nonsense situations. It's really sad that something like that happens.

3. Is it possible to deal with this problem? Can our team somehow be transferred to another region?

Hello everybody. I am pretty interested in AI programming and I am wondering where I can get any information about possible current or upcoming AI contests/events. Are there any resources connected to it? Thank you in advance.

Since the last blog about codechef Algorithmist was deleted, we can discuss it here.

In this post I will describe inadequate solutions for 4 hackerrank problems from last 2 codesprint contest, that I participated(with difficulty hard-advanced), that get 100% score and provide counter-test to each solution.

NCR Codesprint, Coconut Plantation

At first we will water plants, as described in official editorial:

For example, we need to water squares (2,2,3,3) and (3,3,4,4). We add one to the highest cells of this square and decrement one from cells under this square. After we do this with all rectangles, we can get array of watered coconuts by simple cycle:

for (int i = 0; i < r; i++)
 for (int j = 0; j < c; j++)
  b[i][j] = (i>0?b[i-1][j]:0) + a[i][j]; // a[i][j] is array from the picture

We got array b and now we change values of b[i][j] to 1 if b[i][j] >= m else to 0.

In official editorial something is said about HopCroft-Karp algorithm, but I don't even know what is it. So I will try to solve it greedily. We go through all array and find out cells that have only horizontal or only vertical neighbours. It's obvious, that then for horizontal neighbours we have to draw horizontal line through this cell and for vertical neighbours we have to draw vertical line.

We can do nothing after that and this solution will already get 32.00/60.00 points, but it doesn't work even on my random picture case. Code

I will name non-harvested cells free now.

Now we go through all not harvested cells and find out for each cell max(free cells that we can reach from this cell moving horizontally, free cells that we can reach from this cell moving vertically).

Then we sort this cells by decreasing order of this value. Now we go through cells and from each free cell we move horizontally or vertically depending on where is more free cells left. And BOOM, it gets 60/60. Code

Counter-test:

1
7 7 3 1
0 0 6 1
0 0 2 5
4 0 6 5

NCR Codesprint, Area of Triangles

For this task you can just look at this pseudocode and picture and you will understand my solution.

S=0
double dy = 10000000./n;
double dx = (maxx-minx)/dy;
for (double i = minx+dx/2; i <= maxx; i+= dx)
   S += area of triangles on the line x=i //for example for sample case for i=3 area will be equal to 3, for i=2 area=4
print (maxx-minx)*S/dy

Code

Counter-test:

2
-1000000 0 -1000000 1 -999999 0
1000000 0 1000000 1 999999 0

University CodeSprint, Array Construction

I think, I wrote pretty cool solution for this challenge, but it still shouldn't pass TL. Assume, that the answer array for each queue is [ans₁, ..., ans_n].

The sum of absolute differences between each pair of elements will be (ans₂ - ans₁) * (n - 1) * 1 + (ans₃ - ans₂) * (n - 2) * 2 + ... + (ans_n - ans_n - 1) * 1 * (n - 1)

We can go on dp[i][j][k], where dp[i][j][k] means if it's possible to get sum j and sum of absolute differences k for first i elements.

Passing from state to state then will be:

if (dp[i][j][k]) dp[i + 1][j + l * (n - i)][k + (n - i) * i * l] = true

where l is ans_i + 1 - ans_i and we are iterating l from 0 to the time when j + l * (n - i) > 200 or k + (n - i) * i * l > 2000, it will be at average 4 iterations, I guess.

So I precalced dp for all n = 1... 50. It seems, like complexity of this should be O(n * n * s * k), what is very much, but it takes only approximately 67 * 10⁶ operations if we make this dp recursively, but it still couldn't pass TL(precalc was working for 3.3s in CF custom invocation). While dp was done recursively, I was remembering current array, so I could save the answer, when I met triple(i,j,k), that is required from the queries.

But still it works for 3.3s. So I decided not to iterate through all n = 1... 50, but only through n, that was required from the queries and my solution passed in 1.83s. That's not a very big fail in testcases, but it still makes sense.

Code

Counter-test:

50
1 0 0
2 0 0
...
50 0 0

University CodeSprint, Counting On a Tree

I was trying to come up with normal solution like O(n * sqrt(n) * log(n)) or O(n * log³(n)) for whole day, but then I saw this comment. You can see nothing special here, just mad guy, but if you pay more attention to this comment, you will see this sentence: "Problemsetter of last problem said that he will change the test cases, because I told him my old solution with complexity N^2 passed"

CHALLENGE ACCEPTED. It's time to write O(N²) solution.

I wrote this code:

for (i = 0; i < q; i++)
	{
		scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
		ll ans = 0;
		while (!upper(x1,y1))//upper(x1,y1) is function, that check if y1 is in subtree with vertice x1 
		{
			b[a[x1]]++;//a[i] is value of i-th vertex
			x1 = pr[x1];//pr[v] is ancestor of v
		}
		while (y1 != x1)
		{
			b[a[y1]]++;
			y1 = pr[y1];
		}
		b[a[x1]]++;
		
		while (!upper(x2,y2))
		{
			ans+=b[a[x2]];
			x2 = pr[x2];
		}
		while (y2 != x2)
		{
			ans+=b[a[y2]];
			y2 = pr[y2];
		}
		ans+=b[a[x2]];
		cout << ans << endl;
	}

It worked maximum in 1.8s on all testcases and it got WA, because I was not assigning array b to zero and didn't substract the length of two paths intersection. I could go through path (x1,y1) and assign b[a[x1]] to zero, but it would take approximately 0.9s more, so 2.7s will not pass. I almost surrendered trying to optimize this so it will pass in 2s, but then I got an idea. Java got 4s time limit on hackerrank, so I can try to make this solution pass in Java.

I don't know, what's wrong with Java compilator, but same solution was getting randomly TL from set {5,8,11,14,17} of testcases. For example for first time it was getting TL 5,8,14, and for second time it was getting TL 11,17. I separated finding length of two paths intersection by LCA and going through whole path and counting array b, somehow it got accepted.

Code

Counter-test can be generated by this code:

cout << 100000 << " " << 50000 << endl;
for (i = 0; i < 100000; i++)
 cout << 1 << " ";
cout << endl;
for (i = 0; i < 99999; i++)
 cout << i << " " << i+1 << endl;
for (i = 0; i < 50000; i++)
 cout << 1 << " " << 100000 << endl;

My code will get TL for sure and WA because the answer will be approximately 5 × 10⁹ and it doesn't fit an integer.

P.S. This post doesn't contain offense to hackerrank admins and community. I just want to show mistakes, so maybe they will improve. Contests with prize pool 15000$ are pretty cool, but I think that Hackerrank must pay more attention to creating testcases by writing naive solutions to each problem and stresstesting, so inadequate solutions will not pass during the contest.

677A - Vanya and Fence

For each friend we can check, if his height is more than h. If it is, then his width is 2, else 1.

Complexity O(n).

#include <iostream>
using namespace std;
typedef long long ll;
ll i,n,h,ans,x;
int main()
{
	cin >> n >> h;
	ans = n;
	for (i = 0; i < n; i++)
	{
		cin >> x;
		ans += (x>h);
	}
	cout << ans << endl;
	return 0;
}

677B - Vanya and Food Processor

The solution, that does same thing, as in the problem statement will fail with TL, because if the height of each piece of potato will be 10⁹ and smashing speed will be 1, then for each piece we will do 10⁹ operations.

With each new piece of potato a_i we will smash the potato till a[i] MOD k, so we will waste a[i] / k seconds on it. If we can not put this piece of potato after that, we will waste 1 more second to smash everything, that inside, else just put this piece. We will get an answer same as we could get with actions from the statement.

Complexity O(n).

#include <iostream>
#include <stdio.h>
using namespace std;
typedef long long ll;
ll i,n,h,ans,x,cur_h,k;
int main()
{
	cin >> n >> h >> k;
	ans = 0;
	cur_h = 0;
	for (i = 0; i < n; i++)
	{
		scanf("%I64d", &x);
		if (cur_h + x <= h)
		   cur_h += x;
		else
			ans++, cur_h = x;
		ans += cur_h/k;
		cur_h %= k;
	}
	ans += cur_h/k;
	cur_h %= k;
	ans += (cur_h>0);
	cout << ans << endl;
	return 0;
}

677C - Vanya and Label

We can transform our word in binary notation, we can do it easily, because 64 = 2⁶. Move through the bits of this number: if bit is equal to 0, then we can have 3 different optinos of this bit in our pair of words: 0&1, 1&0, 0&0, else we can have only one option: 1&1. So the result will be 3^nullbits, where nullbits — is amount of zero bits.

Complexity O(|s|).

#include <iostream>
#include <stdio.h>
#include <string>
#define MOD 1000000007
using namespace std;
typedef long long ll;
ll i,j,n,h,ans,x,cur_h,k;
string s;
string pattern;
ll symbol_val[305];
int main()
{
	cin >> s;
	for (char i = '0'; i <= '9'; i++)
		pattern.push_back(i);
	for (char i = 'A'; i <= 'Z'; i++)
		pattern.push_back(i);
	for (char i = 'a'; i <= 'z'; i++)
		pattern.push_back(i);
	pattern.push_back('-');
	pattern.push_back('_');
	for (i = 0; i < 64; i++)
		symbol_val[pattern[i]] = i;
	ll ans = 1;
	for (i = 0; i < s.size(); i++)
	{
		ll x = symbol_val[s[i]];
		for (j = 0; j < 6; j++)
			if ((x&(1<<j)) == 0)
			   ans = (ans*3)%MOD;
	}
	cout << ans << endl;
	return 0;
}

677D - Vanya and Treasure

We can make dynamic programming dp[col][row], where dp[col][row] is minimal time, that we have waste to open the chest in the cell (col, row). For the cells of color 1: dp[x][y] = x + y. For each next color color we can look over all cells of color color - 1 and all cells of color color, then for each cell of color color with coordinates (x1, y1) and for each cell with color color - 1 and coordinates (x2, y2) dp[x1][y1] = dp[x2][y2] + abs(x1 - x2) + abs(y1 - y2).

But complexity of this solution is O(n²·m²), what is not enough.

We can do such improvement: let cnt[x] be the amount of cells of color x, then when cnt[color]·cnt[color - 1] ≥ n·m, we can do bfs from cells of color color - 1 to cells of color color.

Then we will have complexity O(n·m·sqrt(n·m)).

Proof

#include <iostream>
#include <stdio.h>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
#define MOD 1000000007
#define N 2005
#define mp make_pair
#define X first
#define Y second
using namespace std;
typedef int ll;
ll i,j,n,h,x,y,cur_h,k,m,p,fx,fy;
ll a[505][505], dp[505][505], d[505][505];
ll dir[4][2] = {{-1,0},{1,0},{0,1},{0,-1}};
vector<pair<ll,ll> > g[250505];
vector<pair<ll, pair<ll,ll> > > lst, bfs;
ll Abs(ll x)
{
	return x>0?x:-x;
}
ll find_dist(ll x1, ll y1, ll x2, ll y2)
{
	return Abs(x1-x2) + Abs(y1-y2);
}
bool in_range(ll x, ll y)
{
	return (x >= 0 && x < y);
}
int main()
{
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	cin >> n >> m >> p;
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			dp[i][j] = (ll)1e+9;
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
		{
			scanf("%d", &a[i][j]);
			g[a[i][j]].push_back(mp(i,j));
			if (a[i][j] == 1)
			   dp[i][j] = i+j;
			if (a[i][j] == p)
			   fx = i, fy = j;
		}
	for (i = 2; i <= p; i++)
	{
		ll cur_size = g[i].size();
		ll last_size = g[i-1].size();
		if (cur_size * last_size <= n * m)
		{
			for (j = 0; j < cur_size; j++)
			{
				ll cur_x = g[i][j].X;
				ll cur_y = g[i][j].Y;
				for (k = 0; k < last_size; k++)
				{
					ll last_x = g[i-1][k].X;
					ll last_y = g[i-1][k].Y;
					dp[cur_x][cur_y] = min(dp[cur_x][cur_y], dp[last_x][last_y] + find_dist(cur_x,cur_y,last_x,last_y));
				}
			}
		} else
		{
			for (k = 0; k < n; k++)
				for (j = 0; j < m; j++)
					d[k][j] = -1;
			bfs.clear();
			lst.clear();
			for (j = 0; j < last_size; j++)
			{
				ll last_x = g[i-1][j].X;
				ll last_y = g[i-1][j].Y;
				lst.push_back(mp(dp[last_x][last_y], mp(last_x, last_y)));
			}
			sort(lst.begin(), lst.end());
			ll pointer = 1;
			j = 0;
			bfs.push_back(lst[0]);
			d[lst[0].Y.X][lst[0].Y.Y] = lst[0].X;
			while (j < bfs.size())
			{
				ll x = bfs[j].Y.X;
				ll y = bfs[j].Y.Y;
				ll val = bfs[j].X;
				j++;
				while (pointer < lst.size() && lst[pointer].X <= val)
					  bfs.push_back(lst[pointer++]);
				for (k = 0; k < 4; k++)
					if (in_range(x+dir[k][0], n) && in_range(y+dir[k][1], m) && d[x+dir[k][0]][y+dir[k][1]] == -1)
					{
						d[x+dir[k][0]][y+dir[k][1]] = val+1;
						bfs.push_back(mp(val+1, mp(x+dir[k][0], y+dir[k][1])));
					}
			}
			for (j = 0; j < cur_size; j++)
			{
				ll cur_x = g[i][j].X;
				ll cur_y = g[i][j].Y;
				dp[cur_x][cur_y] = d[cur_x][cur_y];
			}
		}
	}
	cout << dp[fx][fy] << endl;
	return 0;
}

There also exists solution with 2D segment tree:

#include <iostream>
#include <stdio.h>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
#define MOD 1000000007
#define N 512
#define mp make_pair
#define X first
#define Y second
using namespace std;
typedef int ll;
ll i,j,n,h,x,y,glob,k,m,p,fx,fy;
ll a[505][505], dp[505][505], d[505][505], t[4][2005][2005];
ll dir[4][2] = {{-1,0},{1,0},{0,1},{0,-1}};
vector<pair<ll,ll> > g[250505];
vector<pair<ll, pair<ll,ll> > > lst, bfs;
ll Abs(ll x)
{
	return x>0?x:-x;
}
ll find_dist(ll x1, ll y1, ll x2, ll y2)
{
	return Abs(x1-x2) + Abs(y1-y2);
}
bool in_range(ll x, ll y)
{
	return (x >= 0 && x < y);
}

int get (int lx, int rx, int ly, int ry) {
	rx++;
	ry++;
	int res = MOD;
	ll l = ly, r = ry;
  for (lx += N, rx += N; lx < rx; lx >>= 1, rx >>= 1) {
  	if (rx&1)
  	{
  		ly = l; ry = r;
	    rx--;
	    for (ly += N, ry += N; ly < ry; ly >>= 1, ry >>= 1) {

		    if (ly&1)
		    {
		       res = min(res, t[glob][rx][ly]);
		       ly++;
		    }
			if (ry&1)
			{
			    --ry;
			    res = min(res, t[glob][rx][ry]);
			}
		}
	}
    if (lx&1)
    {
    	ly = l; ry = r;
		for (ly += N, ry += N; ly < ry; ly >>= 1, ry >>= 1) {

		    if (ly&1)
		    {
		       res = min(res, t[glob][lx][ly]);
		       ly++;
		    }
			if (ry&1)
			{
			    --ry;
			    res = min(res, t[glob][lx][ry]);
			}
		}
	    lx++;
    }
  }
  return res;
}

void update (int x, int y, int val) {
	ll tmp = y;
	t[glob][x+N][tmp+N] = val;
	for (x += N; x > 1; x >>= 1)
	{
		y = tmp;
		for (y += N; y > 1; y >>= 1)
		{
			t[glob][x][y>>1] = min(t[glob][x][y], t[glob][x][y^1]);
			t[glob][x>>1][y] = min(t[glob][x][y], t[glob][x^1][y]);
		}
		t[glob][x>>1][y] = min(t[glob][x][y], t[glob][x^1][y]);
	}
}


int main()
{
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	cin >> n >> m >> p;
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			dp[i][j] = MOD;
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
		{
			scanf("%d", &a[i][j]);
			g[a[i][j]].push_back(mp(i,j));
			if (a[i][j] == 1)
			   dp[i][j] = i+j;
			if (a[i][j] == p)
			   fx = i, fy = j;
		}
	for (i = 0; i <= N*2; i++)
		for (j = 0; j <= N*2; j++)
			for (k = 0; k < 4; k++)
				t[k][i][j] = MOD;
	//UR - dp[x2][y2] = dp[x1][y1] + x2-x1+y2-y1 = dp[x1][y1]-x1-y1+(x2+y2)
	//UL - dp[x2][y2] = dp[x1][y1] + x2-x1+y1-y2 = dp[x1][y1]-x1+y1+(x2-y2)
	//DR - dp[x2][y2] = dp[x1][y1] + x1-x2+y2-y1 = dp[x1][y1]-y1+x1+(y2-x1)
	//DL - dp[x2][y2] = dp[x1][y1] + x1-x2+y1-y2 = dp[x1][y1]+x1+y1+(-x2-y2)
	for (i = 2; i <= p; i++)
	{
		ll last_sz = g[i-1].size();
		for (j = 0; j < last_sz; j++)
		{
			ll x = g[i-1][j].X;
			ll y = g[i-1][j].Y;
			glob = 0;
			//cout << x << " " << y << " " << get( 0, x, 0, y) << "g" << endl;
			update(x,y,dp[x][y]-x-y);
			//cout << get( 0, x, 0, y) << "f" << endl;
			glob = 1;
			update(x,y,dp[x][y]-x+y);
			glob = 2;
			update(x,y,dp[x][y]+x-y);
			glob = 3;
			update(x,y,dp[x][y]+x+y);
		}
		ll cur_sz = g[i].size();
		for (j = 0; j < cur_sz; j++)
		{
			ll x = g[i][j].X;
			ll y = g[i][j].Y;
			glob = 0;
			//cout << get( 0, x, 0, y) << endl;
			dp[x][y] = min(dp[x][y], get( 0, x, 0, y)+x+y);
			glob = 1;
			dp[x][y] = min(dp[x][y], get(0, x, y, m-1)+x-y);
			glob = 2;
			dp[x][y] = min(dp[x][y], get(x, n-1, 0, y)-x+y);
			glob = 3;
			dp[x][y] = min(dp[x][y], get(x, n-1, y, m-1)-x-y);
		}
		for (j = 0; j < last_sz; j++)
		{
			ll x = g[i-1][j].X;
			ll y = g[i-1][j].Y;
			glob = 0;
			update(x,y,MOD);
			glob = 1;
			update(x,y,MOD);
			glob = 2;
			update(x,y,MOD);
			glob = 3;
			update(x,y,MOD);
		}
	}
	/*for (i = 0; i < n; i++)
	{
		for (j = 0; j < m; j++)
			cout << dp[i][j] << " ";
		cout << endl;
	}*/
	cout << dp[fx][fy] << endl;
	return 0;
}

677E - Vanya and Balloons

For each cell (x, y) take the maximum possible cross with center in this cell, that doesn't contains zeros. To do it fast, we can make arrays of partial sums for all possible 8 directions, in which each cell will contain the number of non-zero balloons in each direction. For example, if we want to know, how many non-zero balloons are right to cell (x, y), we can create an array p[x][y], where p[x][y] = p[x][y - 1] + 1 if a[x][y]! = 0 else p[x][y] = 0

So now we can for each cell (x, y) we can find the maximum size of cross with the centre in this cell, that will not contain zeros.

We can compare product for crosses with centers in the cells (x, y) and radius r using logarythms. For example, if we need to compare 2 crosses with values x₁·x₂·...·x_n and y₁·y₂·...·y_m, we can compare log(x₁·x₂·...·x_n) and log(y₁·y₂·...·y_n), what will be equivalent to comparing log(x₁) + log(x₂) + ... + log(x_n) and log(y₁) + log(y₂) + ... + log(y_m).

We can also use partial sum arrays to find value log(x₁) + log(x₂) + ... + log(x_n) for each cross, so we can find the product of the values in each cross for O(1) time.

Complexity O(n²).

#include <iostream>
#include <stdio.h>
#include <string>
#include <cmath>
#define MOD 1000000007
#define N 2005
using namespace std;
typedef unsigned int ll;
ll i,j,n,h,x,y,cur_h,k,dir;
ll pre[8][N][N];
double sums[8][N][N],ans,logs[N][N],lg2,lg3;
ll ansx,ansy,anssize,ansdir;
ll total;
ll directions[8][2] = {{-1,-1},{-1,1},{1,-1},{1,1},{1,0},{0,1},{-1,0},{0,-1}};
char a[N][N];
bool in_range(ll x)
{
	return (x >= 0 && x < n);
}
int main()
{
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	lg2 = log(2);
	lg3 = log(3);
	cin >> n;
	for (i = 0; i < n; i++)
		scanf("%s",a[i]);
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			if (a[i][j] == '3')
			   logs[i][j] = lg3;
			else if (a[i][j] == '2')
		 		 logs[i][j] = lg2;
	for (dir = 0; dir < 8; dir++)
	{
		for (i = 0; i < n; i++)
			for (j = 0; j < n; j++)
				if (!in_range(i-directions[dir][0]) || !in_range(j-directions[dir][1]))
				{
					k = 0;
					ll d1 = directions[dir][0], d2 = directions[dir][1];
					for (x = i, y = j; in_range(x) && in_range(y); x += d1, y += d2)
					{
						if (a[x][y] != '0')
						{
						   k++;
						   if (x == i && y == j)
							  sums[dir][x][y] = logs[i][j];
						   else
							   sums[dir][x][y] = sums[dir][x-d1][y-d2] + logs[x][y];
			   			}
						else
						{
							sums[dir][x][y] = 0;
							k = 0;
						}
						pre[dir][x][y] = k;
					}
				}
	}
	ans = -1;
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
		if (a[i][j] != '0')
		{
			ll tmp = n+5;
			for (k = 0; k < 4; k++)
				tmp = min(tmp, pre[k][i][j]);
			double val = logs[i][j];
			for (k = 0; k < 4; k++)
				val += sums[k][i+directions[k][0]*(tmp-1)][j+directions[k][1]*(tmp-1)] - sums[k][i][j];
			if (val > ans)
			{
				ans = val;
				ansx = i;
				ansy = j;
				anssize = tmp;
				ansdir = 0;
			}
			
			tmp = n+5;
			for (k = 4; k < 8; k++)
				tmp = min(tmp, pre[k][i][j]);
			val = logs[i][j];
			for (k = 4; k < 8; k++)
				val += sums[k][i+directions[k][0]*(tmp-1)][j+directions[k][1]*(tmp-1)] - sums[k][i][j];
			if (val > ans)
			{
				ans = val;
				ansx = i;
				ansy = j;
				anssize = tmp;
				ansdir = 4;
			}
		}
	total = a[ansx][ansy]-'0';
	for (k = ansdir; k < ansdir+4; k++)
	{
		for (i = 1; i < anssize; i++)
			total = (total*(a[ansx+directions[k][0]*i][ansy+directions[k][1]*i]-'0'))%MOD;
	}
	cout << total << endl;
	return 0;
}

Greetings to the Codeforces community!

Regular Codeforces round #355 for participants from the second division will take place on 1 June, 19:35 MSK. Participants from the first division are able to participate out of the contest.

It is my third round on Codeforces. Hope you will enjoy this round.

I want to thank Gleb Evstropov (GlebsHP) for help with preparation of this round and Mike Mirzayanov (MikeMirzayanov) for great Codeforces and Polygon systems.

Participants will be given five problems and two hours to solve these problems.

UPD Score distribution: 500-1000-1500-2250-2250

UPD Editorial is here

UPD Congratulations to the winners!

Div. 2

1. fake_fake

2. __Wind

3. Mamedov

4. dianaasau

5. Sorry_Daikon

Div. 1

1. Um_nik

2. TimonKnigge

3. vintage_Vlad_Makeev

4. anta

5. kmjp

552A - Vanya and Table

In this problem we can get AC with many solutions:

1) With every new rectangle we will add his area to the result, so for each line x₁, y₁, x₂, y₂ we will add to answer (x₂ - x₁ + 1) * (y₂ - y₁ + 1)

Time complexity O(n).

2) We can just do all, that is written in the statement: create an array and with each new rectangle we can just increment every element inside rectangle. In the end we can just add all elements inside this array.

Time complexity O(n * x * y)

C++ code Wild_Hamster

Java code Wild_Hamster

Python code Zlobober

552B - Vanya and Books

We can find out a formula for this problem:

for n < 10 answer will be n = n - 1 + 1 = 1 * (n + 1) - 1;

for n < 100 answer will be 2 * (n - 9) + 9 = 2 * n - 9 = 2 * n - 10 - 1 + 2 = 2 * (n + 1) - 11;

for n < 1000 answer will be 3 * (n - 99) + 2 * (99 - 9) + 9 = 3 * n - 99 - 9 = 3 * n - 100 - 10 - 1 + 3 = 3 * (n + 1) - 111;

so for n < 10^sz answer will be ;

Time complexity O(sz), where sz is the length of n.

We also could just try 10 options n < 10, n < 100, ..., n < 10⁹, n = 10⁹ and solve problem for each option.

UPD: Don't use function pow() to find powers of 10, because it doesn't work right sometimes.

C++ code Wild_Hamster

Java code Wild_Hamster

Python code Zlobober

552C - Vanya and Scales

Convert m to number system of base w. If all digits of number – 0 or 1, then we can measure the weight of the item with putting weights, that have digits equal to 1, on one pan, and our item on another one.

If this condition isn't satisfied, then we should iterate from lower digit to high and if digit is not equal to 0 or 1, we try to substract w from it and increment higher digit. If it becomes equal to  - 1, then we can put weight with number of this digit on the same pan with our item, if it becomes equal to 0, then we don't put weight, in another case we can't measure the weight of our item and answer is .

Time complexity O(logm).

C++ code Wild_Hamster

Java code Wild_Hamster

Java code Zlobober

552D - Vanya and Triangles

We can look through all pair of points, draw line through each pair and write, that this line includes these 2 points. We can do it with map. If some line includes x points, then in fact we counted, that it has 2 * x * (x - 1) points, because we included each point 2*(x-1) times in this line.

We can create an array and add to him values b[2 * x * (x - 1)] = x, so we can define, how many points is on the line. Then we can iterate through all lanes and for each line with x points we will loose x * (x - 1) * (x - 2) / 6 possible triangles from all possible n * (n - 1) * (n - 2) / 6 triangles. Decide, that at first ans = n * (n - 1) * (n - 2) / 6. So for every line, that includes x points, we will substract x * (x - 1) * (x - 2) / 6 from ans.

Time complexity O(n² * logn).

C++11 code Wild_Hamster

Java code Wild_Hamster

Java code Zlobober

UPD: I am sorry, that O(n3 / 6) solutions passed, my solution with O(n3 / 6) didn't pass before the contest, so I decided, that TL 4 sec is good(it was for Java TL).

552E - Vanya and Brackets

We can see, that we can reach maximal answer, when brackets will be between two signs  * , or between one sign  *  and the end of expression. For convenience we will add in the begin of expression 1 * , and in the end of expression  * 1.

After that we can iterate all possible pairs of signs  *  and count the expression with putting brackets between two signs  *  for each pair.

We can use two variables x and y to count the value of expression, in the begin x = 0, y = firstnumber, where firstnumber is first digit of expression, then if next sign is  + , then x = y, y = nextnumber, and if next sign is  * , then x = x, y = y * nextnumber. The value of expression will be x + y, we can create function, like that, to count expressions inside and outside the brackets.

Time complexity O(|s| * 17²).

C++ code Wild_Hamster

Java code Wild_Hamster

Java code Zlobober

P.S. Sorry for my bad english, I will try to correct mistakes in the near time.

UPD: Editorial from hsk

Greetings to the Codeforces community!

Regular Codeforces round #308 for participants from the second division will take place on 18 June, 19:30 MSK. Participants from the first division are able to participate out of the contest.

It is my second round on Codeforces(First round — Codeforces Round 280 (Div. 2)). Hope you will enjoy this round.

I want to thank Max Akhmedov (Zlobober) for help with preparation of this round, Maria Belova (Delinur) for translation of statements and Mike Mirzayanov (MikeMirzayanov) for great Codeforces and Polygon systems.

Participants will be given five problems and two hours to solve these problems.

UPD: Scoring is standard: 500-1000-1500-2000-2500.

UPD: Congratulation to the winners:

1. Ttocs45

2. RNS_JKS

3. RNS_CUS

4. kouekosita

5. grenade

UPD: Contest is over. Thanks for participating :)

UPD: Editorial

492A - Vanya and Cubes.

In fact need to do what is asked in the statement. We need to find in a cycle the maximum height h, counting, how many blocks must be in i-th row and adding these values to the result. Iterate until the result is not greater than n.

Jury's solution: 8924831

492B - Vanya and Lanterns.

Sort lanterns in non-decreasing order. Then we need to find maximal distance between two neighbour lanterns, let it be maxdist. Also we need to consider street bounds and count distances from outside lanterns to street bounds, it will be (a[0] - 0) and (l - a[n - 1]). The answer will be max(maxdist / 2, max(a[0] - 0, l - a[n - 1]))

Time complexity O(nlogn).

Jury's solution: 8924823

492C - Vanya and Exams.

Sort (a_i, b_i) in non-decreasing order for number of essays b_i, after that go from the beginning of this sorted pairs and add greedily the maximal number of points we can, i.e. add value min(avg * n - sum, r - a_i), while total amount of points will not be greater, than avg * n.

Time complexity O(nlogn).

Jury's solution: 8924807

492D - Vanya and Computer Game.

Let's create vector rez with size x + y, in which there will be a sequence of Vanya's and Vova's strikes for the first second. To do this, we can take 2 variables cntx = cnty = 0. Then while cntx < x and cnty < y, we will check 3 conditions:

1) If (cntx + 1) / x > (cnty + 1) / y, then add into the vector word “Vova”, cnty++.

2) If (cntx + 1) / x < (cnty + 1) / y, then add into the vector word “Vanya”, cntx++.

3) If (cntx + 1) / x = (cnty + 1) / y, then add into the vector word “Both” 2 times, cntx++, cnty++.

Then we are able to respond on each query for О(1), the answer will be rez[(a_i - 1)mod(x + y)].

Time complexity O(x + y).

Jury's solution: 8924773

492E - Vanya and Field.

As long as gcd(dx, n) = gcd(dy, n) = 1, Vanya will do full cycle for n moves. Let's group all possible pathes into n groups, where 1 - th, 2 - nd, ... , n - th path will be started from points (0, 0), (0, 1), …, (0, n - 1). Let's look on first path: (0, 0) - (dx, dy) - ((2 * dx) mod n, (2 * dy) mod n) - ... - (((n - 1) * dx) mod n, ((n - 1) * dy) mod n). As long as gcd(dx, n) = 1, among the first coordinates of points of the path there will be all the numbers from 0 to n - 1. So we can write in the array all relations between the first and second coordinate in points for the path, that starts in the point (0, 0), i.e. y[0] = 0, y[dx] = dy, ... , y[((n - 1) * dx) mod n] = ((n - 1) * dy) mod n. Now we know, that all points with type (i, y[i]), where 0 ≤ i ≤ n - 1, belong to the group with start point (0, 0). In that case, points with type (i, (y[i] + k)modn) belong to the group with start point (0, k). Then we can add every point (x_i, y_i) to required group k for О(1): (y[x_i] + k) mod n = y_i, k = (y_i - y[x_i] + n) mod n. Then we need just to find group with the maximal amount of elements, it will be the answer.

Time complexity O(n).

Jury's solution: 8924746

P.S. Sorry for my bad English, I hope, I will correct this editorial as much, as possible.

Greetings to the Codeforces community!

Regular Codeforces round #280 for participants from the second division will take place on 1 December, 19:30 MSK. Participants from the first division are able to participate out of the contest.

It is my first round on Codeforces. Hope you will enjoy this round.

I want to thank Max Akhmedov (Zlobober) for help with preparation of this round, Maria Belova (Delinur) for translation of statements and Mike Mirzayanov (MikeMirzayanov) for great Codeforces and Polygon systems.

Participants will be given five problems and two hours to solve these problems.

UPD: Scoring is standard — 500-1000-1500-2000-2500.

UPD: Thanks to everyone, who participated in the round!

Congratulations to the winners:

1.alex_y

2.wingemerald

3.Eric94

4.Zpw987

5.rabbit_TR

standings

UPD: Editorial is here.