How to make this code run within time limit?
def change(string, l, r, ch): l1 = list(string) first = "".join(l1[:l-1]) for i in range(l-1, r): l1[i] = ch str1 = "".join(l1[l-1:r]) last = "".join(l1[r:]) rtnStr = first+str1+last return rtnStr def swap(string, l1, r1, l2, r2): l = list(string) first = "".join(l[:l1-1]) str1 = "".join(l[l1-1:r1]) str3 = "".join(l[r1:l2-1]) str2 = "".join(l[l2-1:r2]) last = "".join(l[r2:]) rtnStr = first+str2+str3+str1+last # print(rtnStr) return rtnStr def reverse(string, l, r): l1 = list(string) first = "".join(l1[:l-1]) nstr = "".join(l1[l-1:r]) rstr = nstr[::-1] last = "".join(l1[r:]) rtnStr = first+rstr+last # print(rtnStr) return rtnStr def hamming(string, l1, l2, r): str1 = string[l1-1:l1+r-1] str2 = string[l2-1:l2+r-1] count = 0 for i in range(0, r): if str1[i] != str2[i]: count += 1 print(count) def solveQuery(givenString, *a): if a[0] == 'C': givenString = change(givenString, int(a[1]), int(a[2]), a[3]) elif a[0] == 'S': givenString = swap(givenString, int( a[1]), int(a[2]), int(a[3]), int(a[4])) elif a[0] == 'R': givenString = reverse(givenString, int(a[1]), int(a[2])) elif a[0] == 'W': print(givenString[int(a[1]) - 1:int(a[2])]) else: hamming(givenString, int(a[1]), int(a[2]), int(a[3])) return givenString def callFunction(l, n, s): for i in range(0, n): prams = l[i].split(" ") s = solveQuery(s, *prams) if __name__ == "__main__": l = int(input()) s = input() n = int(input()) querys = [] for i in range(0, n): querys.append(input()) callFunction(querys, n, s)
include
include
include
include
include
include
include
using namespace std; string func(char ch,string s) { if(ch=='C') { int l,r; cin>>l>>r; char ch; cin>>ch; for(int i=l-1;i>l1>>r1>>l2>>r2; s1=s1+s.substr(l1-1,r1-l1+1); s2=s2+s.substr(l2-1,r2-l2+1); string s3=s.substr(0,l1-1); string s4=s.substr(r2-1,s.size()-r2); string s5=s.substr(r1,l2-r1-1); s=s3+s2+s5+s1+s4; cout<
} else if(ch=='R') { int l,r; cin>>l>>r; reverse(s.begin()+l-1,s.begin()+r); cout<<s<<endl; } else if(ch=='W') { int l1,r1; cin>>l1>>r1; string s1=s.substr(l1-1,r1-l1+1); cout<<s1<<endl; cout<<s<<endl; } else if(ch=='H') { int count=0; int l1,l2,l; cin>>l1>>l2>>l; string s1=s.substr(l1-1,l); string s2=s.substr(l2-1,l); for(int i=0;i<s1.size();i++) { if(s1[i]!=s2[i]) count++; } cout<<count<<endl; cout<<s<<endl; } return s;}
int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */
int n; string s; cin>>n>>s; int m; cin>>m; for(int i=0;i>c; s=func(c,s); }} CAN ANYONE TELL WHERE I AM WRONG I HAVE PRINTED COUT IN EACH CASE JUT TO CHECK WHAT HAPPENS IN EVERYCASE } return 0; }
# Hamming Distance from timeit import default_timer as timer def R(string,i,j): prev = [] next = [] rev = [] for x in range(i-1): prev.append(string[x]) for x in range(j,len(string)): next.append(string[x]) for x in range(i-1,j): rev.append(string[x]) rev.reverse() reversed_string = "".join(str(x) for x in prev) + "".join(str(x) for x in rev) + "".join(str(x) for x in next) return reversed_string def W(string,i,j): for i in range(i-1,j): print(string[i],end="") print() def S(string,i1,j1,i2,j2): prev = [] middle = [] next = [] string1 = [] string2 = [] for x in range(i1-1): prev.append(string[x]) for x in range(i1-1,j1): string1.append(string[x]) for x in range(j1,i2-1): middle.append(string[x]) for x in range(i2-1,j2): string2.append(string[x]) for x in range(j2,len(string)): next.append(string[x]) swapped_string = "".join(str(x) for x in prev) + "".join(str(x) for x in string2) + "".join(str(x) for x in middle) + "".join(str(x) for x in string1) + "".join(str(x) for x in next) return swapped_string def C(string,i,j,ch): prev = [] next = [] equal = [] for x in range(i-1): prev.append(string[x]) for x in range(j,len(string)): next.append(string[x]) for x in range(i-1,j): equal.append(ch) changed_string = "".join(str(x) for x in prev) + "".join(str(x) for x in equal) + "".join(str(x) for x in next) return changed_string def H(string,i,j,length): distance = 0 first = string[i-1:(i-1)+length] second = string[j-1:(j-1)+length] for i in range(len(first)): if first[i] != second[i]: distance += 1 return distance string_size = int(input()) string = input() command_size = int(input()) commands = [] for i in range(command_size): command = input() command_list = command.split(" ") commands.append(command_list) if string_size == len(string): if command_size == len(commands): for i in commands: if i[0] == "R": string = R(string,int(i[1]),int(i[2])) if i[0] == "W": W(string,int(i[1]),int(i[2])) if i[0] == "S": string = S(string,int(i[1]),int(i[2]),int(i[3]),int(i[4])) if i[0] == "C": string = C(string,int(i[1]),int(i[2]),i[3]) if i[0] == "H": distance = H(string,int(i[1]),int(i[2]),int(i[3])) print(distance)
I am trying to solve the problem using python.When I submit the code it passes only the first 10 test cases, and for the other 30 it says that Terminated due to timeout. It runs perfectly on my editor. What am I doing wrong here ? Thank you.
I am trying to solve the problem using python.When I submit the code it passes only the first 10 test cases, and for the other 30 it says that Terminated due to timeout. It runs perfectly on my editor. What am I doing wrong here ? Thank you.
Hamming Distance
from timeit import default_timer as timer
def R(string,i,j): prev = [] next = [] rev = [] for x in range(i-1): prev.append(string[x]) for x in range(j,len(string)): next.append(string[x]) for x in range(i-1,j): rev.append(string[x]) rev.reverse() reversed_string = "".join(str(x) for x in prev) + "".join(str(x) for x in rev) + "".join(str(x) for x in next) return reversed_string
def W(string,i,j): for i in range(i-1,j): print(string[i],end="") print()
def S(string,i1,j1,i2,j2): prev = [] middle = [] next = [] string1 = [] string2 = [] for x in range(i1-1): prev.append(string[x]) for x in range(i1-1,j1): string1.append(string[x]) for x in range(j1,i2-1): middle.append(string[x]) for x in range(i2-1,j2): string2.append(string[x]) for x in range(j2,len(string)): next.append(string[x])
swapped_string = "".join(str(x) for x in prev) + "".join(str(x) for x in string2) + "".join(str(x) for x in middle) + "".join(str(x) for x in string1) + "".join(str(x) for x in next) return swapped_stringdef C(string,i,j,ch): prev = [] next = [] equal = [] for x in range(i-1): prev.append(string[x]) for x in range(j,len(string)): next.append(string[x]) for x in range(i-1,j): equal.append(ch) changed_string = "".join(str(x) for x in prev) + "".join(str(x) for x in equal) + "".join(str(x) for x in next) return changed_string
def H(string,i,j,length): distance = 0 first = string[i-1:(i-1)+length] second = string[j-1:(j-1)+length] for i in range(len(first)): if first[i] != second[i]: distance += 1 return distance
string_size = int(input()) string = input() command_size = int(input()) commands = [] for i in range(command_size): command = input() command_list = command.split(" ") commands.append(command_list)
if string_size == len(string): if command_size == len(commands): for i in commands: if i[0] == "R": string = R(string,int(i[1]),int(i[2])) if i[0] == "W": W(string,int(i[1]),int(i[2])) if i[0] == "S": string = S(string,int(i[1]),int(i[2]),int(i[3]),int(i[4])) if i[0] == "C": string = C(string,int(i[1]),int(i[2]),i[3]) if i[0] == "H": distance = H(string,int(i[1]),int(i[2]),int(i[3])) print(distance)
In Python3, I've used bin(x).count('1') to calc the hamming distance. C, R and S operations are operatated over a BigInteger converted from the ab string and I think they are sufficiently fast. W operation seems fast enough either.
At test 21, where 99% of the time is consumed in H operations, this still hits TLE. It takes 16 secs to process 49937 of H operations on my local machine. Google does not give a faster python algo to count bits set to 1 (in x ^ y).
Has anybody succeeded to pass all the tests in python (without hardcoding)?
Sort 25 Discussions, By:
Please Login in order to post a comment