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

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

Сейчас в Венгрии начинается CEOI 2012 — центральноевропейская олимпиада школьников по информатике. Олимпиада — очень интересная, задачки — крутые, непростые по школьным меркам. По этим же задачам будет проведена интернет-траснляция: первый тур — 09.07.12, второй — 11.07.12, оба тура будут идти с 12:00 до 17:00 по Москве.

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

Регистрация закрывается завтра (08.07.12) в 22:00 по Москве!

Го участвовать?

UPD: (possibly) rules changed this year.

UPD2: you should have recieved e-mail wih password and instructions. Rules indeed were updated.

UPD3: Contest server is veeeery slow so here is the mirror for the tasks (thx to popoffka)

mirror

UPD4: Here is mirror for second day statements (thx to yeputons):

mirror

  • Проголосовать: нравится
  • +42
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А почему "правила — старый IOI"? Под старым подразумевается то, что писать не функции как последние 2 года? Или я что-то ещё не вычитал?

»
12 лет назад, # |
Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Токен — это возможность один раз увидеть полный фидбэк по задаче. В разных версиях может либо регенерироваться через 30 минут после использования, либо просто появляться каждые 30 минут и накапливаться. Нововведение с последних IOI, подробнее можно почитать в правилах IOI 2010/2011/2012.

»
12 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

This year the rules will be different. There will be no groups and the contestants will see the result of theirs submission for every testcase immediately after they submit. There is also a limit on the number of submissions you can make. If I`m correct it is 12.

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    Wow, that's interesting. So the rules placed here are wrong?

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      The new rules were accepted yesterday on the meeting of team leaders and the rules on the web has been changed — actually only two sentences were changed ;-)

      • »
        »
        »
        »
        12 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        And I still can't find any difference on the website :-(

        This remains the same:

        For each task the test data will be divided into batches, with each batch containing one or more test inputs. A test input is solved correctly if the submitted program produces a correct output file within the enforced limits. For output-only tasks test input is solved correctly if the corresponding output file submitted by the contestant is correct. A batch is solved correctly if each of the inputs it contains is solved correctly. Points are awarded only for correctly solved batches of inputs.
        
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          You are right. There are still the old informations... It doesn`t seem that they will manage to update the rules on web before the contest :-(

          It is also possible, that the online contest will run using the old rules...

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

            Anyway thanks. We'll find it out tomorrow.

            If you are a contestant then good luck! Else good luck to all your students ;-)

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Really? If it's true, more people will take part in this contest (because people like me are too lazy to test their submitions well ;) )

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    12 for a single problem or for all?

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Хороший вопрос. Я тоже не понимаю, как хотя бы до тестирующей системы добраться. Давайте, если кто поймёт что да как, отпишется об этом здесь?

»
12 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Почему-то никто здесь не упомянул о пересечении первого раунда с SRM'ом. Кто как для себя решил(решит) эту проблему(для кого-то может и не проблему)??

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    Я лучше напишу 5 часовой контест)Вроде бы полезнее будет)

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    Лучше напишу CEOI в качестве тренировки перед IOI. Хороший контест, этих SRM'ов и так вагон и маленькая тележка, а такой только раз в году, можно и написать.

»
12 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

На почту пришло письмо с паролем и инструкциями.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

У кого-нибудь тестирующая система доступна?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    У меня даже сайт не работает.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Они же вроде врубают её только на время контеста...

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      работает!

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        А пароли у кого-нибудь работают?

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится +14 Проголосовать: не нравится

            Если кто-нибудь достанет задачи, скопипастите сюда, пожалуйста. У меня всё время орёт что неправильный пароль...

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    У меня сайт недоступен...

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Куда заходить, где задачи?

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Как же лагает...

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А contest id = username? У меня при попытке войти говорит "wrong password" =(

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

У меня хоть ты тресни, но постоянно "The password you entered is incorrect."

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    При этом он всё равно показывает username в заголовке... :D

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

      Может это значит что всё-таки залогинилось? Пойду-ка я напишу письмо им...

      UPD: Блин, даже сайт лежит!

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Нет, вроде. Он показывает 3 таска, но при попытке скачать, 2 раза орёт Not logged in!

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +29 Проголосовать: не нравится

И вообще. Может это первый таск — залогиниться в систему.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Пробный тур всегда нужен!

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

С 4 раза залогинился и даже задачи скачались, надо подождать.

»
12 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Мне теперь нравится ограничение "не больше 12 сабмитов на задачу". Послать бы хоть один как-нибудь... :D

»
12 лет назад, # |
Rev. 3   Проголосовать: нравится +24 Проголосовать: не нравится
»
12 лет назад, # |
Rev. 4   Проголосовать: нравится +9 Проголосовать: не нравится

Все таски. Спасибо popoffka .

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Сдавать задачи через stdin, stdout или нет ?

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А таблица есть? Кто-то что-то уже сдавал?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    На IOI-style контестах не бывает таблиц.

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    А таблицы так и не будет ?Неужели "таблиц не бывает" буквально?А списки?

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Будет: участников онлайн после 2го тура, онсайт после закрытия.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    да

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится -9 Проголосовать: не нравится

    Да, но, кажется, сэмплы ваша программа всё равно проходить должна.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      Неправда, у меня в race на сэмпле ассёртится, но баллы набирает.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А 1 тест совпадает с семплом, неизвестно?

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

А сейчас сервер доступен?

UPD: о, снова доступен.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I am unable to access the contest server. Does anyone else have problems?

This is the website url given to me: http://ceoisrv.inf.elte.hu/Day1

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Результат доступен тебе сразу на страницах Result и ShowAllSubmit.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

а) Куда задавать клары? б) Кто-нибудь пробовал печатать? :D

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    1. Не знаю
    2. Zlobober попробовал, никакого эффекта.
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится

      Никакого эффекта у нас — так может у них там на онсайте пошло печататься? :D

»
12 лет назад, # |
Rev. 4   Проголосовать: нравится +1 Проголосовать: не нравится

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

У меня 25-100-40 (ciruit-jobs-race). Что первая, что третья — какие-то неприятные совсем в написании, не нравится мне такое :-\

»
12 лет назад, # |
Rev. 4   Проголосовать: нравится +1 Проголосовать: не нравится

У меня 235:

  • circuit: 45 — квадратом с подгонкой под резалты тестов
  • race: 90 — вроде решил, или баг или могут быть циклы
  • jobs: 100
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Про квадрат с подгонкой:

    • Просто квадрат, где берём отрезок O-точка и проверяем все другие отрезки с 0 на пересечения — если таких всего 2 — эта точка видна.
    • Добавление break, если кол-во пересечений уже 3, не помогло, но тесты стали идти заметно быстрее, но всё ещё TLE.
    • Перебираем другие отрезки не с 0, а с текущего-50. Внезапно взяло 40, пройдя -надцатые группы (видимо там много зигзагов рядом), но не пройдя 4ю.
    • Посколько в 4й группе наверняка ограничение меньше, чем в -надцатых, был наудачу поставлен if — если N <= 10000, начинаем с 0, иначе с текущего — 50. Зашло — 45.

    Поэтому, имхо, говорить полные результаты, где сабтаски не как на IOI, не есть хорошо.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    А как решать race?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    В race ацикличный граф ???

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Там же даже сэмпл с циклами.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Я имел ввиду, не считается ли вдруг путь 1-2-3-4-1 валидным. Хотел задать клар. Но так как у yeputons 100, предположу что таки не мог быть.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

jobs: 100
race: 75
circuit: 85
Как делать race коротко? А то у меня идея на 100 не очень красивая выходит.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Ну у меня вышло так.

    Сначала считаем ДП: a[i][j] — сколько макс. можно сделать этапов, если начать в вершине i и используя следующие j вершин после неё (j может быть и отрицательным, тогда это предыдущие, там всё получается наоборот, буду рассказывать только про следующие).

    a[i][j] = max по к (a[k][длина [i+1..k-1]], a[k][длина [k+1..i+j]) + 1

    Осталось, если можно делать пересечение со стартом.

    Тогда, если мы знаем первую дугу S -> T, то она всё разделит на 2 половины, в ту которую мы зайдём первой, мы можем идти только в одном направлении, потом перейдя во вторую половину, и там уже идти как угодно.

    Зафиксируем T и в какую сторону от Т мы будем сначала идти. Так как в первой половине мы можем идти только в одном направлении, получаем DAG, по которому квадратично считаем для каждой вершины самый длинный путь за который можно дойти из T в неё.

    После чего, возможен такой O(N^4): теперь перебираем и S, а также путь X -> Y. Пояснение общего пути: S -> T -(в одном направлении как-то)-> X -> Y -> ... . Тогда, как дойти до X из T мы знаем, как дойти из Y, можем высчитать за константу по массиву a, и всё прекрасно.

    Сокращаем до куба — не будем фиксировать Х. Если есть S, T и Y, то мы знаем первую половину, и нам всегда выгодно взять такой Х, чтобы он был в ней, есть дуга X -> Y и путь из T в Х — самый длинный. Соответственно, замечаем, что в этих условиях S никак не фигурирует.

    Итого, перед тем как фиксировать S, для каждой вершины Y считаем величину b[Y][k] — максимальный путь до какой-то вершины X на диапазоне T, T+1, ..., k-1, k что есть путь X -> Y. b[Y][k] — это либо b[Y][k-1], либо Х — это вершина k. Получаем O(N^3).

    Красотой это пожалуй не назовёшь, и во время еле заходит. 2 WA.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

В jobs бинпоиск и моделирование?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Да.
    Но я думаю, там M*log(M) не зайдет. Я писал N*log(M): бинпоиск + жадник, то есть фиксирую кол-во, а потом самых старых пытаюсь взять.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Я сломал мозг когда начал писать стек для того чтобы брать самых старых(

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    У меня почему-то 95 и ВА только на первом тесте. Но, наверное, да. Только там надо делать за nlogn + m, но сложности это почти не добавляет.

»
12 лет назад, # |
Rev. 4   Проголосовать: нравится +16 Проголосовать: не нравится

300.

  1. jobs — кэпский бинпоиск
  2. race — сначала решаем для k=0 за куб. Потом делаем четвёртую степень, перебрав первое ребро и ребро, его пересекающее. Потом надо что-то предподсчитать и попихать, чтобы влезло в TL. У меня еще был странный WA, который исчез после оптимизаций.
  3. circuit — вроде как решается стэком. Идём и снимаем-добавляем вершины, но там у меня очень странные условия, поэтмоу был WA на первом тесте, вылечил мержом с тупым решением. Для тестирования: мои тесты и ответы от квадрата (там, правда, иногда бывают нулевые координаты).
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится -13 Проголосовать: не нравится

    Ого, заявочка на золото)

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Как надо было пихать race чтобы получить сотку?

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Мне помогло чуть поиграться с порядком размерностей массивов и в одном месте перебирать только существующие рёбра.

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        И прошло за 4ю?

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    На каких тестах был WA? Мне так и не удалось от него избавиться...

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Может кто нибудь скинуть код(jobs)? Мой бинпоиск почему то не прошло :(

»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

What is the solution to Sailing Race ?

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

    In the beginning we're using dynamic programming: a[i][j] — what is the maximal amount of stages, if we're beginning in harbor i, and are using the next j harbors after i (j can be negative as well, in which case we're using previous j harbors, but the solution will have the same idea, so I'll speak about next harbors only).

    a[i][j] = max by k in [i..i+j] (a[k][length of [i+1..k-1]], a[k][length of [k+1..i+j]) + 1

    This is basically the solution if k = 0, and now we need to deal with the case when k = 1.

    Then, if we know the first stage S -> T, it will divide everything in 2 pieces (at we will visit both of them). In the one we'll be visiting first, we can go only in one direction, otherwise we won't be able to cross to the other piece. Afterwards we will cross into the second piece, and we can go there as we want.

    Imagine we fix T and the side which we will visit first (left or right). Because in that piece we can only go in one direction, we get a directed acyclic graph, for which we can compute for every harbor the longest path from T to it. We can do it for O(N^2).

    Imagine the following O(N^4): we are now fixing not only T, but S and a new path X -> Y as well. The description of a total race is now as follows: S -> T -(in one direction)-> X -> Y -> ... .Now, we know how it is optimal to get from T to X, and we also can calculate for O(1) using previous DP how we need to go from Y.

    Now, let's shorten it to O(N^3). We won't fix X now. If we know S, T and Y, then we know the first piece, and it is always optimal to choose such a X, so that it is in the first piece, the edge X -> Y exists and the path from T to X is the longest possible. We can notice that in that condition S doesn't figure at all.

    So, before we fix S, for every harbor Y we calculate b[Y][k] — the maximum path to Y from some harbor X, where X is in interval {T, T+1, ..., k-1, k} and there exists a path X -> Y. b[Y][k] is either b[Y][k-1] or we get a new optimal X = k. Now all three parts of the case k = 1 are O(N^3).

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +22 Проголосовать: не нравится

      Actually,If we fix T and X,then you can see the closer S to X the better it is,so we just fix T and X and get the optimal S and enumerate Y to solve it..It's also n^3 and easy to write down.

»
12 лет назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится
»
12 лет назад, # |
Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

Кстати, кто-нибудь может объяснить, что подразумевалось под subtask'ом в jobs M <= 100000? У меня сначала было подозрение, что они хотели за M log M давать 40, а за линейку 100....

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    M*log(M) заломать, видимо.

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      У меня и есть M log M, сорри, я просто у себя поменял обозначения констант.

      UPD: При этом заходит с большим запасом: 0.3 секунды.

»
12 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

The problems are interesting~but the server condition is too bad T_T...I always need to wait several minutes to fresh the page. T_T...could it be better in day2? (Maybe it's only in China...)

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Так как сегодня второй этап прошу объяснить. Если я напишу один сэмпл, то я должен получить один бал? А если на примере jobs я вывожу правильно только кол-во машин, то получаю 40?

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    Сэмплы, вроде-бы, не добавляют.
    В случае когда можно получить часть теста, то тест разбит на 2 части, каждая из которых оценивается отдельно(это в протоколе сдачи можешь посмотреть).

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Нового письма мне не пришло. У всех так?

»
12 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Таски добывать будем не как в первый день, я надеюсь...

»
12 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

Пацаны) Ни пуха

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Сервер снова тормозит?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Мне кажется, он просто не поднят.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    404 у меня

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    На этот раз его вообще пока не включили. Впрочем, разница между тем, когда он включен и нет — довольно невелика.

»
12 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

У всех 404 при попытке зайти на сайт?

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is anyone able to access the Day 2 site? I get HTTP Status 404

»
12 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Ну что за .hu

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

О, что-то начало загружаться.

»
12 лет назад, # |
Rev. 4   Проголосовать: нравится +28 Проголосовать: не нравится

The server is up now. All three problems are available here.

UPD: sample.zip for the 'highway' problem is added.

»
12 лет назад, # |
  Проголосовать: нравится -29 Проголосовать: не нравится

How to solve highway?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I mean because of input and output.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      people don't have time to answer "Yes". they just "-" the comment. so number of "-" = number of participants already solved the problem)

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Waste Recycling: can we move first wagon the auxiliary track ??

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain how to write Highway program? I created main.cpp, included "office.h", wrote my function which calls functions from office library, and uploaded — now I got "Compile time error". What is wrong? If anyone knows, please answer. Thanks in advance

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

По сколько баллов оцениваются тесты в highway? Там 20 тестов, по условию по 4 балла максимум. Как 100 набрать?

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Неизвестно. Меня ещё напрягает фраза "Your answer is only accepted if it is implied by the queries previously performed by your program.". Либо я что-то забагал так, что это не ловится на рандомных тестах, либо их грэйдер иногда считает, что я угадал ответ...

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Да, я добавил один лишний запрос, который по мне является очевидным — AC вместо WA.

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Так по ней сотню не набрать никак?

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Может они потом сделают пропорцию до 100...

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Очень надеюсь, что на онсайте творится такой же кошмар и кто-нибудь достучится до жюри.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    А у кого-нибудь вышло получить что-нибудь отличное от 1/1 Correct на каждом тесте? Меня вот эта единичка справа от косой черты смущает, как, впрочем и максимальное количество баллов 20 в тестирующей системе.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      У меня вышло 80/20.

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        А, то есть вот это /20 никакой смысловой нагрузки не несёт. ОК, спасибо :-)

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      У меня двоечки бывали, но единичка справа неизменно стоит тоже)

»
12 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Кстати, пока хочу похвалить сервак. Работает шустро. Тьфу-тьфу. :D

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Как-то тесты сегодня не очень сделаны. Жаль.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What does mean An Error Occurred: java.lang.NumberFormatException: For input string: "0.000"

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It's Russian branch, don't forget to switch the language.

    It means that your system's locale sets ',' as a decimal separator. You need to change it inside your Java program (something like Local.setDefault(Locale.US););

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      Есть одна проблема. Такая ошибка вылезает на сервере при попытке что-нибудь отсабмитить :-\

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      my program is not Java.

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I am solving this kind of problem first time and I dont know what's wrong with my program my code look like

#include <stdlib.h>
#include <iostream>
#include <string>
#include "office.h"
#define MaxN 100001L
using namespace std;

main()
{
 int n, i, j, k, b1, b2, t = 0, a1, a2;
 n = GetN();
 /*
  if(isOnLine(i, j, k))
 */
 Answer(a1, a2, b1, b2);
 return 0;
}
}

server is giving An Error Occurred: java.lang.NumberFormatException: For input string: “0.000”

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Try to define a1, a2, b1 and b2, just to be sure, maybe? 0 isn't a valid argument for that funcion. Like 1, 2, 3 and 4. That's my best guess — I haven't experienced those errors. My last submission on this task was done some time ago though — at 12:10:46 (Hungarian time — 02:10:46 after contest has started).

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Does it give you 20/20? Because I got 20/20, dunno what it means. Is it completely correct?

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        No, maximal score that you can achieve is 80/20. The test&grade system is very strange, slow and buggy.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

what does mean undefined reference to 'GetN()' ?

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

Attention please! Contest was extended for 15 minutes — till 13:15 UTC!

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Как можно умудриться в вагонах, не проходить первую часть теста, но проходить вторую?

UPD: Это чудо уже как-то исправил. Черкер у них там странный.

  • »
    »
    12 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Можно, знакомо. Контест еще не окончен!

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

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Потому что, кажется я знаю, что его сломало — расскажу после контеста.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Итак, всё чем отличались 2 моих сабмита по wagons: это я вместо 0 во второй строчке выводил 1.

      Когда я выводил 1 на некоторых тестах: за первую часть WA, за вторую AC. Когда 0 на тех же тестах: на обоих AC.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Кто-то знает как решать вторую и второй субтаск третей?

»
12 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Поздравьте меня с первыми баллами)Мне нравиться сдавать задачи не решив их)

»
12 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Говорим результаты?

  • highway: 80/80
  • network: 100/100
  • wagons: 80/100 (Я не знаю что я там под стрессом написал в последние полчаса, но это явно много и 80 очков никак не должно набирать. Сейчас подсчитаю.)

UPD: Посчитал. O(N log N * S^2 * 10). Ну точно не должно заходить на 80. Согласен с yeputons по поводу тестов.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    • highway 80/80
    • wagons 20/100 (для случаев когда все можем сделать за день или два)
    • network 40/100 (первый субтаск; довольно просто получилось сделать через конденсацию)
»
12 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

Задачи интересные, но слив.
1я(highway)). 80
2я(wagons)). 70, несколько ВА и несколько ТЛ. Пол контеста не видел что нужно, что-бы в ангаре ничего не осталось (то есть решал другую задачу). Писал бинпоиск по ответу.
3я(network)). 24 — капец, почему у меня подвешивание дерева не прошло на 40? Ведь ответ это размер поддерева вершины в которую идет самое дельнее обратно ребро поддерева вершины?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Не думаю. Для теста

    5 4 1
    1 2
    1 3
    3 4
    3 5
    

    Ответ

    5 1 3 1 1
    3
    5 1
    4 3
    2 1
    
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      У меня так и выводит.

      • »
        »
        »
        »
        12 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        Тут есть одно отличие от поиска мостов. Нас интересует вершина с самым маленьким номеров (в нумерации DFS), по которой можно добраться из данной вершины но не обязательно по одному обратному ребру.

        Например:

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

        Ответ: все 4ки.

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

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Про network. Это неверно, поскольку мы можем сначала пойти вверх, потом вниз, потом опять вверх. Утверждается, что, если запускать ваш алгоритм log n раз, то он найдет правильный ответ. Разумеется, после каждого запуска надо обновлять данные.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    network: Неправда, что самое дальнее обратное ребро даёт нам ответ для вершины. Сходив по этому самому дальнему обратному ребру мы можем чуть-чуть спуститься и снова прыгнуть по обратному ребру, не дойдя до вершины x. Например тест: (1 2), (2 3), (3 4), (3 1), (4 2) — на нём для четвёртой вершины самое дальнее обратное ребро — это (4 2), но ответ для этой вершины — не 3, а 4, потому что из неё можно добраться до корня: 4->2->3->1.

    Я после насчитывания этих величин (самое дальнее обратное ребро из поддерева) ещё и релаксировал их до упора рекурсивной процедурой, чем-то напоминающей сжатие путей в СНМе — если в поддереве конца этого самого глубого ребра для вершины x есть ребро, ведущее ещё выше, то говорим, что мы можем сходить ещё выше.


    int mup(int x) { return up[x] == x ? x : (up[x] = mup(up[x])); }

    Вторую часть подзадачи решал схожими соображениями (yeputons сейчас напишет ниже, наверное).

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

highway: посмотрим на первые пять элементов. Среди них хотя бы один запрос ответят YES. Теперь рассмотрим один элемент из этой тройки (A), а все оставшиеся разобьём на пары. Сделаем N/2 запросов. Если на какой-то ответ "NO", то еще за один запрос определим, который из пары не лежит на одной прямой с A.

wagons: пусть мы выбрали настройки 1 2 3. Тогда структура ответа такая:

  1. 1 вперемешку с 3

  2. 1 вперемешку с 2

  3. 2 вперемешку с 3

Переберём тип 1, найдём первый не-1, переберём его тип (не более 10) — это будет тип 3. Посмотрим на первый не-1 и не-3, переберём его тип (не более 10) — это будет 2. После этого ответ за O(N). Итого получается O(S·10·10·N) = O(2·109), что проходит, потому что не достигается на тестах жюри.

network: сейчас напишу

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    У меня в вагонах получилось структура (за 1 обозначу только последнюю единицу, остальные могут быть где угодно слева от неё): (группа 3) (группа 2) 1 (2 и 3 как угодно). Может мы говорим об одном и том же, но на взгляд, у меня нет этапа 1 вперемешку с 2 3.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Ровно то же самое. (группа 3)(группа 2) + "остальные могут быть где угодно слева от неё" = то, что я сказал.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Киньте код wagons, а то не пойму

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    network:

    1. Разбили на компоненты сильной связности

    2. Получилось дерево (потому что путь из корня всегда единственен)

    3. Посчитали dfs'ом ответы на первую подзадачу

    4. Посмотрим на общий вид требуемых графов. Утверждаю, что это какой-то кактус (никакие два цикла не имеют более одной общей вершины, доказывается достаточно просто).

    5. Заметим, что каждая сильносвязная компонента представляет собой кактус.

    6. Теперь добавляем в ответ следующие ребра: обошли от каждой вершины по ребрам, идущим между разными компонентами. Получилось дерево, которое надо сделать сильносвязным кактусом.

    7. Про дерево: рекурсивно делаем счастье. Надо из каждого листа сделать ребро в самого высокого родителя так, чтобы не возникло пересечений циклов.

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      За (n+m)log n можно проще.

      1. Обойдем граф dfs-ом. Теперь для каждого ребра, которое не лежит в дереве dfs-а выполняется, что оно ведет от вершины к ее предку в дереве.
      2. Посчитаем самую верхнюю вершину, которую мы можем достичь двигаясь сначала вниз по дереву, а потом вверх. Это тоже простой dfs. В нем мы пользовались массивом top, где top[i] — самая высокая вершина, доступная напрямую из вершины i.
      3. Заменим массив top на посчитанное значение для каждой вершины. Повторим log n раз. На каждой итерации top[i] — вершина, доступная при движении вида (вниз по дереву — вверх по ребрам, не принадлежащим дереву) повторенному 2^step раз. Это очевидно доказывается по индукции. Тогда в итоге мы получим лучший ответ.
      4. Ваш пункт 7.
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        Я кажется пункт 3 сделал ещё одним DFS. На входе в вершину смотрим на оригинальное значение top[i] (один раз вниз — вверх), и если top[top[i]] < top[i], то обновляем его. Таким образом мы за один DFS получаем значения для путешествий по сколь угодно обратным рёбрам.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Задача highway убивает. Почему-то очень часто было 20 WA. Довольно странно, на мой взгляд, не рассказывать про логику тестирования. У кого-нибудь есть за нее полный балл? Расскажите, пожалуйста, как вы этого добились. Еще интересно, как решать wagons и можно ли решить network за линию?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    network можно, я решил, сейчас напишу.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Я написал network за O(V+E), ТЛ на двух последних тестах. Есть решение, которое не надо загонять в ТЛ?

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Моё зашло меньше, чем за 0.1. Возможно, вектора или что-то такое?

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Присоединяюсь, у меня 0.04 секунды максимально.

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Я оставил вектора только в графах, может быть, правда, make_pair тормозит.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      У меня зашло O((V+E)log V). Но только после избавления от векторов.

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

My solutions: wagons, highway, network

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I terribly sorry, but can you also upload your solutions from Day1. Thanks in advance :) And, as I understood from the Russian version of the thread, congratulations for your top scores in both days, a really amazing achievement!

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Thank you.

      My solutions for the first day: jobs, race (it works about 6sec on my computer), circuit (it doesn't work well, I got AC by merging it with the naive solution).

»
12 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

Я так понял, что yeputons надо поздравить с максимумом!

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Спасибо :) Надеюсь, баллы по highway всё-таки отмасштабируют.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Интересно, если они таки отмаштабируют, что они с дробными резалтами сделают? Отмаштабированные вроде должны быть с точностью до четвёртых пункта.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It seems that the time limit for networks is a bit tight. I wrote an O(V+E) solution but I got TLE for the last testcase =(

My solution is in the link below: http://pastebin.com/A5aP29fD

Any idea how I can improve it?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    My bet is that the excessive use of STL structures might be guilty.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      In that case, then it means that the time limit really is tight =(

      How do you reduce the number of STL structures? For example, I believe I need to use adjacency list to represent the graph, so I believe I will need a vector for that.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А когда после первого тура были результаты?

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The results of the 2nd day. I will make the total results when CF ends.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Well, the maximum score for highway is still 80. I'm fully disappointed by organization this year.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    А в памятке написано что все задачи по 100 баллов?
    Или может они эту задачу специально так и сделали?

»
12 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

The total standings of CEOI 2012 online contest. Everyone with a score of 0 on both days is omitted from the table.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tomekkulczynski на 54-ом месте?

»
12 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Onsite Results
Why the best bronze is better then worst silver?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Also, for the onsite the maximum seems to be 600 (at least 595). And I would like to know the task order used in that table.

    On the other note, judging by onsite results, this CEOI can be counted as relatively easy compared to the earlier ones.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    This is what I found on topcoder forum:

    "Yes, they are final. During the second day of the contest there were serious problems with problem Highway: problems with library — it was impossible to compile it; until the last hour of the competition the grader told most people had only 60 points even if their solutions were correct and maybe more problems i don't know about.

    This issue was a reason to change the classical distribution of medals. It worked as follows: Each contestant recieved a medal for the first day only (according to classical rules) and for the total score (in the same way) and finally he was assigned better of these two medals. This is also the reason why a person with less total score can have better medal."

    link: http://apps.topcoder.com/forums/?module=Thread&threadID=753938&start=0&mc=3#1569751