HackerEarth Xoring in Base 10 problem solution YASH PAL, 31 July 2024 In this HackerEarth XORing in Base 10 problem solution we have given two numbers A = (A0A1…An) and B = (B0B1…Bn) in base 10, we define the xor of A and B as A . B = (X0X1…Xn), where Xi = (Ai + Bi) mod 10. Little Achraf has an array S of integers in base 10 and he was asked by his professor Toman to find the maximum number he can get by XORing exactly k numbers. HackerEarth Xoring in Base 10 problem solution. #include <cstdio>#include <cstring>#include <string>#include <vector>#include <algorithm>#include <cassert>using namespace std;const int max_len = 10;const int max_nodes = 5000000;struct node { int nxt[10]; node() { memset(nxt, -1, sizeof(nxt)); }};int next_free;node trie[max_nodes];void insert( int root, long long num ) { string digits = to_string(num); digits = string(max_len - int(digits.size()), '0') + digits; int cur = root; for( int i = 0; i < max_len; i++ ) { int j = digits[i] - '0'; if( trie[cur].nxt[j] == -1 ) { assert(next_free + 1 < max_nodes); trie[cur].nxt[j] = next_free++; } cur = trie[cur].nxt[j]; }}void init_trie( void ) { for( int i = 0; i < max_nodes; i++ ) { trie[i] = node(); } next_free = 20;}long long query( int root, long long num ) { long long ret = 0; string digits = to_string(num); digits = string(max_len - int(digits.size()), '0') + digits; int cur = root; for( int i = 0; i < max_len; i++ ) { int d = digits[i] - '0'; int c = 9 - d; for( int j = 0; j < 10; j++ ) { if( trie[cur].nxt[c] != -1 ) { break; } c = (c + 9) % 10; } ret = ret * 10 + (d + c) % 10; cur = trie[cur].nxt[c]; } return ret;}inline long long Xor( long long a, long long b ) { long long ret = 0; long long pw10 = 1; for( int i = 1; i <= max_len; i++ ) { ret += pw10 * ((a+b) % 10); a /= 10; b /= 10; pw10 *= 10; } return ret;}int main( void ) { int n, k; scanf("%i %i", &n, &k); assert(2 <= n && n <= 40); assert(1 <= k && k <= n); vector<long long> S[2]; S[0].resize(n/2); for( int i = 0; i < n/2; i++ ) { scanf("%lld", &S[0][i]); } S[1].resize(n-n/2); for( int i = 0; i < n-n/2; i++ ) { scanf("%lld", &S[1][i]); } bool empty[55]; fill(empty, empty+55, true); init_trie(); int m = (int) S[1].size(); for( int mask = 0; mask < (1<<m); mask++ ) { int sz = __builtin_popcount(mask); if( sz > k ) continue; long long cur = 0; for( int j = 0; j < m; j++ ) { if( mask & (1<<j) ) { cur = Xor(cur, S[1][j]); } } insert(sz, cur); empty[sz] = false; } m = (int) S[0].size(); long long best = 0; for( int mask = 0; mask < (1<<m); mask++ ) { const int num_bits = 22; int sz = __builtin_popcount(mask); if( (sz > k) || empty[k-sz] ) continue; long long cur = 0; for( int j = 0; j < num_bits; j++ ) { if( mask & (1<<j) ) { cur = Xor(cur, S[0][j]); } } best = max(best, query(k-sz, cur)); } printf("%lldn", best); return 0;} Second solution #include <bits/stdc++.h>using namespace std;int n, t;int a[40];int b[40][10];int c[10];vector<array<int, 10>> trie[21];array<int, 10> zero;void rec(int s, int e, int k){ if(s==e) { int cur=0; for(int i=0; i<10; i++) { if(!trie[k][cur][c[i]]) { trie[k][cur][c[i]]=trie[k].size(); trie[k].push_back(zero); } cur=trie[k][cur][c[i]]; } } else { rec(s+1, e, k); for(int i=0; i<10; i++) c[i]=(c[i]+b[s][i])%10; rec(s+1, e, k+1); for(int i=0; i<10; i++) c[i]=(c[i]-b[s][i]+10)%10; }}long long rec2(int s, int e, int k){ if(s==e) { k=t-k; if(k<0 || k>20) return 0; long long ret=0; int cur=0; for(int i=0; i<10; i++) { int d=(10-c[i])%10; ret*=10; bool ok=false; for(int j=9; j>=0; j--) if(trie[k][cur][(d+j)%10]) { ret+=(d+j+c[i])%10; cur=trie[k][cur][(d+j)%10]; ok=true; break; } if(!ok) return 0; } return ret; } else { long long ret=rec2(s+1, e, k); for(int i=0; i<10; i++) c[i]=(c[i]+b[s][i])%10; ret=max(ret, rec2(s+1, e, k+1)); for(int i=0; i<10; i++) c[i]=(c[i]-b[s][i]+10)%10; return ret; }}int main(){ scanf("%d%d", &n, &t); assert(1<=t && t<=n && n<=40); for(int i=0; i<n; i++) { scanf("%d", a+i); assert(0<=a[i] && a[i]<=1000000000); for(int j=0; j<10; j++) { b[i][j]=a[i]%10; a[i]/=10; } reverse(b[i], b[i]+10); } for(int i=0; i<21; i++) trie[i].push_back(zero); int m=n/2; rec(0, m, 0); printf("%lldn", rec2(m, n, 0)); return 0;} coding problems