Подойдет любой online judge.
Спасибо.
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
3 дня
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
3 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
→ Найти пользователя
→ Прямой эфир
Задача:
Есть таблица некоторых критериев, которая имеет следующий вид:
A1 A2 ... A40
B1 B2 ... B40
...
Количество строк может быть около 40000.
Значение каждой ячейки -- произвольная строка (до 256 символов). Также есть специальное значение -- "*" (зведочка).
Теперь есть запрос:
Z1 Z2 ... Z40
Значения полей запроса аналогичны по структуре ячейкам таблицы, включая специальное значение.
Проверка запроса: надо найти среди строк исходной таблицы максимально совпадающую со значениями запроса. Специальное значение "*" либо в запросе, либо в таблице, означает совпадение в данной ячейке вне засимости от значения, с которым сравнивают.
Например:
XYZ GBP 123 * [все значения -- *] *
XYZ USD 123 * [все значения -- *] *
XYZ USD * * [все значения -- *] *
* * * * [все значения -- *] *
Запрос:
XYZ USD 567 * [все значения -- *] *
Ответом должна быть строка номер 3.
При банальном подходе можно просто заранее отсортировать строки таблицы по убыванию количества конкретных значений, и уже для каждого запроса проверять посрочно до первого удачного совпадения. Получается 40000*40 сравнений (не будем учитывать время сравнения самих ячеек).
Может тут как-то можно ускорить, используя результаты предыдущей строки? Например, обработав строку 2, мы знаем, что первые два поля уже совпадают, и может быть их можно уже не сравнивать... Можно индекс какой построить. Ограничения на память особых нет.
Можно даже сгенерить некий код-парсер, которых будет представлять логику конкретной исходной таблицы. Вот только вопрос, в чем должна быть идея этого парсера.
А было бы возможно подключить еще один язык - Go?
Интересный язык, и практиковаться на нем было бы полезно.
UPDATE: Задача решена быстрее, чем за два часа. Первое правильное решение получено от Artemev Vasiliy.
Разного рода "ненормальное" программирование весьма популярно среди любителей поломать голову над разными задачками. Порой программу для очередной "ненормальной" среды программирования уже нереально написать вручную, а надо писать генератор, создающий код.
В задаче, что предлагаю я, программы все еще можно писать вручную на некотором высокоуровневом макроассемблере.
Итак, имеется модель некоторого виртуального процессора, выполняющего только одну логическую операцию - Стрелку Пирса.
На этом процессоре написана программа, на вход которой подается некоторый пароль. Если пароль неверный, то в ответ выдается строка "Wrong password!". Если верный, то выдается определенное волшебное сообщение.
Задача: любым образом выяснить это волшебное сообщение. Как вариант, можно, например, угадать пароль, и программа сама выдаст секрет.
Логика написана таким образом, что разобравшись в алгоритме, можно без труда расшифровать волшебное сообщение.
Раньше я описывал использованный подход во всех деталях.
Оригинальный подход, на котором основан мой эксперимент, был не совсем "чистым", так как команда сложения был вынесена за логику процессора. В моей версии все до единой команды реализованы на самом процессоре. Для этого потребовалось немного изменить интерпретатор, добавив в него сдвиговый регистр.
Для желающих попробовать взломать мой эксперимент, я сделал страничку, на которой на JavaScript'e реализован выше описанный виртуальный процессор с одной командой и программа для него, проверяющая пароль.
Итак, ссылка на задачу: http://demin.ws/norcpu/norcpu.html
Удачи.
P.S. Для первого взломавшего - небольшой приз! Информация по ссылке.
Мое решение (ниже) - это ДП, в котором для каждой клумбы перебираются все предыдующие клумбы, из которых можно прийдти в текущую. Для каждой такой пары (текущая <-> какая-то сзади) перебираются все возможные варианты деревьев. Итого, решение O(M*M*N*N). Но, увы, на каком-то из непервых тестов получаю WA. То есть решение вроде бы верно, но не совсем ;-).
Подскажите проблему, кто видит.
int M;
is >> M;
vector<int> w(M), e(M);
for (int i = 0; i < M; ++i)
is >> w[i] >> e[i];
int N;
is >> N;
vector<int> p(N);
for (int i = 0; i < N; ++i)
is >> p[i];
vector<vector<int> > dp(M, vector<int>(N, 0));
for (int i = 0; i < M; ++i)
dp[i][0] = 1;
for (int i = 1; i < N; ++i) {
for (int j = 0; j < M; ++j) {
for (int i0 = 0; i0 < i; ++i0) {
for (int j0 = 0; j0 < M; ++j0) {
if (p[i0] + e[j0] <= p[i] && p[i] - w[j] >= p[i0])
dp[j][i] = max(dp[j][i], dp[j0][i0] + 1);
}
}
}
}
int ans = 0;
for (int i = 0; i < M; ++i)
ans = max(ans, dp[i][N - 1]);
os << ans << endl;
}
http://acmp.ru/index.asp?main=task&id_task=433
Подскажите идею динамики. Судя по ограничению в 10^6 там требуется максимум n*log(n) решение.
У меня пока, увы, только квадратичное, которые, ясное дело, падает с TLE:
void solve(istream& is, ostream& os) {
int n;
string s;
is >> n >> s;
vector<int> dp(n, 0);
unsigned long long ans = 0;
for (int i = 0; i < n; ++i) {
dp[i] = s[i] == 'a' ? +1 : -1;
for (int j = 0; j < i; ++j) {
dp[j] += dp[i];
if (dp[j] == 0)
ans += 1;
}
}
os << ans << endl;
}
Не пойму, как делать половинное деление, чтобы получить log(n), ведь приходится проверять подстроки не только в кусках с границами в 1/2, 1/4, 1/8 и т.д., но пересекающие их.
Есть задача про Фотографа-зануду
Лично я осилил ее несколько "с фланга", а не составлением динамики, то есть сбрутфорсил полным перебором решения для размерностей до 5-6, и через известную базу данных последовательностей получил формулу (к счастью, такая последовательность там была).
Вопрос номер 1: вообще, для мира спортивного решения "канает" такое решение? Я имею ввиду использование этой базы данных для решение задач, вместо честного вывода формулы.
Вопрос номер 2: в обсуждении этой задачи на Тимусе даются две динамики, смысл которых мне не удается пока постичь.
№1
a[i][1] = a[i - 1][1] + a[i - 1][2],
a[i][2] = a[i - 1][2] + a[i - 3][2]
a[i][2] = a[i - 1][2] + a[i - 3][2]
№2
a[i][1] = a[i-1][1] + a[i-2][2]
a[i][2] = a[i-2][1] + 1
a[i][2] = a[i-2][1] + 1
Может кто-нибудь просто словами проговорить физический смысл a[i,t] в обоих случаях? Ясно, что i - это длина ряда в текущей подзадаче, а вот что такое t?
Подскажите начинающему: есть базовая динамика для задач про правильные скобочные последовательности (ПСП).
F(n, k) = F(n-1, k-1) + F(n-1, k+1).
Многие задачи про скобки к ней сводятся. Но есть такой вариант, когда надо найти количество правильных скобочных последовательностей из n открывающихся скобок, причем максимальная глубина на всей строке (разница между открывающимися и закрывающимися скобками) должна быть равна k. Например, для n=3 и k=2 последовательность ()(()) верная (глубина 2), а ((())) нет (глубина 3).
F(n, k) - количество ПСП длиной n и разницей между количеством открывающихся и закрывающихся скобок (глубиной) k:
F(n, k) = F(n-1, k-1) + F(n-1, k+1).
Многие задачи про скобки к ней сводятся. Но есть такой вариант, когда надо найти количество правильных скобочных последовательностей из n открывающихся скобок, причем максимальная глубина на всей строке (разница между открывающимися и закрывающимися скобками) должна быть равна k. Например, для n=3 и k=2 последовательность ()(()) верная (глубина 2), а ((())) нет (глубина 3).
Подскажите идею динамики тут. Если удасться подтолкнуть в нужном направлении, но без приведения непосредственно решения, будет еще лучше.
Спасибо.
А было бы реально удобно, если б в профайле можно было бы вставлять ссылки на профайлы в других системах (например, ТопКодере). А если б еще и рейтинг автоматически брался, было бы вообще нереально. ;-)
А есть ли в планах проводить матчи не только в 19:00 по Москве? Не могу, правда, сказать, что представляю большое количество людей (только двоих ;-). У нас тут время GMT+0, и московские семь часов вечера нам приходятся аккурат в четыре часа вечера, конец рабочего дня, даже не середина. Вобщем, было бы здорово, если б иногда были матчи в иное время, хотя бы по топкодеровской сетке со смещением в день-два.
Спасибо.
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 27.11.2024 08:39:52 (l1).
Десктопная версия, переключиться на мобильную.
При поддержке
