Header Ad

HackerEarth Xoring in Base 10 problem solution

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


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("%lld\n", 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("%lld\n", rec2(m, n, 0));
return 0;
}

Post a Comment

0 Comments