Categories:

SRM 436

↑1549
Автор сета — Gluk, и у него получилось придумать по-настоящему подлые 1000 в обоих дивизионах.
Пауза с появлением моего разбора как раз и связана с более сложной из них.

div2 250
2-другом называется человек, который либо дружит с, либо дружит с тем, кто дружит с. Найти максимальное число 2-друзей, которое есть у кого-либо в компании (до 50 человек), заданной матрицей смежности.

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

class FriendScore {
public:
int highestScore(vector <string> friends) {
int n = (int) friends.size();
int res = 0;
for (int i = 0; i < n; ++i) {
int f = 0;
for (int j = 0; j < n; ++j) if (i != j) {
if (friends[i][j] == 'Y') ++f;
else {
for (int k = 0; k < n; ++k) if (i != k && j != k) {
if (friends[i][k] == 'Y' && friends[k][j] == 'Y') {
++f;
break;
}
}
}
}
if (f > res) res = f;
}
return res;
}
};

div2 500 & div1 250
Небоскребы (до 50 штук) заданных высот (до 10⁹) стоят в шеренгу, найти максимальное число небоскребов, видимых с какого-либо (отрезком).

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

class BestView {
public:
int numberOfBuildings(vector <int> heights) {
int n = (int) heights.size();
int mx = 0;
for (int i = 0; i < n; ++i) {
int seen = 0;
for (int j = 0; j < n; ++j) if (i != j) {
bool can = true;
for (int k = min(i,j) + 1; k < max(i,j); ++k) {
int dx1 = j - i, dy1 = heights[j] - heights[i],
dx2 = k - i, dy2 = heights[k] - heights[i];
if (dx1 < 0) { dx1 = -dx1; dy1 = -dy1; }
if ((long long) dy1 * dx2 <= (long long) dy2 * dx1) can = false;
}
if (can) ++seen;
}
if (seen > mx) mx = seen;
}
return mx;
}
};

div2 1000
Даны два положительных десятичных числа равной длины (до 50 цифр). Мы можем обменять две i-е цифры местами. Какое максимальное произведение этих чисел мы можем получить после ровно swaps обменов?

Жестокая задача, на контесте ее решили только два человека (причем первый из них, бывший белым AlexeyProkopnev из БГУ, получил сразу 1920 рейтинга).

Сразу заметим, что переставляй или не переставляй числа, их сумма не изменится. А произведение при одинаковой сумме тем больше, чем ближе друг к другу числа. Здесь может быть два варианта — либо мы не будем менять первые отличающиеся цифры, либо поменяем местами и сведем задачу к предыдущему варианту с swaps−1. В меньшем числе нам надо обменять все меньшие цифры (кроме первой меньшей, иначе числа поменяются местами). Здесь возможны два варианта: либо нам разрешено сделать меньше обменов, чем надо для этого (тогда мы делаем все обмены слева направо, чтобы как можно сильнее увеличить меньшее число), либо больше. Если больше, то мы можем обменять все меньшие цифры, но здесь снова возникает два варианта: либо нам останется сделать еще четное число обменов (тогда числа можно не изменить), либо нечетное. Если нечетное, то снова возможны два варианта: либо в паре чисел есть одинаковые пары цифр (тогда мы можем нечетное число раз обменять их и числа не изменятся), либо нет — тогда, чтобы минимизировать потери, мы обменяем последние цифры. Если верно рассмотреть эти 4 разветвления и аккуратно реализовать длинную арифметику, задача должна зайти :)

string add(string x, string y)
{
string res; int cf = 0;
for (int i = (int) x.length() - 1, j = (int) y.length() - 1; i >= 0 || j >= 0; --i, --j) {
int r = (i >= 0 ? x[i] - '0' : 0) + (j >= 0 ? y[j] - '0' : 0) + cf;
res = string(1, r % 10 + '0') + res;
cf = r / 10;
}
if (cf) res = string(1, cf + '0') + res;
return res;
}

string mul(string x, string y)
{
string result = "0", z = "";
for (int i = (int) y.length() - 1; i >= 0; --i) {
string res(x.length(), '0'); int cf = 0;
for (int j = (int) x.length() - 1; j >= 0; --j) {
int r = (x[j] - '0') * (y[i] - '0') + cf;
res[j] += r % 10;
cf = r / 10;
}
if (cf) res = string(1, cf + '0') + res;
result = add(result, res + z);
z += "0";
}
return result;
}

class DigitsSwap {
public:
pair<string, string> mp(string x, string y, int swaps)
{
int n = (int) x.length(), l = 0, fd = n, sw = swaps;
bool haseq = false;
for (int i = n - 1; i >= 0; --i) {
if (x[i] < y[i]) {
++l;
fd = i;
} else if (x[i] == y[i]) {
haseq = true;
}
}
if (l - 1 < swaps) sw = l - 1;
for (int i = fd + 1, c = 0; i < n && c < sw; ++i) if (x[i] < y[i]) { swap(x[i], y[i]); ++c; }
if (l - 1 < swaps && (swaps - l + 1) % 2 && !haseq) {
swap(x[x.length() - 1], y[y.length() - 1]);
}
return make_pair(x, y);
}

string maximalProduct(string x, string y, int swaps) {
int n = (int) x.length(), fd = n;
if (x > y) swap(x, y);
for (int i = n - 1; i >= 0; --i) if (x[i] != y[i]) fd = i;
pair<string, string> d1 = mp(x, y, swaps), d2;
if (swaps) {
swap(y[fd], x[fd]);
d2 = mp(y, x, swaps - 1);
}
if (d1.first > d2.first) return mul(d1.first, d1.second);
else return mul(d2.first, d2.second);
}
};

div1 500
Дан лабиринт (до 500x500), заполняемый заданным ГСЧ, нужно найти путь из 0,0 в N−1,N−1 с минимальным количеством поворотов (первоначальное направление можно выбрать любым)

Простой BFS по массиву [позиция][направление] (для списка текущих вершин используем boost::tuple; да, на TopCoder есть Boost, который хоть и выдает #warning "Unknown compiler version - please run the configure tests and report the results", но работает :)). Увы, простая реализация выдает TL, поэтому следует сделать небольшую оптимизацию — если мы уже были в какой-то позиции с каким-то направлением, то мы были и дальше (тогда макстест работает 140 мс).

unsigned char a[500][500];
short dp[500][500][4];
int shx[] = {0, 0, 1, -1}, shy[] = {1, -1, 0, 0};

class DoNotTurn {
public:
int minimumTurns(int N, int X0, int A, int B, int Y0, int C, int D, int P, int M) {
memset(a, 0, sizeof(a)); memset(dp, 0, sizeof(dp));
int x = X0 % P, y = Y0 % P;
a[x % N][y % N] = 1;
for (int i = 1; i < M; ++i) {
x = ((long long) x * A + B) % P; y = ((long long) y * C + D) % P;
a[x % N][y % N] = 1;
}
a[0][0] = a[N-1][N-1] = 0;

typedef boost::tuple<int, int, int> triple;
vector<triple> wave, nwave;
int step = 1;
for (int i = 0; i < 4; ++i) {
for (int x = 0, y = 0; x >= 0 && x < N && y >= 0 && y < N; x += shx[i], y += shy[i]) {
if (a[x][y]) break;
dp[x][y][i] = 1;
wave.push_back(triple(x, y, i));
}
}

while (true) {
nwave.clear();
for (int i = 0, len = (int) wave.size(); i < len; ++i) {
int cx = wave[i].get<0>(), cy = wave[i].get<1>(), cface = wave[i].get<2>();
for (int face = 0; face < 4; ++face) if (cface != face) {
for (int x = cx, y = cy; x >= 0 && x < N && y >= 0 && y < N; x += shx[face], y += shy[face]) {
if (a[x][y]) break;
if (dp[x][y][face] == 0) {
if (x == N-1 && y == N-1) return step;
dp[x][y][face] = step + 1;
nwave.push_back(triple(x, y, face));
} else break;
}
}
}
if (nwave.empty()) break;
wave = nwave;
++step;
}

int res = 0;
for (int i = 0; i < 4; ++i) {
if (dp[N-1][N-1][i] && (dp[N-1][N-1][i] < res || res == 0)) res = dp[N-1][N-1][i];
}
return res - 1;
}
};

div1 1000
Даны два вектора равной длины N (до 60000), заполняемые с помощью заданного ГСЧ, с числами до 100. Мы можем взять вместо любого вектора его произвольный циклический сдвиг. Нужно найти их максимально возможное скалярное произведение.

Потрясающе подлая задача, которую решили всего 19 человек, причем Petr с худшим временем.

Забавно, что некоторые самостоятельно на C++ реализовывали класс комплексных чисел :) Почти у всех в коде встречалось название FFT или DFT, и только у zcgzcgzcg в решении было написано cheng. Кажется, китайцы чего-то нам не рассказывают :) Но все же особенно отличился по этой задаче Psyho. В то время как все остальные реализовывали в том или ином виде алгоритм O(NlogN), он частично раскрыл цикл и оптимизировал умножения через инструкции MMX.

Очевидно, что достаточно рассматривать сдвиг одного вектора относительно другого. Однако скалярное произведение считается за O(N), а 60000² это все же слишком много. К счастью, если применить макиавеллевскую хитрость, можно заметить, что в произведении полиномов вида

$\left( x_0n^2 + x_1n + x_2 \right) \left( y_1n^4 + y_0n^3 + y_2n^2 + y_1n + y_0 \right) = \\= x_0y_1n^6 + \left( x_0y_0 + x_0y_1 \right)n^5 + \\+ \left( x_0y_2 + x_1y_0 + x_2y_1 \right)n^4 + \\+ \left( x_0y_1 + x_1y_2 + x_2y_0 \right)n^3 + \\+ \left( x_0y_0 + x_1y_1 + x_2y_2 \right)n^2 + \\+ \left( x_1y_0 + x_2y_1 \right)n + x_2y_0$

при степенях от N−1 до 2N−2 как раз присутствуют все искомые скалярные произведения векторов со сдвигами. А перемножить полиномы можно достаточно быстро, используя быстрое преобразование Фурье (БПФ или FFT), подробно описанное у e-maxx. Я его просто скопипастил. Обращу внимание на две вещи:
не допускайте таких ошибок:

copy(y.begin(), y.end() - 1, back_inserter(y));

и почему-то топкодерный GCC не захотел компилировать

wm.imag(-wm.imag());

пришлось заменить на

wm = conj(wm);

int rev(int n, int bits)
{
int res = 0;
for (int i = 0; i < bits; ++i) {
res |= ((n >> i) & 1) << (bits - i - 1);
}
return res;
}

void fft(vector< complex<double> > & a, bool back)
{
int n = (int) a.size();
int lg_n = 0;
for (int i = 1; i < n; i <<= 1, ++lg_n);

vector<char> swapped(n);
for (int i = 0; i < n; ++i) {
if (!swapped[i]) {
int j = rev(i, lg_n);
swap(a[i], a[j]);
swapped[i] = swapped[j] = true;
}
}

for (int s = 1; s <= lg_n; ++s) {
int m = 1 << s;
complex<double> wm(cos(M_PI*2/m), sin(M_PI*2/m));
if (back) wm = conj(wm);
for (int k = 0; k < n; k += m) {
complex<double> w(1);
for (int j = 0; j < m/2; ++j) {
complex<double> t = w * a[k + j + m/2];
complex<double> u = a[k + j];
a[k + j] = u + t;
a[k + j + m/2] = u - t;
if (back) {
a[k + j] /= 2;
a[k + j + m/2] /= 2;
}
w *= wm;
}
}
}
}

void multiply(const vector<int>& a, const vector<int>& b, vector<int>& res)
{
int n = 1;
while (n < (int) max(a.size(), b.size())) n <<= 1;
n <<= 1;

vector< complex<double> > aa(n), bb(n);
copy(a.begin(), a.end(), aa.begin());
copy(b.begin(), b.end(), bb.begin());

fft(aa, false);
fft(bb, false);

vector< complex<double> > cc(n);
for (int i = 0; i < n; ++i) {
cc[i] = aa[i] * bb[i];
}
fft (cc, true);

res.resize(n);
for (int i = 0; i < n; ++i) {
res[i] = (int) floor(cc[i].real() + 0.5);
}
while (res.size() > 1 && res.back() == 0) res.pop_back();
}

class CircularShifts {
public:
int maxScore(int N, int Z0, int A, int B, int M) {
vector<int> x(N), y(N), ny;
for (int i = 0, z = Z0 % M; i < 2 * N; ++i) {
if (i < N) x[i] = z % 100;
else y[i - N] = z % 100;
z = ((long long) z * A + B) % M;
}

ny = y;
copy(y.begin(), y.end() - 1, back_inserter(ny));
reverse(ny.begin(), ny.end());

vector<int> res;
multiply(x, ny, res);

int result = 0;
for (int i = N-1; i <= 2*N-2; ++i) {
if (res[i] > result) result = res[i];
}
return result;
}
};

олимпиады

Follow us:

Applications

COMPANY

PRODUCTS

COMMUNITY

CHOOSE LANGUAGE