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

Автор cerealguy, 14 лет назад, По-русски
Всем привет.

Сегодняшний контест представляем мы: cerealguy и yaro. Некогда мы учились в одной школе, и с нами учился замечательный мальчик Володя. Именно он будет героем сегодняшнего контеста.
Володе предстоит побывать на кухне, посетить музей, попытаться взломать сейф, отправиться в необычный город и, наконец, использовать свои магические способности.

Хочется выразить благодарность команде Codeforces и особенно Артему Рахову за помощь в подготовке контеста и написание альтернативных решений.

Надеемся, задачи придутся вам по вкусу.

Удачи!

Обновление. Частичный разбор задач.
  • Проголосовать: нравится
  • +40
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится
Удачи всем!
14 лет назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится
Good luck to all!!
14 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
I wanted to register for the contest 11 minutes before start and registration was closed. Why did you close it so fast? It would be better if it is closed 5 min before the start.
14 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
How does one stop getting email/delete their account at codeforces.  I am not interested in any of the permitted languages, and am getting tired of the email.  There is no setting to turn off email, and no contact information.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
in the problem B,The black king might be able to take opponent's rooks at his turn,what is the meaning?is it that the black king can only take the opponent's rooks at his adjacent cells or he can take any rooks?
  • 14 лет назад, # ^ |
      Проголосовать: нравится -7 Проголосовать: не нравится
    king only moves to the adjacent cell. it was in the statement.
    also in chess you cant kill a piece with a king if it is defended by another same color piece.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Is pretest 1 the same as sample test 1?
14 лет назад, # |
  Проголосовать: нравится -78 Проголосовать: не нравится
its bull shit codeforces is sheer bull shit i wrote a solution to the problem that got accepted and in a moment i am told that mysolution is hacked y the fuck no measures are taken against the stealers i am ruined and i m not intrstd in solving any further
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    what a pity!just go go!don't fuck,just work more hard and hack others!
  • 14 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    Maybe you did not understand what "hacking" means. It is part of the contest. "Your solution was hacked" means that your solution was wrong and that someone found a test on which your solution fails and inputed it. This is part of the contest. So now, why are you angry that you got hacked, your solution would have failed the System tests eventually...
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    "The round will be held on the rules of Codeforces, so read the rules beforehand."
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
потом расскажите ктонить как D делать
  • 14 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится
    Одна из идей такая: так как все гамильтоновы пути проходят по каждой вершине один раз, давайте взвесим сначала не ребро, а вершину, а вес ребра будет суммой весов инцидентных ему вершин. Тогда если все ребра получатся разными по весу, то это и будет правильным ответом. Так как вес любого гамильтонового пути будет равен удвоенной сумме весов всех вершин. Остается только сгенерить веса вершин. Это можно попробовать сделать жадно. Дать вес 1 первой вершине. А дальше всем последующим вершинам давать такой минимальный вес, чтобы не получилось два ребра одного веса. Для 20 вершин, вес 20-ой вершины получится чуть больше 400. Поэтому веса ребер будут не больше, чем 1000.
14 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Anybody has some ideas for Problem B?
  • 14 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится
    did your solution failed on pretests?
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      I have no idea for it, so I didn`t code it.so.....
      • 14 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        OK,I'll try to help u.
        U should simulate rook's moving until u meet some white figure and mark all the points as bad.But DON'T mark the point,that ur rook\king starts from.Then mark all the points that ur king can beat.Then check the points,that black king can go to and the point that he starts from.If one of them is good one,then "OTHER" else - "CHECKMATE"
        I hope it will help u ;)
14 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится
Задача Е супер. Жаль когда я ее решил у меня оставалось всего 20 минут и я не рискнул ее писать - сделал 4 челленджа вместо этого
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
What happened with problem B, it was massive slaughter in the system test.
Are there maybe wrong tests in it?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Yes, it is strange(although probably fault is mine and not of the systest as always). Maybe some of you knows what the test 7( not pretest) is? I failed on that one.

    If someone has test 7 for problemC(yes, 7 was my unlucky number today) It would be great.

    Thanks in advance, and thanks to the setters for the nice problems!!!!
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      I dont know the seventh one exactly,but i know some another good tests:
      c2 b3 h8 a1 OTHER
      h1 a8 h8 a1 OTHER
      a2 b1 a3 a1 OTHER
      gl
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Thanks for the cases! Anyway, I pass all of them. I'm sure this suggestion has been made before, but.....wouldn´t it be better to have the test cases made public after the contest?
        • 14 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится
          try this one
          b2 b3 d5 d3
          the answer is CHECKMATE for sure
          • 14 лет назад, # ^ |
              Проголосовать: нравится +5 Проголосовать: не нравится
            Your challenge was succesfull.

            Thanks for taking the time man. I guess I should have spent that last ten minutes testing trying to hack myself instead of trying to hack others :).
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Можно узнать тест 7 для задачи B?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    И ещё, пожалуйста, 21-й для B.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    У меня там WA7, т.к. я зачем-то поставил на доску чёрного короля, и при генерации полей под боем сквозь него ничего пройти не могло (т.е. он мог просто сделать шаг назад от ладьи). Наверное, тест именно на это.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Да, тест 7 такой: a1 a2 c4 c2
14 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Well you had to add the magical part, Harry Potter is releasing soon!
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Можно узнать 7 тест для задачи C?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Не знаю, что там в 7ом тесте, но я всех челленджил тестом "2 1 1 1" (на нём жадность не работает). Учитывая, что 7ой упал много у кого, может, это именно он?
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Да, он. Только по кругу повернутый, если кому интересно. =)
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      разве не -1 правильный ответ для этого теста? (и мне досталось от тебя :) )

      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        нет:
        2 1 1 1
        3 2 1 1
        4 2 1 2
        2 1 1 2
        1 1 1 1
        жаль я это понял за 30 секунд до конца :)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Кстати по C отлично заходил метод популяций :o) Нежданчик!
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А можно узнать, что за метод?
    Я сделал просто рекурсией с запоминанием, и все прошло.
    • 14 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

      Вот неплохая показательная статья http://habrahabr.ru/blogs/artificial_intelligence/66121/ .

      PS Хм, я думал, что кол-во состояний ДП будет быстро расти, может быть Вы использовали какие-либо отсечения?

      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ну, я не искал минимальное количество преобразований, то у меня не ДП.
        А отсечение единственное: если предыдущая операция инкремент (возможно нескольких пар одновременно),  то текущая операция - только деление.
      • 14 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        А я в этой задаче втупую прописал 16 случаев if'ами(в зависимости от четности чисел). Не ожидал, что пройдет
14 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
Ура! Я стал жёлтым! :)
14 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится
Even CF couldn't avoid overflow:
http://mirror.codeforces.com/profile/tourist
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Скажите пожалуйста 7 тест на задачу С,я думаю он не только мне нужен.....:)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Выше уже был, читайте внимательнее!
    • 14 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      Да,спасибо,увидел.Хотя при ручном тестировании всё было ок(скорее всего изза рандома).
      Кстати только что сдал эту задачу.Вообще у меня был довольно простой жадный алгоритм,который обрезает циклы длиной 30 путём добавления к рандомным номерам.Брал 30, ибо думал что пару чисел по 2^30 будет именно сколько "убивать".Получил ВА7,потом обрезал циклы по 20 ,потом по 15,по 5,по 3 и...... прошло!!!!Удивительно,но больше чем 3 подряд операции над одним и тем же числом не обязательно выполнять,хоть иногда и выгодно.
      Невероятно,но факт.Надеюсь,что это поможет шаманам,вроде меня, которые писали жадный алго ;)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Можно узнать пожалуйста 10й тест по D, а то у меня на нем ошибка представления данных (хотя вроде выводит все норм, донако насчет постоянства суммы не особо уверен)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
How to do problem C ?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    My solution got failed, but anyway I'll describe it( maybe someone can challenge it).
    I think greedy works here.

    -If you have an even number > 1 between two odd numbers -> -1
    -If you have an odd number > 1 between two even numbers -> -1

    If you don't then you must either:
    1)do a division, or
    2) a sum and a division
    for any pair of numbers that need it.

    repeat this until you end with 1 1 1 1
    • 14 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится
      It is always possible to find an answer. For 1 2 1 1, the answer could be:
      +1
      +2
      /1
      /2

      I finished my code 20 seconds to the end but screwed up when submitting, thanks to my mouse pad.
  • 14 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится
    Generally, you could first greedily decrease some of numbers to 1 few times until numbers that are left are very small. ( I decreased the maximal value until it was not greater than 10. Other possible variant is to decrease each of values to 1 just 3 times ). After that you should just use BFS on different combinations of numbers in code.  I also checked that I don't reach positions with values larger than 30 in my BFS (And for all tests I gave my solution number of moves was always less than 200 so maybe that check is not so important ). Main advantage of this approach is that it is unconditional and you don't need to check cases.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Here is the greedy I used (passed, but I proved it by bruteforce):
    While you have a number different from 1:
    1) Find the maximal number.
    2) If it is even and has an even neighbour, divide. Otherwise, if it is odd and has an odd neighbout, increase them both, otherwise increase and any of it's neighbours.

    Why does it work: Each time before you divide, the total sum increases by 4 (after you make 2 additions, you're guaranteed to divide). So, with each division the total sum decreases (compared to the sum after the previous division) unless the biggest number is 4 and is surrounded by 2 odd ones. Those are not many cases, I just wrone the program and tested all of  them - received answers on all. If anyone can give a better proof, you're welcome.
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    I had such an approach:

    while there is a number not equal to 1:
            if there is a pair of two even numbers:
                    divide them by 2;
            elseif there is a pair of two odd numbers(and at least one of them is no equal to 1):
                    increment both;
                    divide them by 2;
            else
                    find a pair with two different odd/even numbers(i.e. one is even, the other is odd or viceversa); 
                    increment both ;

    My solution failed tests because of the mistake in the last else statement: I wasn't looking for two numbers, instead just incrementing the first two so the test-case '1 1 1 2 1', or alike, killed solution. Afterwards I've changed it in the way as in the pseudocode, it has passed with flying colors.
14 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
I'm not sure I understand the concept of "hacking" here. Apparently in today's match tourist hacked MBabin's solution to problem B. But it shows that it also passed system tests, and he ended up getting full score for it, while tourist also gets score for the hack. What actually happened?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Bad System Tests? Maybe hacking tests aren't added to the System tests and that, along with a bug(Codeforces Beta - Contest alfa) gave the result?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    MBabin didn't lock his solution, so after tourist had hacked it and got the score, MBabin just found the bug, fixed it and resent his solution.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    You can resubmit solution after hack (if you haven't locked it already). So MBabin noticed that his solution is hacked, fixed bug and submitted new version.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Можно тест 41 по задаче B?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Спасибо большое.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Только мне нужен шестой тест на задачу B ?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
я бы хотел 12 на В
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
а можно 10 на С?
14 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Cпасибо за контест, отличные задачи! С и Е просто супер.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
any one can tell the 20th test case of problem B .

Thanks in advance
14 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Как насчет уменьшить число человек в комнате, скажем в 1,5 - 2 раза?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
What is the algorithm for Problem D ? Seems like some small but nice idea ..
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    The idea is to assign some numbers ai to vertices and the lengths ai + aj to edges. Then the condition about hamiltonian cycles will be fulfilled. To ensure the condition about different lengths, just choose the numbers ai one by one so that it was always true that ai + aj ≠ ai' + aj'. In other words, when you choose a new number, it mustn't be equal to ai + aj - ak and ai - aj - ak, for any already chosen ai, aj and ak. It turns out that if n ≤ 20, this process never needs numbers more than 500, so all edges have lengths less than 1000.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    We've put a link to the problemset analysis.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Why can't testcases be made available after a contest is over ?


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

Borscht aint Russian traditional soup. It originates from Ukraine

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

    Russia and Ukraine still have no cultural border.
    There are more differences between eastern and western Ukraine then between eastern Ukraine and Russia.