Всем привет!
Совсем скоро, 5 мая в 19:30 MSK состоится Codeforces Round #182, автором которого являюсь я. Это мой шестой раунд на Codeforces и я надеюсь, что не последний.
Спасибо Геральду Агапову (Gerald) и Диме Соболеву(sdya) за помощь в подготовке раунда и Марии Беловой (Delinur) за перевод условий на английский.
Настоятельно рекомендую прочитать условия ВСЕХ задач.
Gl & hf ! :)
По техническим причинам начало соревнования было сорвано. Приносим извинения, контест будет НЕРЕЙТИНГОВЫМ.
Долгожданный контест от Sereja. Надеюсь задачи будут как всегда интересными.
Очень ждал раунд КФ и обрадовался когда увидел, что дает его Сергей)
Так сильно ждал, что аж не принял в нём участие...
Даешь регулярные Sereja-раунды каждый месяц на Codeforces!
Самому слабо?
Старый-престарый мем. Лучше использовать английский вариант "We got a badass over here". А этот парень черный здесь ни к чем
Upd А лучше вообще не использовать, а то CF превратиться в сборник веселых картинок.
Zlobober готовил раунды (Beta Round #73 например)
-87. Рекорд?
http://mirror.codeforces.com/blog/entry/6450#comment-118782
http://mirror.codeforces.com/blog/entry/2031#comment-39850
http://mirror.codeforces.com/blog/entry/4543#comment-92412
http://mirror.codeforces.com/blog/entry/3649#comment-74074
http://mirror.codeforces.com/blog/entry/2384#comment-50251
http://mirror.codeforces.com/blog/entry/3126#comment-63105
http://mirror.codeforces.com/blog/entry/3126#comment-63104
http://mirror.codeforces.com/blog/entry/7361#comment-130156
http://mirror.codeforces.com/blog/entry/4708#comment-96028
http://mirror.codeforces.com/blog/entry/2112#comment-42252
Я очень удивлен, но из всех этих комментариев лишь один мой.
CodeForces -> Codeforces
Сделано, мой капитан.
Не могу не отметить "удачный" выбор дня для контеста.
Чем же он неудачный?
Пасха
А что, нельзя на пасху контесты писать?
Большинство уедет к родственникам.
Тебе ли не знать :)
Можно, но людям с кривыми руками, вроде меня, придётся сдерживаться в выражениях весь контест.
Если бы это решал я, то сделал бы завтра в 10-12 дня. В СНГ у всех выходной, и азиаты смогут писать. На Америку можно забить, оттуда участников очень мало. Ну и как уже отметили, немалая часть людей из того же СНГ может быть занята сегодня.
Какие минусы у моего варианта?
1 Минус : "На США можно забить". :D
Не понял шутку.
Не обращай внимания. Он часто так шутит.
Так-то в РФ завтра рабочий день.
Всех православных с пасхой, кстати. В Исламе не запрещает писать контест в религиозных праздниках, что тут плохого?
Просто многие в праздник празднуют. Почему на Новый Год контест не сделали?
Потому что новый год все празднуют, а пасху очень мало кто.
Все с вами понятно, ребята.
Сделали, но не здесь.
求轻虐！！！！！！
什么宝宝？
将加:)
А какая разбалловка?
Any info. about the score calculating rules? As usual?
I believe this will be a very level of the game!
all your round announcement posts look like the same :D
but i think problems are different :)
Can you tell me what about the score ? dynamic or 500-1500-1500-2000-2500 ?
Кто-нибудь знает какая будет разбалловка?
Какая разница? Решай всё, что можешь.
Good look to everyone! :)
hope my friends and i can reach blue= =
yes sir in the next contest.
It is easter in the ortodoxal world. I hope a wonder happen and everything with the contest will be OK.
жаль что на 10 минут позже начнется (
а почему перенесли начало на 10 минут?
Мне кажется, пора вносить информацию о разбалловке при создании поста. Например, "динамическая". Или "будет объявлено в момент начала раунда". Или "мы объявим за минуту до начала". Или "придумаем на втором часу контеста". Полагаю, многих достали повторяющиеся комментарии, а некоторым участникам действительно интересно.
looks like the contest is delayed 10 minutes
May be system is experiencing some load. Request are getting timed out.
hope today's sever will be stable
Удачи всем кто лайкнит меня.
Нехорошо так лайки выпрашивать :-)
Думаю, стоит сделать раунд нерейтинговым. 2 минуты назад у меня в одной вкладке контест шел, а в другой шел отсчет (2 минуты) -> есть вероятность того, что кто-то успел прочитать условия за этот промежуток времени.
Когда-то администрация(Gerald) говорила, что может смотреть логи и узнать, кто видел условия.
Yestody, GCJ, Have your score arrived 22.
Сервер воскрес!
Воистину воскресе?
А, не. Показалось. Расходимся.
Не накаркай :(
Скорее уж таймер воскрес. Уже в третий раз.
Hope Codeforces can fixt it .. the server cant breathe right nw :O
WTF IS THAT?!
The contest opened while the server was down and some people managed to get the problem statements!
THIS IS COMPLETELY UNFAIR!!
How you know that ?
One of my friends already sent me the statement for problem A
Problem A. Eugeny and Array
That's sad :-/
, Problem A. Eugeny and Array Input le: stdin Output le: stdout Time limit: 2 seconds Memory limit: 256 megabytes Eugeny has array a = a1; a2; : : : ; an, consisting of n integers. Each integer ai equals to -1, or to 1. Also, he has m queries:
What the....
If this is true, the contest need to be cancelled definitely. Please announce about the situation and stop wasting competitor's time.
..
Will the contest be rated? At some moment, contest once started.
Поставь лайк если ты красный.
Are you sure, you want to continue this contest ?
Походу раунд начнется тогда, когда половине надоест ждать и нагрузка упадет.
Sereja strongly recommends you to read ALL the problems. I strongly recommend you to open ALL the problems :))
its getting late 35 min wasted time yet.
it's really unbearable !!!!!!!1
waste a lot of time
the contest is not started yet
Why 502 Bad Gateway ？？？
Contest gonna start today???
Кстати, как-то не очень хорошо получается, так как я, скажем, смог загрузить условие задачи А див 2, в виде ПДФки. Конечно, это не особо важно, но, все же...
UPD: выше уже написали, опоздал
Ну вот зачем это было делать? Спойлерить таким образом условия — это просто идиотский поступок.
Возможно, если бы не этот идиотский шаг, раунд ещё можно было бы сделать рейтинговым (как случилось недавно при схожих обстоятельствах на квалификации на КРОК).
Ну, можно считать, что с таким скриншотом все в более равных условиях...
При отсутствии таких скриншотов есть надежда, что контест будет рейтинговым...
А по-моему, должно быть почти всё равно, а с точки зрения участника так даже лучше. Всё равно как минимум один участник увидел задачи до того момента, которое в итоге оказалось стартом контеста. Ну вот увидел, поучаствовал. При этом он мог и не заметить, что начало контеста сдвинулось — весьма вероятно, что во время этих сдвигов он решал задачу A.
Какое решение можно принять, если такой участник ровно один? Сделать контест рейтинговым для всех, кроме него? Это нечестно по отношению к нему. К тому же он мог распространить условия по частным каналам, и опять же это не повод его банить.
А если скриншот с условием задачи A висит в треде, это сближает шансы тех, кто успел увидеть задачи, и тех, кто не успел. Хотя и вносит дополнительный элемент случайности.
Да ты что? Этот скриншот наоборот заведомо делает ставит всех в неравные условия — далеко не все, ожидая, пока сервер взлетит, читают пост с анонсом. А вот если бы его не было, то у раунда ещё есть шансы на рейтинговость. Можно почитать логи, посмотреть, кто успел прочитать условие, оценить время доступности и из этого сделать выводы о рейтинговости.
А этот скриншот никакого равноправия не добавляет — это одна проспойлеренная первая задача из Div2. Абсолютно бессмысленной поступок.
Лол. Абсолютно бессмысленно ругать чувака, который не сделал ничего плохого. Разве он виноват в том, что ему досталось условие до начала контеста? Ни разу. Рейтинговым будет следующий контест, будьте спокойнее)
Он мог не сливать его и не участвовать в контесте. Или участвовать, но потом его бы отсеяли по логам, как уже заметили выше.
Получается так: участник слишком часто нажимал F5, и из-за ошибки жюри увидел задачи на пять минут раньше. При этом он честно считает, что контест начался, и начинает писать решение. А в конце соревнования оказывается, что для него оно не рейтинговое.
Мне не нравится такой подход, так как при этом конкретный участник, не нарушивший правила, страдает из-за ошибки жюри.
Может быть, в какой-то конкретной ситуации «посмотреть, кто успел прочитать условие» и сделать вывод — это и хороший метод, но в общем случае он ставит участников в ещё более неравные условия.
Ты предлагаешь, например, если все участники, которые по логам увидели условие, заняли места начиная с 101-го, оставить контест рейтинговым? А если они есть в первой десятке, то нет? Тогда это и есть неравные условия: увидев задачу не вовремя, ты не имеешь права выступить слишком хорошо.
К тому же, опять же, условия могли растечься по приватным каналам.
Ещё аргументы за скриншот — выше.
Я не то чтобы настаиваю, что так всегда надо делать. Я хочу показать, что аргументы за, как минимум, есть.
А это было бы прямое нарушение правил ресурса, разве нет?
Не уверен, скорее нет. Какого именно правила? Мне кажется, передать условие в неприкосновенном виде и без комментариев тем, у кого сервер недоступен — примерно то же самое, что поделиться доступом в интернет в месте, где с ним туго. Второе — явно не нарушение правил, я несколько раз в таком участвовал с обеих сторон.
Другое дело, что, если дошло до массовой необходимости такой передачи (как сегодня) — возможно, раунд действительно пора делать нерейтинговым, если сомневаться в добросовестности этой передачи.
А как считает администрация?
Тогда получается, что я эти правила нарушал уже, даже и не раз. Я бывал и в роли принимающего, и в роли отправляющего. Можно конкретную ссылку на такие правила? Я знаю только, что нельзя обсуждать задачи, но распространение оригинальных условий — это разве обсуждение?
На том же 2 раунде КРОК меня за время контеста выручили целых 2 раза — сначала когда я забыл о волшебном правиле "открывайте все задачи сразу" и не мог открыть вторую, а потом — когда случайно обновил страницу с третьей.
Ты исходишь из тезиса "если хотя бы один человек прочёл условия до начала контеста, то контест должен быть нерейтинговый: иначе это точно будет по отношению к кому-нибудь несправедливо".
Я исхожу из тезиса, что если есть десять человек, прочитавших условия, то этим десяти людям можно сделать раунд нерейтинговым, а остальным — рейтинговым. Смотри: у них так или иначе раунд должен быть нерейтинговый, у остальных же двух тысяч человек — не факт. Да, это обидно, но мне кажется, делать остальным двум тысячам людей раунд нерейтинговым — слишком мощно для того, чтобы сгладить чувство обиды у этих десяти людей. Ну не сложилось, ну бывает. Но у тебя раунд так или иначе будет анрейтед, зачем другим-то портить?
Шаг товарища выше в моём видении мира совершенно ничем не обусловлен и лишь повышает энтропию того безобразия, которое творилось в начале контеста. Возможно, без него можно было бы посчитать раунд рейтинговым, а так — заведомо нельзя.
А насчёт приватных каналов — ну уж вероятность этого крайне мала — она соизмеримо с вероятностью того, что кто-то обсуждает по этим же приватным каналам задачи, или крутые примеры для взломов.
В этом подходе мне не нравится ловушка для участников, которая из «повезло» делает «не повезло». Вот я обновляю страницу, и мне доступны условия. Теперь, если я не заметил, что начало контеста перенесли, то автоматически не пишу контест в рейтинг. А если заметил — я могу что-то сделать, чтобы остаться рейтинговым участником? Закрыть вкладку, написать письмо администрации, предъявить скриншот?..
Мне в такой ситуации больше нравится идея выбрать между «контест рейтинговый для всех», если администрация считает, что эти пять минут преимущества не сильно влияют на результат, и «контест не рейтинговый для всех» в противном случае. Возможно, какие-то сдвиги баллов за задачи для тех, кто по логам раньше открыл задачи, при этом неплохо бы об этом объявить как можно раньше.
Ну был ещё один, наверно технически сложный вариант — рассчитывать время сдачи для этих участников отдельно.
Ну да, просто прибавить сколько-то минут к каждому времени сдачи, я это и имею в виду под сдвигом баллов.
Задача А див2 — обычно очень простая и служит для того, чтобы ранжировать людей внизу таблицы. Весь прикол в том, что для участников, быстро ее решающих, она практически ни на что не влияет, потому что он борется за места с 2-5 задачами, и чтобы он не решил А — это нонсенс. То есть: возьмем двух человек: для одного задача практически ни на что не влияет, второй итак решает ее порядка 40-120 минут. Контест вполне можно было сделать рейтинговым. Но этого не произошло. И в этом виноват явно не парень, выложивший условие задачи А. Естественно, беря во внимание, что контест среднестатистический, а оный сегодня как раз и был. Я имею в виду сложность, а не интересность.
Я бы адресовала этот вопрос тем, кто проводит контест. В див. 1 тоже несколько сдач задачи A в 0:00.
Ну, во-первых, как правильно сказали ниже, условие задачи Аdiv2 мало на что влияет. Выложил же для того, чтобы все были так или иначе в равных условиях. Думаю, не у меня одного такое произошло и, судя по сабмитам в 0.00, это произошло у большого числа людей. И уж вряд ли сделали бы его рейтинговым
Now I have missed my lunch because of this....
If this round will be unrated, please tell us before the contest end.
"Oops! This link appears to be broken"
"502 Bad Gateway"
"504 Gateway Time-out"
"Sorry, the server is too busy at the moment. Please try again later."
For 15 minutes these were the only problems I could see!
Hope system can be fixed as soon as possible. It's hard to not get the request of "502 bad gateway"...
If this round will be unrated, please tell us before the contest end.
5 минут, 5 минут, а потом еще и еще нельзя, наверное, сегодня работать ...
**Server Problem !!!!****Bad Gateway**Hope it'll be OK soon... :/Already 00:05 ! (East Asia)
The server problems are getting really annoying!!! at least could someone explain why the server is down lately??
Похоже, действительно раунд лучше сделать нерейнтиговым. Люди, сдающие задачу на первой минуте это подозрительно.
LOL, they all had the problem statements and the code ready before the contest begins
good that the contest is unrated.
может все-таки сделать нерейтинговым только для тех, кто раньше увидел задачи?
Этого никак не определить.
Даже если узнать каким-то образом, кто увидел их в интерфейсе сайта, а кто нет, то остаются еще варианты в стиле "о, у меня открылось, я сейчас тебе на почту сброшу".
да, осознал. ну, будем решать ради удовольствия :)
thank you for letting us know that the contest will be unrated.
waiting 35 minutes... and... unrated...
Sorry about the contest start. It was my fault: the main reason is — it was a non-production copy of Codeforces deployed before the contest (some experimental code + experimantal JVM settings + enabled profiler). Somehow the production copy was unable to start because of many requests :( It was started after some time, but it was passed about 0.5 hour and it was a moment of contests was started (so some users were read the problems).
The contest is unrated. I'm sorry about it. I hope you will like nice problems by Sereja.
===
Приношу свои извинения в связи со срывом старта контеста. Это по моей вине, основная причина — был запущен не-production вариант Codeforces (с некоторым экспериментальным кодом + с экспериментальными опциями в JVM + под профайлером). Почему-то production-сборка не смогла сразу запуститься под написком потока запросов :( Когда она была запущена (примерно через полчаса), был момент когда контест был доступен и некоторые из вас уже прочли задачи.
Контест будет нерейтинговым. Еще раз приношу извинения. Я надеюсь, вам понравятся красивые задачи от Sereja и вы получите удовольствие от их решения.
... The author is innocent ... We shouldn't blame on him. ... Sereja, Thanks for your work and problems.
PS: I wonder on this particular issue, does Codeforces will pay for the problemset? Does the author will write the Editorial as well as it been rated?
For sure we will pay to the writer.
AC fun girl lol
Problem C, Do the n elements for which we can change the sign needs to be consecutive ?
No. It's not necessary for n elements to be consecutive!
Something is definitely wrong with new Python 3 interpreter. Sorry for spoiling before the end of the contest, but anyway it's unrated.
So I feel I'm clever enough to make a solution for problem A, but it has TL on test 11. I do some stupid things sometimes so I checked here: http://mirror.codeforces.com/contest/302/status and everyone fails on test #11 (no one solved it using python 3). The problem could be in reading input data, but it's not as big (10**5).
Also after direct translating my code to python 2 it was accepted, so I think something has to be repaired here.
It is true (at least for me) that CPython 3 is sometimes slower than CPython 2.
I wonder if Codeforces could implement support for PyPy?
Python 3 can be slower, but if it fails on this example what will be on examples with bigger inputs? I waited py3 really for a long a time, but in my opinion it's better to disable it in this state.
It would be good if admins add PyPy but the problem is that it's implemented, again, only for python 2
I tried Div2 A and B with Go language but both solutions got TLE in pretests. (my solutions: 3675888, 3676731) I feel more optimization is needed for those new languages.
It's strange that solution both in python 3 and Go fail exactly on test #11. I hardly believe they are equally slow.
I tried to run it localy. The result is "time consumed: 2.81 sec". Note, my laptop is much faster than judging machines. It seems IO in Go is a bottleneck.
I also ran it locally and it took 8.1 seconds... looks like the judge was correct and I should use faster IO functions if any. Thank you for pointing it out.
Right, Python 3 is slower than Python 2 in many cases. For example, on my laptop (i7, much faster than judging machines) you solutions work (on the test 11):
Also PyPy works not faster than Python 2:
I believe Python team should "repair" Python 3 to work faster. On the other hand you should know and understand pros and cons of the language.
Another conclusion that PyPy is not a silver bullet, this problem shows again that it doesn't work faster than CPython 2.
no need to complain about unrated contest, just practice in this contest, after all, this contest isn't offering any prize
the important thing is you doing well in that kind of contest, and this codeforces round is one thing to do to achieve that, higher rating doesnt mean always win
http://mirror.codeforces.com/contest/302/status/A/page/24?order=BY_ARRIVED_DESC за 11 секунд прочитать и закодить даже А это круто)
Насчет задачи A под Python 3 — так и есть, оптимизировал все что можно, но 11 тест не проходил по времени. Если бы не увидел комментарий про это, может быть, и не догадался бы адаптировать для Python 2.
Очень интересные задачи, особенно С(div 2)/A(div 1), еле добил :) Жаль что контест не рейтинговый, поднялся бы)
Div 1 C / Div 2 E Yaroslav and Algorithm is very interesting! Anyway thanks for the great questions by the author!
Спасибо за задачу Div1-C, это классно!
Я тоже очень пропёрся. Никогда бы не подумал, что встречу тут алгоритмы Маркова, упражнениями на которые меня гоняли на первом курсе.
Отличные задачи. Не понравилось странное ограничение в B, из-за которого людям приходится участвовать в соревновании на внимательность. E — красивая динамика, не успел дописать. D — подумать и свести к стандартному "сколько точек в прямоугольнике". С — быстро придумал, нужно забить на входные данные и активно пользоваться вопросами. A — больше всего думал, даже смешно. Никак общий алгоритм не мог осознать, в результате получилось, что от четности зависит его существование:) Спасибо за контест. Жаль, что система превратила его в нерейтинговый.
А какую роль играли символы '?' в задаче Div1-C/Div2-E?
Это символ не являющийся цифрой.
У меня в Е какая-то жесть с динамикой по вектору, которую я минут 30 пытался упихать в ТЛ и на последней минуте соптимайзил до 2.8 на макстесте. Причем она на студии работала в 2 раза быстрее, чем в GCC. У тебя тоже что-то такое или нормальная идея?
У меня печаль. Я дописал n^8. Я умею превращать это в n^5logn / много. Теперь оно не только получает WA, но еще я не понимаю, как это упихивать. Мой компьютер не может дать мне точного ответа, зайдет ли это в ТЛ.) За сколько у тебя алгоритм асимптотически?
Авторское было за O(n^5). Сейчас его в разбор допишу.
Сделано.
Теперь я уже понял, что асимптотика у меня O(N6) (может меньше, но тогда я не знаю почему это так). У меня параметры — это количество поставленных чисел, максимальное поставленное число, а также вектор чисел W, в котором для каждого i от 1 до 50 хранится количество способов переставить данный массив таким образом, чтобы у нас было ровно i пар максимальных чисел, стоящих подряд. Переход делается за квадрат, но с кучей отсечений.
What a pity! It was a very interesting problem set. Thanks Sereja
В С у авторов есть решение, существенно пользующееся input'ом?
Инпут был только для того, что бы показать, как будет тестироваться алгоритм. Но у меня есть идеи, как избавиться от знаков вопроса используя инпут.
О, а я только сейчас прочитал, что бывают знаки вопроса...
Знак вопроса равен любому символу или не равен ничему, кроме себя? По условию получается, что это просто отдельный символ, а не wildcard. Но тогда почему не был выбран какой-нибудь другой символ, не имеющий wildcard-смысла?
Я надеялся, что это будет понятно, ведь в условии ничего не сказано про то, что это универсальный символ...
Формально это верно. Но обычно при сравнении строк вопрос выбирается как что-то, равное чему угодно, поэтому у меня возник закономерный вопрос "а не забыл ли автор написать про это в условии". К сожалению, возник не сразу.
ИМХО, лучше было бы выбрать какой-нибудь символ, не нагруженный смыслом в контексте сравнения строк. Например,
!или просто какую-нибудь букву. А формально всё хорошо и так.Учту в будущем.
У меня такое решение, в ответе 32 команды. В нём нужно найти две строки из шести цифр, которые не встретятся ни при каком преобразовании. Для этого перебираются случайные строки и делается симуляция. Видимо, с вопросиками (которые равны только себе) этого делать не нужно — можно взять какие-нибудь
?1?и?2?, — и решение в три раза короче.Просто ? и ??.
The problems are so good. Thanks Sereja, sdya and Gerald. What was the 3rd pretest of Problem C!!!???
I think you understood the task of problem incorrect, read again, sorry for poor English.
comment deleted
2 ≤ n ≤ 100 ;)
input:
3
1 2 2 2 2
output:
7
Did you figure out how the problem works? I'm interpreting the problem as in a single operation you MUST change the sign of n numbers. In pretest 3, however, the solution would require changing the sign of four numbers while n=3, which I thought would be impossible...
It is possible using two operations:
Oh wow, thanks. Wasn't thinking like that for some reason.
O(m*n) solutions accepted in problem B Div2.
Edit
My apologies, i misread the solutions. Is O(n+m) complexity, because they keep the last position found.
read the constraints again
(It is guaranteed that vi < vi + 1)
solutions are O(n+m)
The worst test case is:
n = 10^5
m = 10^5
ci = ti = 1 for 1 <= i <= n
vi = i for 1 <= i <= m
Ops! you are right, i misread solutions... they keep the last position found.
you might be dont know two pointers :)
Ops! you are right, i misread solutions... they keep the last position found.
Thanks for brilliant contest. It could be a great rated contest if CF didn't crash, but as an unrated contest it was outstanding. GL & HF!
Шикарные задачи, очень жаль, что раунд нерейтинговый. Большое спасибо!
Отлично, теперь не так обидно, что пропустил тур!
too slow system test :/
I'm waiting to add problems to practice.
Каждый раз, когда я близок к топ20 то у меня в коде одной задачи непременно есть баг, причем тупейший. И этот раз оказался не исключением. :(
Very nice problems!Especially problem C in div1!Thanks to sereja!
Weak test cases for problem B in DIV2
O(m*n) solutions pass the system test! m,n <= 10^5 !!
Okay I was wrong (It is guaranteed that vi < vi + 1) solutions are O(n+m)
show me the code. i think it's O(m+n) solution, not O(m*n), because variable j can not decrease:)
trying to figure out div1 problem D. i believe the number of divisors of a number n is no greater than 2*sqrt(n), is there a tighter bound?
Look at it as the number of multiples in the range [1,n]. Then you get:
n/1 + n/2 + n/3 + ... + n/n
Sum of numbers of divisors for numbers not exceeding N is
.
Also, number of divisors of N is o(Nε) for every ε > 0.
Задача В, тест:
Насколько я понимаю, ответ должен быть 1000. Почему решения, выдающие 0 (например, мое) прошли тесты? О_о
Этот тест некорректен. ai ≤ 1000.
Ок, а так? Суть то та же.
Тоже некорректен:) d ≥ 1000.
Окау, спасибо, тогда вопросов нет. Жестокая обфусикация условия >_<
да, на этом завязано, собственно, решение)
А я подумал, что заслал фигню, расстроился и ушел писать курсач в середине контеста >_<
Absolutely! except for the last thing :D
Hi there, a quick question.
In Div2 D/Div1 B, what should the output of the following test case be?
Should it be 1000? Because my program outputs 0 and passed system test. Thanks! :)
a_i<=1000
oh, I missed that one. Thanks, Sereja! I really enjoyed your problems :)
Would you mind returning pagination on the 'Contests' page to its normal state (slightly more than 4 contests per page)?
Already
So sorry to hear that...:(
The third topic what is thinking？
div2
In the problem "Yaroslav and Time", I define INF as 20000005, and get "pretest passed". However, "wrong answer on case 51" in rejudging. So Sad that INF shall be 2*20000005 or bigger. PS: If dijkstra algorithm is used in this problem, it's okay. But if dp is used, this test case should be concered: 5 1000 1000 1000 1000 0 0 0 1 1 1 2 1 2 0 What I mean is that we shouldn't just apply dp in just (sx,sy) to (ex, ey), but the whole (-100,-100) to (100,100).
Can someone tell me solution of problem C div 2
The problem tag is dp and math. However, I solve it in a more complicated way — bfs and greedy. First, I use bfs to get all the possible number of multiplying -1. For example, for n = 2, all the possible number are {0,2}. That's to say, I can multiply zero or two numbers in the array by -1. Then, sort the sequence and apply greedy algorithm. If I can make all the numbers positive, then do it. Else I make as more as I can. Be careful of occurrences of 0.
Here's another solution:
If there are any zeros inside the array, then you can ALWAYS make them all positive.
If you have n is an odd number, then you can ALWAYS make them all positive.
If you have n is an even number and there is an even number of negatives, then you can ALWAYS make them all positive. Else, you can ALWAYS make all but one of them positive.
Here is a rigorous proof of the "always"es frznlich said.
First, note that if n is odd, we can change any single number. To see this, take the number x that we want to change, and n more numbers a1, a2, ..., an. We do an operation to each of these: (x, a2, a3, ..., an), (x, a1, a3, a4, ..., an), ..., (x, a1, a2, ..., an - 1) -- basically every combination possible that takes x and n - 1 of the ai's. We can see that x belongs to n (an odd number) operations and hence changes sign, while every ai belongs to n - 1 (an even number) operations so doesn't change sign.
If n is even, we cannot change a single number: The number of numbers we change is even (some number times n which is even), and two changes equal null, so the parity of number of numbers we change is an invariant. So it will stay even. However, we can change two numbers. If we want to change x, y, take numbers a1, a2, ..., an - 1 and perform the operations (x, a1, a2, ..., an - 1), (y, a1, a2, ..., an - 1).
This means we can change all negative numbers to positive except probably one, and this "probably one" only occurs when n is even and there are an odd number of negative numbers.
So what we should do is to determine whether the above condition occurs. Besides, we will also find out the sum of the absolute values of the numbers and to figure out the number with the least absolute value, which we will "sacrifice" as the single negative number if there is any.
So our approach is this:
Loop over all numbers. Compute the number of negative numbers in the input and call it neg, the sum of the absolute values of all numbers sum, and the minimum absolute value of all numbers min. If n is even and neg is odd, output sum - 2min, otherwise output sum.
EDIT: Removed double post (phone acts up at times), useless statement to find the largest number, and useless assumption that zero is negative.
A solution more suitable to a contest, however, is: notice the bound N <= 100 and do BFS on how many negative numbers there could be, since if you change x negative numbers and N-x positive ones in one step, then there will be N-2x more negative numbers (special case: if there's a zero, it's clear that they can all be made non-negative). You don't need to think about all possible cases, just use a simple algorithm to do that for you.
Can someone tell me solution of problem C div 1？ thanks！
Can someone tell me solution of problem C div 1？ thanks！
One approach is this (works for any number):
For example, the number 6299:
6299, 62?99, 629?9, 6299?, 6299??, 629??0, 62??00, 6300
very tanks!
Just output the following:
The above is composed of five parts: End marker movers of 10 commands, end marker converter of 1 command, converter processes of 10 commands, converter finalization of 1 command, and end marker initializations of 10 commands.
At first, the string doesn't contain any question mark, so some of the end marker initialization commands (d>>??d) is encountered. There will be some double question mark, called end marker, inserted in the string.
Now, some of the end marker mover commands (??d>>d??) will be encountered. This basically moves the end marker one step to the right. As long as this end marker isn't at the end yet, the end marker will be constantly moved, so the end marker will eventually reach the end of the string. At the worst case, the end marker begins in the front of a 25-digit string, taking 25 iterations.
Next, the end marker converter (??>>?) is found, and the end marker becomes a converter sign (?). This converter sign's job is to add the digit exactly before it.
Next, some of the converter process commands (d?<>d) will be encountered, which changes the digit in front of the converter sign. If it's not 9, the addition will not cause any carry, so we're done. Otherwise, the special 9?>>?0 command is encountered, which marks that we need to carry and so we need to add 1 to the previous (more significant) digit. At the worst case, the converter processes need to go all the way to the front with the number 1025 - 1 = 9999999999999999999999999, which takes 25 iterations.
Finally, in the case the converter sign reaches the front of the string, we assume that there is an extra 0 in front of the string, and add 1 to it, hence the special (?<>1) converter finalization command.
This takes 32 commands and at most 53 iterations at the worst case, no matter what the actual numbers are.
To arrive at this solution, first you need to realize that 100 numbers is too much to handle by investigating the numbers; there must be some testcase that causes any submission based on handling numbers to fail. Too many numbers for too few commands. So there should be some easy solution independent of the numbers.
Next you need to figure out that you need to find some way to mark the end of the string (so you can start adding), you need to handle all digits, you need to handle 9s added, and you need to handle 999...9s.
The above is mostly trial-and-error after the above realizations.
Instead of last 10 lines you can output ">>??" :)
very tanks!
Because the contest was unrated, There wouldn't be any editorial for it?
There is an editorian on the Russian.
What about English version?
link of that one?
Can you paste the link to the editorial?
http://mirror.codeforces.com/blog/entry/7560
Mistakenly posted in russian
In problem B div 1, I failed at system test 52. There is some thing special in this testcase I couldn't find out . Can anyone help me? I think every station passed have to be inside the rectangle of point 1 and point n because when going out of the rectangle and returning, it will cost at least 2*d which is larger than any a[i]. However, it is inaccurate in test case 52 when the best route pass through outside points and then come to point n. For some more details
Test 52: 12 1211 1 5 7 1000 1000 1000 1000 1000 1000 1000 1 1 5 5 3 4 4 3 0 1 0 2 0 5 0 7 1 0 3 0 8 0 10 10 The best way: (1,1) -> (0,1) -> (0,2) -> (0,5) -> (0,7) -> (10,10)
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm О(n^2) or http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm O(n^3)
back to 1 (1,1)->(0,1), but get 4 additional bonus (0,1),(0,2),(0,5),(0,7)
I got caught in thinking that too, but it's not true. Consider the following situation:
where d=1000 and all ai=1000. You should pay 2000 to get out of the rectangle containing 1 and 9, because the gain is 7000.
As a rule of thumb, I would stick to not optimizing anything that doesn't need to be optimized during programming contest. You can improve algorithm after contest.