SPOJ "SBANK - Sorting Bank Accounts" TLE

Question

I am new tro programming and have chosen python 2.7 to begin with. But, I often have to deal with a TLE while competitive coding like in the problem below, where my code runs fine on all test cases but runs out of the given time bound.

My code runs fine on Ideone.com for all the given test cases, but gives a TLE on SPOJ.

This is the SBANK problem at SPOJ.

In one of the internet banks thousands of operations are being performed every day. Since certain customers do business more actively than others, some of the bank accounts occur many times in the list of operations. Your task is to sort the bank account numbers in ascending order. If an account appears twice or more in the list, write the number of repetitions just after the account number. The format of accounts is as follows: 2 control digits, an 8-digit code of the bank, 16 digits identifying the owner (written in groups of four digits), for example (at the end of each line there is exactly one space):

30 10103538 2222 1233 6160 0142

Banks are real-time institutions and they need FAST solutions. If you feel you can meet the challenge within a very stringent time limit, go ahead! A well designed sorting algorithm in a fast language is likely to succeed.

---

My code as follows :

def neww(k):
    neww=sorted(set(x+"%d"%(k.count(x)) for x in k))
    for each in neww:
        print each
for _ in range(int(raw_input())):
    p=raw_input()
    if p=='':
        p=raw_input()
    k=[raw_input() for _ in xrange(int(p))]
    neww(k)
    print ""

Answer 1

Time limit exceeded

When a solution is too slow, it's typically because the algorithm is one or more orders of magnitude worse than intended for the challenges. So take a hard look at the time complexity of the implementation.

In your implementation, it all comes down to this expression:

sorted(set(x+"%d"%(k.count(x)) for x in k))

• k.count(x) : the centerpiece of the expression, to find the count of some value in a list. The count function does this by iterating over all elements k, and checking each for equality with x. Time complexity: \$O(N)\$, where N is the number of items in k

• ... for x in k : do something for each item in k. Again, \$O(N)\$, where N is the number of items in k

• set(...) : probably \$O(N)\$

• sorted(...) : probably \$O(N\log(N))\$

In total that gives: \$O(N^2) + O(N) + O(N\log(N))\$

Can this be better?

• You need to sort, that's for sure. That's fast enough.

• Do you really need a set? You used a set because the previous operations generate a list with duplicates. Using a set to remove duplicates is fine, but I would question why are duplicates at all in the first place.

• The previous two items actually don't even matter. It's the slowest operation in the \$O(N^2) + O(N) + O(N\log(N))\$ that will drag everything down, the \$O(N^2)\$, so that's what you really need to optimize.

Instead of iterating over every account number for each account number, you could iterate only once, building a dictionary with counts along the way:

def print_sorted_with_count(accounts):
    counts = {}
    for account in accounts:
        counts[account] = counts.get(account, 0) + 1
    for account, count in sorted(counts.items()):
        print('{} {}'.format(account, count))

This implementation reduces the time complexity from \$O(N^2)\$ to \$O(N)\$, and also gets rid of an \$O(N)\$ operation (no more need for the set.)

UPDATE

As @abarnert pointed out, the dictionary of counts can be created with a single expression using collections.Counter, so the above code can become simply:

from collections import Counter


def print_sorted_with_count(accounts):
    counts = Counter(accounts)
    for account, count in sorted(counts.items()):
        print('{} {}'.format(account, count))

Naming

The variable names in the posted code are horrible, and it makes it very hard to read. Avoid single-letter variable names, try to use descriptive names.

Coding style

I suggest to follow the recommendations of PEP8.