SRM 397
↑1481
Я вошел в 1/5 лучших программистов мира (процентиль 82.7902) и чуть-чуть не дотянул до желтого цвета и призового 3-го места в комнате (стал 4-м).
250
Условие
В задаче требовалось найти минимальное число шагов, сортирующих перестановку {1, ..., n}, где за каждый шаг можно выбрать k рядом стоящих чисел и обратить их порядок. Причем n был до неприличия маленьким - не больше 8.
Нетрудно заметить, что 8! = 40320, так что даже полный пошаговый перебор всех возможных перестановок едва ли займет много времени. Что я и сделал. Максимальное время на тесте {{8,7,6,5,4,3,2,1}, 2} составило 260 мс.
#include
#include
#include
#include
using namespace std;
typedef vector vi;
class SortingGame
{
public:
int fewestMoves(vector board, int k)
{
vi so = board;
sort(so.begin(), so.end());
if (board == so) return 0;
int n = board.size();
set< vi > all;
vector< set< vi > > v;
set< vi > e;
v.push_back(e);
v[0].insert(board);
int c = 0;
bool end = false;
for (;;) {
end = true;
v.push_back(e); c++;
for (int i = 0; i <= n - k; i++) {
for (set::iterator i_s = v[c - 1].begin(); i_s != v[c - 1].end(); i_s++) {
vi b = *i_s;
int j, l;
for (j = i, l = i + k - 1; j < l; j++, l--) {
int t = b[j];
b[j] = b[l];
b[l] = t;
}
if (all.find(b) == all.end()) {
end = false;
v[c].insert(b);
all.insert(b);
if(b == so) return c;
}
}
}
if (end) return -1;
}
}
};
500
Условие
В этой задаче нужно всего-то найти сумму 1k + 2k + ... + nk по модулю 1000000007. Но вот беда, k может быть до 50, а n аж до 109.
Взглянув на эту задачу, я сразу подумал: «Боян!». Действительно, подобная задача есть на Тимусе и даже в Демидовиче (кажется). Задачей этой интересовался еще Бернулли; он решил ее, доказав, что сумма k-ых степеней чисел от 1 до n выражается через полином k+1-й степени от n. Основная проблема состоит в вычислении этих коэффициентов, но Бернулли справился и с этим, введя числа Бернулли (логично, не правда ли?). Сейчас применений у этих чисел достаточно много, поэтому формула для суммы степеней называется формулой Faulhaber (я постеснялся предположить транскрипцию). Вот она:
Писать длинную арифметику не хотелось. После недолгих экспериментов оказалось, что C# на TopCoder старый, и там System.Numeric.BigInteger нет. А на Java я начал писать слишком поздно, причем, как показало дорешивание, и большее количество времени не помогло бы (даже несмотря на то, что числа Бернулли я захардкодил, воспользовавшись Maple. А вот что такое с размерностью 100x50 захардкодил pawa в этой задаче, мне до сих пор любопытно знать). Жутко интересно, какой такой логичностью объясняется то, что у этого класса нет обычных арифметических операторов, конструктора из int и других вещей, настолько очевидных, что ради них даже как-то странно заглядывать в мануал?
Поэтому я, наконец, решился прочитать решение Jedi_Knight, которое он мне описал :)
(Далее простите за формулы c texify.com, я так и не разобрался, как заставить wordpress.com рендерить матрицы)
Хитрый Джедай заметил, что вектор (1, n, n2, n3, ...) отображается оператором с матрицей треугольника Паскаля
в вектор (1, n+1, (n+1)2, (n+1)3, ...). Очевидно, что достаточно применить этот оператор N−1 раз к вектору (1, 1, 1, 1, ...) (либо N раз к (1, 0, 0, 0, ...)), чтобы получить вектор (1, N, N2, N3, ...). А теперь заметим, что%5Ek&bg=ffffff&fg=000000&s=0)
. Это значит, что мы можем добавить в вектор новую компоненту, равную
и слегка видоизменить матрицу оператора. Тогда его действие будет выглядеть так:
Интересно, догадался бы до этого наш линалист Борат? :)
Применить полученный оператор к вектору (1, 0, 0, 0, ...) n раз (скажем, миллиард) достаточно просто. Для этого возведем матрицу оператора в n-ю степень (напомню, умножение матриц вполне себе ассоциативно, хотя и некоммутативно), а это можно сделать простым матричным возведением в степень, когда считаются только A2k, а An получается перемножением соответствующих матриц. Так-то!
#include
#include
using namespace std;
class SumOfPowers
{
const static int MAGIC = 1000000007;
const static int MDIM = 53;
const static int MBSIZE = sizeof(int) * MDIM * MDIM;
public:
void matrix_multiply(int a[MDIM][MDIM], int b[MDIM][MDIM], int dim)
{
int c[MDIM][MDIM];
for (int i = 0; i < dim; i++) {
for (int j = 0; j < dim; j++) {
long long res = 0;
for (int k = 0; k < dim; k++) {
res += ((long long)a[i][k] * (long long)b[k][j]) % MAGIC;
}
c[i][j] = res % MAGIC;
}
}
memcpy(a, c, MBSIZE);
}
int value(int n, int k)
{
// Треугольник Паскаля
int a[MDIM][MDIM]; memset(a, 0, MBSIZE);
a[0][0] = 1;
for (int i = 0; i <= k; i++) {
a[i][0] = a[i][i] = 1;
}
for (int i = 0; i <= k; i++) {
for (int j = 1; j < i; j++) {
a[i][j] = (long long)(a[i-1][j-1] + a[i-1][j]) % MAGIC;
}
}
// Добавляем строчку
for (int i = 0; i < k; i++) {
a[k+1][i] = 0;
}
a[k+1][k] = a[k+1][k+1] = 1;
// Возводим в n-ю степень
int p[32][MDIM][MDIM];
memcpy(p[0], a, MBSIZE);
for (int i = 1; i < log2(n) + 1; i++) {
matrix_multiply(a, a, k + 2);
memcpy(p[i], a, MBSIZE);
}
int res[MDIM][MDIM]; memset(res, 0, MBSIZE);
for (int i = 0; i < k+2; i++) {
res[i][i] = 1;
}
for (int i = 0; i < log2(n) + 1; i++) {
if (n & (1 << i)) {
matrix_multiply(res, p[i], k + 2);
}
}
// Умножаем на вектор-столбец [1,1,1,...,1,0]
long long result = 0;
for (int i = 0; i <= k; i++) {
result += res[k+1][i];
}
return result % MAGIC;
}
};
К слову, в чате Арены один игрок заявил, что уже отсылал эту задачу организаторам, но те развернули ее с формулировкой «слишком математическая» :). Так что TopCoder растет, и вскоре и впрямь понадобится доказывать теорему Римана в частном случае 250-й (давайте все дружно подколем сами-знаете-кого :)).
Вы могли заметить (а могли и не заметить), что отныне я придерживаюсь в своем коде с Си-синтаксисом стандартов кодирования PEAR. Это круто.
Аддон: Тут выяснилось, что BigInteger удален из .NET 3.5, предположительно из-за его низкого быстродействия. Это ужасно.
Я вошел в 1/5 лучших программистов мира (процентиль 82.7902) и чуть-чуть не дотянул до желтого цвета и призового 3-го места в комнате (стал 4-м).
250
Условие
В задаче требовалось найти минимальное число шагов, сортирующих перестановку {1, ..., n}, где за каждый шаг можно выбрать k рядом стоящих чисел и обратить их порядок. Причем n был до неприличия маленьким - не больше 8.
Нетрудно заметить, что 8! = 40320, так что даже полный пошаговый перебор всех возможных перестановок едва ли займет много времени. Что я и сделал. Максимальное время на тесте {{8,7,6,5,4,3,2,1}, 2} составило 260 мс.
#include
#include
#include
#include
using namespace std;
typedef vector vi;
class SortingGame
{
public:
int fewestMoves(vector board, int k)
{
vi so = board;
sort(so.begin(), so.end());
if (board == so) return 0;
int n = board.size();
set< vi > all;
vector< set< vi > > v;
set< vi > e;
v.push_back(e);
v[0].insert(board);
int c = 0;
bool end = false;
for (;;) {
end = true;
v.push_back(e); c++;
for (int i = 0; i <= n - k; i++) {
for (set::iterator i_s = v[c - 1].begin(); i_s != v[c - 1].end(); i_s++) {
vi b = *i_s;
int j, l;
for (j = i, l = i + k - 1; j < l; j++, l--) {
int t = b[j];
b[j] = b[l];
b[l] = t;
}
if (all.find(b) == all.end()) {
end = false;
v[c].insert(b);
all.insert(b);
if(b == so) return c;
}
}
}
if (end) return -1;
}
}
};
500
Условие
В этой задаче нужно всего-то найти сумму 1k + 2k + ... + nk по модулю 1000000007. Но вот беда, k может быть до 50, а n аж до 109.
Взглянув на эту задачу, я сразу подумал: «Боян!». Действительно, подобная задача есть на Тимусе и даже в Демидовиче (кажется). Задачей этой интересовался еще Бернулли; он решил ее, доказав, что сумма k-ых степеней чисел от 1 до n выражается через полином k+1-й степени от n. Основная проблема состоит в вычислении этих коэффициентов, но Бернулли справился и с этим, введя числа Бернулли (логично, не правда ли?). Сейчас применений у этих чисел достаточно много, поэтому формула для суммы степеней называется формулой Faulhaber (я постеснялся предположить транскрипцию). Вот она:
Писать длинную арифметику не хотелось. После недолгих экспериментов оказалось, что C# на TopCoder старый, и там System.Numeric.BigInteger нет. А на Java я начал писать слишком поздно, причем, как показало дорешивание, и большее количество времени не помогло бы (даже несмотря на то, что числа Бернулли я захардкодил, воспользовавшись Maple. А вот что такое с размерностью 100x50 захардкодил pawa в этой задаче, мне до сих пор любопытно знать). Жутко интересно, какой такой логичностью объясняется то, что у этого класса нет обычных арифметических операторов, конструктора из int и других вещей, настолько очевидных, что ради них даже как-то странно заглядывать в мануал?
Поэтому я, наконец, решился прочитать решение Jedi_Knight, которое он мне описал :)
(Далее простите за формулы c texify.com, я так и не разобрался, как заставить wordpress.com рендерить матрицы)
Хитрый Джедай заметил, что вектор (1, n, n2, n3, ...) отображается оператором с матрицей треугольника Паскаля
в вектор (1, n+1, (n+1)2, (n+1)3, ...). Очевидно, что достаточно применить этот оператор N−1 раз к вектору (1, 1, 1, 1, ...) (либо N раз к (1, 0, 0, 0, ...)), чтобы получить вектор (1, N, N2, N3, ...). А теперь заметим, что
. Это значит, что мы можем добавить в вектор новую компоненту, равную
и слегка видоизменить матрицу оператора. Тогда его действие будет выглядеть так:
Интересно, догадался бы до этого наш линалист Борат? :)
Применить полученный оператор к вектору (1, 0, 0, 0, ...) n раз (скажем, миллиард) достаточно просто. Для этого возведем матрицу оператора в n-ю степень (напомню, умножение матриц вполне себе ассоциативно, хотя и некоммутативно), а это можно сделать простым матричным возведением в степень, когда считаются только A2k, а An получается перемножением соответствующих матриц. Так-то!
#include
#include
using namespace std;
class SumOfPowers
{
const static int MAGIC = 1000000007;
const static int MDIM = 53;
const static int MBSIZE = sizeof(int) * MDIM * MDIM;
public:
void matrix_multiply(int a[MDIM][MDIM], int b[MDIM][MDIM], int dim)
{
int c[MDIM][MDIM];
for (int i = 0; i < dim; i++) {
for (int j = 0; j < dim; j++) {
long long res = 0;
for (int k = 0; k < dim; k++) {
res += ((long long)a[i][k] * (long long)b[k][j]) % MAGIC;
}
c[i][j] = res % MAGIC;
}
}
memcpy(a, c, MBSIZE);
}
int value(int n, int k)
{
// Треугольник Паскаля
int a[MDIM][MDIM]; memset(a, 0, MBSIZE);
a[0][0] = 1;
for (int i = 0; i <= k; i++) {
a[i][0] = a[i][i] = 1;
}
for (int i = 0; i <= k; i++) {
for (int j = 1; j < i; j++) {
a[i][j] = (long long)(a[i-1][j-1] + a[i-1][j]) % MAGIC;
}
}
// Добавляем строчку
for (int i = 0; i < k; i++) {
a[k+1][i] = 0;
}
a[k+1][k] = a[k+1][k+1] = 1;
// Возводим в n-ю степень
int p[32][MDIM][MDIM];
memcpy(p[0], a, MBSIZE);
for (int i = 1; i < log2(n) + 1; i++) {
matrix_multiply(a, a, k + 2);
memcpy(p[i], a, MBSIZE);
}
int res[MDIM][MDIM]; memset(res, 0, MBSIZE);
for (int i = 0; i < k+2; i++) {
res[i][i] = 1;
}
for (int i = 0; i < log2(n) + 1; i++) {
if (n & (1 << i)) {
matrix_multiply(res, p[i], k + 2);
}
}
// Умножаем на вектор-столбец [1,1,1,...,1,0]
long long result = 0;
for (int i = 0; i <= k; i++) {
result += res[k+1][i];
}
return result % MAGIC;
}
};
К слову, в чате Арены один игрок заявил, что уже отсылал эту задачу организаторам, но те развернули ее с формулировкой «слишком математическая» :). Так что TopCoder растет, и вскоре и впрямь понадобится доказывать теорему Римана в частном случае 250-й (давайте все дружно подколем сами-знаете-кого :)).
Вы могли заметить (а могли и не заметить), что отныне я придерживаюсь в своем коде с Си-синтаксисом стандартов кодирования PEAR. Это круто.
Аддон: Тут выяснилось, что BigInteger удален из .NET 3.5, предположительно из-за его низкого быстродействия. Это ужасно.