Service Temporarily Unavailable

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

Быстрее бы 100 раунд =D как ни как круглая дата )

→ Ответить

natalia

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

Можно 100-й раунд как-нибудь приурочить к Новому году

→ Ответить

Alex_KPR

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

а когда там конец света обещают?...

→ Ответить

SyFy	13 лет назад, # ^ \| +4 Перенесли на какое-то там февраля 14 года, так что можно пока спокойно вздохнуть. → Ответить

agul	13 лет назад, # ^ \| +5 На время олимпиады в Сочи? Не все тут чисто... → Ответить

aqua4

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

← Rev. 2 →

+27

Может после нового года наконец-то напишут "Codeforces Round # ??? ", вместо "Codeforces Beta Round # ??? "!

→ Ответить

SyFy	13 лет назад, # ^ \| 0 CBR как-то звучит лучше. → Ответить

aqua4

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

Просто вы привыкли к трех-буквенным значениям, таким как SRM или CBR. Пора разрушать стереотипы! Ну, если хотите, можете называть "CFR" или "CF round".

→ Ответить

SyFy	13 лет назад, # ^ \| -12 А что собственно изменится от того, что изменится название отображаемое при проведении раунда? CF пока в бета стадии, соответственно и раунды бета. → Ответить

aqua4

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

Я имею в виду название раундов после бета стадии :)

→ Ответить

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

По мне СR лучше)

→ Ответить

al13n

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

+13

Более того, "Codeforces Round # ???", вместо "Codeforces Beta Round # ??" :)

→ Ответить

Tranvick

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

+43

Главное чтоб не вечером с 31ого на 13ое =)

→ Ответить

cmd	13 лет назад, # ^ \| +18 Угу! А то будет пересекаться с традиционными новогодними контестами на snarknews.info =) → Ответить

valikluks1995

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

← Rev. 3 →

To natalia: Я предложил это MikeMirzayanov еще вчера или позавчера

→ Ответить

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

Было бы круто

→ Ответить

JKeeJ1e30

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

+24

100 - не круглая, круглая - 128.

→ Ответить

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

← Rev. 2 →

+58

→ Ответить

izban

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

Сколько задач? Разбалловка стандартная?

→ Ответить

RodionGork

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

Об этом сообщат с началом контеста. А вообще какая разница? Или от этого методика подготовки меняется?

→ Ответить

Ariza

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

Thanks for your hardwork.

By the way, anyone can explain me what is "classical Codeforces round" means?

→ Ответить

Nickolas

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

+32

I can guess that it's a typical Beta round, as opposed to Unknown Language Round or other unrated events with different rules.

→ Ответить

nathanajah

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

Apparently, I accidentally registered twice...

→ Ответить

Egor	13 лет назад, # \| +10 В связи с изменением формата страниц Codeforces прошу обновить CHelper до последней версии --- Due to format of Codeforces pages change please update CHelper to the latest version → Ответить

Egor	13 лет назад, # ^ \| +1 Due to bug in build process incorrect jar file was uploaded. Please redownload → Ответить

TMandzu

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

-12

It would be very good if someone will make the round at 31 December , something different and interesting ...

→ Ответить

NKolotey

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

Подскажите плиз, внеконкурсную регистрацию во втором дивизионе совсем отменили или как-то по особому нужно это делать? Если просто кликаю на "Зарегистрироваться", получаю:

Рейтинг должен быть от 0 до 1,699 для возможности регистрации на это соревнование

→ Ответить

tunyash

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

А смысл регаться вне конкурса, когда можно реально поучаствовать? По-моему, вне конкурса можно участвовать только когда одновременно див1 не идет.

→ Ответить

NKolotey

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

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

→ Ответить

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

+19

Ложись спать, потом сможешь написать виртуально.

→ Ответить

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

Есть контест для своего дивизиона => нельзя вне конкурса

→ Ответить

NKolotey

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

Ок, спасибо, понятно

→ Ответить

dyussenaliyev

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

-17

У ErzhanDS сегодня день рождения!!!

→ Ответить

abdukodir

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

поздравляю!!!

→ Ответить

nurbol

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

← Rev. 2 →

У Нуржана кстати тоже ДР сегодня!!))

→ Ответить

RodionGork

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

В контесте более 2000 участников, значит можно ожидать что примерно у 6 человек из них сегодня ДР. И что? Всем +300 рейтинга? :D

Даже в нашей конторе из ~300чел сегодня 5 ДРов и ещё ДР собачки одной из сотрудниц...

→ Ответить

dyussenaliyev

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

Я у тебя статистик не спрашивал...

→ Ответить

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

← Rev. 4 →

+11

Но нет день рождения близнецов. Имею в виду dyussenaliyev'a и ErzhanDS. И потом критиковать обезательно надо было?

→ Ответить

aropan

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

+19

Давайте ещё перенос на 5 минут... я зарегаюсь)))

→ Ответить

Sultan

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

← Rev. 2 →

Извините, не прочитал сообщение на главной.

→ Ответить

ViktorM

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

-9

Кто-то может помочь разобраться с условием задачи С 2го дивизиона и объяснить, что в ней требуется найти?

→ Ответить

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

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

→ Ответить

KF2017

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

← Rev. 2 →

Массив при вводе был уже отсортирован, или его надо было сортировать?

Я не сортировал, навеорное надо было. На 6 претесте провалилась. В чем причина не мог понять.

→ Ответить

iama	13 лет назад, # ^ \| 0 Стоило перечитать условие. → Ответить

KF2017

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

Тесты в условии сбили столку(хоть бы один был не отсортирован). С условия не мог понять на вводе массив подаренный мамой или уже отсортированный с замененым числом.

→ Ответить

bolivar1997

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

Надо было отсортировать но по другому.
Первый массив a вводишь а в массив b заносиш эти элементы
Потом сортиш массив b qSortом.
И выводиш от 2 элемента до n do write(b[i-1]);
там есть 1 случай когда все n элементов единицы тогда выводи
for i:=1 to n-1 do write(1,' ');
writeln(2);

→ Ответить

bolivar1997

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

вот мой код
var
a,b:array[0..1000000]of longint;
z,i,n:longint;
procedure qSort(l,r:longint);
var i,j,m,p:longint;
begin
i:=l;
j:=r;
m:=b[l+random(r-l+1)];
repeat
while b[i]<m do inc(i);
while b[j]>m do dec(j);
if i>j then break;
p:=b[i];
b[i]:=b[j];
b[j]:=p;
inc(i);
dec(j);
until i>j;
if i<r then qSort(i,r);
if l<j then qSort(l,j);
end;
begin
readln(n);
z:=0;
for i:=1 to n do
begin
read(a[i]);
b[i]:=a[i];
if a[i]=1 then inc(z);
end;
qSort(1,n);
if (z=n) then
begin
for i:=1 to n-1 do write('1 ');
write(2);
halt;
end;
write(1,' ');
for i:=2 to n do write(b[i-1],' ');
end.

→ Ответить

alex270295

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

обалдеть блин.. по задаче B одинаковый код на fpc проходит а на delphi неправильный ответ на 3 претесте

→ Ответить

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

[:||||||||||||:]

→ Ответить

AWPRIS

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

← Rev. 3 →

+20

Личное спасибо от меня автору задач (он же автор задач на Всеукраинских олимпиадах) Ярославу Твердохлебу за интересную подборку задач на контест.
В виде благодарности принимайте в ряды решателей троих новых решателей-девятиклассников (они после сегодняшней своей городской олимпиады загорелись желанием что-то решить и здесь). :)
Удачи всем: и автору и всем решателям.

→ Ответить

herr_bilbo

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

← Rev. 2 →

извините, вы с Украины, я даже об этом как-то и не подумал...

→ Ответить

AWPRIS

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

← Rev. 2 →

Да ничего - просто у нас городская олимпиада уже прошла, а во всей остальной области на других задачах будет только завтра-плослезавтра.

Двое уже получили первый урок (взломали на задаче С) - нужно уметь писать быструю сортировку...
И это своего рода плюс - им есть самостоятельно над чем работать!

→ Ответить

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

Да и по стране не в один день. В Московской области писали 20-ого ноября.

→ Ответить

natalia

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

Это региональный этап у всех в один день.

→ Ответить

dengaleev

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

Спасибо за классные задачи, интресно было их решать)

→ Ответить

NVAL	13 лет назад, # \| +1 Задачи B и C в div 2 можно было бы местами поменять имхо, хотя посмотрим, как пройдет системное тестирование. Вообще задачи понравились, особенно D. → Ответить

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

Возможно в С есть "подводный камень"?

→ Ответить

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

Большая часть этого подводного камня ловится претестами(по крайней мере в div1)

→ Ответить

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

А разве претесты отличаются?)

→ Ответить

natalia

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

Да, есть случаи вида 1 1 1 и 1 1 2.

→ Ответить

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

Извините за тупость, но ответы на эти случаи - 1 1 2 и 1 1 1? ))

→ Ответить

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

Да, вы правы.

→ Ответить

NVAL	13 лет назад, # ^ \| +4 Есть, но увидел сразу. Большинство вроде на претестах его тоже заметили. Было бы интереснее, если бы было без претестов на этот камень. → Ответить

SyFy	13 лет назад, # ^ \| 0 Таки да, думаю, если бы претесты не имели этого 1 1 1, то финальные тесты бы огорчили достаточно народу. → Ответить

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

Вряд ли, скорее бы было много заработавших баллы на взломах

→ Ответить

emil	13 лет назад, # ^ \| +3 я на этот подводный камень так сильно наткнулся, что только под конец понял кто дурак, я или задача. → Ответить

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

Я минуты три сидел смотрел на эту C, пытаясь понять, то ли она такая простая, то ли я глупый, не вижу какого-то подвоха, потом все-таки быстренько написал и отправил. Тест 1 1 1 и тому подобные учел сразу, даже на всякий случай перемешал массив, а то вдруг автор захочет qsort повалить :D

→ Ответить

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

← Rev. 2 →

Еще бы претесты чуть послабже и было бы мясо)

Спасибо за контест!

→ Ответить

yarrr

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

Да, зря 2-ку в претесты включили в А :(

→ Ответить

kvo	13 лет назад, # \| +7 funny, I could challenge one solution with Anti QuickSort, be carefull next time! → Ответить

Coder

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

AntiQuicksort detected in final tests

→ Ответить

KADR	13 лет назад, # ^ \| +10 There were a few successful hacks made with antiquicksort and they were added to the final testset. → Ответить

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

Are all successful hacks added to final tests?

→ Ответить

KADR	13 лет назад, # ^ \| 0 Well, I'm not sure about all of them, but most of them are added to the final testset. → Ответить

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

← Rev. 2 →

I forgot that I have antiquicksort generator :(

FFFFFFFFFFUUUUUUUUUUUU, I also have anti-java-sort generator :(

→ Ответить

kvo	13 лет назад, # ^ \| 0 in last comments someone wrote: "some of challenges are added to system tests" → Ответить

ikk	13 лет назад, # ^ \| 0 Does this mean we shouldn't use quicksort in sports programming? Is `qsort(3)` or `std::sort` safe? → Ответить

paladin8

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

← Rev. 2 →

I believe C++ STL sort uses introsort so that is safe.

EDIT: I should say, rather, that GNU C++ does this. The actual standard does not require it.

→ Ответить

haas	13 лет назад, # ^ \| ← Rev. 2 → +5 quick sort has random parts, hasn't? so what the hell is Anti Quicksort? :D → Ответить

soerend

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

In practice a lot of quick sorts are implemented by taking the median of the first, last and middle element instead of using random. This has been shown to give great performance in practice.

→ Ответить

Hohol

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

+11

Огромное спасибо ltaravilse, взломавшему мою B за 10 минут до конца! И что бы я без него делал)

→ Ответить

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

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

→ Ответить

Hohol

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

Нет, там была абсолютно неведомая опечатка. Хз, мож еще упадет.

→ Ответить

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

как С решалась?=(

→ Ответить

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

Стратегия кажись такая:

Первый игрок убирает единицы с начала, а потом нули с конца, второй игрок действует наоборот.

Достаточно рассмотреть несколько случаев: ставим вместо вопросов одни нули - возможно получится 00. Ставим одни единицы - возможно 11. Ставим так чтобы половина нулей, половина единиц, причем нули сначала - это под 01, нули с конца - под 10. В каждом из четырех случаев можно симулировать игру и посмотреть что выйдет.

→ Ответить

agul	13 лет назад, # ^ \| 0 Ээ... Тест 11010 По вашей стратегии: 1) 11010 2) 11010 3) 11010 Ответ: 01 Оптимально для второго игрока: 1) 11010 2) 11010 3) 11010 Ответ: 10 → Ответить

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

Первый начинает удалять нули с конца, только после того как все единицы кончились, очевидно.

→ Ответить

agul	13 лет назад, # ^ \| -8 Ну у меня так и есть, как бы. → Ответить

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

Второй делает наоборот, т.е. удаляет нули с конца сначала, а у тебя почему то последний ноль он удалил

→ Ответить

agul	13 лет назад, # ^ \| 0 Удаляет нули с конца - поэтому удалил последний ноль. → Ответить

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

← Rev. 2 →

Мда, это я наркоман, запутал ты меня.

Конечно же второй игрок начинает удалять нули тоже с начала.

→ Ответить

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

Если кончились все единицы или все нули, то ответ 00 либо 11. Это быстро проверяется без симуляции.

→ Ответить

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

Под "наоборот" я подразумевал то что второй игрок будет удалять нули, а когда они кончатся - единички.

→ Ответить

kit1980

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

+10

Можно все просчитать без симуляции.

00 может получиться, если количество 1 <= ходам Маши.
1 может получиться, если количество 1 + количество ? >= ходам Маши + 2.

01/10 может получиться, если количество 1 + количество ? хотя бы на один больше ходов Маши, но при этом количество уже присутствующих 1 не превышает количество ходов Маши на 2 или больше (иначе только 11 возможно).
Дальше для 01/10 можно смотреть по последней цифре.
Если 0 (или ?, который можно превратить в 0, не сводя к 00) - 10.
Если 1 (или ?, который можно превратить в 1, не сводя к 11) - 01.


tm = (len(s) - 2) / 2 + len(s) % 2

if n1 <= tm:
    print "00"

if n1 + np >= tm + 1 and not (n1 >= tm + 2):
    if (s[-1] == "1") or (s[-1] == "?" and not (n1 + 1 >= tm + 2)):
        print "01"
    if (s[-1] == "0") or (s[-1] == "?" and not (n1 + np - 1 <= tm)):
        print "10"

if n1 + np >= tm + 2:
    print "11"

Полное решение.

→ Ответить

rembocoder

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

+29

Самый ужасный контест, который я писал на сodeforces. В первых четырёх задачах первого дива абсолютно не надо думать, зато надо разбирать случаи, просто отвратительно.

→ Ответить

tunyash

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

-6

А в Б какие случаи?

→ Ответить

agul	13 лет назад, # ^ \| +10 Я проверял является ли набор точек квадратом / прямоугольником разбором случаев → Ответить

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

Как минимум в B никаких случаев можно было не разбирать.

→ Ответить

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

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

→ Ответить

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

← Rev. 2 →

Каких характеристик? Ну перебор это да, но не скажу, что 4 цикла сложно\долго писать.

UPD. Упало. Соглашаюсь, я идиот =)

→ Ответить

agul	13 лет назад, # \| +11 I hope that today system testing will be fast... → Ответить

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

It seems that it's not as usual! :(

→ Ответить

Amir.bh

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

Great contest! Questions was so interesting! Thanks Codeforces that cause me to advance a lot in algorithms!

→ Ответить

YouTubeHeroes

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

+13

Как решить задачу A ЗА ДВЕ МИНУТЫ ?!

→ Ответить

dengaleev

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

да там писать не многа

я за три решил :P , если не тестировать то можна и за две было

→ Ответить

agul	13 лет назад, # ^ \| ← Rev. 2 → 0 за 00:01:35 :D → Ответить

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

+10

Сортировка, замена последнего элемента на 1, а если он уже 1 то на 2, снова сортировка, вывод.

→ Ответить

agul	13 лет назад, # ^ \| +1 Он спрашивал про див2. Там нет никакой сортировки. → Ответить

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

Обе А решаются за 2 минуты =)

→ Ответить

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

Нужно уметь быстро читать условие=)

→ Ответить

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

← Rev. 2 →

+25

Мне одному кажется что тут сидит 4 гоблина и минусуют просто всех?

→ Ответить

malcolm

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

-14

Нет, конечно, что вы в самом деле)

→ Ответить

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

← Rev. 3 →

-8

В семье не без урода:)

UPD. То есть всегда найдутся антиобщественные люди.

→ Ответить

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

А в претестах ведь был тест из одних единиц?
Лучше бы не было, я вот сразу перед сабмитом поднял такой тест.

→ Ответить

SyFy	13 лет назад, # ^ \| +1 Я вовремя-то успел СТОП в браузере нажать после клика на сабмит файла, когда понял, что ВОТ ОНО 1 1 1 =D → Ответить

agul	13 лет назад, # ^ \| 0 Да, такой тест, видимо, был, т.к. многие упали на претесте 5, при этом при взломах я не нашел ни одного решения с такой ошибкой. → Ответить

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

+13

А когда начнут проверять? Раз уж "По причине большого числа участников и большого количества тестов, результаты появятся не скоро.", почему бы уже не начать?

→ Ответить

MikeMirzayanov

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

Теневое тестирование идет во время контеста и перед запуском основного системного. Так что не переживайте, инвокеры работают без остановки!

→ Ответить

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

I am baffled, and I tried for ages to figure out why my B.cpp kept failing the very first pretest.

http://pastebin.com/Jpa6M6DX

Things like the paralel and area check I added after trying many things. Initially I only had distance and perpendicular checks. I noted that Romka passed system tests using only distance and perpendicular checks, and his method to check if there is a right angle is equivalent to mine. So, really any help is appreciated.

→ Ответить

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

-14

"Romka passed system tests"

Do you see the system tests finished? I see "Pending system tests". Codeforces system testing uses to start early is it something happening now that doesn't make possible to start system testing?

→ Ответить

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

← Rev. 2 →

I meant pretests, my problem is that I can't pass even pretest #1

→ Ответить

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

Also, isn't it usual for pretest#1 to be the example case? If that is the case then this is very strange because the examples work correctly in my machine. If that's not necessarily the case, that's good to know.

→ Ответить

KADR	13 лет назад, # ^ \| +3 Pretest #1 is always the first example case. → Ответить

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

Thanks. Though I am now officially confused.

Maybe it is something about compiler versions being different.

→ Ответить

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

Maybe garbage in variables?

→ Ответить

Killever

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

← Rev. 4 →

I run your program in my machine

First case

your output

YES
1 2 3 4
5 6 7 8

but it have to be
YES
5 6 7 8
1 2 3 4

→ Ответить

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

I get the correct result in my computer. I will try getting identical compiler setup to CF.

→ Ответить

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

I have been using gcc 4.2 to compile and test locally. If I change it to 4.3 , I start getting WA in the first case. CF uses 4.6 , so there's probably a change in 4.3 that stayed.

I guess it would have been better to figure out that pretest#1 was the first example, that way I would have focused on compiler-related things.

→ Ответить

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

← Rev. 2 →

Edit: No, wrong theory.

→ Ответить

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

I just forgot a "return false" in isRectangle(), this caused undefined behavior, so it behaves differently in different compiler versions.

→ Ответить

0x1337

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

← Rev. 3 →

ignore

→ Ответить

Killever

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

he first make

while( cin >> x[0] >> y[0] )

then read other data in loop 1->8

→ Ответить

ifsmirnov

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

+22

Поддерживаю написавшего про разбор случаев. Четыре задачи, где в каждой либо есть какой-то corner-case, либо она сама решается только разбором случаев - это перебор. Особенно в четвертой это напрягло.

→ Ответить

PeaceDeath

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

Хватит это терпеть!

→ Ответить

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

Началась проверка. Ждём =)

→ Ответить

vici	13 лет назад, # \| ← Rev. 2 → +3 div1.C, when the digits on the cards got blurred, do the players know the digits? How do they make their decisions? → Ответить

KADR	13 лет назад, # ^ \| 0 Yes, they know the digits. One need to find the outcomes for all possible replacements of '?' with '0' and '1'. → Ответить

Acko	13 лет назад, # \| +5 Very nice problem set, thank you for this competition! :) → Ответить

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

← Rev. 5 →

-8

Было бы обидно, если бы решения с голым qsort в C прошли финальные тесты)

Надеюсь, они все упадут, мвахахах!

→ Ответить

SyFy	13 лет назад, # \| 0 А как скоро разборы будут? → Ответить

KADR	13 лет назад, # ^ \| +1 На днях постараюсь опубликовать. → Ответить

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

Сто тестов на А - не лучшая идея... Хотя несколько ТЛ было на последних, там антиквиксорт?

→ Ответить

KADR	13 лет назад, # ^ \| +10 Там тесты со взломов. Среди них есть и антиквиксорт. → Ответить

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

+12

Вау, крутое нововведение. Я про него даже и не слышал ещё, хотя мб, где-то и писали. Спасибо!

→ Ответить

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

Расскажите про антиквиксорт пожалуйста =)

→ Ответить

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

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

→ Ответить

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

← Rev. 2 →

Спасибо =)

UPD. Через что реализован sort в С++ ?

→ Ответить

SyFy	13 лет назад, # ^ \| +1 merge sort? → Ответить

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

По версии cplusplus.com то его асимптотика примерно NlogN, N^2 в худшем случае..

→ Ответить

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

Я слышал, что на C++ сорт не валится, что там если quicksort выполняется слишком долго, запускается heapsort, который гарантированно NlogN

→ Ответить

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

Спасибо за информацию =)

→ Ответить

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

Я тоже такое слышал)

→ Ответить

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

А вот Java можно ломать, как и паскалистов. Но во время контеста абсолютно забыл об этом. Привык уже, что не дают задачи с сортом.

→ Ответить

SyFy

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

С чего это вдруг яву можно?

Судя по этому и этому там всё хорошо реализовано.

1. This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.

2. The sorting algorithm used (in Sun's implementation at least) is a version of mergesort

→ Ответить

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

===========================================
Объекты сортируются mergesort-ом, а примитивные типы - чуть-чуть улучшенным quicksort-ом, но все же quicksort-ом. Почитай исходники.

→ Ответить

shevchen

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

На примитивных типах данных quicksort, на объектах - mergesort.

_______________________________

→ Ответить

OSt	13 лет назад, # ^ \| +7 Исследования на эту тему: http://codeforces.net/blog/entry/2298 → Ответить

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

Просто я решал С (div.2) через sort, как вижу в 1 дивизионе проходит.

→ Ответить

NVAL	13 лет назад, # ^ \| +1 Introsort n log n, сначала идет quicksort, а когда глубина рекурсии больше n log n - идет пирамидальная → Ответить

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

На С++ этот финт не работает, ибо сорт там, насколько я знаю, рандомизирован.

→ Ответить

ifsmirnov

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

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

→ Ответить

SyFy	13 лет назад, # ^ \| 0 а на генератор можно взглянуть? → Ответить

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

Конечно, нет. Это относительно редкая вещь. На Е-Олимпе есть задача, которая посвящена этому. Можешь там поиграться.

→ Ответить

SyFy	13 лет назад, # ^ \| 0 Мог бы ссылочку кинуть? Хочется с условием ознакомиться. → Ответить

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

Можно тут сдать.

→ Ответить

alex270295

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

а рандомизированный quicksort должен ведь сработать?

→ Ответить

NVAL	13 лет назад, # ^ \| +8 Рэндомизированный не сработает только если теория вероятности сильно на тебя разгневана → Ответить

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

Был такой случай))

→ Ответить

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

Я сломаю ваш рандомизированный quicksort, если не забуду об этом :)

→ Ответить

k-va	13 лет назад, # ^ \| +2 На А - сотня тестов, на В - две сотни. Если и дальше так же, то не скоро тестирование закончится. С этим что-то надо делать, а то часами ждать результаты - неинтересно. → Ответить

SyFy	13 лет назад, # ^ \| +1 А какие варианты есть? → Ответить

NVAL	13 лет назад, # ^ \| 0 Надо делать по-меньше претестов, чтобы работали на взломах, а тестов достаточно ~70 → Ответить

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

-31

Можно ввсести ограничение по кол-ву участников. Например div 1 - 300 мест, div 2 - 700 мест.

→ Ответить

SyFy	13 лет назад, # ^ \| +7 нельзя. → Ответить

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

Да вроде и так все оптимально: система контеста с претестами и финальным тестированием - хороша, кол-во тестов также оптимально, не мало, но и не так уж много, время проверки одного теста, уверен, настолько быстрое, насколько это возможно. Так что еще вы хотите? Лучше 3-4 часа подождать, а перед эти поучаствовать в хорошем контесте, чем быстро получить результаты, но от контеста удовольствия не получить. Поправьте, где я не прав)

→ Ответить

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

← Rev. 2 →

вот в этом месте

>>кол-во тестов также оптимально, не мало, но и не так уж много

→ Ответить

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

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

→ Ответить

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

← Rev. 2 →

это утрировано: >>А сокращать кол-во тестов до минимума, в котором будут несколько крайних тестов и еще парочка промежуточных, ну уж, для полноты действа, - не вариант.

ну почему в каких олимпиадах я не участвовал, не было тестов больше 50, а если были, то это было довольно диковино (и что, скажете тесты были неполные????)

ну в задачах типа Д-Е конечно много тестов (<= 100) это конечно вполне норм, но зачем столько в задаче Б(див2), например?

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

→ Ответить

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

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

→ Ответить

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

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

→ Ответить

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

можно руками просматривать некоторые из них

→ Ответить

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

А можно сразу придумывать хорошие тесты =) WA 211 намекает на то, что тесты были не очень сильные, что не может не удручать.

→ Ответить

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

Tottally off-topic but I don't know where to ask. What is the contribution in CodeForces?

→ Ответить

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

It's something you gain/lose writing your comments/blog:)

→ Ответить

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

We have been waiting 1 hour for less than 20% done of the system test! :(

→ Ответить

taserghar

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

one of the finest set in code forces.......thanks to KADR......... :)

→ Ответить

SyFy	13 лет назад, # \| 0 А каким образом влияет кол-во раз после которых удалось отправить задачу с полным решением на очки за данную задачу? → Ответить

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

-50 за каждый неуспешный сабмит, свалившийся не на 1 тесте

→ Ответить

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

As the codes are tested in the same order they are submitted, don't you think it may be a good idea to show the time when the last tested code was submited during the system tests?

→ Ответить

KADR	13 лет назад, # ^ \| +17 You can open the "Status" tab and watch it there. → Ответить

ridowan007

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

Was this was really necessary to make 100+ test cases? If you only keep tricky cases then may be 50> case could be enough for testing and will take smaller system testing time :-|

→ Ответить

KADR	13 лет назад, # ^ \| +10 Most of the successful hacks were also added to the final testset. → Ответить

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

+34

For the next time it may be a good idea to make the tricky test cases be the first one so there's no need to test 200 cases before test case 201 fails.

→ Ответить

havaliza

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

+15

It would have been better to include the cycle
11
11
in Div1-D sample tests.
Many didn't pass the pretests because of this.

→ Ответить

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

Меня почему-то дико пугают ВА 200+ на задачу В :о

→ Ответить

valikluks1995

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

Ну что ты, а меня радует AC после 200+ тестов :)

→ Ответить

gravity

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

I just saw the solution to Problem B Div 2, Lolz, my solution to the problem is so crappy !! I can't believe it didn't strike me. Well, you always learn something new here. :)

→ Ответить

Fcdkbear

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

+27

Вы уж простите, но настолько медленное тестирование - это уже слишком.

→ Ответить

MikeMirzayanov

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

+24

Да, в самом деле результаты появляются медленно. С другой стороны система обрабатывает ~100 тестов в секунду. В любом случае к следующему раунду внедрим очередную оптимизацию, надеюсь, получится значительно ускорить процесс.

→ Ответить

RetiredLoser

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

+18

too slow system test :(

→ Ответить

userlond

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

+11

Check system's verdict is Time Limit :)

→ Ответить

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

Now around 2 hours waiting and only less than 50% done of the system test! :\

→ Ответить

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

f5 after f5, tired :(

→ Ответить

userlond

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

+15

f5 will be broken tonight...

→ Ответить

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

surely :)

→ Ответить

Oi.	13 лет назад, # ^ \| +16 I'm not sure if the system testing is done on the same server, but if that is the case, ironically, pressing f5 will only make it slower ;) → Ответить

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

Count them so you don't get bored :D

→ Ответить

R_R_	13 лет назад, # ^ \| +9 :( I lost my count somewhere after 999997 → Ответить

Coder

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

And the waiting world record goes to the guy who submitted last.

→ Ответить

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

Вот объясните мне пожалуйста, зачем делать столько тестов? Почему нельзя просто сделать 30-40 нормальных? ~220 по B, ~100 по С. Зачем?! В итоге после 2 часов тестирования проверено около 50%.

→ Ответить

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

Лучше подождать лишние два часа, чем получить неверные результаты...

→ Ответить

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

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

→ Ответить

Romka

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

+19

"Послушать, так вся страна в футбол играть умеет; одни мы, 11 человек, уроды кривоногие..." (с) Из шутки про футболистов

→ Ответить

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

→ Ответить

PavelKunyavskiy

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

Ну 50 это иногда мало. Когда я что-то делаю у меня обычно 70-80 получается.

→ Ответить

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

но не 220 же)

→ Ответить

Dmitry_Egorov

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

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

→ Ответить

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

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

→ Ответить

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

← Rev. 2 →

Если решение укладывается в ТЛ - оно не тленое.

Более того, удачно пропихнуть такое решение тоже скилл, так почему бы ему не отражаться местным рейтингом?

→ Ответить

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

да ладно вам! сколько(пожалуй несколько) случаев было что автор просто не учел такой случай, например мне вспомнился случай товарища maksay, когда сдал квадратичние (в какую то задачу про дерево)

→ Ответить

AlexErofeev

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

Я боюсь, для B не так просто будет написать решение, содержательная часть которого ТЛится

→ Ответить

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

атас, ВА219 %)

→ Ответить

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

← Rev. 2 →

+13

222, у кого ~~длиннее~~ больше?

→ Ответить

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

По моему первый раз столько много тестов. Именно в этот раз решили добавлять тесты со взломов?

→ Ответить

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

Раньше тоже добавляли, но, видимо, сегодня добавили вообще все взломы.

→ Ответить

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

И у меня слетела B на 222 тесте:D

→ Ответить

KADR	13 лет назад, # ^ \| 0 Ну нет, не то чтобы взломов было 100 штук. Там и так тестов много было. В общем, большое количество тестов в задачах для обоих дивизионов плюс большое количество участников плохо сказывается на скорости тестирования. → Ответить

SyFy	13 лет назад, # \| +5 Завел будильник на 02.30, надеюсь сис тесты завершатся... → Ответить

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

Какой толк от результатов контеста посреди ночи?!

→ Ответить

SyFy	13 лет назад, # ^ \| 0 любопытство. не усну же. → Ответить

AlexErofeev

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

+26

Зачем тогда будильник?))

→ Ответить

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

Наверное, чтобы тут же похвастаться результатом=))

→ Ответить

http://codeforces.net/contest/135/submission/939936

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

Будет лежать, пытаться уснуть, а тут бац - будильник, встанет - пойдёт посмотрит результаты =)

→ Ответить

Dmitry_Egorov

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

← Rev. 2 →

А зачем будильник тогда?)

P.s. Опоздал.

→ Ответить

JKeeJ1e30

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

← Rev. 2 →

Ребят, помогите увидеть где меня ломанули в В. Я слепой не вижу.

→ Ответить

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

Элементарно, Ватсон. Вот контрпример:
0 1
1 1
0 0
1 0
0 5
0 6
0 7
0 8

Ваша программа выдаёт "YES 1 2 3 4 5 6 7 8", хотя очевидно, что точки 5 6 7 8 лежат на одной линии и не могут быть прямоугольником :)

→ Ответить

JKeeJ1e30

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

-7

Я буду читать условие

→ Ответить

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

маловато будет....

→ Ответить

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

Спасибо за тест!
У меня с этим тестом всё ОК, надеюсь, что остальные 200+ пройдёт так же)

→ Ответить

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

установлен абсолютный рекорд codeforces по времени тестирования =(

→ Ответить

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

Уфф D-шка (див 2) ацептед =) Интересно, кто-нибудь ещё использовал в этой задаче выпуклую оболочку?) Ведь она сразу решает половину проблем, остаётся лишь проверить углы и длины противоположных сторон :)

→ Ответить

NVAL	13 лет назад, # ^ \| 0 Я просто проверял у квадрата равенство всех четырех сторон и два противоположных угла на то, что они прямые(по теореме Пифагора), а у прямоугольника равенство диагоналей. → Ответить

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

Но ведь надо было перебирать все варианты построения фигуры из 4 точек. А выпуклая оболочка сразу выдавала единственный верный =)

→ Ответить

NVAL	13 лет назад, # ^ \| 0 Мои познания слишком скудны, увы, я не знаю, что такое выпуклая оболочка... → Ответить

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

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

→ Ответить

NVAL	13 лет назад, # ^ \| 0 Спасибо, изучу → Ответить

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

Уфф, моя, D-шка (див-2) прошла все тесты и я могу теперь спокойно сказать, что выпуклая оболочка в данной задаче - это как по воробьям из пушки=)
Я всё решал "в лоб"
http://codeforces.net/contest/136/submission/945918

→ Ответить

AlexanderBolshakov

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

Мое решение с next_permutation в два раза короче :)

→ Ответить

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

И красивее)

→ Ответить

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

Слишком сложно. Я перебирал что является диагональю. Это также решает все проблемы.

→ Ответить

I_love_47

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

At last! :)

→ Ответить

Anarivu

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

кто нибудь знает в чем прикол 96-го теста по В?

→ Ответить

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

автор контеста, вероятно

→ Ответить

SyFy

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

-6

Пока ловил

Service Temporarily Unavailable

The server is temporarily unable to service your request due to maintenance downtime or capacity problems. Please try again later.

Apache/2.2.21 (Fedora) Server at codeforces.ru Port 80

или

Oops! Google Chrome could not connect to codeforces.ru

Try reloading: codeforces.ru

возник вопросец: а не горит ли желанием ВК предоставить скажем часть своих серверов под КФ для благих целей-то? а?

→ Ответить

Sultan

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

Здесь спорный вопрос, так как это происходит только один раз в неделю, при том не всегда(когда only div 2, такое редко случается), а сегодня как раз стечение обстоятельств, много участников и всем интересны результаты.

→ Ответить

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

Несмотря на то, что в задаче B было 200 с гаком тестов, мое не совсем верное решение прошло. Я написал решение с масками и проверял лишь 2 противоположных угла на 90 градусов. Это не совсем верно, надо проверять все углы. Вот тест, который придумал AlexanderBolshakov :

0 0
0 100
75 0
96 72
1 1
1 2
2 1
2 2

У первого 4-х угольника есть 2 противоположных угла по 90 градусов, но он не является прямоугольником. Правильный ответ здесь NO, а мое решение выдает YES

→ Ответить

NVAL	13 лет назад, # ^ \| ← Rev. 2 → -10 Это где же у него 2 противоположных по 90 градусов? Курс геометрии подсказывает, что если два противоположных по 90 градусов, то это и есть прямоугольник... UPD: да, действительно плохо, больше не буду умничать → Ответить

AlexanderBolshakov

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

Плохо Вы учили геометрию... Здесь получается дельтоид, а не прямоугольник.

→ Ответить

SupeR-MaN

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

а я Д перестановками сделал =)

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

→ Ответить

UCI-Night

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

Great contest, I really enjoy, thanks to all whose work makes it possible that this site is.

→ Ответить

kasitan

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

← Rev. 2 →

Подскажите, а хоть кто-то уложился на C# в задаче "Замена" (задача А в 1 диве) в лимит по времени?

→ Ответить

kasitan

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

← Rev. 2 →

Получилось решить, не сразу выводя в консоль, а сначала в стрингбилдер.

UPD. Но правда с запасом прочности всего лишь 20 мс и 32 МБ съеденной памяти :) Подскажите, как по-правильному? Или по-правильному - переходить на С++? :)

→ Ответить

it4.kp

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

Можно еще вот так.

→ Ответить

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

+21

Офигеть, моей проге в D не хватило 32 мегабайта стека, поставил 64 и прошла :( А цена - победа на соревновании...

→ Ответить

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

Я думал, что на CF стек не ограничивается, а тут такое... о_О

→ Ответить

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

Так я его всегда 32 мегабайта ставлю, самостоятельно.

→ Ответить

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

Печально, но почему сразу не поставить 256 MB?

→ Ответить

AlexanderBolshakov

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

Возможно, потому что будет MLE. Если ошибаюсь - поправьте меня кто-нибудь.

→ Ответить

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

Не будет, всю жизнь так делал

→ Ответить

dashka_z

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

меня взломали на задаче С(2 div), вбив n=100000 чисел, хотя по условию n<10^5. это нормально?

→ Ответить

agul	13 лет назад, # ^ \| +12 1 ≤ n ≤ 10⁵ → Ответить

kit1980

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

+12

По условию n <= 10^5, так что 100000 допускается, конечно.
Решение должно ломаться и для меньших чисел из-за сортировки пузырьком.

→ Ответить

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

Перестраховываться надо и делать массив чуть-чуть побольше, чем просят

→ Ответить

reiracofage

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

I think Petya is the person who enjoyed the contest most. He received a lot of gifts from his mother in this end of year! Wondering if it could happen to us...
Seriously now, the system test case took really a long time, but ignoring this fact, I liked the contest. I think the problems difficulty were indeed propotional to the problems' points/values, and the statements were easy to read.

→ Ответить

duo	13 лет назад, # \| 0 Great contest! By the way, anyone can give me some ideas to solve problem E-div2? → Ответить

HisShadow

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

Интересно, почему 1ая программа выдает -67399853 на 1ом тесте, а во второй всё ок?
1. http://paste.pocoo.org/show/518715/
2. http://paste.pocoo.org/show/518716/

→ Ответить

rminuv372

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

the meaning of problem A is ambiguous.

→ Ответить

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

← Rev. 6 →

really enjoyed the contest, thnx KADR. wish I didn't make a stupid mistake in D :(

→ Ответить

SyFy	13 лет назад, # ^ \| +1 really enjoyed the contest, thnx KADR. wish I didn't make a stupid mistake in D :( example =) read this. → Ответить

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

thnx, I got it now.

→ Ответить

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

← Rev. 3 →

В div.2 в задаче D в тесте

0 0

0 1

1 0
1 1
2 0
2 1

3 1

4 0

ответ должен быть

"YES

3 4 5 6

1 2 7 8"???

→ Ответить

KADR	13 лет назад, # ^ \| 0 А почему 1 2 7 8 - это прямоугольник? → Ответить

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

Кстати С задача также решается через ассоциативный массив (map в С++).

→ Ответить

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

I failed in case 222 in problem 'Rectangle and Square' and I can't find what the problem is in my code, did anyone encountered the same problem? May anyone help?

→ Ответить

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

This isn't a valid rectangle.

Input:

Output:

NO

→ Ответить

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

← Rev. 2 →

Check the part of your code where you check whether it is a rectangle or not.

→ Ответить