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

Автор goryinyich, 13 лет назад, перевод, По-русски

Всем привет!

Я автор сегодняшнего раунда.

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

Хочу поблагодарить Артема Рахова за неоценимую помощь в подготовке раунда, Марию Белову за перевод задач, Михаила Мирзаянова за отличную систему CF и всех участников за то, что не оставляют это событие без внимания.

Больше полных решений и высокого рейтинга всем! gl & hf

UPD: Раунд завершен, поздравляем победителей и призеров обоих дивизионов!

Div-1
3. Egor
6. Coder
8. neal
9. WXYZ
10. whhone

Div-2
2. songlj

UPD: Опубликован разбор задач. По техническим причинам русская версия разбора будет опубликована позднее.
  • Проголосовать: нравится
  • +90
  • Проголосовать: не нравится

»
13 лет назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится
Thanks for preparing this round! Good luck to all the participants :-)
»
13 лет назад, # |
Rev. 2   Проголосовать: нравится -13 Проголосовать: не нравится

Hi Sergei!

Thank you for your round. This event help me to rest and relax of boring examinations. I suppose that the problems is good and I'll get enjoy of this round.
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
может все таки в английской версии сайта разместить английскую версию, а тут русскую? 
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    Unfortunately, I don't have russian keyboard at the office =(((
    • »
      »
      »
      13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

      Привет!

      Я автор сегодняшнего раунда.

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

      Я хочу поблагодарить Артема Рахова за неоценимую помощь в подготовке раунда, Марию Белову за перевод задач, Михаила Мирзаянова за отличную систему CF и всех участников за то, что не оставляют это событие без внимания.

      Больше АС и высокого рейтинга всем вам!

      Ctrl+C, Ctrl+V
»
13 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится
На этот раз не повторятся ошибки раунда #78, я надеюсь.
»
13 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится
При регистрации вместо правил - их HTML код
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Это будет первый мой КФ раунд после НГ... постараюсь не тупить и нормально отрешать хотя бы потому что это последняя тренировка перед областной)) Удачи всем
  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    18-ого января есть еще CFR 103(div 2) и 14-ого числа ИОИП с условиями приближенным к областной, если не 11 класс, то можно просто поучаствовать(по ссылке все сказано).
    А так - удачи :)

    UPD: не посмотрел страну в профиле, я подумал об областной в России, а не в Белоруссии.

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      я ж из Беларуси, у нас с 16 января область так что только ИОИП ну и всё пожалуй...

      P.S. ИОИП? Не, не слышал... =)
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    К ней лучше готовиться IOI-стайл контестами все же.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Тоже область будет 16-ого, только Брестская.
    Удачи вам :)
»
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Спасибо за новый контест) Обязательно поучаствую. Всем удачи!
»
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Thanks for this contest!!! I'll enjoy it =)  good luck and more AC to all !
»
13 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится
Thanks for the preparation! It's your efforts that will give us a meanful night (in my nation) !
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    orz npc                                                                                                        langren...
»
13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
Какая разбалловка?
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Очередной рекорд по участникам в див2 :)

p. s. Хотелось бы что бы это не сказалось на системе.
  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    да в 100 раунде тоже был рекорд по регистрации - 2800, а участвовали 1800 вот вам и рекорд

»
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Можно узнать почему раунд на 5 минут сдвинули?
»
13 лет назад, # |
  Проголосовать: нравится +59 Проголосовать: не нравится
+5 mins. Why? :) The contest is running away from us D:
»
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

див2 бежит впереди паровоза - время до начала раунда див2 на 1 сек меньше, чем див1

P.S. пока писал , пофиксили

»
13 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится
Maybe the contest is scared :)) Anyway,good luck everybody :D
»
13 лет назад, # |
  Проголосовать: нравится -48 Проголосовать: не нравится
Опять та же история.
Возвращайте приставку Beta.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится
    на тс тоже такое бывает...в последнее время...но там никто не собирается возвращать приставку Beta.
»
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

participants > 2000 in div2

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
в С на тест 9 9 ответ 14?
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    Надеюсь, что 13 =)
    А у тебя 14 получилось? Можешь показать замощение?
    • »
      »
      »
      13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      блин(( я конь( не заслал правильное решение... пойду убьюсь ап стену

      P.S. ну правда читерское решение прикалком, так что ниче страшного))

      а вообще эта задача и расчитывалась на перебор? или дп по профилю?

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Похоже действительно 14 :(
      • »
        »
        »
        »
        13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        почему? можете замощение показать?

      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится
        ....эм..странно, когда я взламывал, писало, что 13.
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
          Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

          Значит неправильное решение у KADR =)

          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Ага, у меня говорит что поставило 14, а ставит 13 штук.
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          кстати, спасибо за попытку взлома. успокоил за 10 минут до конца раунда :)
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится -13 Проголосовать: не нравится
          Сейчас как назло опять unrated будет, так что давайте помолчим...
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
какое решение D div 2?
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Надо расставить всех шахматных коней на поле nxm клеток. Коней надо ставить на один цвет, что бы они не били друг друга. (если черных больше то на черные если белых то на белые)

    Общая формула (n*m+1) div 2. Отдельно случай 3x2 который не  подходит под эту формулу. Надеюсь систесты пройдут.  

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Не пройдет. 5x2 ответ 6.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Огорчу - не пройдут, есть еще случаи, описанные постами ниже.
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Жаль. Нас так в школе математик учил по цвету ставить.
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Обламилась на 56 тесте. Случай 583 2. 

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

        2x2 у меня 4.

        Я не полностью описал решение. Вот строчка с кода

        if (m<2) or (n<2) or ((m=2) and (n=2)) then writeln(n*m)


    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      5x2 
      ответ - 6
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Есть еще прекрасный случай 2xN. Например, при N=6 ответ - 8.
      Я лично убеждался стрессом с перебором на всех тестах :)
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        а как 2х6 получить 8?
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          xx..xx
          xx..xx
          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            кажется я сейчас убьюсь об стену....
            я весь контест думала, что 6-ой столбец поставить невозможно....

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      Коней надо ставить на один цвет внутри компоненты связности. То бишь запускать обход графа из каждой клетки и считать, сколько черных и сколько белых.

      Ваша логика обвалится на тесте 2 5 (ответ 6).
»
13 лет назад, # |
Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

Самый лучший раунд за последнее время.
И взломы были(6 взломов по D(B div 1) сделал, а потом самого взломали в придачу :D), и возможность сдать задачу E(C div 1) просто перебрав варианты(чуть-чуть не успел).
Спасибо за контест!

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Спасибо за возможность побыть полчаса на первом месте. По Е отправил лажу для взломов, пашет только при n*m<=36(кстати как ее решать), по D забыл 1 случай, но 7 взломал =)
  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    а что за случаи были в D(div2)?

    p.s. и собственно на чем в ней ломали?

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      n==2
      Учел для n==2  и m<=3, а для n==2 и m>3 не заметил, что тоже особое решение нужно.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      если решение как (n * m + 1) / 2, то:
      при n или m равном 1
      при 2 2, 3 2, 2 3, 2 6, 6 2
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        я на 2 5 ломал еще. И вообще на любом 2 .. 3k-1 можно вроде бы
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Самое классное решение по Е(див2) / С(див1) - у Гены.
»
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
АААААААААААА! Как можно так лажать? Вместо
if ((r && g) && m != 1) 

было написано

if ((r && g)) 

И не хватило всего 1 секунды чтобы отослать. Если зайдет в дорешивании, убьюсь... 

»
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
A very mathematical round. Thanks just as much.
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Спасибо за задачу Е, очень классная задача, жаль что не успел решить ее за время контеста. PS не было бы случая про основание конуса, понравилась бы еще больше ;)
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Сделал 2 вывода:
1. Мою B вообще никто не читал
2. В китайской википедии та же бага про мультиним, что и в нашей
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится -30 Проголосовать: не нравится
    Егор, у меня лично других дел хватало, чем твою В читать. Спасибо, кстати, что взломал мою:)
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится
    ну, я читала, решила на всякий случай не трогать.
    Кстати, в вашем коде искать, где решение - отдельный челленж.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится
      Ну не знаю. Я честно говорю, где решение, в отличии от половины людей, которые его так прячут, что и найти нельзя. Вот мою задачу С надо в Кунсткамеру отдавать, это да
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Бага в википедии - это просто ужасающе :( 
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ну не надо верить википедии на слово. А при попытке доказать и лажа находится, и правильное решение. Тем более что понятно, что доказательство не сильно от обычного отличается.
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А что, если посылка не проходит на претесте из условия, то засчитывается штраф?
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Не засчитывается, только если не проходит первый
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Что ж, справедливо получил штраф за свою лень (читать правила или условия). :-)
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    если претест не первый - да.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Если не проходит первый претест, то ничего страшного. За все остальные штраф.
»
13 лет назад, # |
  Проголосовать: нравится +68 Проголосовать: не нравится
A and C are implementation problems.
Have seen B before and D is based on known idea which was used in IPSC 2010 task K.

I expected more from this author.
»
13 лет назад, # |
  Проголосовать: нравится +55 Проголосовать: не нравится
Не любитель я hacking rounds, эхъ.
Больше половины условий про прямоугольные клетчатые поля - знакомый синдром, когда придумываешь задачки. "Квадратно-гнездовое мышление". =)
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А как делать взломы, а то я не нашел как. Научите пожалуйста.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Клик на замок на странице со списком задач.
    Переход в комнату. Открывать чужие задачи дабл кликом или ctrl+click по ячейке с кол-вом баллов
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Блокировка задачи - замок на странице "Задачи".
    Просмотр решения и взлом - двойной клик по количеству баллов у кого-нибудь из комнаты по какой-либо задаче.
»
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Am I the only one who wrote the complicated DP for problem C (div 1)?
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится
    ... which wasn't quite right? You are not the only one.
    • »
      »
      »
      13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

      I compared the maximum number of T-shape thing with tourist's solution. All my answer was correct. I hope my printing the board was correct too :(

      Edit: final test passed :D

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

      Разве не работал перебор?

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

      Why not DP?
      It was a rather simple one, though a bit more technical than usual.
  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    Am I the only one who wrote the compilacated code for problem C (div 1) and didn't even pass pretest? :( http://codeforces.me/contest/142/submission/1040136

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I wrote the complicated DP too..
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      and my solution is fast enough to solve n=m=9
      • »
        »
        »
        »
        13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        My solution is fast enough to run all 81 possible test case in 1s :)

        May be the limit should have been min(m,n) <= 9, max(m,n) <= 20 ?

        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          My DP solution is a little bit special. It will get TLE when max(m,n)<=20.  
»
13 лет назад, # |
  Проголосовать: нравится +41 Проголосовать: не нравится
Раунд жутко не понравился... Задачам наподобие B место на ACM-контестах, а не здесь. Не в обиду автору.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    ну а как же взломы?
    давно не было задач, где можно много поломать - пожалуйста. 
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    Конечно, это уже много обсуждали.
    Соглашусь, простая задача может дать слишком большое преимущество.
    Может это не так сильно ощущалось бы, если бы комнаты были поменьше.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Это было бы в том плане еще хуже, что тут преимущества почти любому, кто быстро написал и решил хачить, а там еще бы сильно зависело от того, кто в комнате
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        Блин, вот кому не повезло, так мне.
        Я первый в комнате заметил набор тестов (2; n) как взламывающие (правда, ценой блокировки собственного неправильного решения), отломал три решения, а потом пришёл neal и начал у меня уводить взлом за взломом прямо из-под носа! Я буквально сидел и F5чил, и сразу бросался вводить неправильный тест, но он меня как-то обгонял. Похоже, либо у него реакция запредельная, либо у него какой-то свой софт, который следит за него за эвентами вида "появилось решение". Даже не знаю.
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Мне кажется, комнаты сильно отличаются в этом плане очень редко.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      У меня возникла аналогия с B-шкой с вашего и нашего четвертьфинала. На четвертьфинале мы за нее получили полноценное очко, и только одно, пусть и ценой 3 штрафных попыток. Здесь же такие, как я, не получили ничего, а те, кто догадались быстро, получили по 1000-2000 очков...
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Задача как задача. Правда нас что-то подобное RAD заставил добавить в претесты.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Если точнее, обидно, что ни одного теста вида (2; n) при n >= 3 и n != 4 в претестах не было. В результате сегодня была ярмарка взломов по B, на чём я тоже поломался :-(
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Она решается не кучей if-ов, а серией обхода в ширину.
»
13 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится
задрали математические раунды, ну хоть кто нибудь, проведите neerc-style!
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится
    По вашему neerc-style это 5 техник?
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      по мойму neerc-style это neerc-style, это применение алгоритмов с интересной идеей

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

        Задачи на математику - это есть какое-то непонятно что выведите формулы и забейте ее. Задачи которые тут на применение здравого смысла(A,B) или алгоритмов(функция гранди и подобное)(D). Задача С - какой-то непонятный перебор или динамика. Тоже алгоритмы если хотите. Где математику то вы нашли? В том что у числа мало делителей в A?

        Кстати, если сильно хочется B - поиск минимального независимого множества в двудольном графе. Собственно я так и решал, только поверил на слово что полное парасочетание существует.

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
замечательные задачки, очень понравились, спасибо автору... только вот 142B - Помогите воеводе особенная... тем, что не такая уж оригинальная как другие и тем, что люди как будто хотели чтобы по ней их взламывали...
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Задача A была на NEERC в каком-то году...
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Такие задачи могут придумываться независимо разными людьми. Да и для простой задачи это не критично. Куда более грустно что D - комбинация двух боянов и очевидной идеи.
»
13 лет назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится
Very fast System testing today.Its making up for the 5 mins delay in the start of the round.
I liked this round....Was logical and mathematical one...........:)
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
К счастью, написал в Ddiv2 dfs, не заметив этот очевидный факт.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    как решать dfs-ом?
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      ребро (i, j) - возможность из i попасть в j одним ходом.
      Заметим, что компонента связности разбивается на двудольный граф. Строим его. Прибавляем к ответу размер бОльшей доли.
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится
        Ну почемууу это корректно =( ?
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Блин я не могу уснуть.

          Для произвольного двудольного графа это не работает:

          Что в конно-шахматном графе такого крутого, что на нем работает?

          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится +8 Проголосовать: не нравится
            Полное паросочетание?
            • »
              »
              »
              »
              »
              »
              »
              13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              ?
              • »
                »
                »
                »
                »
                »
                »
                »
                13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Это был ответ на вопрос "что такого крутого?"
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  Полное паросочетание? Но там даже вершин нечетное количество бывает...
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  13 лет назад, # ^ |
                    Проголосовать: нравится +8 Проголосовать: не нравится
                  Полное - когда с одной из сторон не осталось вершин
»
13 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Мне одному кажется, что раунды становятся все хуже и хуже? Div1, по крайней мере. Весьма "нехороший" сотый раунд (эх... юбилейный, блин), а теперь еще одно неудачное мероприятие. 

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

При этом разница по сложности между первой и второй... невысокая (разве что подводные камни второй, за них единственный +). Третья задача сильно отличается от первых двух, опять получился контест, который для всех ниже красного, получался удачным при условии хорошей сдачи даже не первых 3, а первых 2 задач.

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

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится
    я скажу так - пока я не буду отрешивать стабильно 4-5 задач в каждом раунде для меня див1 "не будет становится хуже".
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Каков идеальный раунд в Вашем видении? По сложности/ранжировке/количеству взломов?
    Просто интересно :)
    • »
      »
      »
      13 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

      Можно я?
      1) Взломы есть, но не случаеподобные. Т. е. я считаю, что тесты 2 3 и 2 7 в B должны быть в претестах (а без них задача просто превращается в боян)
      2) Если есть задача, в которой ответ выводится за O(1) размышлением с ручкой/листиком/бумажкой/салфеткой, то она - А.
      3) Задачи не столь боянисты. А именно: B - просто гуглится, да и боян страшнейший, а D - прямая сумма двух общеизвестных вещей (ещё бы я знал одну из них, но это, видимо, мой промах - похоже, я проспал одну из лекций в ЛКШ.А)
      Видимо, вот.

      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Не случаеподобные - это какого вида? Лонги? Что еще?
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится +16 Проголосовать: не нравится
          Не только. Ошибка в логике решения на больших тестах.
          Всякие тупые описки/опечатки.
          Ладно если есть какой-нибудь принципиальный случай в сложной задаче. Но когда задача по модулю этого случая ничего из себя не представляет, и только превращает контест в карнавал взломов - по-моему это не дело.
      • »
        »
        »
        »
        13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        2) Если есть задача, в которой ответ выводится 

        за O(1) размышлением с ручкой/листиком/бумажкой/салфеткой, то она - А.

        Зачастую нужно потратить существенное время на такое размышление с бумажкой, в отличие от написание простого жадника (а-ля D на 100 контесте) или какой-то суперпозиции тривиальных алгоритмов (правда у каждого набор тривиальных алгоритмов свой, но во многом такие наборы пересекаются). По крайней мере на opencup'e мною убивалось довольно существенное время на решение задач типа "выведите формулу".

        UPD) Или я неправильно понял, что подразумевалось под О(1) =)
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится
          Ну, мы же не про АСМ-стайл контесты говорим?
          Никто не спорит, что такие задачи бывают интересными, что таким задачам место на определённых соревнованиях. Я тоже такие люблю.
          Но в контексте сегодняшнего соревнования, повторюсь: сегодня она не представляла собой что-то особо интересное (моё субъективное имхо, конечно же), поэтому ставить её на B было как-то нелогично.
          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Ну сегодняшняя то да... В принципе соглашусь, сложно придумать интересную задачу на формулу, которая при этом бы ещё достаточно быстро решалась, и не была баяном.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +7 Проголосовать: не нравится

      В текущем формате схема "если ломаем, то на чем-то одном, и всех" - явно не то, так как разброс по комнатам сильно влияет на результат. Рулетка получается.

      И переход по сложности должен быть более плавным. Или вторую решают меньше, или третью - больше. 

      Как уже было сказано, боянистость задач - вот главная беда. Остальное - дело вкуса. Вот, пишут, четвертая - тоже боян :)

»
13 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
Блин, весь раунд считал что нельзя ставить 2 фигуры на расстоянии пять в одном столбце/строке %)
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Так нельзя...или я чего-то не понимаю?
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      В одном как раз можно, надо внимательно читать дополнительные условия.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Расстояние != квадрат расстояния.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Если квадрат расстояния равен 5 и только тогда, а когда все стоят на линии там
      1,4,9...
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      увы можно Т_Т
      там сумма квадратов разниц  координат, а не самих разниц
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я перечитал через пару минут, потому что прочитал тест :-)
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
подсказали такую мыслю - тестирование задерживается из-за того что взломы добавляются в систесты, правда или нет?
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Правда, что добавляются. Неправда, что всегда занимает столько времени. Обычно быстрее.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    вроде вначале полностью протестили див2
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      У нас тестирование шло параллельно. Но может что-то поменялось.
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится
        нет, у нас началось тестирование только после того, как у див 2 были уже результаты
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Can someone please point out why my solution to problem A (div2) in Python kept getting runtime error on pretest 1, even though it ran fine on my side. I had to re implement the exact same solution in C++ to get it AC. Darn! Here is the code: #
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    Ghm. Maybe I misunderstand something, but sys.exit(1) looks strange. Return code 1 means runtime error in any programming language.
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Извините, не подскажите, какое правильно решение А div 2? писал просто тупейший перебор
»
13 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
юху, первый accepted мой :D
»
13 лет назад, # |
  Проголосовать: нравится -33 Проголосовать: не нравится
wow! Greatest contest i've ever seen! I think this was a record for Div 2 to have ~2000 registered people! Thanks Codeforces
»
13 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится
На дорешивании действительно длинная очередь или что то с CF?
»
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Запомните меня фиолетовым -_-
»
13 лет назад, # |
  Проголосовать: нравится -27 Проголосовать: не нравится
Просьба автору: пожалуйста если вы считаете себя математиком давайте свои задачи на математических олимпиадах.
  • »
    »
    13 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +36 Проголосовать: не нравится


    Не удержался.

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Тот же вопрос что и к yahooo. Где математика, кроме того что в задаче А у числа мало делителей?
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится
      Я вот не вспомнил как решать D-шный ним, а с этим знанием становится совсем легкой.
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится -7 Проголосовать: не нравится
        Уточним что имеется ввиду под словом "математика". Если уж на то пошло, то придумывание любой идеи/алгоритма математика. Такая теория игр это все таки вполне себе Computer Scince, и рассказывается везде где только можно на лекциях в среде спортивного программирования.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      Математика там где надо писать меньше 20 строк кода
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Гы, hello world подходит под определение)
        Вы код Пети или Гены часто читаете? Там иногда можно и D, и E в 20 строк встретить.
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится -8 Проголосовать: не нравится
        В такой формулировке согласен. Хотя A,B на мой взгляд вообще undefined тематики, ибо тупость. А решение D я не умею в 20 строк умещать.
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится -9 Проголосовать: не нравится
          Паш задачи А, B и D решались на листочке. Они явно не задачи по программированию. А учитывая что Е никто не решил 75% задач контеста решались на листочке. Я не говорю, что это какие-то сложные математические задачи. Если бы они были сложными их можно было дать на мат олимпиаду.
          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится +11 Проголосовать: не нравится
            А и B могут быть либо такими либо простыми реализациями. По мне так лучше такое, но это дело вкуса. D задачка по теории игр. При чем по теории игр скорее компьютерной чем математической. Ну тут уже вопрос терминологии, так что спорить не о чем. На мой взгляд она вполне себе D и вполне имеет право быть на контесте. 
            • »
              »
              »
              »
              »
              »
              »
              13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Об этом можно спорить бесконечно. Моё мнение такое: на контесте задач которые решаются на листочке должно быть не больше 20%. И уж точно это должна быть не задача D. Моя ошибка видимо в том, что я считаю математикой: все что кодится 2 минуты.
              • »
                »
                »
                »
                »
                »
                »
                »
                13 лет назад, # ^ |
                Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

                Аааа, все, неправильно прочитал ваш пост, все в порядке :-)

»
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Когда КФ придет в нормальный режим?
»
13 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится
Thanks for preparing this round!It was really good contest!!
»
13 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится
А раунд вообще рейтинговый? просто долго не считают.
»
13 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
Мне раунд понравился. А как обычно халява, B я вообще не сразу придумал, только как понял, что граф двудольный и что надо рассматривать отдельные компоненты, сдал решение. Причем для меня вообще загадкой было как делали взломы, потому что идеи с формулами лично у меня было 0. С - поотсекать перебор. При наличии вкладки запуск - нормальная задача. D - интересная задача на сведение к k-ниму. E - понятия не имею как решать ))
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится -7 Проголосовать: не нравится
    В С проходит перебор ответа + внутри перебор с отсечением по времени. Работает моментально, а потом тупит в поисках несуществующего ответа.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    Функан, мать его.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Решение скорее всего численное. Разбить конус на точки, запустить дейкстру, потом как-то двигать точки пока есть улучшения. Вот как двигать видимо зависит от типа пути.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится
      Геодезические на конусе ищутся явно, поэтому я уверен, что решение точное. Правда будет некоторый геморрой с дном конуса.
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        А там придётся поминимизировать функцию двух переменных, что несложно.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    В B было много неправильных формул. Кто-то не учитывал N = 1, кто-то N = 2, а кто-то учитывал оба случая, но когда N > 2 и M > 2 выводил (N * M) / 2 вместо (N * M + 1) / 2. Ну и некоторые просто неправильную формулу использовали (со всякими делениями на 3).
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А как вкладка запуск помогает? Не пишется же сколько времени программа отработала. 
    В задачах, где макстест с большим вводом вообще бесполезна, потому что его не вбить...
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Пишется. В окошке "вывод".
      Насчёт большого макстеста - можно вбить генератор в программу. Но, да, неудобно, что даже генераторы посылать нельзя.
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Я идиот. Даже если бы не писалось, то можно было бы самому выводить.
        Значит, полезная всё-таки фича.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Почему такое решение B корректно?
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как все же решалась c(div2)?

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

    Можно перебирать число a до корня кубического, b до sqrt(n / a) и затем просто находить c, если n % (a * b) = 0. А затем для чисел a, b, c можно за O(1) пересчитать min, max.


    P.S. Это не самое хорошее решение, просто это самое первое, что пришло мне в голову :)

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

    Нужно среди всех возможных разложений числа n на 3 сомножителя найти максимальный и минимальный ответ.

    Для этого найдем все делители числа n и покидаем их в вектор.

    Потом разделим n на каждый из этих делителей, и результат еще раз разделим на каждый из них. Из всех валидных вариантов (когда второй раз разделилось нацело) выбираем максимальный и минимальный.
»
13 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится
Я ненавижу этот контест. Я ненавижу всех. Я ненавижу себя за этот дебильно пропущенный else. Такой досады не было еще ни разу. Пойду выпью яду. Или тупо коньяка.
»
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
У меня не зашло две отправки на задачу C(div 2) в последние пять минут, ну т.е. система считает что их просто нет. Т.к. проверялось всё медленно, то я долго не решался сабмитить повторно(жалко же баллы на ровном месте терять), потом засабмитил, а эффекта нет. Теперь вопрос, это только моя личная проблема растущих рук или ещё у кого - нибудь было такое?
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    На последних секундах челленжил. Выдало: игнорированно. Возможно, потому что второй раз человека ломал или это можно?
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      2 раза можно ломать. Я одного даже 3 раза сегодня, кажется, взломал.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    На прошлом раунде у меня было то же самое. Я, вроде как, даже написал об этом в комментариях.
»
13 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится
что это за фокусы? 15 мин тестирование, 20 мин нет обновления рейта... так не пойдет....
  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

    Не угадал, третья. Что-то уже обновилось, а что-то нет.

»
13 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится
Такой вот вопрос по четвертой задаче.
На 56 тесте вводятся 583 и 2, и на выходе должны получить 584. Но как? По идее же 583 должно получиться, если отталкиваться от того, что используется "шахматное" расположение бойцов. Или я в чём-то ошибаюсь?
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    когда min(n,m) = 2, то немного другое разбиение.
    к примеру, n =5, m = 2
    KK..K
    KK..K
    Ну и дальше по аналогии
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Я нарисовал на бумажке эту картинку и почему-то посчитал, что так надо действовать только при маленьких n, m. Снова дурацкий фиолетовый цвет.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Для двойки нужно было отдельно посмотреть
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Шахматное расположение не всегда оптимально, на этом всех и ломали. Здесь оптимальный ответ - 
    хх
    хх
    ..
    ..
    xx
    xx
    ...
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как решать задачу E div 1? Неужели задача о расстоянии между двумя точками конуса не является стандартной геометрией?
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Если обе точки на дне конуса, ответ очевиден.
    Иначе нужно искать геодезические на конусе (это не очень сложно, если знать как они в принципе ищутся), если нашли, то знаем кратчайшее расстояние между двумя точками по боковой поверхности конуса. Если одна точка на дне, то нужно минимизировать функцию одной переменной (перебираем точку на границе), если обе точки на боковой поверхности, то двух переменных, т.к. кратчайший путь может проходить по дну.
»
13 лет назад, # |
  Проголосовать: нравится -53 Проголосовать: не нравится

Задача B (div1) D(div2) - кривая. здесь подробнее.

»
13 лет назад, # |
  Проголосовать: нравится -30 Проголосовать: не нравится
КГ/АМ
»
13 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
Editorial please
»
13 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Во 2.div в задаче B на тест 1000000000 я думал ответ будет 1000, 000, 000.00, а не 1,000,000,000.00, в условии было сказано "цифры целой части числа разбиваются для удобочитаемости на группы по ТРИ разряда, начиная с младших разрядов, группы разделяются символом «,» (запятая).", ето разве не так - 11111111,321,123? 

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Нет это не так...
    Разбивать нужно по количеству цифр а не по их арифметическому значению... Т.е. в числе 11111111321123 - 14 цифр а значит 4 "," и добавляешь ".00" и получишь 11,111,111,321,123.00...

    P.S. в седующий раз повнимательнее читайте условия задачи..=)
»
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
По поводу того, почему ответ в div2D/div1B именно такой (в дальнейшем n ≤ m):
Случай n = 1 очевиден.
В случае n = 2 граф разбивается на четыре пути, начинающиеся в клетках самого левого квадрата 2 × 2. Нам нельзя брать две соседние клетки в любом пути, поэтому для каждого из них ответ (длина пути) / 2.
При n ≥ 3 в графе есть гамильтонов путь (кроме случая m = 3, но ответ будет верен и там). Поэтому по указанной выше формуле ответ nm / 2⌉.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Наличие гамильтоного пути считать общеизвестным, или есть этому простое обоснование?
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Я не знаю доказательства, но факт, кажется, более-менее известный.
      Это не строгое обоснование, это скорее для успокоения совести. =)
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        Доску 4 x 4 нельзя обойти конем, если что.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Для случая N ≥ 3, M ≥ 3 можно вместо гамильтонового пути просто показать, что есть одна компонента связности. А поскольку граф двудольный и в нем существует паросочетание размера NM / 2⌋, то ответ будет NM / 2⌉

    Для того чтобы показать что есть всего одна компонента связности, достаточно показать что из каждой клетки достижим левый верхний угол. Понятно, что ходами коня из любой клетки можно прийти в квадратик 2х2 в левом верхнем углу таблицы. Ну а дальше для этого квадратика на бумажке выписать ходы, которые приведут в левую верхнюю клетку. 
    • »
      »
      »
      13 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

      Rendering to html failed: Transformation failed: Unclosed math text.

      Всегда мечтал сказать это.

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится
      Почему в графе есть паросочетание размера NM / 2⌋?
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится -8 Проголосовать: не нравится
        Ну замостите его доминошками :)
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится
          Это какие-то конимошки получаются.
          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Иван, вот ты придумал и написал это решение на контесте. Как ты для себя обосновал его правильность?
            • »
              »
              »
              »
              »
              »
              »
              13 лет назад, # ^ |
                Проголосовать: нравится -8 Проголосовать: не нравится
              Вообще формально доказать пока не знаю как. Надо подумать. А на контестах до задачи С мне хватает примерно такого мышления:
              • Понятно, что если построить граф как бьет конь, то будет задача найти максимальное независимое подмножество вершин. Так как граф двудольный, то можно найти парсочем.
              • Парсоч на 10^6 вершин? Задача B?
              • АААА, нет вырезанных клеток, значит граф очень хороший.
              • ???
              • PROFIT

      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Поставим на все черные клетки. профит
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Это, кстати, неверное утверждение для n = m = 3. Но там все равно 5
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
i realize a useful "cut case" technique which sometimes works (like problem C this time) by reading others' codes...=D

  1.         // "useful" technique XD
  2.         if (clock() - start > 2.7*CLOCKS_PER_SEC) return;

(this technique was once used by my team in an acm-icpc regional contest too.)
  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится -7 Проголосовать: не нравится

    You can improve this even more.

    clock() function and floating-point comparison aren't the fastest operations.

    We usually use something like

    1. const int MAX_ITER = 80000000;
    2. int curIter;

    3. void solve(int x, int y){
    4. ...
    5.     if(curIter > MAX_ITER)
    6.         return;
    7.     curIter++;
    8. ...
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      in the regional contest experience i mentioned above, we used exactly the method you suggested: count number of iterations in the searching function
      this worked well since our machine was (theoretically) identical to the judge machine
      (e.g., we found that 1,000,000 iterations ~= 1 second, the number of test cases <= 10, and there is 10 second time limit, so it should be save to set MAX_ITER = 1000000)

      while this method is also practical. however, in Codeforces/SRM/...etc contest, it may be a bit less convenient to "estimate" MAX_ITER, since the environment setting is a bit different. 
    • »
      »
      »
      13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

      It seems to me that it's greater to use clock(), but not as mentioned above, but somehow like this:

      const int ITER = 1000;

      const float MAX_TIME = 2.8;
      int iter = 0;

      ...
      if (!(++iter % ITER))

        if ((float)clock() / CLOCKS_PER_SEC > MAX_TIME)

          return;

      ...


      It's better because we don't know, how much iterations our algorithm can do in time-limit; in my variant it will work exactly MAX_TIME (+/- EPS), and won't slow much because we check time only each ITERth iteration.

      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится -10 Проголосовать: не нравится
        When iterations where answer exists work immediately, and time-limit cut-off need only for last iteration where no answer exist, there is no need for any optimization.
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Can you please post the tutorial for this round?!
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

this submission shouldn't have passed it was missing a case and I added it here

here a test case:

12 5
20 10
8 9

the output should be -1, but it outputs

5 7
2 3