4
\$\begingroup\$

Honestly, I'm doing a practice and get blocked. Problem link.

The problem is simple, given a string, calculate the number of max length palindromes (Any substring is valid, which means you can take any chars you want and reorder them as you want). Return the result modulo 1000000007.

For example, given amim, the answer is 2 (mim and mam).

Full Code

#!/bin/python3

import math
import os
import random
import re
import sys
from itertools import permutations
from functools import lru_cache

# Complete the initialize function below.
def initialize(s):
    # This function is called once before all queries.
    s = [ord(i) - 97 for i in s]
    results = [[0] * 26]
    for i, v in enumerate(s):
        result = results[i].copy()
        result[v] += 1
        results.append(result)
    return results

def count(s):
    result = [0] * 26
    for i in s:
        result[i] += 1
    return result

factorial = lru_cache(None)(math.factorial)

p = 1000000007

pow = lru_cache(None)(pow)

# Complete the answerQuery function below.
def answerQuery(l, r):
    # Return the answer for this query modulo 1000000007.
    counted1 = counted_list[l - 1]
    counted2 = counted_list[r]
    counted = [counted2[i] - counted1[i] for i in range(26)]
    left = 0
    total = 0
    divide = []
    for temp in counted:
        left += temp & 1
        total += temp >> 1
        divide.append(temp >> 1)
    total = factorial(total)
    total = total % p
    for i in divide:
        temp = factorial(i)
        temp = pow(temp, p - 2, p)
        total = total * temp
    result = total * (left or 1)
    return result % p


if __name__ == '__main__':
    s = input()

    counted_list = initialize(s)
    q = int(input())

    for q_itr in range(q):
        lr = input().split()

        l = int(lr[0])

        r = int(lr[1])

        result = answerQuery(l, r)

        print(result)

The code above can pass #0~#21 testcases and will fail in #22 due to timeout. (Just copy it to Problem link page given at the top)

As #22 testcase is very huge, I cannot post it here. So here is the link:

https://files.fm/u/mekwpf8u

If I can use numpy to rewrite this function, I think it will be better. But I cannot, I can only use the standard libs.

update

I use another customized factorial function but exceed memory usage limitation :/ But it really reduces the total time cost.

factorial_table = [1, 1]
def factorial(n):
    if n < len(factorial_table):
        return factorial_table[n]

    last = len(factorial_table) - 1
    total = factorial_table[last]
    for i in range(last + 1, n + 1):
        total *= i
        factorial_table.append(total)

    return total
\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review. Asking for advice on code yet to be written or implemented is off-topic for this site. See What topics can I ask about? for reference. Once you have written working code, you're welcome to ask a new question here and we can then help you improve it! \$\endgroup\$ – Phrancis Jun 27 '18 at 6:02
  • \$\begingroup\$ @Phrancis Um... I don't understand what you mean? I have read your link and I think I am asking a question about best practice? The snippet given in my question is definitely a worked one, but it cost too much time. I want to know which part can be optimized. \$\endgroup\$ – Sraw Jun 27 '18 at 6:14
  • 1
    \$\begingroup\$ @Phrancis I think this is a performance related issue, hence why I'm not voting to close. \$\endgroup\$ – Daniel Jun 27 '18 at 6:29
  • \$\begingroup\$ @Sraw This is a really interesting problem. Can you update your question containing your full code (ie, initialize func, and main), with sample input/output. So others can better understand what it is supposed to do. \$\endgroup\$ – Ludisposed Jun 27 '18 at 8:28
  • \$\begingroup\$ @Ludisposed OK, wait a minute. \$\endgroup\$ – Sraw Jun 27 '18 at 8:40
2
\$\begingroup\$
  • Do % p early.

    Since the test case is huge, I expect intermediate values you compute to be huge as well. Multiplication of large numbers is a very expensive operation. Try to keep your results in a native range. Consider e.g.

    def modulo_factorial(n, mod):
        result = 1
        for i in range(1, n + 1):
            result = (result * i) % mod
        return result
    

    Ditto for pow.

  • Do not recompute factorials from scratch. Instead of

    for i in divide:
        temp = factorial(i)
        temp = pow(temp, p - 2, p)
        total = total * temp
    

    sort divide first. Then computation of each factorial can be started where the previous one ended.

    Also notice that since total is greater than any element of divide, you should compute factorial(total) after the this loop, using the same technique.

    And don't forget to % p early.

  • Most of your imports are never used.

\$\endgroup\$
  • \$\begingroup\$ I thought the same about the first point. But the code I had (which was the same as yours) was always slower than doing the % mod afterwards (for n <= 10**6). I thought this quite surprising. \$\endgroup\$ – Graipher Jun 27 '18 at 19:55
  • \$\begingroup\$ I will try your first point. For the second point and the third point, I have already implement a factorial function like you say, you can see it in my update of question. And the unused imports are imported by default in this practice. As they are default ones, I believe I can pass this case even with these useless imports. Finally, thank you! \$\endgroup\$ – Sraw Jun 28 '18 at 1:26
  • \$\begingroup\$ Wow, your first point is really important. Finally I think I get the most important point and pass all the cases. \$\endgroup\$ – Sraw Jun 28 '18 at 1:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.