"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://codeforces.net/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?

Сегодня проходила 1/4 финала Украины. Очень интересно она проходила в западном регионе. Некоторые команды хотели поучавствовать вне конкурса на Львовськой площадке, но т. Месюра уничтожил эту инициативу. Интересный факт: логины и пароли для участия в пробном раунде были для команд вне конкурса, а логинов и паролей в официальном раунде для команд вне конкурса не было, что очень логично(нет). Отсюда вопросы: "Почему командам не разрешили учавствовать неофициально? Давали ли логины/пароли для команд вне конкурса у других регионах? Почему т. Месюра убивает и так уже почти мёртвый АСМ в Украине?"

Пост создан так же для обсуждения отличных задач/баянов с четвертьфинала.

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 - Ваня и забор

Для каждого друга смотрим, будет ли его высота больше h. Если да, то его ширина — 2, иначе — 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 - Ваня и кухонный комбайн

Решение, которое просто делает то, что описано в условии, не пройдет, т.к. если высота каждой картофелины будет 10⁹, а скорость измельчения — 1, то на каждую картофелину будем тратить 10⁹ операций.

С каждой новой картофелиной высотой a_i будем измельчать картофель до высоты a_i MOD k, тогда мы будем тратить на это a[i] / k секунд. Если мы не можем засунуть после этого новую картофелину, то мы потратим еще 1 секунду, иначе просто положим эту картофелину. Мы получим такой же ответ, как бы если мы делали то, что описано в условии.

Асимптотика 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 - Ваня и надпись

Переведем слово в 2-ичную систему счисления, это сделать легко, так как 64 — степень двойки. Проходимся по битах этого числа: если бит равен 0, то у нас может быть 3 различных варианта этого бита в нашей паре слов: 0&1, 1&0, 0&0, иначе только один вариант: 1&1. В таком случае результатом будет 3^nullbits, где nullbits — количество нулевых битов.

Асимптотика 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 - Ваня и сокровище

Сделаем динамику dp[col][row], где dp[col][row] — минимальное время, которое нужно для того, чтобы открыть сундук в клетке (col, row). Для клеток цвета 1 dp[x][y] = x + y. Для каждого следующего цвета color будем перебирать все клетки цвета color - 1 и все клетки цвета color, тогда для каждой клетки цвета color с координатами (x1, y1) и клетки цвета color - 1 с координатами (x2, y2) dp[x1][y1] = dp[x2][y2] + abs(x1 - x2) + abs(y1 - y2).

Но этого решения будет недостаточно, так как его асимптотика — O(n²·m²)

Можем сделать такое улучшение: пусть cnt[x] — количество клеток цвета x, тогда когда cnt[color]·cnt[color - 1] ≥ n·m, можно сделать поиск в ширину от клеток цвета color - 1 к клеткам цвета color.

В таком случае будет асимптотика O(n·m·sqrt(n·m)).

Доказательство

#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;
}

Также есть решение с использованием двухмерного дерева отрезков:

#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 - Ваня и шарики

Для каждой клетки (x, y) в таблице возьмем максимально возможный крест, в котором не присутствуют нули. Чтобы сделать это быстро, сохраним массивы частичных сумм для всех возможных 8 направлений, где каждая клетка будет обозначать количество ненулевых шариков в каждом из направлений. Например для того, чтобы узнать, сколько ненулевых шариков находится справа от клетки (x, y), создадим массив p[x][y], в котором p[x][y] = p[x][y - 1] + 1 если a[x][y]! = 0 иначе p[x][y] = 0

Таким образом для каждой клетки (x, y) мы можем найти крест максимального размера, в котором не будет нулей.

Мы можем сравнить значения произведений для крестов в координатах (x, y) и с радиусом r, воспользовавшись логарифмированием. К примеру, если нам нужно сравнить кресты с значениями x₁·x₂·...·x_n и y₁·y₂·...·y_m, мы можем сравнить log(x₁·x₂·...·x_n) и log(y₁·y₂·...·y_n), что будет эквивалентно сравнению log(x₁) + log(x₂) + ... + log(x_n) и log(y₁) + log(y₂) + ... + log(y_m).

Таким образом для нахождения значения log(x₁) + log(x₂) + ... + log(x_n) для каждого креста мы можем аналогично хранить массивы частичных сумм для каждого с направлений и для каждой клетки (x, y) искать максимальное значение креста с центром в ней за O(1).

Итоговая асимптотика 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;
}

Приветствую сообщество Codeforces.

1 июня 2016 года в 19:35 MSK состоится очередной раунд Codeforces #355 для участников из второго дивизиона. Традиционно, участники из первого дивизиона могут участвовать в соревновании вне конкурса.

Это мой третий раунд. Надеюсь, он вам понравится.

Большое спасибо Глебу Евстропову (GlebsHP) за помощь в подготовке задач и Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon.

Участникам будет предложено пять задач и два часа на их решение.

UPD Разбалловка: 500-1000-1500-2250-2250

UPD Разбор здесь

UPD Поздравляем победителей!

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

У меня возникла проблема.

Этот код(http://pastebin.com/7fG1A6P6) получает RE на одной из систем тестирования.

Понятно, что скорее всего это из-за глубины рекурсии. Как можно обойти это с моей стороны? У меня на компьютере этот код так же вылетает.

Буду благодарен за помощь.

Вообще не могу понять, почему вылетает ВА 11 все время.

Задача 563

Код к задаче

552A - Ваня и таблица

В этой задаче проходило множество решений:

1) С каждым новым прямоугольником добавляется его площадь к результату, так что будем считать площадь каждого прямоугольника и прибавлять к ответу, т.е. для каждой строки x₁, y₁, x₂, y₂ прибавляем к ответу (x₂ - x₁ + 1) * (y₂ - y₁ + 1)

Асимптотика данного решения по времени O(n).

2) Просто сделаем все, что описано в условии, создадим массив и с каждым запросом будем прибавлять прямоугольник к массиву, после чего просто сложим все элементы массива.

Асимптотика по времени O(n * x * y)

C++ code Wild_Hamster

Java code Wild_Hamster

Python code Zlobober

552B - Ваня и книги

Можно вывести формулу результата:

для n < 10 ответом будет n = n - 1 + 1 = 1 * (n + 1) - 1;

для n < 100 ответом будет 2 * (n - 9) + 9 = 2 * n - 9 = 2 * n - 10 - 1 + 2 = 2 * (n + 1) - 11;

для n < 1000 ответом будет 3 * (n - 99) + 2 * (99 - 9) + 9 = 3 * n - 99 - 9 = 3 * n - 100 - 10 - 1 + 3 = 3 * (n + 1) - 111;

для n < 10^sz ответом будет ;

Асимптотика по времени O(sz), где sz — длина числа.

Так же можно было просто перебрать всех возможных 10 вариантов n < 10, n < 100, ..., n < 10⁹, n = 10⁹ и подсчитывать для каждого результат.

C++ code Wild_Hamster

Java code Wild_Hamster

Python code Zlobober

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

552C - Ваня и весы

Переведем число m в w-ичную систему счисления. Если все разряды числа – 0 или 1, то нашу вещь можно взвесить, поставив гири, номера разрядов которых равны 1, на одну чашу весов, а нашу вещь на другую.

Если же это условие не выполняется, то пройдемся от младшего разряда к старшему и если он не равен 0 или 1, пытаемся отнять от него w и прибавить к старшему разряду единицу. Если этот разряд становится равен  - 1, то ставим гирю под данным номером на одну чашу с нашей вещью, если 0 — то не ставим гирю никуда, если иначе – то вещь нельзя взвесить по заданным условиям и ответ .

Асимптотика по времени O(logm).

C++ code Wild_Hamster

Java code Wild_Hamster

Java code Zlobober

552D - Ваня и треугольники

Переберем все возможные пары точек, проведем через каждую из пар прямую и запишем, что этой прямой принадлежат эти 2 точки с помощью map. Если на прямой находится x точек, то на самом деле мы посчитаем нашим перебором, что на ней 2 * x * (x - 1) точек. Таким образом можно завести массив типа b[2 * x * (x - 1)] = x, чтобы определять, сколько точек находится на прямой. Тогда если на прямой находится x точек, то мы теряем x * (x - 1) * (x - 2) / 6 возможных треугольников с возможных n * (n - 1) * (n - 2) / 6 треугольников. Таким образом, для каждой прямой, на которой находится x точек, мы будем отнимать от n * (n - 1) * (n - 2) / 6 значение x * (x - 1) * (x - 2) / 6, таким образом подсчитывая ответ.

Асимптотика решения O(n² * logn).

Поскольку map очень медленный, можно было для каждой пары точек каждую прямую заносить в массив, после этого отсортировать его и искать количество точек на каждой прямой нахождением количества подряд идущих одинаковых значений одной и той самой прямой.

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

C++11 code Wild_Hamster

Java code Wild_Hamster

Java code Zlobober

552E - Ваня и скобки

Можно увидеть, что максимальный ответ будет тогда, когда скобки будут находится между двумя знаками  * , или между знаком  *  и концом выражения. Для удобства прибавим в начало выражения 1 * , а в конец выражения  * 1.

Далее переберем все возможные пары знаков  *  и попробуем посчитать выражение, поставив скобки между двумя знаками  *  для каждой пары.

Чтобы подсчитать выражение, используем две переменные x и y, в начале x = 0, y = firstnumber, где firstnumber — первая цифра выражения, тогда если следующий знак  + , тогда x = y, y = nextnumber, а если  * , тогда x = x, y = y * nextnumber. Результатом выражения будет x + y, для подсчета выражений в скобках и вне скобок можно написать функцию.

Асимптотика по времени O(|s| * 17²).

C++ code Wild_Hamster

Java code Wild_Hamster

Java code Zlobober

Приветствую сообщество Codeforces.

18 июня 2015 года в 19:30 MSK состоится очередной раунд Codeforces #308 для участников из второго дивизиона. Традиционно, участники из первого дивизиона могут участвовать в соревновании вне конкурса.

Это мой второй Codeforces раунд(первым был раунд Codeforces Round 280 (Div. 2)). Надеюсь, он вам понравится.

Большое спасибо Максиму Ахмедову (Zlobober) за помощь в подготовке задач, Марии Беловой (Delinur) за переводы на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon.

Участникам будет предложено пять задач и два часа на их решение.

UPD: Разбаловка стандартная: 500-1000-1500-2000-2500.

UPD: Поздравляю победителей:

1. Ttocs45

2. RNS_JKS

3. RNS_CUS

4. kouekosita

5. grenade

UPD: Контест закончен. Всем спасибо за участие :)

UPD: Разбор задач

Можно ли в полигоне полностью копировать готовые задачи? Или хотя бы частично? Если нельзя, то как найболее удобно копировать задачи?

492A - Ваня и кубики.

По сути нужно выполнить то, что просят в условии. Находим в цикле максимальную высоту h, подсчитывая, сколько кубиков должно быть в i-м рядку и добавляя эти значения к результату. Выполняем цикл, пока результат не превышает n.

Авторское решение: 8924831

492B - Ваня и фонари.

Отсортируем фонари в порядке возрастания. Дальше найдем максимально возможное расстояние между двумя соседними фонарями, пусть это будет maxdist. Также учтем границы улицы, т.е. найдем расстояния от крайних фонарей к концам улицы (a[0] - 0) и (l - a[n - 1]). Ответом будет max(maxdist / 2, max(a[0] - 0, l - a[n - 1]))

Асимптотика по времени O(nlogn), учитывая сортировку.

Авторское решение: 8924823

492C - Ваня и экзамены.

Сортируем пары (a_i, b_i) в порядке возрастания по количеству рефератов b_i, после этого проходимся от самого начала отсортированных пар и добавляем жадно по максимуму количество баллов, то есть добавляем значение min(avg * n - sum, r - a_i), пока суммарное количество баллов не будет не меньше, чем avg * n.

Асимптотика по времени O(nlogn), учитывая сортировку.

Авторское решение: 8924807

492D - Ваня и компьютерная игра.

Создадим вектор rez размером x + y, в котором будут находится последовательность ударов Вани и Вовы за первую секунду. Для этого заведем 2 переменные cntx = cnty = 0. Дальше пока cntx < x и cnty < y, мы проверяем 3 условия:

1) Если (cntx + 1) / x > (cnty + 1) / y, то добавляем в вектор “Vova”, cnty++.

2) Если (cntx + 1) / x < (cnty + 1) / y, то добавляем в вектор “Vanya”, cntx++.

3) Если (cntx + 1) / x = (cnty + 1) / y, то добавляем в вектор “Both” 2 раза, cntx++, cnty++.

Дальше можем отвечать на каждый запрос за О(1), ответом будет rez[(a_i - 1)mod(x + y)].

Асимптотика по времени O(x + y).

Авторское решение: 8924773

492E - Ваня и поле.

Поскольку gcd(dx, n) = gcd(dy, n) = 1, то Ваня сделает полный цикл за n движений. Сгруппируем все возможные пути в n групп, то есть те, что начинаются с точки (0, 0), (0, 1), …, (0, n - 1). Рассмотрим первый путь: он будет иметь вид (0, 0) - (dx, dy) - ((2 * dx) mod n, (2 * dy) mod n) - ... - (((n - 1) * dx) mod n, ((n - 1) * dy) mod n). Поскольку gcd(dx, n) = 1, то среди всех первых координат будут присутствовать все числа от 0 до n - 1. То есть можем занести в массив все соответствия между первой и второй координатой для пути с точки (0, 0), т.е. y[0] = 0, y[dx] = dy, ... , y[((n - 1) * dx) mod n] = ((n - 1) * dy) mod n. Теперь мы знаем, что все точки типа (i, y[i]), где 0 ≤ i ≤ n - 1, принадлежат к группе (0, 0). В таком случае точки типа (i, (y[i] + k)modn) принадлежат к группе (0, k). Тогда каждую точку (x_i, y_i) мы можем добавить к нужной группе k за О(1): (y[x_i] + k) mod n = y_i, k = (y_i - y[x_i] + n) mod n. Дальше просто ищем группу с максимальным количеством элементов, она и будет ответом.

Асимптотика по времени O(n).

Авторское решение: 8924746

Приветствую сообщество Codeforces.

1 декабря 2014 года в 19:30 MSK состоится очередной раунд Codeforces #280 для участников из второго дивизиона. Традиционно, участники из первого дивизиона могут участвовать в соревновании вне конкурса.

Это мой первый Codeforces раунд. Надеюсь, он вам понравится.

Большое спасибо Максиму Ахмедову (Zlobober) за помощь в подготовке задач, Марии Беловой (Delinur) за переводы на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon.

Участникам будет предложено пять задач и два часа на их решение.

UPD: Разбалловка стандартная — 500-1000-1500-2000-2500.

UPD: Спасибо всем, кто принимал участие в раунде!

Поздравляю победителей:

1.alex_y

2.wingemerald

3.Eric94

4.Zpw987

5.rabbit_TR

результаты

UPD: Разбор задач здесь.

Есть матрица размером n на m, заполнена нулями и единицами. Нужно найти найбольший по площе прямоугольник, который содержит только единицы. Если можно, подскажите с решением и возможно местом, где эта задача находится на онлайн ресурсе.

Не могу понять, почему выбивает memory limit. Использование памяти в моем коде примерно O(2^(n/2)), при ограничениях 64МБ не должно бы вроде быть такого вердикта. Подскажите пожалуйста, что не так. Мой код. Задача.