Educational Codeforces Round 6

№	Пользователь	Рейтинг
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

Привет, Codeforces!

21 января 2016 года в 18:00 MSK состоится шестой учебный раунд Educational Codeforces Round 6 для участников из первого и второго дивизионов.

<Здесь могла быть ваша реклама>

О формате и деталях проведения учебных раундов я писал уже ранее. Также об учебных раундах вы можете прочитать здесь.

Раунд будет нерейтинговым. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. На решение задач у вас будет два часа. После окончания раунда будет период времени длительностью в один день, в течение которых вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования. Таким образом вы можете локально тестировать решение, которое хотите взломать, или, например, запустить стресс-тест.

Если у вас есть идеи каких-то задач, которые вам кажутся интересными, или может есть уже что-то почти готовое, что вы по каким-то причинам не можете дать на раунд (злой координатор сказал, что задача БАЯН), официальное соревнование (жюри не хочет переграбливать соревнование), можете писать мне.

</Здесь могла быть ваша реклама>

Большое спасибо Aleksa Plavsic allllekssssa, который предложил несколько отличных задач, две из них вы увидите на раунде (задачи D и F). Также большое пользователям Bayram Berdiyev bayram, Allanur Shiriyev Allanur, Bekmyrat Atayev Bekmyrat.A, они совместно (через Aleksa Plavsic) предложили несколько задач. Две из них вы увидите на раунде (задачи B и E).

Подготовкой задач как всегда занимался я (Эдвард Давтян). Благодарю MikeMirzayanov мы вместе придумывали задачи A и C. Спасибо Маше Беловой Delinur за проверку английских текстов условий. Также большое спасибо Aleksa Plavsic allllekssssa, который тестировал задачи и постоянно был на связи.

На этом раунде вам по традиции будет предложено шесть задач. Первая задача в этот раз проще, чем обычно (я надеюсь на очень быстрые сабмиты по ней от вас), а последняя, на мой взгляд, очень сложная (респект участникам, которые смогут её сдать). Надеюсь комплект задач вам понравится и вы хорошо их порешаете!

Good luck and have fun!

UPD 1: Забыл поблагодарить всех ребят, которые мне уже прислали идеи задач, но мы их ещё не взяли в раунд. Я постараюсь поскорее их дать.

UPD 2: Основная часть соревнования закончилась. Фаза открытых взломов открыта.

UPD 3: Разбор задач готов.

UPD 4: Соревнование закончено, результаты окончательные.

extern int abs (int __x) throw () __attribute__ ((__const__)) ; extern long int labs (long int __x) throw () __attribute__ ((__const__)) ; -- __extension__ extern long long int llabs (long long int __x) -- using ::getenv; using ::labs; -- inline long abs(long __i) { return __builtin_labs(__i); } -- inline long long abs(long long __x) { return __builtin_llabs (__x); } -- using ::llabs; -- using ::__gnu_cxx::llabs;

Комментарии (73)

Показать архивные | Написать комментарий?

allllekssssa

9 лет назад, # |

← Rev. 2 →

+27

Thanks Edvard for mentioning my friends and me. I'll really tried to give good and interesting tasks for contest. Possible you will see more our tasks in future rounds, that doesn't depend on me :)

Enjoy in contest, as always I am glad to hear comments and suggestions after round.

→ Ответить

akvasha

-20

Waiting for tourist with AC on last problem in 10 minutes.

9 лет назад, # ^ |

← Rev. 3 →

+25

I think no man on the world who can solve last task in 10 minutes :P

EDIT: Congratulation to tourist, he is incredible! But I am not counting his solution as regular :P

I can promise that he won't solve the hardest task in 10 minutes on my next round ( normally if he works it :D ).

GoToCoding

← Rev. 4 →

tourist isn't a man, he's a SuperMan

AClover

+21

Good tactic to invite tourist to contest :)

step_by_step

+14

It took only 7 minutes for tourist to solve the last problem(judging by his submissions)

Mr.Awesome

+56

Actually he was able to solve the last one (problem F) in 7 minute .

egor.okhterov

-12

We don't know it yet. It could be a hackable solution :)

crim

-91

These contests are sucks.

utku_mert

+59

You mean this

Lo_R_D

Первая задача в этот раз проще, чем обычно (я надеюсь на очень быстрые сабмиты по ней от вас)

Быстрее, чем 1-2 минуты? Или имеется ввиду среднее время сдачи задачи от всех участников?

Edvard

+13

Хочется более быстрого среднего времени, а также большее количество Accepted-ов.

Я был прав. First accepted на 43й секунде :-)

Beresta

Всегда удивляюсь как люди умудряются так быстро сдавать даже тривиальные задачки, у меня цикл прочитать_условие — создать_проект — набить_код — проверить_тестовые_примеры гарантированно больше времени занимает )

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

Сразу набивают на сайте, ничего не проверяя?

MrDindows

Проект создал заренее. Условие проглянул дважды. Код не запускал и не тестировал. Сдал на 52й секунде.

Kerim.K

-21

I think it is first Turkmen contest.Good luck to everyone!And thanks to contest all problemsetters.

accidentallygivenfuck

-6

Ahahaha minus yagdyrayypdyrlaraooooow. allllekssssa-nam Turkmen edayipsina.

nikitaodnorob2

+23

Эх, третий раз подряд уже пропускаю эти раунды из-за дополнительных занятий :( Всем Accepted'ов ! :)

И вопрос к Администрации — может проводить какие-нибудь соревнования по выходным? Можно простенькие, чтоб мозги в форме поддерживать, так сказать :)

Khina

-24

На 44 минуте tourist-y уже был готов к фазе взломов!

I_love_Captain_America

So, D is solvable by binary search right?

SarvagyaAgarwal

+19

Maybe you can if instead of wasting time in writing comments , you make the changes :)

I am tired. Only the fact that I figured how to solve D kept me going. Now I'm watching youtube :) Commenting takes literally 1-2 minutes.

nikitosoleil

Am I the only who have passed pretests in B using 7-dimensional array? :D

+30

Unfortunately we gave bad constraints to the problem F. As a result some participants solved the problem in O(n²). In spite of this some participants solved the problem with better complexity. The author solution works in $\text{[math]}$ time.

К сожалению в задаче F мы неудачно поставили ограничения и поэтому некоторые участники сдали решение за O(n²). Несмотря на это среди решений есть решения асимптотически более быстрые, но работающие примерно столько же. Авторское решение работает за $\text{[math]}$ .

Egor

Even author solution runtime does not explain such strange difference between limits on n and m.

+10

Actually the hidden constants for m and n is different.

Sorry, I didn't answer before I had some other obligations.

I am setter of fourth and sixth task. The number of good submissions (till now) is great and I think this round is really good for education..

I only suggested tasks, with official solutions, so I didn't decide about final constrains for numbers and time limits. In my version(when I sent task) constrains were :

n<=10^5 m<=10^4 Ai<=10^12

And my estimation was that 5 seconds enough, but it is changed. Edvard is better programmer with more experience, so I beleive in his decision (and possible it is better to have more correct submissions — 8 good solutions in two hour aren't a lot of).

I hope you enjoyed in tasks and spent 2 great hours. See you on some other round, any suggestion and opinion about tasks will be helpful.

aid

Так вот как её за 7 минут сдавать. Обидно :(

-13

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

Nice contest overall! Russian statements was very clear, except maybe a bit lack of comments on math, like that (+) operation in F is XOR :) I know that, but I also know a lot of people who wouldn't figure out what operation it is. And they can't google for it I guess — hard to write search engine request.

The only flaw I see is difficulty gap between C and DEF. But it is probably very personal thing.

+31

Problem title can help with this

Haha, nice. Well I haven't read problem title until this moment :D

Anyway, I'm kinda used to get such comments in statement, because they are often presented in regular contests (even easily googled ones like what is tree, what is subtree, etc).

I actually get to the clarification writing interface just to be sure, but when I selected problem I had to read the title

coder_in_use

Что за идея в задаче D?

Разбор по первым четырём задачам на русском языке уже опубликован.

Я решил так:

Сначала посчитал все возможные дельты за один ход (макс 4 * 10^6).

Отсортировал их по возрастанию.

Дальше в цикле прошел по каждой и бин поиском нашел парную ей такую, что бы суммарно они давали как можно ближний к 0 результат.

Ну и дальше цикл в обе стороны от нее в поиске подходящей, у которой позиции обмена отличаются от первой дальты (которая в основном цикле зафиксирована), потому что мы не можем совершить две операции обмена с одной позицией.

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

the_art_of_war

я сделал тоже самое только после бинпоиска я проходил на один элемент вверх и на один элемент вниз. Этого было достаточно

Нууууу, следующие элементы вверх и вниз легко могут оказаться с той же позицией обмена, что и первая дельта. Я проходил по сути до первого элемента в каждую сторону, в котором d2.I != d1.I && d2.J != d1.J.

inactive06

+16

Everyone is trying so hard to hack tourist on problem A. well , my friendly advice to those desperate souls: "let it go, my fellow coders. Sad but truth is tourist can solve easy problems too beside hard ones"

+48

Мой код: 15483583 tourist'a код: 15470173 Где в мире справедливость?

abs из cmath возвращает double, abs из cstdlib возвращает int.

izban

-9

В cstdlib вроде нет abs-a, причина скорее в algorithm.

Есть: ссылка. А ещё есть labs и llabs для long и long long соответственно. А вот про abs из algorithm я впервые слышу.

Да, с abs-ом я наврал.

Zharaskhan

15484104

Compiler GNU C++ WA, GNU C++11 AC.

Интересно

soon

Стандарт C++ не гарантирует, какие заголовочные файлы будут использованы при реализации STL. Похоже, что реализация iostream начиная с версии С++11 от g++ включает в себя stdlib.h, и именно поэтому находится перегрузка long abs(long) вместо double abs(long). Я могу это подтвердить на своей локальной машине, но на онлайн компиляторе не получилось.

Поиграть с заголовочниками и настройками можно тут: Coliru live.

Проверить локально можно с помощью следующего кода:

#include <cmath>
#include <iostream>

int main()
{

}

Строка компиляции:

$ g++ main.cpp --std=c++03 -E -o main.cpp.p && grep labs main.cpp.p -B 1

Выхлоп на c++03 у меня пустой. Выхлоп на c++11 следующий:

Что подтверждает наличие перегрузки

3_question

I think i could not understand problem C properly. In the test case 5 2 2 3 3 3 will 3-5 be a good segment? if yes, then can a good segment contain more than two pearls of same kind, also two pearls each of two different kind?

Yes, and yes, and yes.

uhh i totally misunderstood the question. Got it accepted easily now. thanks!

bhishma

Can someone share their approach for problem D

NYU

Will the editorial be post after the end of hacking phase?

mm_kishor

how to solve D?

I used the fact that after 1 change, answer is the minimum of absolute value of

sumA-sumB-2*a[i]+2*b[i]

to use binary search on b[] for closest value to (sumA-sumB-2*a[i])/2. Similarly, for making 2 swaps, you can make to arrays c[] and d[] where c has sum of pairs of elements of a[], and d has sum of pairs of b[]. Then, for each element in c[], binary search in d[]. This step has complexity n^2 log(m^2)

vsp4

Tried similar thing, looks like tle on test 13: http://codeforces.me/contest/620/submission/15485606

Feras.Kastantin

me too, and i don't know why...

I just read editorial. Instead of storing pairs for both arrays in a map, just store for one and directly use the other from the loop. This leads to AC now

Maybe map has huge constants. Why not use a static array of size n^2 ?

http://codeforces.me/blog/Edvard

Hmm, my approach seems correct :)

tweety

The second problem is very annoying. Otherwise very good and interesting problemset.

dush1729

I like how you wrote

while (x)
            ans += ar[x%10], x /= 10;

Didn't knew we could do that!

Hm, interesting. I've submitted two AC solutions to D. Second one was a bit more optimized. And now first one got hacked. And I got penalty as if I made one WA submission before.

Feels fair, but didn't expected such thing :)

So basically I can submit as many AC as I want, and the first one which won't be hacked will be considered as accepted solution, right? And how about hacked ones? Will I get penalty for every one or how else it works?

anh1l1ator

In problem E , Why am I getting a RTE on test 51 . I am using Segment Tree on Time Stamps 15485066

Moreover what is the stack limit on Code Forces? Might be recursion is causing stack overflow ..

tantam75

I got that problem too. You might use 2d arrays for the trees (i guess). Try using 1d arrays. I tried then time limited :D

carlotheboss

During the contest i solved B casting every integer in the range [a, b] into a string (using std::to_string()) and then iterating the string with a range based for, and I got TLE (code here).

Then I removed the std::string conversion and did the same thing extracting every digit from the number, using the same complexity [ O(b — a) ], and got AC in 15 ms (code here).

Now on my pc the first solution, with the 1 1000000 tc, works in 130ms while the second one takes 40ms (I haven't got any kind of supercomputer or quantum computer and I compile with the same flags of Codeforces (C++11)). Now the question is: does codeforces hate std::string? is std::to_string() very very slow?

I got 3 TLEs for this :(

+36

I wish to say few more things about tasks and whole contest till now.

First I hope you find something interesting in problemset or at least you don't hate tasks :)

This was my help to codeforces, I do this only because of the passion for programming ( and I don't have girlfriend to spend time on it :D ).

I hope to see your problems on the following educational rounds, Edvard is great guy he finished good part of preparation and certainly he would help to new problemsetters. Also I'm always here for any help and question for anything needed.

Diego1149

I liked the contest, F was a though one :)

kfx

In problem C:

a submission with unordered_map fails with TL: 15496737
a submission with map gets AC (only one line of code changed!): 15496747
a submission with unordered_map and custom hash function: AC again! 15497036. Bit slower compared to map, anyway.

What exactly is test 42? Looks like someone went through the trouble to generated an extremely bad test case input that causes huge number of collisions in that specific G++ implementation of unordered map. In my opinion, it's a bit against the spirit of the competition ;)

sgtlaugh

+11

Against the spirit of the competition? Come on, it's just an unrated competition and also it's called an educational round ;) how so?

sidak

Hi kfx and sgtlaugh,

Can you please explain how having huge number of collisions give TLE? Shouldn't it give a Wrong Answer instead?

And also can you please explain how would one generate such a test case programmatically.

(My solution also got hacked due to the same reason)

Thanks a lot! :)

Goran1

← Rev. 5 →

Now when the hacking is finished I want to ask something. On the A problem I found a solution with O(n) complexity, e.g. there was iterating from 10^9 to -10^9. I tried to hack it using x1=10^9 and x2=-10^9 and the hacking attempt was unsuccessful. However, on my laptop it run more than 2s and the limit is 0.5s. Is the limit actually higher or am I missing something?

Thanks.

Codeforces servers are very fast. Did you compile with optimization options like -o2 etc.?

Блог пользователя Edvard