Hello all!

I have some news to share about CF-Predictor (a service that allows you to view rating changes before official results). This extension was launched almost 6 years ago. Number of users has grwon from a couple hundreds to nearly 50k! I'm very proud that this service is used by so many people!

One of the cool features of mine extension is that it is friendly to codeforces API :) All the request to codeforces are sent from just one backend server. Therefore, users don't overload codeforces with extra API calls.

I was using Heroku as a cloud provider to run my servers. Unfortunately, they are closing their free accounts on Nov 28th. So, I decided to take down my servers on heroku. Thus, starting from 2022-11-27 cf-predictor-frontend.herokuapp.com and cf-predictor.herokuapp.com will not work.

On a bright side, I though that upsetting 50k people isn't a good thing. Therefore, I'm renting a VPS and you can continue to use CF-Predictor via cf-predictor.wasylf.xyz! I already updated extentions for Chrome, Mozilla and Opera to use the new backends. However only Mozilla has accepted the new version so far. I hope the changes will be reviewed quickly and you all will be able to use new version soon!

Good luck to all of you and have a high rating!

Hello everyone!

I'm the author and maintainer of CF-Predictor. Unfortunately, CF-Predictor didn't work well today during the beginning of round #773. Its backends were OOMing... This is very strange because it was using way less memory than the free limits permit.

As mitigation, I've restricted rating calculation to just round773, so sorry to everyone who participates in Kotlin Heroes: Practice 9. Predictions will start working again once round #773 is finished.

Thanks, everyone for using CF-Predictor! I'll look into the memory usage issue later this week, hope it will not be too complicated to fix :)

Всем привет! Недавно прошел первый див.2 раунд по новым правилам. Конечно, мне стало интересно, как новый формат отразился на рейтинговой системе. Я разделил участников по дивизионам, как обычно, и посчитал изменения рейтинга для них независимо. Эти данные можно найти по ссылкам: div1 only, div2 only.

Посчитав сумму изменений рейтинга для участников одного дивизиона и разделив на количество участников из этого дивизиона получим среднее изменение рейтинга по дивизиону:

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

Глядя на полученные данные возникает ощущение, что участники из первого дивизиона получили неплохой бонус почти в 12 очков и это может несколько усложнить переход из второго в первый дивизион. А что вы думаете по этому поводу? Может стоит пересчитывать рейтинги внутри дивизионов независимо друг от друга? А может это средняя температура по больнице и ни очем не говорит:)

PS Сама идея разрешить фиолетовым писать контесты вместе со вторым дивизионом мне очень нравится и я давно ждал эту "фичу":)

Хочу обратится за советом к сообщесту codeforces.

Я учусь на втором курсе магистратуры и мне нужно в этом году писать дипломную работу. В прошлом году, в качестве курсовой сделал CF-Predictor, я бы очень хотел как-нибудь развить тему (добавить научности) и продолжить этот проект, но к сожелению никаких подходящих идей мне не приходит. Возможно кто-нибудь может подсказать мне, в каком направлении можно продолжить разработку или какой новый сервис можно разрабработать для codeforces, чтобы эта затея вылилась в не плохой диплом!

Заранее спасибо

В Украине достаточно давно (1 июня 2017г.) заблокировали доступ к куче российских компаний в том чисе Яндекс и Mail.Ru, Codeforces тоже перестал быть доступным в тот день, я так понимаю, из-за того, что хостится на серверах Mail.Ru.

Для свободного доступа к Codeforces я просто в настройках роутера убрал DNS сервер провайдера и поставил гугловский DNS (8.8.8.8). И все было хорошо до 16 сентября. В этот день неожиданно Codeforces стал доступен со всех мобильных операторов (Vodafone, Lifecell, Kyivstar) и стал ОЧЕНЬ МЕДЛЕННО грузится в универе и у меня дома :(

Я не большой специалист по сетям, попробовал пропинговать CF, вроде все нормально:

>ping codeforces.com
PING codeforces.com (212.193.33.27) 56(84) bytes of data.
64 bytes from codeforces.ptr.sgu.ru (212.193.33.27): icmp_seq=1 ttl=56 time=35.4 ms
64 bytes from codeforces.ptr.sgu.ru (212.193.33.27): icmp_seq=2 ttl=56 time=36.8 ms
64 bytes from codeforces.ptr.sgu.ru (212.193.33.27): icmp_seq=3 ttl=56 time=35.7 ms
64 bytes from codeforces.ptr.sgu.ru (212.193.33.27): icmp_seq=4 ttl=56 time=37.3 ms
^C
--- codeforces.com ping statistics ---
4 packets transmitted, 4 received, 0% packet loss, time 3002ms
rtt min/avg/max/mdev = 35.499/36.340/37.343/0.761 ms

Я пока вижу 2 способа решения проблемы:

1) открывать CF через опера впн, но тут минус в том, что флеш не грузится и делать взломы во время раунда не получится

2) раздавать интернет с мобильного, но тоже как-то не удобно каждый раз переподключаться к сети, когда решишь зайти на CF.

Кто-нибудь еще испытывает такую проблему? Может есть какие-нибудь более удачные способы решения?

Всем привет! Я на прошлом контесте предлагал всем желающий потестировать мой сервис предсказания изменений рейтинга. Сейчас я рад представить его!

Огромное количество Ваших нервных клеток погибает, так и не дождавшись обновления рейтинга. Хватит это терпеть! Теперь Вы можете использовать данный сервис для приблизительно вычисления изменения рейтинга.

Наиболее интересная составляющая — расширение для хрома. Оно изменять страницу положения, добавляя предсказываемые дельты. Расширения доступны для 3х браузеров:

Расширение в работе:

Более детальную информацию (seed, rank, expected delta, etc.) можно посмотреть на сайте.

Проект до сих пор в бете, так что предсказания не очень точны. В среднем ошибка не превышает 5 очков, но для участников из конца положения ошибка может достигать нескольки сотен.

Я хочу выразить благодарность Rubanenko и всей команде разработчиков NBHEXT за их открытые исходники и MikeMirzayanov за отличную платформу Codeforces с публичным API и формулами подсчета рейтинга!

AWESOME UPD Предсказание для сегоднешнего контеста (cf #399) полностью соответствует реальным изменениям! Спасибо riadwaw! Он направил меня в правильное русло, и баг рассчета рейтинга пофикшен!

Всем доброго времени суток!

Как известно, в ноябре 2015 были опубликованы формулы для рассчета рейтинга. Как мне кажется, наиболее неоднозначная часть — определение вероятности, что один участник выступит лучше другого:

А где вероятность — там мат. статистика. Уже прошло довольно много рейтинговых раундов на Codeforces, поэтому я задумал вычислить данную вероятность статистически. Было решено провести вычисления на раундах cf №200 — №350 (отдельно по дивизионам). Для этого я написал небольшую программку (иссходники). Закинул полученные результаты в Excel и получил такие графики:

для первого дивизиона

для второго дивизиона

Кажется довольно не плохая аппроксимация но я решил попробовать найти что-нибудь поближе:) Подбор выполнял вручную (так что наверно можно получить результаты получше) вышло:

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

Теперь посмотрим, как это выглядит на графиках:

для первого дивизиона

для второго дивизиона

Кажется, так выглядит получше:)

Может возникнуть несколько вопросов, так что попробую ответить:)

1) Почему при нулевой разнице рейтинга статистическая вероятность победы не 50%?
Потому, что пользователи с одинаковыми рейтингами иногда занимают одинаковое место.

2) Почему во втором дивизионе аппроксимация хуже?
Скорее всего это из-за читеров, так как большое расхождение начинается при разнице рейтинга от 200.

P.S. Что побудило меня на эти исследования?

По результатам 3 раунд VK CUP неожиданно для меня понизился рейтинг. По этому, пользуясь открытыми формулами, быстренько посчитал сиды для всех участников контеста, у нашей команды вышел seed = 97.3936 а место — 96.. но причина падения — в этом раунде рейтинг считался не для всех сразу, а отдельно по дивизионам. Но я уже разогрелся и не захотел останавливаться на полученном:)

P.P.S. На всякий случай, отмечу, что я глубоко уважаю Михаила MikeMirzayanov Мирзаянова, Максима Zlobober Ахмедова, Глеба GlebsHP Евстропова и всех остальных причастных к созданию и функционированию Codeforces и у меня нет никаких претензий, только предложения по улучшению:)

UPD: Уже решено.

Всем привет! Встретилась задача и я не догадываюсь как ее решать((

Условие:

Есть взвешенное дерево из N (N <= 150 000) вершин Q (Q <= 75 000) запросов: найти кратчайшее расстояние между парой вершин.

Мои скудные соображения: 1. Традиционный поиск в ширину/глубину дает сложность O( N*Q ) — слишком много. 2. Алгоритм Флойда-Уоршелла дает O ( N^3 + Q) — еще хуже. 3. Мне кажеться, что должен быть какой-то препроцессинг за O(N * logN) или O(N^1.5) и выполнение запросов за O(log N) или O(N^0.5). На этом все((

Задача не с олимпиады или соревнования, нам показали пример вступительных билетов в магистратуру. Фото (на украинском) ниже:

Всем привет! Сегодня наткнулся на новость: "Сделка года: Snapchat купил одесский стартап Looksery за $150 млн". И вспомнил, что на кф есть организация, которая точно так же называется. Очень рад за них, это еще один пример на пользу олимпиадного программирования.

Основатели популярного мобильного приложения Snapchat для обмена сообщениями в 2012 году отказались от $3 млрд, которые им предлагал Марк Цукерберг за проект. А в 2015 году Snapchat помог украинской команде совершить пока что самый крупный экзит в истории украинских стартапов. Редакции AIN.UA стало известно, что одесский Looksery стал частью Snapchat. CEO Looksery Виктор Шабуров и сотрудники компании от комментариев отказались. Сумма сделки, по данным редакции, составила около $150 млн. По слухам, вся команда разработки украинского приложения из Одессы переедет в США.

Отдельное приложение Looksery исчезло из AppStore, став частью приложения Snapchat — если во время записи видеозвонка тапнуть по изображению своего лица, на экране появятся знакомые фильтры от Looksery.

источник

Здравствуйте! Не мог бы кто-нибудь подсказать, где найти portable версию gcc 4.9.2 для win 32?

Мы решили обновить версию компилятора на Киевской городской олимпиаде (и отборах) и попутно добавить поддержку С++11. Версию 4.9.2 выбрал, потому что на КФ такая)) Компьютеров для участников много, поэтому не хотелось бы проводить установку на каждый компьютер по отдельности.

Заранее спасибо

Мне наконец-то пришла футболка с Russian code cup 2014! Я, проживающий в Киеве, потерял всякую надежду на ее получение, но случилось новогоднее чудо — пришла бандероль с России:

а в ней футболочка!

Большое спасибо Mail.ru и всем побольше приятных новогодних сюрпризов!

На топкодере 1 декабря вторник...

Недавно я с удивлением узнал, что алгоритм, которым я пользовался для нахождения минимального пути в графе от одной вершины до остальных, не совпадает с классической дейстрой описанной на википедии или e-maxx. Теперь напишу, как я ищу минимальный путь.

1. Создаем линейный массив cost в котором будем хранить минимальное расстояние до каждой вершины. Инициализируем его БОЛЬШИМИ значениями, а для стартовой вершины запишем 0.
2. Создаем сет интов s, в него мы будем помещать вершины, которые стоит посетить. Изначально s содержит только стартовую вершину.
3. Пока s не пустой выполняем следующее

• берем вершину с начала s, обозначим ее через u, удаляем из сета;
• проходимся по всем ребрам идущим из u. Пусть текущее ребро соединяет вершину u с вершиной v и имеет вес w. Если cost[u]+w < cost[v] тогда обновляем значение для cost[v]= cost[u]+w и добавляем в s вершину v, так как мы нашли до нее "более короткий" путь.

В массиве cost содержаться минимальные расстояния до каждой вершины.

код:

const int inf= INT_MAX/2;
const int MaxN= 2000;
vector<pii> a[MaxN+5]; // список смежности. 
//a[i][j].vartex – номер вершины смежной с i-ой, 
//a[i][j].weight – вес ребра, соединяющего эти вершины.
int cost[MaxN+5];
...
int u,w;
int from; //номер стартовой вершины. 

// заполняем массив БОЛЬШИМИ значениями
for (int i=0; i<=MaxN; i++)
   cost[i]= inf;

set<int> s;
s.clear();
// кладем в начало сета "стартовую вершину" и ставим расстояние до нее 0
s.insert(from); cost[from]= 0; 
int c;

while (!s.empty()) //пока сет не пустой
{
    u= *s.begin(); c= cost[u];
    s.erase(s.begin());
    for (int i=a[u].size()-1; i>=0; i--)
    {// проходимся по всем вершинам смежным с u
       if (cost[a[u][i].vartex]>c+a[u][i].weight) 
       {// если до текущей вершины путь через u "короче"
           cost[a[u][i].vartex]= c+a[u][i].weight; // обновляем значение в массиве
           s.insert(a[u][i].vartex); // добавляем в сет
       }
    }
}

Я пока что точно не оценил сложность алгоритма, но надеюсь на что-то вроде O(E logV), где V – количество вершин, а E – количество ребер в графе. Из возможных преимуществ данного алгоритма можно считать: чуть более краткий код, корректность работы при отрицательном весе ребер.

И собственно вопрос)) можно ли этот алгоритм считать модификацией Дейкстры или он как-то по-другому называется? Или это вообще не ясно что?))

UPD Как уже написали хорошие люди, этот алгоритм неэффективный. так что лучше им не пользововаться

Данный пост продолжение этого
Для решения будет использоваться мой код класса дерево отрезков единичная модификация.

1. Дима и массив

Мама подарила мальчику Диме массив длины n. Массив этот не простой, а особенный. Дима может выбрать два числа i и d (1 ≤ i ≤ n, -1000 ≤ d ≤ 1000), и элемент с индексом i магически становится равным d. Дима играет со своим массивом, а мама время от времени задает ему вопросы — какова сумма всех чисел в массиве с индексами от f до t? Дима легко справился с этими вопросами, сможете ли Вы?

Технические условия

Входные данные

В первой строке находятся два целых числа n и q (1 ≤ n ≤ 5•105, 1 ≤ q ≤ 105) — количество элементов в массиве и суммарное количество операций и запросов соответственно. В следующей строке дано n чисел a1, a2, ..., an (−1000 ≤ ai ≤ 1000) — начальное состояние массива. В следующих q строках заданы операции и запросы. Первый символ в строке может быть = или ?. Если строка начинается с =, то это операция присваивания. Далее следуют i и d, ограничения на которые описаны в условии. Если строка начинается с ?, то это запрос. Далее следуют числа f и t(1 ≤ f, t ≤ n).

Выходные данные

Для каждого запроса выведите сумму чисел в массиве с индексами от f до t, по одному результату в строке.

Решение.

Это одна из классических задач на ДО. В качестве функции используется сумма.

Код

const int MaxN= 5*100*1000;
int a[MaxN+5];

int main()
{
   ios::sync_with_stdio(0);
 //freopen("input.txt","r",stdin);
 //freopen("output.txt","w",stdout);

int n,q;
cin>>n>>q;
for (int i=0; i<n; i++)
   cin>>a[i];

SegmentTree<int> st(n,a);
char c;
int l,r;
int i,d;
for (int Q=0; Q<q; Q++)
{
   cin>>c;
   if (c=='?')
   {
       cin>>l>>r;
       cout<<st.query(l-1,r-1)<<endl;
   }
   else
   { //c== '='
       cin>>i>>d;
       st.update(i-1,d);
   }
}
return 0;
}

2. В стране невыученных уроков

Витя попал в страну невыученных уроков. Для того, чтобы вернуться домой ему нужно выполнить множество заданий. В этой задаче он должен выиграть у стражей в НОД-игру. Правила этой игры очень простые: есть массив натуральных чисел, после чего игроки выбирают два числа l и r, и им надо посчитать наибольший общий делитель (НОД) всех элементов в массиве с индексами от l до r включительно. Кто быстрее посчитает, тот и выиграл. Чтобы избежать нечестных игр, они иногда заменяют некоторые числа в массиве на другие. Витя очень хочет домой, помогите ему в этом, для чего напишите программу, которая будет очень быстро считать НОД на заданном промежутке.

Технические условия

Входные данные

Первая строка содержит количество элементов n (1 ≤ n ≤ 105) в массиве. Во второй строке находится n чисел – элементы ai (1 ≤ ai ≤ 109) массива. В третьей строке находится количество запросов m (1 ≤ m ≤ 105). Далее в m строках находятся по три числа q, l, r (1 ≤ l ≤ r ≤ n). Если q = 1, требуется посчитать НОД элементов на промежутке [l, r], если q = 2, то надо заменить элемент в позиции l на число r.

Выходные данные

Для каждого запроса с номером 1 в отдельной строке выведите ответ на запрос. Подсказка. Тут все просто:)

Решение.

Просто напишем функцию наибольшего общего делителя и передадим ее в качестве ассоциативной функции для ДО.

Код.

int gcd(int a, int b)
{
   if (a==0) return b;
   return gcd(b%a,a);
}


const int MaxN= 5*100*1000;
int a[MaxN+5];

int main()
{
  ios::sync_with_stdio(0);
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);

int n,q;

cin>>n;
for (int i=0; i<n; i++)
  cin>>a[i];
cin>>q;

SegmentTree<int> st(n,a,gcd);
char c;
int l,r;
int i,d;
for (int Q=0; Q<q; Q++)
{
  cin>>c;
  if (c=='1')
  {
      cin>>l>>r;
      cout<<st.query(l-1,r-1)<<endl;
  }
  else
  { //c== '2'
      cin>>i>>d;
      st.update(i-1,d);
  }
}
return 0;
}

3. Range Variation Query

Последовательность an задается следующей формулой: an = n2 mod 12345 + n3 mod 23456. Требуется много раз отвечать на запросы следующего вида: • найти разность между максимальным и минимальным значением среди элементов ai, ai+1, ...,aj; • присвоить элементу ai значение j.

Технические условия

Входные данные

Первая строка содержит натуральное число k (k ≤ 100 000) — количество запросов. Следующиеk строк содержат запросы, по одному в строке. Запрос номер i описывается двумя целыми числамиxi, yi. Если xi > 0, то требуется найти разность между максимальным и минимальным значением среди элементов axi...ayi. При этом 1 ≤ xi ≤ yi ≤ 100 000. Если xi < 0, то требуется присвоить элементу a-xi значение yi. При этом -100 000 ≤ xi ≤ -1 и |yi| ≤ 100 000.

Выходные данные

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

Подсказка.

Создать 2 дерева отрезков.

Решение.

В одном будем хранить максимум на отрезке, в другом – минимум. Нам понадобиться лишь написать функции минимума и максимума и передать в качестве 0 для минимума ОЧЕНЬ большое число, для максимума ОЧЕНЬ маленькое.

Код.

 int Max(int a, int b)
 {
return max(a,b);
 }

 int Min(int a, int b)
 {
return min(a,b);
 }

const int MaxN= 100000;
const int inf= 1000*1000*1000;
int a[MaxN+5];

int main()
{

 ios_base::sync_with_stdio(0);
 cin.tie(0);
 srand(__rdtsc());

 for (LL i=0; i<=MaxN; i++)
a[i]= i*i % 12345 + i*i*i % 23456;


 SegmentTree<int> stMin(MaxN,a+1,Min,inf);
 SegmentTree<int> stMax(MaxN,a+1,Max,-inf);

 int x,y,k;
 cin>>k;
 for (int i=0; i<k; i++)
 {
 cin>>x>>y;
 if (x>0) cout<<(stMax.query(x-1,y-1)-stMin.query(x-1,y-1))<<endl;
 else
 {
 stMin.update(-x-1,y);
 stMax.update(-x-1,y);
 }
 }

 return 0;
}

4. Можете ли Вы ответить на эти вопросы — 3

Задана последовательность целых чисел a1, a2, ..., an (|ai| ≤ 10000 , 1 ≤ n ≤ 50000). Над ней Вам следует выполнить m (m ≤ 50000) операций: • модифицировать i-ый элемент последовательности • для заданных x и y вывести MAX {ai + ai+1 + ... + aj, x ≤ i ≤ j ≤ y}

Технические условия

Входные данные

Первая строка содержит значение n. Следующая строка содержит n целых чисел, задающих последовательность a1, a2, ..., an. Третья строка содержит число m. Следующие m строк содержат запросы вида: • 0 x y: изменить ax на y (|y| ≤ 10000). • 1 x y: вывести MAX {ai + ai+1 + ... + aj, x ≤ i ≤ j ≤ y}

Выходные данные

Для каждого запроса вывести ответ как требуется в задаче.

Подсказка.

Создадим структуру из 4 элементов: сумма на отрезке, максимальная сумма на отрезке (ответ на запрос), максимальная сумма начинающаяся с начала отрезка, максимальная сумма заканчивающаяся в конце отрезка.

Решение.

Создадим на этой структуре ДО. Функцию нужно задать следующим образом: сумма на отрезке, очевидно, равна сумме всех чисел; левая сумма – максимум среди [левая сумма левого отрезка], [сумма всех чисел левого отрезка и левая сумма правого отрезка]; правая сумма – максимум среди [правая сумма правого отрезка], [сумма всех чисел правого отрезка и правая сумма левого отрезка]; максимальная сумма – максимум среди [максимальная сумма левого отрезка, максимальная сумма правого отрезка, правая сумма левого отрезка+левая сумма правого отрезка]

Код.

const int inf= 16000;

class Four
{
public:
int leftSum,rightSum,maxSum,sum;
Four()
{
leftSum= -inf;
rightSum= -inf;
maxSum= -inf;
sum= 0;
}

Four(int a, int b, int c, int d)
{
leftSum= a;
rightSum= b;
maxSum= c;
sum= d;
}
};

 Four maxSum(Four a, Four b)
 {
 Four res;
 res.leftSum= max(a.leftSum,a.sum+b.leftSum);
 res.rightSum= max(b.rightSum,b.sum+a.rightSum);
 res.maxSum= max(a.maxSum,max(b.maxSum,a.rightSum+b.leftSum));
 res.sum= a.sum+b.sum;
 return res;
 }


const int MaxN= 50000;
Four a[MaxN+5];



int main()
{

 ios_base::sync_with_stdio(0);
 cin.tie(0);
 srand(__rdtsc());

 int n;
 cin>>n;
 {
 int t;
 for (int i=0; i<n; i++)
 {
 cin>>t;
 a[i]= Four(t,t,t,t);
 }
 }

 Four zero(-inf,-inf,-inf,0);
 SegmentTree<Four> st(n,a,maxSum,zero);

 int x,y,m,q;
 cin>>m;
 Four t;
 for (int i=0; i<m; i++)
 {
 cin>>q>>x>>y;
 if (q==1)
 {
t= st.query(x-1,y-1);
cout<<t.maxSum<<endl;
 }
 else
 {
 st.update(x-1,Four(y,y,y,y));
 }
 }

 return 0;
}

Тема данного поста — не нова, но, наверняка, кому-нибудь пригодится:) Начнём с примера задачи, в которой используется дерево отрезков.

Имеется массив из n (n≤10^5) целых чисел, нужно находить сумму на отрезке от l до r (0≤l,r≤n-1) и изменять значение i-го
(0≤i≤n-1) элемента. Количество запросов m (m≤10^5).

Очевидно, что наивное решение работает за O(n*m), а дерево отрезков дает возможность решать данную задачу с асимптотикой O(m*log2n).

Существует множество разных видов деревьев отрезков. В данной статье дерево отрезков – структура данных, которая по имеющейся последовательности из n чисел умеет выполнять быстро (за логарифмическое время) 2 вида запросов:

1) Изменить значение i-го элемента
2) Вычислить значение некоторой фиксированной ассоциативной функции на отрезке от l до r.

Что же собой представляет дерево отрезков(ДО)? ДО – бинарное дерево (обычно, для удобства дополняют до полного нулевыми элементами), в котором листьями являются элементы исходного массива, а в каждой вершине записано значение функции f от двух сыновей. То есть в листах записано значение функции на отрезке длинной 1, в родителе записано значение функции на отрезке длинны 2, в родителе которого – 4… таким образом, в каждой вершине записано значение функции на некотором отрезке, что и послужило поводом для такого названия.

Для нашего примера задачи функция f – сумма, тогда ДО для четырех элементов будет выглядеть следующим образом:

Если же у нас количество элементов (n) не является степенью двойки, то мы дополним их нулями. (В общем случае, когда мы работает с типом данных Т и функцией f, то ноль — такое значение, что для любого x из T верно f(x,ноль)=x.) Например, ДО сумм для 3 элементов будет выглядеть так:

Как же хранить ДО? Существует 2 способа:
• структуры на указателях;
• линейный массив.

На сколько мне известно, первый способ используют только для персистентных ДО. Мы же пока разбираем самую обычную и простую модификацию ДО, поэтому воспользуемся вторым способом. Создадим линейный массив a из 2*nMax элементов, где nMax – наименьшая степень двойки, которая не превосходит n. В первом элементе (a[1]) будем хранить корень дерева, а для каждой вершины i её сыновья хранятся в ячейках с номерами 2*i (левый сын), 2*i+1 (правый сын). Почему для хранения достаточно 2*nMax элементов? Мы имеем nMax листов, у них nMax/2 родителей, у них nMax/4 … и 1 корень, очевидно, что эта сумма (1+2+4+…+ nMax/4+ nMax/2+ nMax) равняется 2*nMax-1.

На рисунке проставим возле каждой вершины ее индекс в массиве:

А в массив дерево будет уложено следующим образом:

Теперь определим, какие операции мы хотим выполнять с нашим ДО:
1) построить ДО;
2) узнать значение i-го элемента;
3) изменить значение i-го элемента;
4) найти значение функции на отрезке от l до r.

Разберем по очереди все операции.

1 Построить дерево отрезков.

Пусть у нас есть массив b из n элементов. Для начала нам нужно найти nMax (наименьшая степень двойки, которая не превосходит n). Это можно реализовать как через формулу:

nMax = (1 << (int)(log2(1.0*(n-1)) + 1);

так и простеньким циклом:

nMax= 1;
while (nMax<n) nMax<<= 1;

Далее нужно заполнить массив a нулями (соответствующего типа) и заполнить листы ДО значениями из массива b (мы помним, что в ДО индексы листьев от nMax до 2*nMax-1):

for (int i=0; i<n; i++)
    a[nMax+i]= b[i];

На данный момент имеем:

Теперь осталось только заполнить значения во всех родителях. Это можно сделать за один линейный проход (помним, что у i-ой вершины сыновья с индексами 2*i и 2*i+1, а в вершине мы храним значение функции от двух сыновей):

        for (int i=nMax-1; i>0; i--)
            a[i]= f(a[2*i],a[2*i+1]);

Таким образом мы построили ДО с асимптотикой O(nMax) = O(n).

2 Узнать значение i-го элемента.

Как уже писалось ранее у нашего ДО листья имеют индексы от nMax до 2*nMax-1, поэтому значение i-го элемента элемента находиться в ячейке с индексом nMax+i: return a[nMax+i] Очевидно, что данный запрос выполняется за константу.

3 Изменить значение i-го элемента.

Если мы изменим значение в листе дерева, то все значения на пути к корню от данного листа перестанут соответствовать действительности, поэтому их нужно пересчитать, в остальных же останутся корректные значения. Как известно, глубина полного бинарного дерева из m вершин равна log2m, поэтому мы должны выполнить данную операцию за логарифмическое время. Например, изменим a2 на a2 I :

Красным цветом выделены вершины, в которых нужно изменить значения.

Что бы «обновить» ДО нам нужно записать в лист новое значение, а затем подняться до корня, каждый раз пересчитывая значение функции в вершине. Изменить значение в листе очень просто (вспомним, что индексы листьев от nMax до 2*nMax-1). Значение i-го листа имеет индекс nMax+i :

       a[nMax+i]= newValue;

Теперь осталось подняться до корня, это можно сделать с помощью цикла:

        while (i>1)
        {
          i/= 2;
          a[i]= f(a[2*i],a[2*i+1]);
        }

4 Найти значение функции на отрезке от l до r.

Наконец-то, мы добрались до самого интересного запроса. Стоит отметить, что частный случай, когда l=r разобран в пункте 2 и выполняется за константу, в общем же случае асимптотика логарифмическая.

Введем определения.

Фундаментальный отрезок – такой отрезок, для которого существует вершина в дереве, хранящая значение функции на данном отрезке.

Уровень. Уровень корня – 1, а для каждого сына уровень на единицу больше, чем у родителя.

Для того, что бы вычислить значение функции на отрезке, нам необходимо разбить его на МИНИМАЛЬНОЕ количество фундаментальных отрезков. Что бы найти значение для любой вершины (кроме листа), нам нужно знать значения для сыновей. Мы будем спускаться по ДО. Изначально встаем в корень. Пусть мы находимся в какой-то вершине. Рассмотрим 3 возможных случая: отрезок [l..r] совпадает с отрезком, соответствующим текущей вершине, отрезок [l..r] полностью принадлежит одному из сыновей, отрезок принадлежит обоим сыновьям. В первом случае просто возвращаем посчитанное значение из ДО, во-втором – спускаемся в данного сына, в-третьем же случае разобьем данный отрезок на два: [l..правый конец левого сына] и [левый конец правого сына..r]. Рекурсивно вычислим значения для каждого из них.

Рассмотрим на примере. Пусть у нас есть ДО для 8 элементов, запишем, какой отрезок соответствует каждой вершине:

А теперь посмотрим, как будет выполняться запрос для отрезка [1..5].

Сначала встаем в корень — наш отрезок принадлежит обоим сыновьям. Значит, нам нужно разбить его на 2 отрезка: [1..3] и [4..5]. Для каждого из них рекурсивно вычислить значение. Далее отрезок [1..3] опять принадлежит 2 сыновьям, разбиваем его на 2 отрезка: [1..1] и [2..3]. Отрезок [1..1] принадлежит только правому сыну, спускаемся в него и видим, что отрезок [1..1] – фундаментальный. Берем для него значение из вершины, и поднимаемся до 2 уровня (вершина [0..3]). Для левого сына мы уже рекурсивно посчитали, теперь посчитаем для правого: спускаемся в него. Отрезок [2..3] – фундаментальный, берем значение из вершины. Возвращаемся в [0..3] и уже можем вычислить значение для отрезка [1..3], так как значение функции уже вычислили для обеих его частей. Возвращаемся в корень и спускаемся в правого сына [4..7], наш подотрезок ([4..5]) принадлежит только одному левому сыну, спускаемся в него. Вершине соответствует отрезок [4..5], следовательно, он — фундаментальный, берем из вершины значение. Возвращаемся в корень и вычисляем ответ.

Почему этот запрос выполниться за логарифмическое время? Как известно, глубина (количество уровней) дерева из n вершин равняется log2n, кроме того, утверждается, что на каждом уровне мы посетим не более 4 вершин, таким образом, мы посетим O (log2n) вершин. Рассмотрим код. Для вычисления значения на отрезке нам понадобится вызвать рекурсивную функцию от 5 аргументов, для удобства напишем функцию, которая по 2 аргументам (границы отрезка для запроса) вызывает функцию 5-и аргументов и возвращает значение:

T query(int l, int r)
{// return value function f on the segment [l;r]
return query(l,r,0,nMax-1,1);
}

Теперь наша рекурсивная функция:

T query(int l, int r, int leftPosition, int rightPosition, int v) 
{// return value function f on the intersection segments [l;r] and [leftPosition;rightPosition]
 // l – левая граница запроса
 // r – правая граница запроса
 // v – текущая вершина дерева отрезков
 // [leftPosition; rightPosition] – отрезок соответствующий v

if (r<l) return zero;
//если отрезок не существует, то возвращаем ноль.
if (l==leftPosition && r==rightPosition) return a[v];
// если отрезок фундаментальный,то возвращаем значение из вершины
// раз мы дошли сюда, то отрезок принадлежит сыновьям
int middle= (leftPosition+rightPosition)/2;
// вычисляем правую границу левого сына
return f(query(l,min(middle,r),leftPosition,middle,v*2),
    query(max(l,middle+1),r,middle+1,rightPosition,v*2+1));
// рекурсивно вычисляем запросы для сыновей
}

Мой код класса дерево отрезков единичная модификация.

Скоро выложу несколько примеров задач с решениями с использованием опубликованного класса.

P.S. Буду рад конструктивным замечаниям/предложениям по написанию статьи/кода

UPD: вот примеры

Я, конечно, не в праве требовать, но все же интересно, почему вчера целый день не работал кодефорсес?))

26 апреля 2014 года пройдет I этап ACM 2014/15 в Украине. разные документы/приказы по этому поводу.

Всем удачи и больших квот:)

Здравствуйте! Появилась следующая проблема. Решаю задачу с e-olimp, и мое решение проходит только первый тест. Подобрать вручную тест, который не пройдет мне не удалось. Тогда я вспомнил про стресс тесты (моя первая попытка), написал лобовое решение, генератор и батник. запустил все это дело и за 2 часа так и не удалось найти тест, на котором программы работают по-разному. Подскажите, пожалуйста, как лучше писать стресс тесты? или может я что-то не так понимаю?

вот ссылки:
задача
лобовое решение
решение с ошибкой
генератор
сам батник:

@ echo off
:1
echo good
gener.exe
brut.exe
2.exe
fc /L output.txt output_brut.txt 
if %errorlevel% == 0 goto 1
echo NeSovpalo
pause

спасибо за помощь

UPD новое лобовое решение + в генераторе изменил количество тесто на 10 000. запустил, жду...