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

Codechef's August Challenge Discussion
Автор code_kika, история, 8 лет назад, По-английски

https://www.codechef.com/AUG16 Every month Codechef organises a Long Challenge of 10 questions. Many users of Codeforces do try the Long Challenges. As the discussion forums of Codechef is inactive than that of Codeforces, it would be nice if users discussed their solutions for the questions. Especially from task 5 as they usually have many different solution and it would be helpful for others too .

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

»
8 лет назад, # |
← Rev. 3   Проголосовать: нравится +19 Проголосовать: не нравится

Did anyone have a simple solution to "A Good Problem?"

Also, how long does it usually take for the editorial to come out?

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

    Usually the editorials are out within a day. This time there is an unusual delay.

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

    Good day to you!

    I have a solution, anyway it is not good (well it got AC, but it is consists of "limits-tuning")

    At first, make solution, which can solve "40pt" (lets call it "foo(L,R)")

    Also let us have BIT-TRIE, with following operations: ADD/DELETE/SUM{1,2}

    SUM1(A) find number of elements for which the "AND" condition is true.

    SUM2(TRIE) finds number of combinations of elements from first/second trie, for which the "AND" condition is true.

    Also as precalculation, make a RMQ which finds maximum(along with index) on interval.

    Now let us make recursion, which can solve "Left → Right" interval, starting with full TRIE.

    Now, if the interval is LESSER than a "chosen constant" (5000 is OK), use your "40pt" solution, which deals with it in O(N^2)

    Otherwise, find index of MAXIMUM, and split interval into two halves (left/right of the maximum). First, add TRIE.SUM1(MAX) to your solution. Then lake LESSER half and move all elements from the half from TRIE to TRIE2. Then add TRIE2.SUM2(TRIE) to your solution.

    The continue with solution of both halves separately.

    Well I guess it is all. I know I'm bad at explaining, so don't hesitate to ask.

    PS: I made little measurement, and "SUM2" takes a few milion operations (+/- 40 times better than number of combinations)

    Here is the solution (hope the link is working)

    Good Luck & Have nice day!

    → Ответить