Школьная индивидуальная олимпиада #2 (ЗКШ 2010/11) - Codeforces Beta Round #43 (ACM-ICPC Rules)

№	Пользователь	Рейтинг
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

№	Пользователь	Вклад
1	maomao90	174
2	adamant	164
2	awoo	164
4	TheScrasse	160
5	nor	159
6	maroonrk	156
7	-is-this-fft-	150
7	SecondThread	150
9	orz	146
10	pajenegod	145

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

Завтра, 5 декабря, в 11:00 по московскому времени я приглашаю всех желающих принять участие в очередном соревновании Codeforces. Оно будет одновременно являться очередной индивидуальной олимпиадой в рамках ЗКШ (подробности тут) и обычным раундом Codeforces для тех, кто не участвует в зачете ЗКШ.

Это соревнование, как и все предыдущие олимпиады ЗКШ, проводится при поддержке компаний Яндекс и ABBYY.

Совернование пройдет по правилам ACM-ICPC.

Участники, не участвующие в зачете олимпиад ЗКШ, будут отображаться в таблице результатов как участники "вне конкурса". Тем не менее, раунд будет рейтинговым для всех, а рейтинг будет посчитан в соответствии с объединенной таблицей результатов.

Авторы задач соревнования: Наталья Бондаренко и я. Благодарим Эдварда Давтяна за помощь в подготовке контеста, а также Марию Белову за перевод условий задач.

Не забудьте зарегистрироваться для участия в соревновании. Удачи на контесте!

UPD: Как только начнется соревнование, то будут доступны задачи в PDF (для печати):

UPD: Результаты соревнования. Поздавляем Геннадия Короткевича, победившего в олимпиаде ЗКШ, и Петра Митричева, победителя 43 бета-раунда.

UPD: Ссылки на разборы задач: A,C,F,G и B,D,E.

1000 12 16 100 1 16 1 52 1 55 2 3 2 2 2 1 1 97 1 53 1 29 2 9 1 2 1 91 2 8 2 12 1 35 1 92 1 62 2 15 2 11 2 7 1 14 2 16 1 93 1 67 1 97 1 33 1 98 1 23 1 60 1 66 1 8 1 87 2 32 1 62 1 45 2 25 2 23 1 29 2 29 2 38 1 34 1 71 1 24 2 31 1 21 1 77 1 67 2 26 1 6 2 30 2 24 2 46 1 77 2 28 1 13 2 21 2 35 1 6 1 100 1 10 1 56 1 37 2 62 1 52 1 70 1 95 1 14 2 64 1 91 1 68 1 72 2 41 1 76 1 29 1 86 2 43 1 82 2 45 2 60 2 65 1 58 1 44 2 27 1 1 1 57 1 70 1 87 1 16 1 1 1 58 1 85 1 58 1 22 1 13 1 81 1 57 2 58 1 22 2 93 1 41

Я вот сдал задачу G на дорешивании. И у меня возник вопрос:
Почему ответ на тест 3: Yes 1 1 2 2 3 4 проходит?
Ответ явно не самый оптимальный.

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

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

NALP	13 лет назад, # \| -17 Эвдард Давтян... :-D nice... → Ответить

AVoz	13 лет назад, # ^ \| ← Rev. 3 → +2 о таких вещах принято писать в личку... не красиво просто выглядит → Ответить

Babanin_Ivan

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

-24

Можно ли перенести олимпиаду на вечер?

→ Ответить

Nerevar

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

← Rev. 2 →

Сейчас уже нельзя ничего перенести.

-6

А следующую олимпиаду ЗКШ?

natalia

Расписание оставшихся олимпиад ЗКШ окончательное. Они не могут быть перенесены.

Connector

-18

Как считается рейтинг для участников команды?

Вопрос как минимум не в эту тему. Олимпиада индивидуальная, см. название.

Понял, извиняюсь.

Vaness

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

caustique

Согласен насчет расписания.

Я не московский школьник, а питерский студент и у нас в следующее воскресенье чемпионат СПбГУ. Кроме того, этот чемпионат совпадает с Гран-При Петергофа в Открытом кубке, так что многие не смогут написать CFBR # 45.

MikeMirzayanov

Наше расписание было утверждено и опубликовано довольно давно. При его составлении мы приняли во внимание все другие открытые соревнования, расписания которых опубликованы в сети. Относительно этапа кубка, в тот момент на официальном сайте в качестве даты значилось "11-е или 12-е декабря". Мы не можем менять время или дату контеста, который был анонсирован почти 2 месяца назад.

k-va

← Rev. 3 →

Извините, я очень внимательно отслеживаю расписание соревнований и не видел, чтобы на сайте OpenCup значилось "11-е или 12-е декабря". Первоначально было указано 5-е декабря, потом перенесено на 12-е. И 5-е декабря на OpenCup было объявлено очень давно, заведомо раньше, чем туры ЗКШ. То есть в любом случае, тур ЗКШ (2-й или 3-й) был объявлен на то же время, что и тур OpenCup. Думаю, что это все-таки накладка по вине CF, и лучше бы тур CF перенести. Или очень многих на ЗКШ и, главное, Codeforces Beta Round #45 недосчитаться...

+11

Получилось так, что Opencup был объявлен на 11:00 на 12 декабря уже после того, как на это время была объявлена олимпиада ЗКШ. Для тех, кто все-таки хочет поучаствовать в обоих соревнованиях (как я, например), есть вариант попробовать перенести Opencup на альтернативную дату.

Да, ЗКШ-олимпиады были анонсированы 2 месяца назад вместе с расписанием, но Вы не написали, что они будут совпадать с рейтинговыми CodeForces Beta Round'ами.

Вопрос не по расписанию.

Ну сколько можно проводить раунды, в которых может участвовать ТОЛЬКО второй дивизион? В чем смысл, если они участвуют везде, а первый только в некоторых? Можно ли сделать совмещенные раунды (первый отдельно, второй отдельно), в которых, к примеру, 1, 2, 3 задачи первого дива будут совпадать с 3, 4, 5 второго дива? То есть придется доделать 2 более сложных задачи. Возможны, конечно, и другие варианты.

Как на это смотрят организаторы или чем они объясняют свою любовь ко второму диву?

Alex_KPR

+19

я не организаторы, но постараюсь ответить

согласись, что сделать сложные и интересные задачи для первого дивизиона намного сложнее, чем аналогичные для второго

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

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

вот и результат :)

Да, этот комментарий очень правильно отражает ситуацию. Команда Codeforces проделывает напряженную и интенсивную работу, подготавливая три (или около того) див. 1 раунда в месяц. С другой стороны, див. 2 раунды носят значительно более учебный характер и их подготавливать заметно проще. Думаю, что начинающим участникам полезно участвовать в обоих типах раундов.

Тогда почему бы не отменить дивизионы и не проводить все контесты для всех?

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

новичку любая задача див-1 покажется невыносимым кошмаром, в то время как "бывалые" сдадут все задачи див-2 за 10-20 минут

it4.kp

+12

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

imslavko

У меня справа, в колонке написано, что осталось 4 часа
А в Контестах - 1 час.
То есть справа московское время, а в контестах -- местное? Немного путает, надеюсь Вы найдете способ сделать и там, и там местное -- будет удобно.
Thx in advance.

Нет, справа написано время до окончания регистрации. На странице /contests - до начала соревнования.

-12

Тогда я ничего не понимаю. До окончания регистрации осталось 4 часа? А до начала контеста -- 1 час? Или это регистрация на цикл контестов?

ant.ermilov

+13

Контест проводится по правилам ACM ICPC - следовательно можно регистрироваться по ходу соревнования.

Спасибо, я просто ничего в этом не понимаю. Пойду почитаю чего-нибудь

Уже заминусовали :). Выходит спрашивать нельзя или не приветствуется участниками :)

bubnov

На вашем месте я бы не задумывался о вкладе - имхо рейтинг важнее.

Старайтесь гуглить вопрос перед тем как задавать, но если найти ответ не смогли - нет ничего плохого в том что вы задаёте вопрос.

Как написано в письме - регистрация открыта все соревнование.

В связи с неточностями в условии задачи А все попытки по ней, которые получили вердикт WRONG_ANSWER, упали на 1-ом тесте и сделаны до 2010-12-05 11:30:00 не учитываются при подведении результатов.

Copymaster

В задаче E первый тест совпадает с тестом из условия?

Да, но вопросу по задачам и контесту лучше задавать из интерфейса контеста.

A.K.Goharshady

The tasks were extremely nice. Thanks

After the end of contest please provide me with test 17 of problem D.

ZumZoom

And 24, please :)

24 is a big random test

Чорт(

Totally agree with you.

Also want to know test #3 of E , that given +9 for me.

Task E, test #3:

3 3
-3 -4 2
-1 2 -1
-4 -3 0

Right answer is -11 (-5 +1 -7).

hydrastuff

а можно второй тест?

3 3
-2 1 -5
4 -5 -4
-1 1 -1

dmitrydyatlov

А мне 21-й тест =) почему-то, сколько я не смотрел, решение на нем падало только у меня...

Ой, ужас какой. А можно верный ответ к нему, а то вручную всё проверять очень долго?
UPD. ответ можно не выкладывать. я взял верный код у тех, кто задачу сдал =)

JKeeJ1e30

and test #20:)

Спасибо:)

Thanks

sabbir_yousuf

Can you please provide test 15 of problem D?

Thanks. Found my mistake.

AndreySiunov

Оч. говёно получилось с задачей А... сидел 15 минут пытался понять почему там такие выходные данные. Не приятно такую задачу так долго сдавать.
Ещё более не приятно, что решение на задаче E с cin выпадает по времени (работает минимум в 4 раза дольше чем scanf). Считаю не правильным делать такие ограничения, чтобы не проходило cin. Из-за этого 5 попыток штрафных и куча потерянного времени на вдупление "чё за лажа".

Разве в Е проходит решение за n*n*m?

Timus

с cin решение за N*M не проходит... хотя 2 * 10 ^ 6 чисел не так много, поэтому вообще не думал менять на сканф.

Ничего страшного, все приходит с опытом. 2 миллиона чисел это много. Попробуйте на своем компьютере поэкспериментировать.

Конечно нет. У меня n*m постоянно получало тл на 18. Стоило изменить cin на scanf и случился ас.

allocator

+10

Б**ть...

я после TL#18

оптимизировал память до O(n), чтоб в кэш влезло...

как можно было про cin забыть?!

Смею не согласиться. Нужно знать особенности языка.

"Считаю не правильным делать такие ограничения, чтобы не проходило cin." -- это все равно что сказать: "Считаю не правильным делать такие ограничения, чтобы значения не входили в 32 битный тип." или "Считаю не правильным делать такие ограничения, чтобы не заходило кубическое решение.".

-19

cin это C++, а scanf это C.

Rasifiel

И что? Может надо еще писать все задачи с регэкспами, чтобы они решались встроенными средствами жабы для регэкспов, а всю длинную математику, чтобы она решалась на BigInteger и т.п.
Надо знать те средства которыми пользуетесь и их скорость работы.

-16

Может ещё сделать так, чтобы можно было решать только ассемблерными вставками?

ralekseenkov

у тех кто пишет на яве тоже может случиться TL, если использовать Scanner, например.

придет с тренировками. читать данные тоже нужно эффективно :)

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

Согласен с тобой.

Я писал на Java и заюзал Scanner - получилась та же бага.

Почему я использую Scanner, хотя знаю о BufferedReader? Чтобы в коде не было кучи всяких методов, отвечающих за ввод-вывод. Сейчас это не критично, а в раундах, где возможен взлом, мне не нравится огромное количество неиспользованного кода у других участников.

taras.klaskovsky

Я считаю неправильным делать ограничения на ограничения из-за того, что сишникам лень писать scanf)

Как решать G?

появился разбор

На английском можно посмотреть здесь.

After all, I think it would be really nice if Codeforces publishes all test cases for all tasks after the contests.

scientist1642

also small editorials would not be bad.

slycelote

Why is negative result allowed in task E? It doesn't make sense. It's also sad that the solution using iostream doesn't pass the TL, because usually at CF it's OK to use iostream and some of us got used to it:)
But overall, the problems are very nice, thanks!

I was also wondering whether a negative result is allowed or not. Had to ask this question through the system before submitting.

Hackson

According to the problem statement:

"...Lara found a guidance note which said that to get hold of the treasures one has to choose some non-zero number of the first panels in each row of the table and put stones on all those panels to push them down."

Given all values in the table are negative, you are forced to choose some negative values as answer.

Yep, it's obvious. I got confused by "the maximum number of coins Lara can get" phrase though. The "number of coins" cannot be negative, assuming you treat coin as a physical object.

"Lara found a guidance note which said that to get hold of the treasures one has to choose some non-zero number"

What if I refuse to take the treasure? And how do you imagine getting a negative number of coins?

RAVEman

+21

It seems that problem G has wrong checker.

There is no way this solution could pass sys-tests (but it got AC):

scanf("%d",&n);

printf("YES\n");

int s=0;

for (int i=0;i<n;i++) {

printf("%d %d\n",i,s);

s+=i;

}

Sereja

Most likely they do not check a couple of (1, N).

Matt	13 лет назад, # ^ \| 0 Not only that YES 0 0 -2 -1 -2 -3 0 -1 YES 0 0 1 0 1 2 -1 1 YES 0 0 1 0 2 1 3 2 All of them passed the tests. → Ответить

Matt	13 лет назад, # ^ \| 0 It seems true... For the test case n=4,I've got series of different answers for that among Accepted programs. → Ответить

Yes, there was a terrible bug in the checker. Now it is fixed, and solutions that passed after the end of the contest were rejudged. Solutions that got accepted during the contest won't be rejudged.

I apologize for that, and also for the bug in the first sample in the problem A.

Thank you for that comment.

dragoon

Head was out when saw A's sample does not match but still some people managed to get AC. So waited.. then got the message to submit :( unfortunate lost 10min valuable time :(

scottai1

Could someone give me the test 6 for problem F?

Are you take into account that all doors in second night must be closed?

ahmed_aly

I did all checks, but I couldn't check if all doors are closed. How to do this?

3 3 3

1 2

2 3

3 1

a 1 1 1

b 2 1 3

c 3 1 2

b 1 1 2

c 2 1 3

a 3 1 1

Kharybin

Скажите, пожалуйста, 7 тест к задаче D.

10 1 1

1 3

1 7

-8

Рейтинг tourista уже не помещается на графике :)

Artishok

Он уже давно не помещается :-)

Запаздываете с новостями :)

Уже помещается. Ждем новых рекордов!

rng_58

We should change the upper bound of the graph for tourist :)

Check now, I've added the space for tourist growth :)

if you can add "2400" and a line along too. :)

IvayloS

I would like to know test number 14 of F. Can you please give it to me?

----edit: fixed I am sorry for being so stupid ! I really am ... trust me ;)

что может быть причиной что код скомпилировный MS VS получает AC, а GNU c++ ВА?

или как нужно не cin/cout считывать/выводить 64битное целое со знаком для gnu c++??

VArt	13 лет назад, # ^ \| 0 Попробуй scanf("%lld", &n); или scanf("%I64d", &n); Точно не помню, как именно в gnu c++ → Ответить

я спрашиваю чтобы точно знать)

Да вроде оба подходят:)

scanf("%lld",&n);

Так в gcc

Но в портированном gcc под ОС Windows, aka mingw-gcc

маска "%lld" работает весьма опосредованно, поэтому разумнее использовать "%I64d" на всех Windows.

К тому же "%I64d" придумали мелкомягкие, не будет мешать отлаживать в студии

bohuss

Where can results for Codeforces Beta Round #43 be found?
thanks

http://codeforces.com/contest/46/standings

Fcdkbear

Можно узнать тест 7 на Е?

5 5
8 -8 7 -5 0
-6 3 1 5 5
2 6 -8 -7 2
6 -8 7 0 -7
-4 -6 0 7 -6

hmelnoy

можно 9 тест на D ?

и 12 пожалуйста :-)

AntonDubovik

У меня тоже на 9ом падало. Возможно, был такого рода тест:
100 1 1
5
1 2
2 1
1 2
2 3
1 4
ответ: 0 0 0

Can you please publish input for test 28 for problem E - Comb?
thanks

Test 28 is a big random test with size 1000x2

asif_iut

how to solve problem E??

russian http://codeforces.com/blog/entry/916

Denote F(i, j) as the maximum values that you can get from row 1 up to row i and at row i, you take c_i = j. It is not hard to see that the following gives the correct value of F(i, j), for i > 1:

F(i, j) = max{F(i-1, k)} + S(i, j)

where k is ranged from 1 to j-1 if i is odd, j+1 to m otherwise.

S(i, j) = sum of values at row i, from 1^st column up to the j^th column.

If i = 1 then F(i, j) = S(i, j).

Consider i > 2 as odd row. To calculate F(i, j) you don't need to rescan F(i-1, 1) ... F(i-1, j-1) to pick the maximal value, since to calculate F(i, j-1) you have found m = max{F(i-1, k)} for 1 <= k <= j-2, then in calculating F(i, j), max{F(i-1, k)} = max(m, F(i-1, j-1)) for 1 <= k <= j - 1. Hence in O(1) time you can determine F(i, j).

For even i, you just do from decreasing j ,the trick is the same.

Hence all F(i, j) can be found in O(nm) time.

Michael_Spitzin

А в 9ом тесте задачи D должен быть ответ 0 0 0? Если да и тест именно тот который вы дали, то непонятно, почему у меня выподает ошибка, якобы у меня неправильный ответ на тесте 9.

Да, ответ такой. Сообщите номер вашей посылки.

plokzfadai

What is the test 8 for F?
Could someone post it please?

4 5 3
1 2
2 3
2 4
1 3
1 3
a 1 2 4 3
b 1 0
c 4 3 1 2 5
a 1 2 4 3
b 1 1 5
c 4 2 1 2

208356 - вот номермоей посылки. Только это номер той, которая уже после соревнования была. А номер той, которая во время соревнования была послана, я узнать не могу.

Это решение выдает на тесте 9 ответ 0 1 1, хотя правильный ответ - 0 0 0.

О этот тест я, слава Богу, одолел. А можно узнать 11ый тест, пожалуйста?

And please gimme test 25 of task B.

13 0 2 4 41
20
S
XXL
XXL
L
XXL
M
L
M
XXL
M
XXL
L
XXL
XL
M
XL
XL
L
L
M

ViktorM

Может у меня замылился взгляд, но в связи с неудачным выступлением в этом раунде и падением в рейтинге решил уточнить могу ли я сейчас снова участвовать во втором дивизионе. Так вот я облазил весь сайт и понажимал на все ссылки, но так и не сумел найти раздел где описываются правила участия в раундах, да и регламент проведения самих соревнований тоже не нашёл. Не мог бы кто-нибудь напомнить мне какая верхняя граница 2-го дивизиона - 1400 или 1500?

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

серый и зеленый - 2 дивизион. синий, желтый, красный - 1 дивизион.

Граница 1500.

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

danek_g30

Можно узнать 8 ой тест по задаче Е?

5 5
-1 0 -8 0 2
-8 4 -8 -1 3
-4 -7 6 -1 -5
-3 2 -8 -1 6
0 7 1 6 2

ysyshtc

what is the test 11 for F?

thanks

philolo1

I think i have some trivial error in E. Could you give me test case 2, please?

Thanks, my error was not in the coding, but in reading. Somehow, %lld does not work in Codeforce.

Aleksey

-13

Почему тут не обновлен компилятор GNU C++? Уже надоело получать непонятные WA 1. Просидел пол контеста пытаясь понять в чем ошибка в решении задачи D, а сейчас попробовал отправить под MS C++ и оказалось что все было верно.

g++ --version:

g++.EXE (TDM-2 mingw32) 4.4.1

This is free software; see the source for copying conditions. There is NO

warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Я не думаю, что 4.4.1 сильно устаревший компилятор.

А чем тогда объясняется такое поведение?

Kenny_HORROR

У MS C++ и GNU C++ есть некоторые различия =). В частности например могут отличаться форматы scanf, printf и некоторые другие вещи, а также поведение в местах где не документировано в стандарте C++. Пару лет назад сам очень ругался, когда полностью рабочая таска не заходила на Open Cup, на G++, в то время как на локальной машине все работало отлично (тогда перепись некоторых кусков кода на чуть более аккуратный код помогла).

lyrics

What is the test 6 for F? Thanks...

sdryapko

Дайте пожалуйста 11 тест на D

AVoz	13 лет назад, # ^ \| ← Rev. 2 → 0 и 23-ий пожалуйста → Ответить

Just to make sure you know:

Links for tutorials B,D,E is not correct

The url is http://codeforces.com/blog/entry/edit/916, delete the "edit/", http://codeforces.com/blog/entry/916 is useable.

Thanks.

Мелочь, но место в всплывающем окошке в профиле на первой личной олимпиаде ЗКШ показывается среди школьников, а на второй среди всех.