Всем привет!

Сейчас проходит зимняя смена ЛКШ (Летней Компьютерной Школы), и мы в составе параллели А*+ с ее преподавателями подготовили полноценный Codeforces Round.

Раунд состоится в 05.01.2020 17:05 (Московское время) и продлится 2 часа. В каждом дивизионе будет предложено по 6 задач.

Задачи раунда были придуманы и подготовлены ismagilov.code, devid, Volkov_Ivan, Jatana, karasek, polinarria, cookiedoth, AlesyaIvanova, KhB, AliceG, D.Pavlenko, VFeafanov, LordVoIdebug, forestryks, Ilistratov, seiko.iwasawa, senjougaharin, Drozd_off под руководством преподавателей PavelKunyavskiy, VArtem, meshanya, budalnik.

Спасибо aneesh2312 MarcosK Stepavly Infinity25 tourist antontrygubO_o isaf27 fedoseev.timofey, Kurpilyansky, vintage_Vlad_Makeev за тестирование!

И, конечно же, спасибо MikeMirzayanov за великолепные системы Codeforces и Polygon, и 300iq за координацию раунда.

Всем удачи!

UPD: В задаче E была допущена ошибка в авторском решении, а именно переполнение типа long long при подсчете ответа. До первого теста, на котором оно случалось, дошли 4 участника (ainta aid Um_nik ecnerwala), из которых 2 прошли претесты, а не должны были, и еще 2 не прошли претесты, хотя были должны. В автоматическом режиме протестировать так, чтобы оба ответа принимались не представляется возможным, т.к. переполнение меняет тесты из-за способа шифрования запросов. Поэтому, мы решили, протестировать два решения прошедших до перетестирования решения на старом наборе тестов, а остальные — на новом. В результате, три из решений прошли тесты, с чем мы подзравляем авторов, а одно получило WA80 на 17-ом ответе внутри теста, что явно не связано с проблемами с переполнением. В дорешивание можно сдать только решение, которое учитывает проблему с переполнением.

UPD: Разбор!

The MEX Foundation Contest #1 (supported by AIM Tech) that was held in the 37th Petrozavodsk Programming Camp now available in the Gym.

The authors of the contest are Jatana, cookiedoth, Egor.Lifar. The problems are of a good quality, a number of participants can approve it.

Special thanks to vintage_Vlad_Makeev for useful advices, LHiC for testing the contest, vintage_Vlad_Makeev for inspiration and AIM Tech Members for the problem review.

Hello, I would like to introduce the plugin FastOlympicCoding for Sublime Text.
It provides several useful features for competitive programming.

I invent method to merge two cartesian trees with maybe intersect keys. And want to know what is asymptotic of it.

method:

let's add to a standard cartesian tree field musorka

struct Node {
  Node *l = NULL, *r = NULL;
  int key, priority, cnt = 1;

  Node *musorka = NULL;
}

and when we want to merge trees A and B A->musorka = B

then write push

void push(Node *node) {
  if (!node->musorka) return;
  push(node->l);
  push(node->r);

  pair<Node*, Node*> spl = split(node->musorka, node->key);
  pair<Node*, Node*> spl2 = split(spl.second, node->key + 1);
  
  if (spl2.first) {
    node->cnt++;
  }

  node->l->musorka = spl.first;
  node->r->musorka = spl2.second;
  node->musorka = NULL;
}

then add this push to merge and split.

Maybe someone can estimate asimptotic of this or give counter test where it works n^2?