Please read the new rule regarding the restriction on the use of AI tools. ×

code_kika's blog

Codechef's August Challenge Discussion
By code_kika, history, 8 years ago, In English

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 .

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

»
8 years ago, # |
← Rev. 3   Vote: I like it +19 Vote: I do not like it

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

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

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

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

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

    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!

    → Reply