UVA 10324 - Zeroes and One

help
1

I am getting the Time Limit Exceeded Error in the code which i wrote. First I tried by appending values into the empty list and checking the length of list. But i also though that was a lot of runtime. So i tried by creating Counter, which possibily i guess reduced time. Pls help me with my code.

from collections import Counter

test=1
while True:
    pattern=input()
    if pattern=="":
        break
    else:
        print('Case {}:'.format(test))
        n = int(input())
        for t in range(0, n):
            i, j = map(int, input().split())
            if i > j:
                i, j = j, i
            if i == j:
                print('Yes')
            else:
                    count = Counter(pattern[i:j + 1])
                    if len(count) > 1:
                        print('No')
                    else:
                        print('Yes')
        test += 1
2

You are processing queries in O(|j-i|), which is too slow. You can process queries in O(1) if you use prefix sums. Store the number of ones till each position, and find the number of ones from i to j. If it’s 0 or j-i+1, then print yes, otherwise print no.

Code 
import sys
try:
    tests=1
    while(tests):
        seq=sys.stdin.readline()
        prefixsums=[]
        prefixsums.append(0)
        for i in range(len(seq)):
            if(seq[i]=='1'):
                prefixsums.append(prefixsums[i]+1)
            else:
                prefixsums.append(prefixsums[i])
        Q=int(sys.stdin.readline())
        print("Case "+str(tests)+":")
        for i in range(Q):
            i,j=map(int, sys.stdin.readline().split())
            if(i>j):
                i,j=j,i
            if(prefixsums[j+1]-prefixsums[i] == j-i+1 or prefixsums[j+1]==prefixsums[i]):
                print("Yes")
            else:
                print("No")
        tests+=1
except:
    pass
3

Thanks a lot for the help! I really appreciate it :slight_smile: