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.

#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 solutions