Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке: https://t.me/codeforces_official. ×

Автор savkinsd2089, история, 12 часов назад, По-русски,

Привет, Codeforces!

Рад пригласить вас на Codeforces Round #526, который пройдет 10.12.2018 19:35 (Московское время). Раунд будет рейтинговым для обоих дивизионов.

Задачи были подготовлены мной, Dimon, maxim.shuklin, egor.lifar.

Большое спасибо ismagilov.code, Kuyan, 300iq, alexey_kuldoshin, Jatana за тестирование задач, arsijo и gritukan за помощь в подготовке раунда, а также MikeMirzayanov за системы Codeforces и Polygon.

На раунде вам будет предложено 6 задач в каждом дивизионе и 2 часа на их решение. Разбалловка будет объявлена ближе к началу раунда.

UPD:

Разбалловка в Div. 1: 500-1000-1500-2000-2000-2500

Разбалловка в Div. 2: 500-1000-1500-1750-2250-2750

Удачи!

Полный текст »

 
 
 
 
  • Проголосовать: нравится  
  • +154
  • Проголосовать: не нравится  

Автор erdos, история, 2 дня назад, По-английски,

SnackDown 2018 elimination round starts in ~8 minutes. Top 300 get T-shirts

Let's discuss the problems after the contest!

Полный текст »

 
 
 
 
  • Проголосовать: нравится  
  • +60
  • Проголосовать: не нравится  

Автор NeercNews, 3 дня назад, По-русски,

Всем привет!

text

Окончательные результаты Условия задач

В эти выходные 8-9 декабря в Санкт-Петербурге, Барнауле, Кременчуге, Тбилиси, Алматы и Сочи пройдет XIX открытая Всероссийская командная олимпиада школьников по программированию, в которой примет участие более 250 команд. В Сочи ВКОШП проходит впервые, и в этом году Образовательный центр Сириус примет у себя девять команд.

Тур начнется в воскресенье 9 декабря в 10:00. За текущими результатами можно будет следить по ссылке. А после начала тура мы добавим ссылку на условия задач.

Для тех, кто не является участником, но тоже хочет порешать интересные задачи от жюри ВКОШП, будет доступно зеркало, которое начнется в 09.12.2018 11:05 (Московское время). Не присоединяйтесь к нашим трансляциям, если вы планируете принять участие в зеркале, ведь там могут быть спойлеры к задачам. И, конечно, не открывайте условия задач до начала раунда.

UPD: медалистами чемпионата стали:

  1. Москва, 57 + 179: "Пурпурный виноград"
  2. Сборная команда Казани, Лицей КФУ + СПб, ФМЛ 239: "Мертвые души"
  3. Казань, "Преимущественно овощи"
  4. Москва, Интеллектуал #1: "Red Gate"
  5. СПб, ФТШ + 239 + Всеволожск, 6: "Проблемы с Поллардом?"
  6. Алматы, РФМШ: "Чудо Зверята!"
  7. Тбилиси, Школа 199 (им. Комарова) #1: "Komarovi+Mziuri 1"
  8. Москва, СУНЦ МГУ #1: "Вова спит дома"
  9. Москва, 179: "У вас математик есть, чтобы это делать"
  10. Самара + Москва, Гимназия 1 + Школа 97 + СамЛИТ: "МГУ"
  11. Челябинск, Лицей 31: "Пыльная Испания"
  12. Могилёв, Гимназия 2: "Могилёвские орлы"
  13. Москва, СУНЦ МГУ #3: "Ланемия #17"
  14. Москва, 1540: Tinkoff + СУНЦ: "neteam"
  15. Екатеринбург, СУНЦ УРФУ + Гимназия 9: "Жизнь прекрасна"

Если вы не пишите зеркало, то обязательно присоединяйтесь к нашим трансляциям. Для вас, как обычно, будет проводиться трансляция в видеоформате от команды ICPCLive и в текстовом формате в нашем Telegram-канале.

А если вы хотите прийти на ВКОШП в Санкт-Петербурге гостем — заполните гостевую форму и получите свой бейдж на регистрации!

У ismagilov.code в посте есть ссылка на большой набор команд с суммарным рейтингом. Спасибо за интересную информацию!

А вот некоторые команды, у которых есть неплохой шанс стать обладателями кубка:

Команда Город Участник 1 Участник 2 Участник 3 Рейтинг
Мертвые души Казань + СПб Морозов Александр 
scanhex
Гайнуллин Ильдар 
gainullin.ildar
Крамник Сергей 5641
Вова спит дома Москва Романов Владимир 
voidmax
Колодезный Александр
aleksandr2754
Шеховцов Александр
Jatana
6854
Чудо Зверята! Алматы Закарин Данияр
YaDon4ick
Сардарбеков Батыр
Batrr
Джанкуразов Руслан
ruslanjan
6727
danya.smelskiy Кременчуг Мельник София
Sonechko
Зуб Максим
zubec
Деньга Назарий
Nasic_number_one
6701
Проблемы с Поллардом? СПб, Всеволожск Карнаухов Кирилл
Qlukva
Ефремов Андрей 
andrey_efremov
Одинцов Андрей
Forestryks
6660
Komarovi+Mziuri 1 Тбилиси Birkadze Nika
nikabb
Toloraia Teimuraz
temotoloraia
Gamezardashvili Baqar
baqargam
6597
Пурпурный виноград Москва Савкин Семён
savkinsd2089
Куянов Фёдор
Kuyan
Пискалов Дмитрий
Dimon
6558
Пыльная Испания Челябинск Будников Михаил
Mlxa
Григорьев Савелий 
sava-cska
Ахметшин Кирилл
liriKl
6529

Подписывайтесь на нас!

Полный текст »

 
 
 
 
  • Проголосовать: нравится  
  • +79
  • Проголосовать: не нравится  

Автор I_love_isaf27, 29 часов назад, По-русски,

Предыдущий выпуск

Сегодняшним героем прожарки будет создатель Codeforces Михаил MikeMirzayanov Мирзаянов (Не баньте, плиз, Майк — лучший).

Полный текст »

 
 
 
 
  • Проголосовать: нравится  
  • +83
  • Проголосовать: не нравится  

Автор shahiduI_brur, история, 19 часов назад, По-английски,

It's the happy birthday of our beloved Dr. Bill Poucher!

Happy birthday sir.

You are a legend.

<3 <3 <3

Полный текст »

 
 
 
 
  • Проголосовать: нравится  
  • +130
  • Проголосовать: не нравится  

Автор mkisic, история, 4 часа назад, По-английски,

Hi!

There are a lot of competitive programming coaches who offer online lessons. What do you think, should Codeforces create some subpage where coach can provide information (like prices) about himself?

In chess world, popular sites have pages about that. For example,

https://lichess.org/coach

https://www.chess.com/coaches

Полный текст »

 
 
 
 
  • Проголосовать: нравится  
  • +49
  • Проголосовать: не нравится  

Автор hmehta, история, 30 часов назад, По-английски,

Topcoder SRM 743 is scheduled to start at 12:00 UTC -5, December 9, 2018. Registration begins 24 hours before the match and closes 5 minutes before the match begins.

Problem Writer: boba5551

This is the second SRM of Stage 2 of TCO19 Algorithm.

Stage 2 TCO19 Points Leaderboard | Topcoder Java Applet | Next SRM 744 — December 14

Hope to see most of you competing! All the best!

Полный текст »

 
 
 
 
  • Проголосовать: нравится  
  • +26
  • Проголосовать: не нравится  

Автор justsolveit, история, 12 часов назад, По-русски,

Пожалуйста, помогите мне написать код на c++, который переводить число а в систему счисления b.

Полный текст »

 
 
 
 
  • Проголосовать: нравится  
  • +1
  • Проголосовать: не нравится  

Автор Chilli, история, 5 месяцев назад, По-английски,

One of my favorite implementations of segment trees has always been "Easy and Efficient Segment Trees, by Al.Cash. I used to dread segtree problems, but after reading that blog post and adapting a super simple implementation I've gotten a lot better with them. However, there are some types of segtree that you can't implement in that fashion, namely dynamic segtrees and persistent segtrees. See here for criticism. With the advent of policy hash tables, however, one can now implement dynamic segtrees in Al.Cash's style with somewhat comparable performance to a custom dynamic segtree.

Standard segtree

This is how a standard segtree looks like. You can set a single element, and query for ranges. It's nice and simple, and I think it's a great implementation.

int N;
int seg[2 * MAXN];

void modify(int p, int val) {
    for (seg[p += N] = val; p > 0; p >>= 1)
        seg[p >> 1] = seg[p] + seg[p ^ 1];
}

int query(int l, int r) {
    int res = 0;
    for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
        if (l & 1)
            res += seg[l++];
        if (r & 1)
            res += seg[--r];
    }
    return res;
}

Dynamic Segtree

However, say your underlying array had 1e9 possible locations, but it only contained 1e5 elements. For example, take a look at this post. Obviously, you can't store all 2e9 elements in your segtree, so what should you do? Here's one solution, replace the array with a hash table. However, as adamant mentions, unordered_map has too much overhead. We'll be benchmarking against the dynamic segtree provided here. I'll also be using a custom hash function. So to be clear, the implementation now looks like:

Code

And benchmarking it with 1e5 random insertions and 1e5 random queries.

pointer: 0.171485
unordered_map: 2.0646

Wow. The unordered_map is nearly 12x slower. That's not really feasible for a lot of contests. What if we replace it with a policy hash table, though?

Code
pointer: 0.202186
policy hash table: 0.384312

Only a 2x decrease in speed. That's already very feasible. However, one might notice that since maps in C++ create elements if you try to access a key that doesn't exist, we're creating a lot of useless elements. Thus, we can simply wrap a check to make sure the element is in the array before we try to access it

EDIT: Updated with dalex's optimization.

gp_hash_table<ll, ll, chash> seg;

ll get(ll x) { return (seg.find(x) == seg.end()) ? 0 : seg[x]; }
void modify(ll p, ll val) {
    for (seg[p += N] = val; p > 0; p >>= 1) {
        seg[p >> 1] = get(p) + get(p ^ 1);
    }
}

ll query(ll l, ll r) {
    ll res = 0;
    for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
        if (l & 1)
            res += get(l++);
        if (r & 1)
            res += get(--r);
    }
    return res;
}

Results (averaged over twenty runs):

2e5 insertions and 2e5 queries

pointer: 0.44085
policy hash table: 0.57878

1e5 insertions and 1e5 queries

pointer: 0.19855
policy hash table: 0.29467

1e4 insertions and 1e4 queries

pointer: 0.014
policy hash table: 0.027

So while we're nearly twice as slow with 1e4 elements and 1e4 queries, we're actually only 30% slower with 2e5 insertions and 2e5 queries.

One more thing. While I'm giving numbers like "30% slower", that's a little bit misleading. If we break down the numbers between insertion/querying, we see this:

2e5 insertions and 2e5 queries Queries:

pointer: 0.41625
policy hash table: 0.15627

Insertions:

pointer: 0.1367
policy hash table: 0.42619

1e4 insertions and 1e4 queries Queries:

pointer : 0.094
policy hash table: 0.007

Insertions:

pointer : 0.0045
policy hash table: 0.0191

So as we see from this more granular breakdown, the Policy Hash Table implementation is actually ~3x faster at querying than the custom implementation, while the custom implementation is roughly ~3x faster at inserting elements.

TL;DR: Using policy hash tables is an extremely easy and fairly efficient method of implementing dynamic segtrees.

Полный текст »

 
 
 
 
  • Проголосовать: нравится  
  • +77
  • Проголосовать: не нравится  

Автор randHandle, история, 7 часов назад, По-английски,

Hi, I came across this problem where you are given an array a, your task is to convert it into a non-increasing form such that we can either increment or decrement the array value by 1 in minimum changes possible.

One approach that I could think of using dp where dp[i][j] stood for minimum number of changes for first i elements if we use the largest j heights in the original array.

This approach has time complexity of O(N^2) and space complexity of O(N). But there seems to be better approach as mentioned in this blog https://www.geeksforgeeks.org/minimum-incrementdecrement-to-make-array-non-increasing/. But I was neither able to understand the approach described nor the code given.

But I checked the correctness of the code in the blog against my dp code. Both of them were producing same results. So if anyone could let me know how the O(N*log(N)) solution works that would be great.

Полный текст »

 
 
 
 
  • Проголосовать: нравится  
  • +6
  • Проголосовать: не нравится