Flipping coins performance This is the Flipping coins problem on CodeChef:


  There are \$N\$ coins kept on the table, numbered from \$0\$ to \$N - 1\$. Initially, each coin is kept tails up. You have to perform two types of operations:
  
  
  Flip all coins numbered between \$A\$ and \$B\$ inclusive. This is represented by the command "0 A B"
  Answer how many coins numbered between \$A\$ and \$B\$ inclusive are heads up. This is represented by the command "1 A B".
  
  
  Input:
  
  The first line contains two integers, \$N\$ and \$Q\$. Each of the next \$Q\$ lines are either of the form "0 A B" or "1 A B" as mentioned above.
  
  Output:
  
  Output 1 line for each of the queries of the form "1 A B" containing the required answer for the corresponding query.


Out of all the submissions in Python 3.5, none was able to solve it in the provided time limit (probably 0.3s, it is not specified exactly). How can I optimize my code?

n,q = map(int,input().split())
c = [0]*n
for i in range(q):
    j,k,l = list(map(int,input().split()))
    co = 0 
    if j == 1:
        #do Something
        for m in range(k,l+1):
            if c[m] == 1:
                co += 1
        print(co)
    if j == 0:
        #do something
        for m in range(k,l+1):
            if c[m] == 1:
                c[m] = 0
            else:
                c[m] = 1
The code you have posted is straightforward and basic. Because of this, I'm going to assume you are not super-experienced with Python. I'll make some direct suggestions to go from your current code to a faster version of your code, but I don't expect you'll be able to make the time limit with this structure. See @vnp's answer for how to do that.

You wrote:

n,q = map(int,input().split())
c = [0]*n
for i in range(q):
    j,k,l = list(map(int,input().split()))
    co = 0 
    if j == 1:
        #do Something
        for m in range(k,l+1):
            if c[m] == 1:
                co += 1
        print(co)
    if j == 0:
        #do something
        for m in range(k,l+1):
            if c[m] == 1:
                c[m] = 0
            else:
                c[m] = 1


When I read the assignment, this is what I saw:


  There are N coins kept on the table, numbered from 0 to N - 1.
  Initially, each coin is kept tails up. You have to perform two types
  of operations:
  
  1) Flip all coins numbered between A and B inclusive. This is
  represented by the command "0 A B" ...


Yet, when I look at your code, I see this:

for i in range(q):
    j,k,l = list(map(int,input().split()))


You aren't mapping the problem space into your code. This makes it harder for you- and me, and everyone else that sees it- to reason about your code.

Let me suggest right up front that you adopt names that reflect the problem statement whereever possible. Note that in cases where you get clever and use a different algorithm, the names are entirely up to you. In that case, they should not conflict with the problem statement:

N, num_opns = list(map(int, input().split()))

for i in range(num_opns):
    operation, A, B = list(map(int, input().split()))


See the difference? N is N. There are operations that can be 0 or 1. Guess which is the operation? And there are parameters A and B, clearly marked. I haven't changed how it functions, but someone reading the code can now refer to the instructions and see what's what.

Adding Faster

Next, let's look at your two operations. Here's your first one, counting the 1 values:

for m in range(k,l+1):
    if c[m] == 1:
        co += 1


Your code looks at every value, and if it's 1, adds 1 to the count, and if it's not 1, adds nothing to the count.

Now, think like a programmer! Ask, "how can I get rid of any of that code?" In this case, what happens when c[m] is not equal to 1? Why, then, it's equal to 0. And what happens when you add 0 to any number? Nothing - the number doesn't change. So you could change that code to:

for m in range(k,l+1):
    co += c[m]


And get the same result! 

Going further, it turns out that Python has a built-in sum that adds up a sequence of values! You can switch from adding these numbers in Python to having Python's interpreter add the numbers in C. That should speed things up nicely:

co = sum(c[k:l+1])


There's two things going on in there. The first, c[k:l+1] is called a slicing expression. It creates a "sub-list" of the c list, with just the values in question. The second is the use of the sum() built-in.

Switching Faster

Your second operation just changes values:

for m in range(k,l+1):
    if c[m] == 1:
        c[m] = 0
    else:
        c[m] = 1


There are a couple of ways to speed this up, and they all involve doing some kind of single operation instead of an if statement. For example, you could perform a bitwise exclusive-or of the value with 1. Bitwise xor is also bitwise (no borrow) subtraction modulo 2, so when you xor things 0 becomes 1, and 1 becomes 0.

for m in range(k,l+1):
    c[m] ^= 1


Alternatively, you could store the values in a tuple and map the old value to the new value:

new_values = (1, 0)
for m in range(k,l+1):
    c[m] = new_values[c[m]]


Finally, I'll point you at the timeit module, which is the standard Python way of measuring speed. If you are trying to beat a time limit in any challenge, make sure you use timeit so you can keep track of what effect every change you make has on performance.