Clarification in Chefs in Queue Problem

In Chefs in Queue problem, if I don’t do modulo for product by 10 power 9+7 in the intermediate stages and do it only at the end , it is giving me TLE.
Whereas when i do the modulo for product by 10 power 9+7 in intermediate stages also then it is giving AC.
what may be the reason for this? Is it numerical overflow?

Share link to your solution.

Without the link, I think TLE is not Overflow. Overflows lead to WA. Most likely you are using long long, so you are not getting Overflow but the complexity of multiplying large numbers is probably TLE.

For (a*b) mod m, I always do (a mod m * b mod m + m) mod m.

It’s slightly important to mention that you’re using python, where there is no overflow - that’s why submission links are necessary. If you’re working with enormous numbers with thousands of digits, doing a single operation on them will have the complexity of their number of digits.

1 Like

How are large numbers stored in Python? Does it always use binary representation? Or when the value crosses 64-bit max value it dynamically implements bignumber datatypes?

If you declare a sufficiently large number, it takes it as a big num. Internally, these big nums are represented as array of conventional numbers. Hence the problem. We might end up multiplying a 1000 digit number with a 1000 digit number.

Karatsuba multiplication will put complexity at O(n^log3).

@abhi_telukunta
My two cents, python not worth it for CP. Generally we use Python to make life easier. But in CP, we have to work very hard to make Python run code that CPP will zerg through. Bucky C++ videos (on youtube) will make you ready in a day. Read the blog below after that:

https://codeforces.com/blog/entry/10124

1 Like

This is the link to my solution which gave me TLE:
https://www.codechef.com/viewsolution/35725130
This is the link to my solution which gave me AC:
https://www.codechef.com/viewsolution/35725345

This is the link to my solution which gave me TLE:
https://www.codechef.com/viewsolution/35725130
This is the link to my solution which gave me AC:
https://www.codechef.com/viewsolution/35725345
I did it in python 3

# cook your dish here
n,k=map(int,input().split())
arr=[int(x) for x in input().split()]
prod=1
l=[]
for i in range(n):
    while len(l)!=0 and l[-1][0]>arr[i]:
        prod*=(i-l[-1][1]+1)
        l.pop()
    l.append([arr[i],i])
print(prod%1000000007)

prod*=(i-l[-1][1]+1) means keep on accumulating prod. When a 3 digit number is multiplied by 3 digit, you get 5 digit number. 5X5 = 9 digits. 9X9 = 17 digits. 17X17 = 33 digits. 33X33= 65 digits. so on and so forth.
The cost of multiplying 2 65 digit numbers is 65^log3 is O(800).
Cost of multiplying 2 7 digit numbers is O(25). In other words, first operation is 32 times more expensive.
Do you now understand why TLE?

@dardev Thank you for your advice. But I am habituated to Python 3 so much that I cannot switch from it to CPP. Python makes me really very comfortable to code.

okay cleared thanks!!

If you are going to use python, a few pointers:

  1. Write your solution inside a function. Lookup variables in the global scope is more expensive, than using variables in the local scope.
  2. Avoid for loops like the plague . Favor Python builtins. Always use map , filter , concatenate strings with join , etc.
  3. Writing output is really expensive. Writting a gigantic string once, may be better than writting several small strings.
  4. Type casting is really expensive. Avoid if possible (string to int).
  5. Avoid dots. In other words: Cache function lookups. Example: Avoid using stdout.write directly, put it in a variable w = stdout.write .
  6. Careful with Dict vs Lists for graphs

xposted from: https://codeforces.com/blog/entry/46459?