Hamming Distance
Hamming Distance
+ 1 comment Solution C++
#include <algorithm> #include <cstdio> #include <cstdint> #include <set> using namespace std; #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define REP(i, n) for (int i = 0; i < (n); i++) int ri() { int x; scanf("%d", &x); return x; } const int N = 50000, NN = (N+63)/64; char a[N+1]; typedef uint64_t u64; u64 rev(u64 x) { x = (x & 0xaaaaaaaaaaaaaaaaull) >> 1 | (x & 0x5555555555555555ull) << 1; x = (x & 0xccccccccccccccccull) >> 2 | (x & 0x3333333333333333ull) << 2; x = (x & 0xf0f0f0f0f0f0f0f0ull) >> 4 | (x & 0x0f0f0f0f0f0f0f0full) << 4; x = (x & 0xff00ff00ff00ff00ull) >> 8 | (x & 0x00ff00ff00ff00ffull) << 8; x = (x & 0xffff0000ffff0000ull) >>16 | (x & 0x0000ffff0000ffffull) <<16; return x >> 32 | x << 32; } struct BitSet { u64 a[NN]; BitSet() { clear(); } void clear() { fill_n(a, NN, 0); } void flip(int i) { a[i>>6] ^= 1ull << (i&63); } int get(int i) const { return a[i>>6] >> (i&63) & 1; } void set(int i, int v) { if (get(i) != v) flip(i); } void word(int i, u64 w) { int j = i>>6; a[j] |= w << (i&63); i += 63; j = i>>6; if (j < NN) a[j] |= w >> 63-(i&63); } BitSet shr(int i) { BitSet ret; int o = i & 63, shift = i/64; if (! o) REP(i, NN-shift) ret.a[i] = a[i+shift]; else { REP(i, NN-shift-1) ret.a[i] = a[i+shift]>>o | a[i+shift+1]<<64-o; ret.a[NN-shift-1] = a[NN-1]>>o; } return ret; } void fill(int l, int r, int v) { for (int i = l; i < r; ) if (i&63 || i+63 >= r) { set(i, v); i++; } else { a[i>>6] = v ? -1ull : 0; i += 64; } } void copy(const BitSet &o, int l, int r, int to) { int shift = to-l; for (int i = l; i < r; ) if (i&63 || i+63 >= r) { set(i+shift, o.get(i)); i++; } else { word(i+shift, o.a[i>>6]); i += 64; } } void reverse(int l, int r) { BitSet t = *this; fill(l, r, 0); for (int i = l; i < r; ) if (i&63 || i+63 >= r) { set(r-1-(i-l), t.get(i)); i++; } else { word(r-64-(i-l), rev(t.a[i>>6])); i += 64; } } BitSet operator^(const BitSet &o) const { BitSet ret; REP(i, NN) ret.a[i] = a[i] ^ o.a[i]; return ret; } }; int main() { int n = ri(); BitSet b; scanf("%s", a); REP(i, n) if (a[i] == 'b') b.flip(i); for (int m = ri(); m--; ) { char op; scanf(" %c", &op); int x = ri()-1, y = ri(); switch (op) { case 'C': { scanf(" %c", &op); b.fill(x, y, op-'a'); break; } case 'R': b.reverse(x, y); break; case 'W': FOR(i, x, y) a[i-x] = 'a'+b.get(i); a[y-x] = '\0'; puts(a); break; case 'S': { int xx = ri()-1, yy = ri(); BitSet t = b; b.fill(x, yy, 0); b.copy(t, x, y, yy-(y-x)); b.copy(t, y, xx, x+(yy-xx)); b.copy(t, xx, yy, x); break; } case 'H': { y--; if (x > y) swap(x, y); int z = ri(), pop = 0; BitSet t = b ^ b.shr(y-x); for (int i = x; i < x+z; ) if (i&63 || i+63 >= x+z) pop += t.get(i++); else { pop += __builtin_popcountll(t.a[i>>6]); i += 64; } printf("%d\n", pop); break; } } } }
+ 2 comments hey guys, is the sample output correct? I think both tge 1st and 3rd answers are not correct. What do you think?
+ 2 comments I wrote efficient functions for doing these specific queries over a bit-packed array in C++14. The slowest executing test took 0.44s.
I also wrote a much easier solution that uses vector(char) and doesn't bit-pack. It only took a couple minor optimizations to the hamming distance and print functions and it executed the slowest test at around 1.9s - just barely fast enough, I wonder if that was even "supposed" to work. The constraints on N and M aren't enough to force the use of bitpacking it seems.
Another funny thing - vector(bool) performed worse than vector (char).
+ 1 comment Could you verify the time needed for the solutions in Python? I'm getting timeout using Python but it seems no one could resolve this problem in Python until now.
+ 1 comment # 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.
Sort 25 Discussions, By:
Please Login in order to post a comment