witua's blog

November Cook-Off
By witua, 11 years ago, In English

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!

  • Vote: I like it
  • +55
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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? :)

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 11   Vote: I like it +3 Vote: I do not like it

    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).

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +47 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
11 years ago, # |
  Vote: I like it +24 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

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

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply