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

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

Завтра на CodeChef короткий 2.5 часовой контест. Здесь можно его обсудить, а мне интересно как переводится индийское время в московское (т.е. во сколько по Москве начинается контест).

UPD: Информация для тех кто ни разу не участвовал в Codechef (я сам участвовал один раз). Формат там очень похож на ACM, полное онлайн-тестирование (на всех тестах). В марте было 5 задач, думаю там обычно всегда так. Вместо вердиктов AC, WA, TL и прочих приходят прикольные картинки (если навести мышкой на картинку, то всплывает письменный вердикт). Ввод/вывод стандартный, скорее всего будут multitestы в хорошем формате, т.е. сначала дано количество тестов потом сами тесты. Вообще у них достаточно удобный интерфейс.

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

14 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
В 8 вечера вроде бы
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
а как войти то на сайт? я что ни набираю в поля login password мне никакого ответа страница не даёт, всё равно кнопки login / signup светятся. что в opera что в chrome
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ну сначала зарегаться надо на http://www.codechef.com/user/register/, а потом только login. Ну после подтверждения почты конечно.
    • 14 лет назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится
      Спасибо кэп. Ты действительно считаешь что я полный даун? Ну конечно же я зареган там. Насколько я понял у меня был какой-то временный пароль срок действия которого истек. В общем запутанная там система. Ну и поведение сайта достаточно странно, он не ругается на то что вы ввели неверный логин/пароль, а просто делает вид что ничего не происходило.
      • 14 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Извини я не думаю что ты даун. Просто люблю кепские шутки :-) (посмотри пониже ещё одна)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Регистрироваться на event нужно или достаточно быть зарегистрированным на сайте?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
а где можно посмотреть монитор?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Я что-то не понимаю одна коробка может быть покрыта более чем одной резинкой в задаче PACKBAND?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    Нет, не может. Каждая резинка может быть использована только для одной коробки, а каждую коробку можно обвязать не более чем одной резинкой.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А что тогда значит это: "A box needs at least one rubber"?
      • 14 лет назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится
        Ну я понял так, что коробка не развалиться на куски, если ее обвязать хотя бы одной веревкой.
        • 14 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится
          Блииин лано спасиб
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Блин я готов материть этот грёбанный линух часами. Я час не мог понять почему у меня не проходит задача. Думал уже что неправильно понимаю условие. Думал что я ваще не то решаю а там нужно %lld вместо %I64d. Бл..........
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Я, как и все кому не лень, сегодня сдал 4 задачи, но ни в одной из них не потребовался long long. Ну в задаче про коробки вычисления были близки к пределу int'а, но все-таки ответ-то хоть как влазит в int.
            • 14 лет назад, # ^ |
                Проголосовать: нравится +5 Проголосовать: не нравится
              Я в задаче про коробки считал всё в целых числах поэтому там вроде могли быть переполнения. Максимальное число вроде 100'000'000*2*22=4'400'000'000
              • 14 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Но выводить это число вроде не надо.
              • 14 лет назад, # ^ |
                  Проголосовать: нравится +5 Проголосовать: не нравится
                Но считывать то можно было инты....
                Вот у меня прошло решение, тоже которое получило WA. Я час его стресил парсочем, потом в конце еще раз посабмитил... и почему то прошло, хотя до этого абсолютно идентичный код получил WA...
                • 14 лет назад, # ^ |
                    Проголосовать: нравится +13 Проголосовать: не нравится
                  Гер там можно смотреть свои субмиты. Можешь взять старый и сделать fc. Я просто scanfом читал и массивы сразу сделал логовыми, поэтому такой треш вышел.
              • 14 лет назад, # ^ |
                  Проголосовать: нравится +3 Проголосовать: не нравится
                Я тоже считал в целых. Сам посмотри:
                2 * 22 * R1 / 7 <= 4L <= 2 * 22 * R2 / 7
                Разделим обе части на 4 и умножим на 7:
                11R1 <= 7L <= 11R2
                Бабах, и никаких переполнений!
                • 14 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  Я подумал проще ничего не сокращать и просто в лонгах всё посчитать и ничего точно не переполнится.
              • 14 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Можно было обе части неравенства
                2 * K * R1 <= 4  * L <= 2 * K * R2
                сократить на 4, и тогда переполнений не будет.
              • 14 лет назад, # ^ |
                Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                Не туда ушло.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Кто знает, как делать 5ую?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Подскажите пожалуйста, что неправильно в моем решении задачи про кубики и ленточки? Вот оно. Мое решение - алгоритм Куна + жадность(когда-то прочитанная в статье на e-maxx.ru). Вердикт - wrong answer.

14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Просто из интереса, назрело два вопроса:
1) Зашел ли у кого-нибудь на задачу про коробки алгоритм Куна?
2) Зашел ли у кого-нибудь на задачу про коробки алгоритм Диница?
Сам решил эту задачу жадностью, правильность которой зачем-то сидел и доказывал себе на контесте.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Кун не зашел, Диниц тоже :-(. Но тут нужно учитывать мою криворукость.

    А как можно паросочетание жадностью сдать?

    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      жадно некоторые ребра добавить в паросочетание , а потом кун
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        у меня это не прошло, честно говоря сомневаюсь, что задча решается куном
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Паросочетание жадностью никак не сдашь. Здесь граф достаточно специфичный в этой задаче. Собственно сам граф тут строить не обязательно.
      Ладно, расскажу решение (тем, кто еще сам хочет подумать, лучше не читать дальше):
      Отсортируем все коробки по длине стороны (в порядке неубывания).
      Отсортируем все резинки в порядке неубывания R2, а при равенстве в порядке невозрастания R1.
      По очереди (в порядке сортировки) для каждой коробки будем выбирать самую первую резинку, которая ей подходит (в порядке сортировки).
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      но это не прошло у меня
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        По времени?
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          естественно
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Достаточно просто придумать тест, где будет полный двудольный граф. Так как алгоритм Куна работает в общем случае за O(NM), то это явный TLE. Другое дело, что если такие решения все-таки умудрялись получить Accepted, то можно было бы говорить о неполных тестах.
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Кун на полном графе летает, интересный кстати вопрос на каком тесте Кун будет достигать этой оценки
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Ради интереса решил затолкать паросочетание в ТЛ. Такое проходит за 2.59.
    • 14 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      Я тоже для интереса потолкал, без рандом-шафла за 0.95 проходит =)
      Видимо рандом шафл дольше чем кун работает =)