Привет, Codeforces!

Сегодня утром (в 12:00) мой вклад был +41. Дальше я в 16:00 вновь заглянул на аккаунт, и ОБНАРУЖИЛ, что мой вклад стал -104.

Все посты были старыми. А сегодня за 4 часа пост с +10 слетел до -75 и похоже, что все еще уменьшается(

Вот пост, про который идет речь: https://codeforces.com/blog/entry/127411

Могу добавить только это фото. Может кто-то знает, почему так. Вот ник на фото: hmmmmm

P.S. Я стал почти последним по вкладу =O

How did tourist solve E from last Div. 2 in 2 minutes?!

Привет, CodeForces! ヾ(•ω•`)o

Со мной произошла веселая (и немного грустная) история. Вот как это было...

Я со своей командой писал ВКОШП.Junior (наша команда — СеВеР, сслыка на результаты). Так вот.

Все началось хорошо. Мы сдали халявные задачи, дальше было затишье на час. В этот час мы писали задачу D. У нас на тот момент было -5 на J и примерно -10 на D (везде WA7). Я по указаниям сокомандника переписал J, но это не помогло. Мы сидим, ничего не понимаем, оба уверены, что оба решения верны. Далее осознаем, что у нас маленькие константы в D, но это ничего не меняет (все еще WA7). Потом снова затишье... Я в отчаянии решил заглянуть в шапку программы и обнаружил, что там у нас написано #define int long вместо #define int long long. После исправления этого бага прошла задача J (наконец-то!), а D к сожалению — нет. Но мы сошли с мертвой точки, у нас был WA, но не 7! Ура! Далее чуть-чуть подкручиваем константы + добавляем ios::sync_with_stdio(false); cin.tie(nullptr); и получаем RE39, что нас немного расстроило. В последние полтора часа мы решали другие задачи, которые решили все и дебагали D, постоянно получав RE39. Мы решили, что это выход за границы, после исправления этого момента — TLE39, от чего мы были удивлены (и в плохом, и в хорошем смысле одновременно). Поняли, что теперь константы слишком велики, подкручивали их долго, но безуспешно. После 25 неправильных посылок мы все же поняли, что у нас есть циклы, которые работают за $$$10^9$$$. Поставили if и успешно сдали задачу в последние 7 минут олимпиады =) (она к слову, длилась 4 часа)

Итог: проверьте, что написано #define int long long, ios::sync_with_stdio(false); cin.tie(nullptr);, проверьте ограничения в задаче заново ;)

Привет, CodeForces!

Основная информация

Я написал генератор тестов на C++. Он очень прост, состоит из двух функций: генерация случайного числа в промежутке от $$$a$$$ до $$$b$$$, так, чтобы это случайное число было кратно $$$k$$$ (функция: genint(a, b, k, add), где add — "добавлять" ли в тест это число) и генерация случайной строки. Тут надо расписать:

• Генерирует строку случайной длины в промежутке от $$$a$$$ до $$$b$$$, так, чтобы она была кратна $$$k$$$.
• Состоящую из заданных символов. Задавать символы можно двумя способами: написать промежуток ("a-f", "x-z") или конкретный символ ("m", "o"). Функция: genstr(a, b, k, pattern, add), где pattern — массив заданных промежутков или конкретных символов.

#include <bits/stdc++.h>
using namespace std;
#define int long long
string test = "";

int genint(int a, int b, int k, bool add) {
  if (a == b) {
    if (add) test += to_string(a);
    return a;
  }
  int ans = (rand() % (b / k - a / k) + (a / k + (a % k != 0))) * k;
  if (add) test += to_string(ans);
  return ans;
}

string genstr(int a, int b, int k, vector <string> p, bool add) {
  int l = genint(a, b, k, 0);
  vector <char> symbols;
  for (int i = 0; i < p.size(); i++) {
    if (p[i].size() == 1) {
      symbols.push_back(p[i][0]);
    } else {
      for (char j = p[i][0]; j <= p[i][2]; j++) {
        symbols.push_back(j);
      }
    }
  }
  string ans = "";
  for (int i = 0; i < l; i++) {
    ans += symbols[genint(0, symbols.size(), 1, 0)];
  }
  if (add) test += ans;
  return ans;
}

signed main() {
  srand(time(NULL));
  // generating test

  // ---------------
  freopen("test", "w", stdout);
  cout << test;
}

Применения

Есть такая задача: Вам дана строка состоящая из $$$n (n \le 10^5)$$$ символов. Вам требуется процент содержания (с точностью до $$$10^{-5}$$$) каждого символа, который есть в строке. Пример ввода и вывода:

Ввод
1
5
abcde
Вывод
a 20
b 20
c 20
d 20
e 20

Ввод
1
5
abcda
Вывод
a 40
b 20
c 20
d 20

Вам требуется обработать $$$t$$$ наборов входных данных

Для нас, участников соревнования, эта задача очень проста, но для составителей надо написать такие тесты, в которых будут и крайние и обычные случаи. Писать это вручную — плохой вариант. Тем более, что $$$n \le 10^5$$$

С помощью моего генератора можно сделать хорошие тесты в несколько строк:

const int mintestcases = 5;
const int maxtestcases = 8;
const int minlength = 10;
const int maxlength = 20;
for (int i = 0; i < 5; i++) { // генерирует 5 тестов
  string test = "";
  int t = genint(mintestcases, maxtestcases, 1, true);
  test += '\n';
  for (int j = 0; j < t; j++) {
    int n = genint(minlength, maxlength, 5, true);
    test += '\n';
    genstr(n, n, 1, {"a-z"}, true);
    test += '\n';
  }
}

Тест 1

7
15
qghumeaylnlfdxf
10
rcvscxggbw
10
fnqduxwfnf
10
zvsrtkjpre
15
ggxrpnrvystmwcy
10
yycqpevike
15
fmznimkkasvwsre

Тест 2

6
15
kycxfxtlsgypsfa
15
pooefxzbcoejuvp
15
aboygpoeylfpbnp
15
jvrvipyamyehwqn
10
rqpmxujjlo
10
vaowuxwhms

Тест 3

6
10
bxcoksfzkv
10
txdknlyjyh
15
ixjswnkkufnuxxz
15
zbmnmgqooketlyh
15
koaugzqrcddiute
10
ojwayyzpvs

Тест 4

5
10
psajlfvgub
15
aaovlzylntrkdcp
10
srtesjwhdi
15
cobzcnfwlqijtvd
10
vxhrcbldvg

Тест 5

7
15
wgbusbmborxtlhc
10
mpxohgmgnk
10
ufdxotogbg
15
peyanfetcukepzs
15
kljugggekjdqzje
15
pevqgxiepjsrdzj
10
zujllchhbf

Чтобы сделать большие тесты надо увеличить значения mintestcases, maxtestcases, minlength, maxlength. Для претестов можно взять по 1-2 тесту каждого "размера".

Можно генерировать строки состоящие из заглавных букв: genstr(10, 20, 5, {"A-D"}, true), результат: DCABACCCABBBDBD

Можно и сгенерировать строку состоящую из строчных и заглавных букв: genstr(10, 20, 5, {"A-D", "a-d"}, true), результат: DcaBaccCABBBDBD

Заключение

Этот генератор подойдет и для стресс тестирования. Генерировать тесты в задаче обычно не очень сложно. Подойдет он и для взломов. Можно очень легко сгенерировать "максимальный" тест.

Всем удачных раундов и высокого рейтинга, пока!

Привет, CodeForces!

Наконец-то. Скоро будет новый раунд!

Привет, CodeForces!

Я решил уже 300+ задач. Сейчас я стараюсь решать задачи с рейтингом 1300+. Думаю, что пока не буду повышать сложность, еще не со всеми такими справляюсь

Привет, CodeForces!

Появились результаты регионального этапа по информатике.

Привет, CodeForces!

В сумме я решил уже $$$2^8$$$, $$$4^4$$$ или $$$16^2$$$ задач. Также я решаю задачи на протяжении 63 дней подряд!

Привет, CodeForces!

Сегодня у меня удачный день:

1. Я дорешал C из Див. 2
2. Решил задачу на КТО на 1800
3. Решил ещё одну задачу на КТО (не с КФ, оцениваю на 1400-1600)

Все без разборов.

Я доволен. Надеюсь, будущие раунды станут более удачными для меня, чем этот Див. 2 (я не смог реализовать решение, хотя оно идейно было верно)

Привет, CodeForces!

Ну вот, вся эта суматоха с регионом кончилась, пора вернуться к прежней жизни) Сейчас планы такие: в архиве сортировать задачи с рейтингом от 1300 по количеству решивших. Плавно эти задачи 1300-1500 станут задачами 1400-1600, 1500-1700 и т.д.

Привет, CodeForces!

Без долгих вступлений, я набрал $$$100+100+10+15=225$$$ баллов. Даже лучше, чем в первый день + я решил B, чем был сильно удивлен (так не всегда получается). В сумме $$$100+41+46+100+100+10+15=412$$$, для меня не плохо!

Привет, CodeForces!

Как и для многих, вчерашний день для меня был очень важным. Надо было выложиться по максимуму.

Я набрал $$$100+41+46=187$$$ баллов. Думаю, что я мог получить хоть какие-то баллы за задачу D, если бы так сильно (3 часа) не зациклился на B. Что сильно меня удивило, я получил $$$46$$$ баллов за задачу C, даже больше, чем за B. Но в целом, я примерно так и рассчитывал, написать на $$$180$$$-$$$200$$$ баллов. Сегодня надо максимально отдохнуть перед завтрашним днем. Желаю всем удачи завтра! ;)

UPD: второй день — https://codeforces.com/blog/entry/124985

С Новым Годом, CodeForces!

Удачных всем раундов и высокого рейтинга!

Привет, CodeForces!

Я сейчас изучаю комбинаторику и наткнулся (сам нашел) на одну интересную вещь:

$$$C_{n}^{0}+C_{n}^{1}+\ldots+C_{n}^{n-1}+C_{n}^{n}=2^n$$$

Например, если $$$n=3$$$, то

$$$C_{3}^{0}+C_{3}^{1}+C_{3}^{2}+C_{3}^{3}=2^3=8$$$

$$$C_{3}^{0}=1;$$$ $$$C_{3}^{1}=3;$$$ $$$C_{3}^{2}=3;$$$ $$$C_{3}^{3}=1$$$

$$$1+3+3+1=8$$$

Если $$$n=4$$$, то

$$$C_{4}^{0}+C_{4}^{1}+C_{4}^{2}+C_{4}^{3}+C_{4}^{4}=2^4=16$$$

$$$C_{4}^{0}=1;$$$ $$$C_{4}^{1}=4;$$$ $$$C_{4}^{2}=6;$$$ $$$C_{4}^{3}=4;$$$ $$$C_{4}^{4}=1;$$$

$$$1+4+6+4+1=16$$$

Буду благодарен, если кто-нибудь объяснит!

Привет, CodeForces!

Наконец-то! Я решил свои первые 100 задач! Дальше — больше :)