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

Автор witua, 12 лет назад, По-английски

Hi!

I'm glad to invite you to my short contest on codechef.com on Sunday, 18th. (Check your time zone here.) I also want to note that Anton_Lunyov help my a lot in preparing of the contest, thanks to him.

In order to take part in the contest you should be registrated on the site, you don't need a separate registration for the contest. The competition will consist of 5 problems for 2.5 hours, using the standard ACM-ICPC rules.

After the contest you can discuss problems here and public all your wishes for the next contests.

Good Luck!

P. S. Please also note that CodeChef is now using much faster judging server!

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

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

I didn't know about this site(codechef), thank you.

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

Nice to see you as an author of Cook-Off again. Waiting for a good contest, as always:)

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

I enjoyed the contest. Thank you :) Those "Lucky" problems are becoming classics :D

How to solve "Little Elephant and Lucky Segment". Does anyone has any ideas? :)

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

    My approach is to divide into several cases.

    The number of pairs (C4, C7) is quite small when C7 > 2.

    C7 = 0 is trivial.

    C7 = 1 is probably the most tricky part. Let S4[i] is sum of F4 of the first i numbers. For each i, we need to count how many j in some segments [L, R] such that S4[i] - S4[j] <= i - j. Let T[i] = S4[i] - i, the condition becomes T[i] <= T[j]. This can be done by using Binary Indexed Tree (Fenwick Tree).

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

Опять тупые задачи. Ни одной интересной так для себя и не нашел(

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

Little Elephant and Lucky Segment — такая классная ИДЕЙНАЯ задача на разбор 100500 случаев, я просто тащусь.

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

    Ну что прям так критично. Там фактически два принципиально разных случая. Когда C7=1, там надо за логарифм решать, например, деревом отрезков или можно обычной сортировкой и бинпоиском, если подумать. Если С7!=1, то совсем тупо, перебираем все пары (С4, С7), которые подходят. Ну да, надо аккуратно разобрать случаи C4=0,1, С7=0. Но в этом же ничего такого нет. Если правильно кодить, то получается очень нормально. А 2-ку убрали, потому что N * sqrt(N) медленно работает.

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

      ну спорить с вами не стану, останусь при мнении, что не самая подходящая задача для одной из самых сложных.

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

быстрота сервера порадовала, однако

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    Я даже пофиксил template.

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

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

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

      Эх. Если б все так просто было. Когда решение за линию то самым тормозным местом становится считывание и с помощью всяких fread можно и log проталкивать. А переход к генераторам инпутов внутри входных данных усложняет подготовку.