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

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

Всем привет!

Праздники кончились, и наступила сессия. На голову студентов сразу обрушилось множество проблем. Долги растут, а времени их сдать - все меньше и меньше. Думаю, всем вам знакома эта ситуация. Осознавать ее и бездействовать - просто невыносимо, и недавно я понял, что больше так не могу. Выход был один - перебороть лень, собрать всю волю в кулак и начать наконец писать... январский 10-дневный контест на codechef.com :)

Мне кажется, это было правильное решение. Голова прояснилась, и несколько дней пролетели незаметно. План-минимум гласил - нужно попасть в Top-10 Global, чтобы получить... а что получить? Несколько раз, краем уха я слышал про прикольные призы, высылаемые лидерам контестов. Начиная от футболок, и заканчивая наклейками и деньгами. Подробностей я не уточнял. Мне почему-то казалось, что попадание в десятку лучших на контесте профильного формата - это хорошо, и должно обязательно повлечь за собой приятные сувениры. Но контест шел, времени было мало, а смысла думать о призах - еще меньше...

И вот, на сайте появилась надпись "коннест завершен". По правде говоря, написал я его не очень. Во всяком случае, придумать качественное решение на challenge-задачку мне так и не удалось. Однако, как это и ни странно, план-минимум я все-таки выполнил - на "минимум", заняв в итоге 10-е место. Надо сказать, я был немного удивлен. Но каково же было мое удивление, когда беглый поиск в интернете по вопросу призов не дал никаких результатов! Первые два места - да, а вот остальные... И тут у меня назрел вопрос. Неужели все так несправедливо? :)
  • Проголосовать: нравится
  • +24
  • Проголосовать: не нравится

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
В коротких ежемесячных контестах Codechef CookOff призы даютдавали за попадение в десятку. Правда, они в последнее время почему-то перестали их присылать.
»
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
В длинных контестах обычно за глобал 10ку дают футболку + какие-нибудь ништяки - то пару наклеек, то 5 ручек
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Спасибо, звучит обнадеживающе :) Интересует только, не перестали ли их тоже пересылать в последнее время? И как долго они идут.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Ну, идут порядка пары месяцев, ymmv
      У меня, вроде, за кук офф спрашивали адрес. Но футболок давно не было, может, застряли где
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ясно. Вообще адрес в профиле вроде указан.
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится +31 Проголосовать: не нравится
          Это никого не волнует. Они каждый раз его спрашивают, каждый раз говорят, что добавили в базу - и все равно
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Блин... задачу http://www.codechef.com/JAN12/problems/MISINT2 свёл к нахождению n-го члена  последовательности https://oeis.org/A081844 , но как за разумное время его найти так и не придумал. Почитал разбор - не осилил, забил, ибо там начались жуткие вещи :) 

По теме: за октябрьский лонг отозвались и спросили  только 9-го декабря куда высылать футболку ... ну и соответственно щас ещё ничего не приходило...

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Кстати, кому-нибудь кто попал в десятку на октябрьском коротком контесте уже писали что-нибудь на счет футболок? Может, есть какой-то критерий, по которому определяют, давать за контест призы или нет.
»
13 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

мне нравится разбор MISINT2: докажем формулу

 

интересно, как прикажете ее выводить когда ее не знаешь?

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Это как раз самая простая часть ;) Just use OEIS. 
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Хм, а на CC считается нормальным, что для решения задачи надо забрать OEIS? Или просто дозволяется?
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится
    Можно и без OEIS. Она естественно получается сама по себе если идти тем путем, который изложен в доказательстве. А про то, что она есть на OEIS, я узнал уже после того как вывел эту формулу.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Я просто посчитал для n до 100, а там понятно, что при (2*n) надо действовать также как и при (2*n+1), так как символ на месте (2*n+1) встанет на это же место. Поэтому я вбил в oeis те числа, которые стоят на нечётных местах. Вылезла эта последовательность :)

      Очень крутая задача...

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

        Я шел другим путем. Есть такая известная перестановка - Perfect shuffle (Faro shuffle) - есественно возникает при тасовке игральных карт слиянием. Она же используется в нетривиальных алгоритмах inplace_merge, обеспечивая логарифмическую (или даже константную, не помню) дополнительную память. Так вот, она в некотором роде эквивалентна перестановке из нашей задачи. В том числе, и по количеству циклов. Почитав статьи с анализом этих алгоритмов, можно натолкнуться на вышеприведенную формулу. Далее - дело техники. Но я бы сказал, магии :) Разбор еще не читал, но в моем случае было достаточно сложно уложить программу в местный ТЛ. Машины там слабоваты... :( Ну, еще - немного теории чисел. 

        P.S.: по теме треда - сегодня пришло уведомление от индусов, с просьбой _подтвердить_ данные и адрес. Те, что взяты с сайта. Судя по всему, к словам Egor они все-таки прислушались.
        P.P.S.: да, я тоже использовал OEIS :)