Всем привет!
В пятницу, 9 декабря в 19:00 MSK состоится Codeforces Beta Round #97, автором которого являюсь я. Это мой второй полноценный раунд на Codeforces и надеюсь, что не последний :)
Спасибо maksay, Shtrix, it4.kp, RAD и Delinur за помощь в подготовке раунда, тестировании задач и переводе условий.
Удачи на раунде!
UPD: По техническим причинам раунд переносится на 5 минут вперед.
UPD 2: По причине большого числа участников и большого количества тестов, результаты появятся не скоро.
UPD 3: Тестирование завершено, результаты известны. Всем спасибо за участие! Приношу свои извинения за настолько длительное тестирование.
Победители:
Div 1
1. Romka
2. vepifanov
4. Shef
6. shangjingbo
7. ania
8. Ra16bit
9. NALP
10. enot110
Div 2
UPD 4: Опубликован разбор.
Ждёмс с нетерпением!
Спасибо авторам контеста!
Может после нового года наконец-то напишут "Codeforces Round # ??? ", вместо "Codeforces Beta Round # ??? "!
To natalia: Я предложил это MikeMirzayanov еще вчера или позавчера
By the way, anyone can explain me what is "classical Codeforces round" means?
У Нуржана кстати тоже ДР сегодня!!))
Даже в нашей конторе из ~300чел сегодня 5 ДРов и ещё ДР собачки одной из сотрудниц...
Но нет день рождения близнецов. Имею в виду dyussenaliyev'a и ErzhanDS. И потом критиковать обезательно надо было?
Извините, не прочитал сообщение на главной.
Массив при вводе был уже отсортирован, или его надо было сортировать?
Я не сортировал, навеорное надо было. На 6 претесте провалилась. В чем причина не мог понять.
Тесты в условии сбили столку(хоть бы один был не отсортирован). С условия не мог понять на вводе массив подаренный мамой или уже отсортированный с замененым числом.
Первый массив a вводишь а в массив b заносиш эти элементы
Потом сортиш массив b qSortом.
И выводиш от 2 элемента до n do write(b[i-1]);
там есть 1 случай когда все n элементов единицы тогда выводи
for i:=1 to n-1 do write(1,' ');
writeln(2);
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.
Личное спасибо от меня автору задач (он же автор задач на Всеукраинских олимпиадах) Ярославу Твердохлебу за интересную подборку задач на контест.
В виде благодарности принимайте в ряды решателей троих новых решателей-девятиклассников (они после сегодняшней своей городской олимпиады загорелись желанием что-то решить и здесь). :)
Удачи всем: и автору и всем решателям.
извините, вы с Украины, я даже об этом как-то и не подумал...
Да ничего - просто у нас городская олимпиада уже прошла, а во всей остальной области на других задачах будет только завтра-плослезавтра.
Двое уже получили первый урок (взломали на задаче С) - нужно уметь писать быструю сортировку...
И это своего рода плюс - им есть самостоятельно над чем работать!
Вообще задачи понравились, особенно D.
Большинство вроде на претестах его тоже заметили.
Было бы интереснее, если бы было без претестов на этот камень.
Еще бы претесты чуть послабже и было бы мясо)
Спасибо за контест!
I forgot that I have antiquicksort generator :(
FFFFFFFFFFUUUUUUUUUUUU, I also have anti-java-sort generator :(
qsort(3)orstd::sortsafe?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.
quick sort has random parts, hasn't? so what the hell is Anti Quicksort? :D
По вашей стратегии:
110101101011010110101101011010Мда, это я наркоман, запутал ты меня.
Конечно же второй игрок начинает удалять нули тоже с начала.
00 может получиться, если количество 1 <= ходам Маши.
1 может получиться, если количество 1 + количество ? >= ходам Маши + 2.
01/10 может получиться, если количество 1 + количество ? хотя бы на один больше ходов Маши, но при этом количество уже присутствующих 1 не превышает количество ходов Маши на 2 или больше (иначе только 11 возможно).
Дальше для 01/10 можно смотреть по последней цифре.
Если 0 (или ?, который можно превратить в 0, не сводя к 00) - 10.
Если 1 (или ?, который можно превратить в 1, не сводя к 11) - 01.
Полное решение.
В общем полностью согласен с тем что контест уныло реализационный, причем сложности реализации заключались в нахождении крайних случаев.
Каких характеристик? Ну перебор это да, но не скажу, что 4 цикла сложно\долго писать.
UPD. Упало. Соглашаюсь, я идиот =)
да там писать не многа
я за три решил :P , если не тестировать то можна и за две было
за 00:01:35 :D
Мне одному кажется что тут сидит 4 гоблина и минусуют просто всех?
В семье не без урода:)
UPD. То есть всегда найдутся антиобщественные люди.
Лучше бы не было, я вот сразу перед сабмитом поднял такой тест.
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.
I meant pretests, my problem is that I can't pass even pretest #1
Maybe it is something about compiler versions being different.
I run your program in my machine
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.
Edit: No, wrong theory.
Было бы обидно, если бы решения с голым qsort в C прошли финальные тесты)
Надеюсь, они все упадут, мвахахах!
Спасибо =)
UPD. Через что реализован sort в С++ ?
Объекты сортируются mergesort-ом, а примитивные типы - чуть-чуть улучшенным quicksort-ом, но все же quicksort-ом. Почитай исходники.
Исследования на эту тему:
http://mirror.codeforces.com/blog/entry/2298
n log n, сначала идет quicksort, а когда глубина рекурсии больше n log n - идет пирамидальная
С этим что-то надо делать, а то часами ждать результаты - неинтересно.
вот в этом месте
>>кол-во тестов также оптимально, не мало, но и не так уж много
это утрировано: >>А сокращать кол-во тестов до минимума, в котором будут несколько крайних тестов и еще парочка промежуточных, ну уж, для полноты действа, - не вариант.
ну почему в каких олимпиадах я не участвовал, не было тестов больше 50, а если были, то это было довольно диковино (и что, скажете тесты были неполные????)
ну в задачах типа Д-Е конечно много тестов (<= 100) это конечно вполне норм, но зачем столько в задаче Б(див2), например?
а насчет времени: это не программирование, где константа при оценке сложности не учитывается, в 2 раза ускорить тестирование -это значительное ускорение
11
11
in Div1-D sample tests.
Many didn't pass the pretests because of this.
Если решение укладывается в ТЛ - оно не тленое.
222, у кого
длиннеебольше?А зачем будильник тогда?)
P.s. Опоздал.
Ребят, помогите увидеть где меня ломанули в В. Я слепой не вижу.
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 лежат на одной линии и не могут быть прямоугольником :)
У меня с этим тестом всё ОК, надеюсь, что остальные 200+ пройдёт так же)
Собственно главным преимуществом для данной задачи являлось то, что она сортировала точки по часовой стрелке.
Я всё решал "в лоб"
http://mirror.codeforces.com/contest/136/submission/945918
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
0 100
75 0
96 72
1 1
1 2
2 1
2 2
У первого 4-х угольника есть 2 противоположных угла по 90 градусов, но он не является прямоугольником. Правильный ответ здесь NO, а мое решение выдает YES
Это где же у него 2 противоположных по 90 градусов? Курс геометрии подсказывает, что если два противоположных по 90 градусов, то это и есть прямоугольник...
UPD: да, действительно плохо, больше не буду умничать
Подскажите, а хоть кто-то уложился на C# в задаче "Замена" (задача А в 1 диве) в лимит по времени?
Получилось решить, не сразу выводя в консоль, а сначала в стрингбилдер.
UPD. Но правда с запасом прочности всего лишь 20 мс и 32 МБ съеденной памяти :) Подскажите, как по-правильному? Или по-правильному - переходить на С++? :)
Решение должно ломаться и для меньших чисел из-за сортировки пузырьком.
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.
1. http://paste.pocoo.org/show/518715/
2. http://paste.pocoo.org/show/518716/
really enjoyed the contest, thnx KADR. wish I didn't make a stupid mistake in D :(
В div.2 в задаче D в тесте
0 0
0 1
1 01 1
2 0
2 1
3 1
4 0
ответ должен быть
"YES
3 4 5 6
1 2 7 8"???
Check the part of your code where you check whether it is a rectangle or not.
Thanks.
Я не могу понять как в задаче D div 2 на тест