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

Facebook Hacker Cup Online Round 2
Автор freopen, 14 лет назад, По-русски

Round 2 состоится 6 февраля в 00:00 по московскому времени. Сегодня утром мне пришло следующее письмо:

Congratulations on advancing to Online Round 2 of the Facebook Hacker Cup!

Online Round 2 will begin on February 5, 2011 at 21:00 UTC (February 5, 2011 at 1:00 PM PST) and end February 6, 2011 at 0:00 UTC (February 5, 2011 at 4:00 PM PST).

You can find the starting times for Online Round 2 around the world here.

Competitors will have three hours to solve the presented problem sets. The top-scoring 300 participants from Online Round 2 will receive an official Hacker Cup t-shirt.

The top 25 scoring contestants from Online Round 2 will be flown to Facebook headquarters in Palo Alto, California, USA to compete in the Hacker Cup Finals. Finalists will be notified via email that they have advanced to the Final Round.

---

Since you’ve made it this far, we know you’ve got skills. Send us your resume if you’re interested in working with us using the links below and we’ll fast track you through the interview process.

Software Engineer - Full Time (Employed/Not in school)
Currently employed or not in school/pursuing a degree.

Software Engineer - Full Time (Currently in school)
Currently in school/pursuing a degree and expecting to graduate soon.

Software Engineer - Internship/Co-op (Currently in school)
If you’re still studying at a university (undergrad, masters, Ph.D.) and not graduating in the next year, our internship program might be right for you! Our interns get to work on big projects, ship code and get paired with an engineering mentor for guidance and fast learning.

Happy Hacking!
The Facebook team

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

14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Везёт тебе :) А я квал из оперы писал :)
→ Ответить
14 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
Топ-300 получат футболку, больше нам ничего от этого Воронежа не надо :)
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    То есть если вдруг получится, что ты в топ25, а я на 26-ом месте например, я понимаю ты будешь не против отказаться от своей проходящей путевки? :о)

     

    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Я думаю учитывая время между 2 раундом и финалом и то, что визы в Штаты все еще нужны для многих стран - все шансы есть и у 50го места
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        как известно, финал переносится на май-июнь-июль..

        так что, финалисты теперь свободны для этого Воронежа =)
        → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится -16 Проголосовать: не нравится
    Да ну, я бы съездил хотя бы чисто для того, чтобы побухать с Цукербергом.
    → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Есть ли кроме меня те, кто прошел во 2-ой  раунд и ему(ей) меньше 18? =)
И что делать? Писать мне его или нет? Не забанят?
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится -13 Проголосовать: не нравится
    Есть:))
    Да не должны поидеи:)

    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    Было бы реально забавно быть забаненным на фейсбуке :)
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      *пользуясь той же логикой, могу только посочувствовать забаненным в Google Code Jam*
      → Ответить
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Осталось ~2:30. Всем удачи!!!
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    До хакеркапа полтора часа. И никаких сообщений ни на сайте, ни по почте. Есть гипотеза, что организаторы забыли, что контест сегодня.
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Полчаса, однако!
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        А ссылки все нет...если тока они не захотели какой-нить подкол сделать...
        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится +6 Проголосовать: не нравится
          Первые 300 человек, которые найдут ссылку...
          → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Смотрите, второй тур пропал :)
        → Ответить
        • 14 лет назад, # ^ |
          ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится
          Ничего он не пропал, там просто с учётом поясного времени всё криво, он переехал в "прошедшие".
          P.S. Тьфу, ну вот я дурак, зачем сказал, а... так можно было бы здорово сократить конкуренцию.
          → Ответить
          • 14 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится
            Это как? Он же везде одинаково начинается. Значит, и уехать должен одинаково, разве нет?
            → Ответить
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Time paradox
            → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Ну тогда это будет реальное свинство, не предупредить заранее об отмене.....Воронеж че уж тут...
          → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          У них при отображении мероприятий не проверяется часовой пояс и по этому второй тур уже в прошедших мероприятиях
          → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Может они ещё футболки печатают пока?
          → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Интересно, как скоро будет Вконтакте Кап :)
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Что-то мне кажется, что "ВКонтакте Кап" если будет, то как раз прямо здесь и пройдёт. Они же не зря Codeforces спонсируют :)
    → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Объясните пож. условия Studious Student II, Bonus Assignments!!!
→ Ответить
14 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
по предварительным результатам, fb сэкономил 150 футболок =)
также, предварительно поздравляем Petra с победой в round2!
→ Ответить
14 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
Буду очень благодарен за разбор, или хотя бы идеи, первой и второй задачи.
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    и третьей :(
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится
      Третью так можно:
      F(l, r) - количество наборов длины n, что все числа лежат на отрезке l..r и что gcd всех чисел == 1
      тогда ответ F(a, d) - F(a, c - 1) - F(b + 1, c) + F(b + 1, c - 1);

      F(l, r) = (r - l + 1) ^ n - P(l, r)  где P(l, r) - количество таких наборов длины n, что все числа лежат на отрезке l..r и gcd всех чисел > 1
      P(l, r) можно посчитать по формуле включения исключения. Пусть P(l, r, x) - это количество таких наборов из n чисел, что все числа лежат на отрезке l..r и каждое число делится на x. x нас интересует вида 2, 3, 5, 2 * 3, 2 * 5 и т.д. (т.е. все возможные произведения из простых чисел).
      Тогда P(l, r) = P(l, r, 2) + P(l, r, 3) + .... - P(l, r, 2 * 3) - P(l, r, 2 * 5) - ......... ну и знаки чередуются если в произведении нечетное количество простых чисел, то +, иначе-.

      У меня получались ассимптотика O(D * log^2(D)). 

      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Странно. Я решал так же, но у меня задача упала. Можно уточнить, как вы считаете P(l, r, 12)? По моей логике эту величину я пропускал (не добавлял и не вычитал), потому что она является частью P(l, r, 6) и верно учитывается при вычитании P(l, r, 6). Вообще, я не брал во внимание все числа, в которых какой-либо простой множитель входит со степенью больше 1. Я был прав или нет?
        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Был прав.
          Я тоже вычитал добавлял только числа вида p_1^1 * p_2^1 * .. p_k^1.
          → Ответить
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            В таком случае можно попросить написать ответ на мой инпут:
            20
            65592 248848 392957 194562 283603
            910742 381930 566774 806763 978304
            927314 494904 960966 184497 965404
            880945 453538 578071 784625 823099
            500287 241534 376733 26331 582200
            722151 504239 512389 482328 581525
            191030 29487 877727 108655 233297
            361848 44268 705702 834987 915017
            120134 413651 492288 81430 704632
            885492 676904 872721 549248 886879
            265484 514708 539464 292653 644857
            154590 150277 801206 272718 636750
            5 5 7 2 3
            388678 58031 114788 165231 410512
            1 1 1000000 1 1000000
            680308 776819 884066 834141 942279
            1000000 500000 1000000 1 500001
            451526 153494 327021 624662 993206
            982066 439237 714284 602768 687230
            600708 706263 833354 902802 957144
            → Ответить
            • 14 лет назад, # ^ |
                Проголосовать: нравится +3 Проголосовать: не нравится
              254663128
              250834317
              368666389
              256142678
              810702447
              745974134
              21864261
              435707570
              918530096
              228177391
              43042542
              884819122
              0
              103428520
              1
              877731877
              235042057
              923152211
              992526239
              508535498

              → Ответить
              • 14 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Благодарю. Пошёл искать косяки =)
                → Ответить
                • 14 лет назад, # ^ |
                  ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
                  У меня был косяк с подсчетом количества простых делителей у чисел. Я делал это решетом Эратосфена, а в нем у меня было стандартное 
                  for(int i = 2; i * i <= maxn; ++i) 
                  и на больших числах это не работало (надо было i < maxn), чтобы все простые просмотреть и посчитать), хотя на сэмплах, понятное дело, нормально было.
                  → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится
    В первой надо представить массивы в виде многочленов. Находим первообразный корень этого поля, тогда каждый (почти) остаток можно представить как root^k. Вот такой многочлен и строим, коэффициент - сколько раз такой остаток встречался. Тогда после быстрого перемножения можно пройтись по результату и посуммировать коэффициенты у тех слагаемых, в которых root^k < L.

    Для меня обида состоит в том, что я это все придумал, но почему-то не сдал... Как решать вторую не знаю, а в третьей писал включение-исключение (и даже двойное). Видимо, решать надо было две.

    Очень рад за Артема (и виза у него есть:)) и за других российских участников. Молодцы!
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А для меня обида в том что, я это сдал (скопировал fft с емакса), но не делал +0.5 при округлении коэффициентов после умножения.
      → Ответить
14 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
В 3 часа ночи с больной головой, на таблетках, просидев первые 20 минут контеста в душе, с инетом который не выдерживает критики (билайн-мобильный петрозаводско-древлянский), с неправильной тактикой решения (взялся сначала за первую), написав свой FFT на яве с обычными даблами, Я СДАЛ ДВЕ ЗАДАЧИ И ОНИ ПРОШЛИ! АААААААААААААААААААААААААААААААААААААААА!!!
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Ого, и без 20 минут в душе вошёл бы в топ-25.
    Но всё равно, если теперь хотя бы двое выше откажутся, тебе придётся дарить свой аккаунт на Facebook Скиданову =)
    → Ответить
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
А Facebook вроде выправился ко второму раунду) Квал и 1ый были тогда провальные, потом более менее 1-3 раунды. А второй мне понравился) Прикольные задачи, быстро проверили, багов с кнопкой сабмит не было. Единственное, что решать в 5 утра такие задачи как то не очень. Я очень долго тупил с третей (хорошо хоть вроде прошла), а идей по первой вообще не возникло, а теперь посмотрев решение Петра, видимо и по второй тоже :)
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    Я бы сказал что не хватило четвертой простенькой задачи чтобы втянуться и футболки раздать. А так - хороший раунд
    → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Обновилась таблица (выкинули тех, кто посылал под time expired)
Теперь 27 2задачников и у меня 34 место. В GCJ  я попал с 38го...
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Я занял 31 место. Но пока еще не получил загранпаспорт, поэтому если дата онсайта не изменится, то я точно не поеду. В общем, можете считать, что у вас 33 место :)
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Учитывая Калиновича - 7 человек мне еще нужны. Вань, меня на тех же условиях, что и Алекса Скиданова не пропустишь? ;)
      → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Текущая версия поста rng_58 с топкодера:

All competitors who solved at least 2 problems:

1. Petr
2. lyrically
3. tomek
4. meret
5. jakubr
6. rng_58
7. Eryx
8. ACRush
9. andrewzta
10. gnurdux
11. kalinov
12. Akim
13. Zhukov_Dmitry
14. Bolek
15. dgarthur
16. bwps
17. tomekkulczynski
18. Soultaker
19. gawry
20. Xazker
21. Vintik
22. RAD.
23. embe
24. ktuan
25. Jedi_Knight
26. kmod
27. John Dethridge

Top 25 distribution:
Poland(8): tomek, meret, jakubr, Eryx, Bolek, tomekkulczynski, gawry, embe
Russian Federation(7): Petr, andrewzta, Akim, Zhukov_Dmitry, Vintik, RAD., Jedi_Knight
Japan: lyrically, rng_58
China: ACRush
United States: gnurdux
Croatia: kalinov
Canada: dgarthur
Germany: bwps
Netherlands: Soultaker
Ukraine: Xazker
Vietnam: ktuan
→ Ответить