Первый отборочный тур в ЗКШ-2012

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

Автор Nadin, 12 лет назад, По-русски

Всем привет!
17 декабря пройдет первый отборочный тур в Зимнюю компьютерную школу для школьников 10-11 классов. Приглашаем всех желающих принять в нем участие. Контест будет состоять из 6 задач. Условия задач будут доступны на русском, английском и китайском языках.

Время начала тура: 16:00 (мск). Продолжительность: 3 часа.
Правила тура
Регистрация на тур

Желаем успехов !

Nadin
12 лет назад
64

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

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

iama

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

← Rev. 2 →

Спасибо за напоминание

→ Ответить

x1te

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

← Rev. 2 →

ОГРОМНОЕ спасибо за информацию. А есть инфа когда ЗКШ проходить будет? Перед заочкой или же на зимних каникулах?

UPD. Не заметил инфу большим шрифтом в самом верху страницы. перед заочкой - это в стопицот раз круче чем на зимних каникулах! :D

→ Ответить

CherryTree

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

← Rev. 2 →

Может ли кто нибудь рассказать что из себя представляет ЗКШ, можно ли в нее попасть не россиянину, насколько сложно туда отобраться, можно ли участвовать не во всех отборочных турах чтобы пройти (завтра, например, COCI в то же время) и дорого ли туда поехать?

→ Ответить

iRomchig

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

В прошлом году все, у кого был выше 2-го диплома на вкошпе, денег не платили вообще. Школа длилась две недели. Обучение состояло из контестов формата acm и лекций(некоторые были связаны с олимпиадным программированием, некоторые нет). Проживали мы в аспирантской общяге мфти. Мне лично школа понравилась)

→ Ответить

iama

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

Контесты же личные?

→ Ответить

yeputons

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

← Rev. 2 →

А есть ли кнопка "восстановить пароль к аккаунту ejudge"?

→ Ответить

sdryapko

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

А регистрироваться надо только в ejudge?

→ Ответить

Hohol

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

Монитор есть?

→ Ответить

zurg

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

← Rev. 2 →

UPD: теперь есть http://ejudge.innolab.net.ru/problems/000004/standings/standings.html

→ Ответить

maslowmw

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

Интересно, что за тест 52 в первой задаче...

→ Ответить

zurg

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

Тест такого вида:

64009

*: C p, q.

*: Q F, ALD.

*: s q.

*: x, g S, W T.

*: HC, cO.

*: y d.

*: d b, r.

*: c, h V, Q u.

*: N A, bkK.

*: M V, xJ.

*: i A, w.

*: DB, TjQ.

*: S j, Q U, Z N.

*: J U, N O, n.

......

Всего одна команда. Много раз. Имена из 1, 2, 3 символов.

→ Ответить

maslowmw

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

Не вижу подвоха в этом тесте)

→ Ответить

zurg

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

Однако чекер так не считает и говорит следующее:

wrong answer 38th line differ - expected: ' h, 394.', found: ' k, 394.'

→ Ответить

zurg

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

Запустил локально. Ошибка следующая:

должно быть

....

h, 394.

k, 394.

....

а у Вас

....

k, 394.

h, 394.

....

Т.е. при равенстве количества участий одного участника Вы не сортируете лексикографически участников.

→ Ответить

maslowmw

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

Нормально я так ошибся) гг

→ Ответить

iama

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

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

→ Ответить

maslowmw

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

не знаю, у меня локально сортируется

→ Ответить

maslowmw

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

А там точно местами различаются? То есть оба участника есть, но в разном порядке?

→ Ответить

zurg

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

Да. В этом тесте в двух местах (при равенстве участий в неправильном порядке) именно по два подряд не правильно.

→ Ответить

SkyHawk

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

Надо учить Java =)

→ Ответить

zurg

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

Можно просто длинную арифметику)

→ Ответить

SkyHawk

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

Лень. Лучше джаву) Да и полезней.

→ Ответить

AlexanderBolshakov

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

Лучше то и другое - некоторые задачи BigInteger'ом в лоб и даже в зад не берутся.

→ Ответить

pkhaustov

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

-6

Как одному из неудачников контеста, хочется знать, как же решать задачу B. Мне удалось дотолкать читосол до 96 теста, на большее времени не хватило.

Почти полезная информация: Задача E оказалась сдаваемой на C++. Длинка на динамической памяти по 9 разрядов прошла без пропихиваний.

→ Ответить

Jughead

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

B: за O(M + 3^N), предподсчитываем для маски была у нас или нет, а дальше ДП по маске, выдираем подмаску данной маски и смотрим ответ для получившейся.

→ Ответить

Eledven

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

Задача В - для каждой маски букв сохраним максимальное по длине слово, в которой присутствуют только эти буквы и только один раз. Дальше динамика f(mask) - максимальный выигрыш для текущей маски буков. Переход - перебираем подмаску нашей маски, запускаемся от f(mask ^ cmask), cmask - текущая подмаска. Получаем O(3^n + количество слов)

→ Ответить

pkhaustov

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

Блин... Я считал, что это TL :) Оказывается это имеет оценку O(3^N).

→ Ответить

tunyash

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

← Rev. 2 →

А архив жюри будет доступен? Или дорешка.

→ Ответить

zurg

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

Уже есть дорешивание.

→ Ответить

iama

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

Не подскажете 6-ой тест в А?

Ну, или почему этот код - получает ВА на нем.

→ Ответить

zurg

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

← Rev. 2 →

100000

: a.

(аналогично до конца файла)

Название команды - пробел.

→ Ответить

iama

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

У меня gets не считывает первый пробел, потому и ВА. Не знаете, почему так?

→ Ответить

zurg

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

Наверно из-за строчки scanf("%d\n", &n);

Лучше так не делать.

Рекомендуется делать следующим образом:

#define nextline() {int c; while ((c = getchar()) != 10 && c != EOF);}

.....

scanf("%d", &n);

nextline();

....

gets(s);

→ Ответить

Hohol

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

Ужос. А кто знает, каким фигом тот сканф мешает читать гетсу? Не вижу никакой логики.

→ Ответить

PavelKunyavskiy

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

команда scanf("\n") ровно как и scanf(" ") считывает все пробельные символы начиная с текущей позиции.

→ Ответить

Hohol

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

Спасибо.

→ Ответить

iama

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

И вообще, побитовые чекеры - зло.

→ Ответить

PavelKunyavskiy

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

Я обычно тогда все читаю gets'ом, а числа достаю из него sscanf.

→ Ответить

Furko

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

А можете дать 15 тест на задачу Е?

→ Ответить

zurg

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

Там нужна длинная арифметика (какой-то большой тест).

→ Ответить

Furko

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

а дорешивание будет?

→ Ответить

zurg

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

Уже есть.

→ Ответить

Astekinane

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

Можно 9ый тест на задачу B, раз такое дело.

→ Ответить

zurg

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

Уже есть дорешивание.

→ Ответить

vlad107

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

Расскажите кто-нибудь как решалась D.

→ Ответить

Jughead

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

В этой задаче необходимо было использовать структуру декартово дерево по неявному ключу, хранить в узлах дерева хеш поддерева. Информацию можно почитать вроде бы на e-maxx.ru

→ Ответить

Sereja

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

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

→ Ответить

Jughead

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

Хороший вопрос, мне вот почему-то проще с декартовым написать.

→ Ответить

zurg

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

Возможно пройдет. Можно попробовать дорешать.

→ Ответить

Furko

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

а как понять, прошол ли ты 1-й раунд или нет?

→ Ответить

Nadin

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

-6

Да, тур прошел. Результаты здесь: http://ejudge.innolab.net.ru/problems/000004/standings/standings.html

→ Ответить

x1te

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

А сколько человек проходят в ЗКШ?

→ Ответить

x1te

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

← Rev. 2 →

-13

Просто слив... Почему нет компилятора delphi? Это же жестоко - сдавать под fpc и иметь +2 по задаче С не из-за алгоритмических ошибок и откатиться на 10 мест из-за штрафа -_- А задача А.... Глупая реализация, в которой у меня не работает qsort(WTF?!?!??!??!? WHY!?!?!?!??!?!?!), при этом ошибка больше похожа на баг в компиляторе уже у меня на компе. Может, пожалуйста, кто нибудь посмотреть мой код? Я понимаю, он немного нечитаем... Но заранее спасибо :D Хотел написать задачу Е - но понял, что длинка и отбросил эту идею :D

→ Ответить

AWPRIS

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

← Rev. 2 →

+11

Это не баг в компиляторе - это специфика FreePascal:
Функция

function less(a1, a2, b1, b2: string): boolean;
begin
  result:= false;
  if a1 < b1 then result:= true else
  if a1 > b1 then result:= false else
  if a1 = b1 then begin
    if a2 <= b2 then result:= true else result:= false;
  end;
end;

применительно к реализации на FPC должна выглядеть так:

function less(a1, a2, b1, b2: string): boolean;
begin
  less := false;
  if a1 < b1 then less:= true else
  if a1 > b1 then less:= false else
  if a1 = b1 then begin
    if a2 <= b2 then less:= true else less:= false;
  end;
end;
Т.е. во фришнике не используется для возврата значения функции 
переменная result - в этом одно из отличий FPC от Delphi.

→ Ответить

x1te

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

← Rev. 2 →

Спасибо!

Ато я полтора часа промучался, перезагружая компьютер. Решение-то правильное! Хоть и написанное в спешке, и код совершенно нечитаем :D Огромное спасибо, что разобрались в коде. Сейчас попробую переписать и сдать.

UPD. Код все равно не работает. Строчка

if i < last then qsort(i, last);

мигает красным при зажатой клавише F8. Все-таки, как мне кажется, тут есть два варианта.

Либо это баг в дебаггере/компиляторе, либо это уже ошибка в коде ДНК.

→ Ответить

AWPRIS

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

qsort просто нужно писать самостоятельно - компилятор его не находит в подключенных в системе библиотеках... :)

→ Ответить

x1te

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

Ну... Я самостоятельно его и написал. :D Что-то непонятное творится с delphi... Ну ничего, завтра высплюсь - и найду ошибку)

→ Ответить

KAN

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

Если дописать ключ "mode delphi" в начале, то будет и первый вариант работать

→ Ответить

Sereja

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

Иногда бывает что и 2я реализация не будет работать, то есть функции можно присвоить значение только один раз(возможно на новых версиях паскаля уже не так).

→ Ответить

sdryapko

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

Обязательно ли учавствовать в отборочных турах, чтобы попасть на ЗКШ?

→ Ответить

sdryapko

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

Что надо указывать в анкете регистрации на ЗКШ в графе телефонный номер, если я из Беларуси?...там написано, что надо указать 10 знаков, а у нас получается 12.

→ Ответить