INVASION-Editorial

PROBLEM LINK:

Practice
Alien Invasion

Author: chirag_mathur
Testers: hellb0y_suru, valiant_vidit, abhinav42
Editorialist: chirag_mathur

DIFFICULTY:

EASY

PROBLEM:

Given a numerical system consisting of {! #,%,*,@}.

  • Predict the next/upcoming magical year from the given year Y.
  • Add the given age A to the magical year and print the new age X

Prerequisites:

  • knowledge of sorting and recursion.
  • A little amount of brain to be applied while solving or understanding the editorial :wink:

QUICK EXPLANATION:

Try storing all the magical years in a vector in a sorted manner, then find the upcoming/next magical year using lower_bound function and add it to the given age.

EXPLANATION:

According to the rules of the magical year, the magical year will be of even length and consists of only '! and ‘*’. First, we will precompute a vector with all the magical years till length 16 consisting of ‘!’ and ‘*’ using recursive function. If the length of the given year is odd then the next magical year will be the smallest possible magical year of length + 1 and if it is of even length then we can find the next magical year using lower_bound function from the precomputed vector. If the given year is a magical year then we have to take the next magical year.

Then we can define the rules of adding and carry forwarding in the given numerical system consisting of {!,#,%,*,@} for each character and then we can add the two strings which are a magical year and the given age and then print the resulting string which is the age.

The complexity of the code is O(k + T*log(n)) where k is the constant time taken to precompute the vector consisting magical year and T is the number of testcases.

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<string> v;
ll n;

char addc(char a, char b)
{
   if (a == '!')
   {
       return b;
   }
   else if (b == '!')
   {
       return a;
   }
   else
   {
       if (a == '#' && b == '#')
       {
           return '%';
       }
       else if (a == '%' && b == '%')
       {
           return '@';
       }
       else if (a == '*' && b == '*')
       {
           return '#';
       }
       else if (a == '@' && b == '@')
       {
           return '*';
       }
       else if (a == '#' && b == '%' || b == '#' && a == '%')
       {
           return '*';
       }
       else if (a == '#' && b == '*' || b == '#' && a == '*')
       {
           return '@';
       }
       else if (a == '#' && b == '@' || b == '#' && a == '@')
       {
           return '!';
       }
       else if (a == '%' && b == '@' || b == '%' && a == '@')
       {
           return '#';
       }
       else if (a == '%' && b == '*' || b == '%' && a == '*')
       {
           return '!';
       }
       else
       // else if (a == '*' && b == '@' || b == '*' && a == '@')
       {
           return '%';
       }
   }
}
char carryc(char a, char b)
{
   if (a == '!')
   {
       return '!';
   }
   else if (b == '!')
   {
       return '!';
   }
   else
   {
       if (a == '#' && b == '#')
       {
           return '!';
       }
       else if (a == '%' && b == '%')
       {
           return '!';
       }
       else if (a == '*' && b == '*')
       {
           return '#';
       }
       else if (a == '@' && b == '@')
       {
           return '#';
       }
       else if (a == '#' && b == '%' || b == '#' && a == '%')
       {
           return '!';
       }
       else if (a == '#' && b == '*' || b == '#' && a == '*')
       {
           return '!';
       }
       else if (a == '#' && b == '@' || b == '#' && a == '@')
       {
           return '#';
       }
       else if (a == '%' && b == '@' || b == '%' && a == '@')
       {
           return '#';
       }
       else if (a == '%' && b == '*' || b == '%' && a == '*')
       {
           return '#';
       }
       else
       // else if (a == '*' && b == '@' || b == '*' && a == '@')
       {
           return '#';
       }
   }
}

string finalage(string yr, string age)
{
   string x = yr.length() >= age.length() ? yr : age;
   string y = age.length() <= yr.length() ? age : yr;
   string fage = "";

   int diff = x.length() - y.length();
   for (int i = 1; i <= diff; i++)
   {
       y = '!' + y;
   }
 
   char fcarry = '!';
   char c1, c2, a1, a2;
   for (int i = x.length() - 1; i >= 0; i--)
   {
       c1 = carryc(fcarry, x[i]);
       a1 = addc(fcarry, x[i]);
       c2 = carryc(a1, y[i]);
       a2 = addc(a1, y[i]);
       fage = a2 + fage;
       fcarry = addc(c1, c2);
   }
   if (fcarry != '!')
   {
       fage = fcarry + fage;
   }

   return fage;
}

void getpossiblevalues(string value, int numberemark, int numberstar)
{
   if (value.length() > 16)
       return;
   if (numberemark == numberstar)
       v.push_back(value);
   getpossiblevalues(value + '*', numberemark, numberstar + 1);
   if (value.length() != 0)
       getpossiblevalues(value + '!', numberemark + 1, numberstar);
}
int main()
{
   getpossiblevalues("", 0, 0);
   sort(v.begin(), v.end());
   //cout<<v.size()<<endl;

   vector<string> v1[9];
   for (int i = 0; i <= v.size(); i++)
   {
       v1[v[i].length() / 2].push_back(v[i]);
   }
   ll t;
   cin >> t;
   while (t--)
   {

       string year;
       string age;
       cin >> year;
       cin >> age;

       string magicalyr = "";
       int len = year.length();

       if (year.length() % 2 != 0)
       {
           magicalyr = v1[(year.length() + 1) / 2][0];
       }
       else
       {
           if (lower_bound(v1[year.length() / 2].begin(), v1[year.length() / 2].end(), year) == v1[year.length() / 2].end())
           {
               magicalyr = v1[(year.length() / 2) + 1][0];
           }
           else
           {
               int pos = lower_bound(v1[year.length() / 2].begin(), v1[year.length() / 2].end(), year) - v1[year.length() / 2].begin();
               magicalyr = v1[(year.length() / 2)][pos];
               if (year == magicalyr)
               {
                   magicalyr = pos + 1 < v1[(year.length() / 2)].size() ? v1[(year.length() / 2)][pos + 1] : v1[((year.length() / 2) + 1)][0];
               }
           }
       }
       //cout<<magicalyr<<endl;
       cout << finalage(magicalyr, age) << endl;
   }

   return 0;
} 
Tester's Solution 1
#include <bits/stdc++.h>
using namespace std;

// ! # % * @

vector<long long int> v;

long long int changeTo10(long long int n){
   long long int cnt = 1,ans=0;
   while(n>0){
       ans+= cnt*(n%10);
       n/=10;
       cnt*=5;
   }
   return ans;
}
long long int changeTo5(long long int n){
   vector<long long int> temp;
   while(n>0){
       temp.push_back(n%5);
       n/=5;
   }
   reverse(temp.begin(),temp.end());
   long long int ans = 0;
   for(auto &i: temp) ans=ans*10 + i;
   return ans;
}
long long int add(long long int &n, long long int x){
  long long int a = changeTo10(n) , b = changeTo10(x);
  a = a + b;
  return changeTo5(a);
}


void gen(int zero, int once, long long int ans){
   if(zero==0 && once==0){
       v.push_back(ans);
       return;
   }
   else{
       if(once>0){
           gen(zero,once-1, (ans*10) + 3 );
       }
       if(zero>0){
           gen(zero-1,once,ans*10);
       }
       
   }
}

long long int strToNum(string &a){
   long long int ans=0;
   for(int i=0;i<a.size();i++){
       if(a[i]=='!') ans=ans*10;
       else if(a[i]=='#') ans=ans*10 + 1;
       else if(a[i]=='%') ans=ans*10 + 2;
       else if(a[i]=='*') ans=ans*10 + 3;
       else if(a[i]=='@') ans=ans*10 + 4;
   }
   return ans;
}

string NumToStr(long long int n){
   string res="";
   if(n==0){
       res = '!';
       return res;
   }
   else{
       while(n>0){
           if( n%10 == 0 ) res = '!' + res;
           else if( n%10 == 1 ) res = '#' + res;
           else if( n%10 == 2 ) res = '%' + res;
           else if( n%10 == 3 ) res = '*' + res;
           else if( n%10 == 4 ) res = '@' + res;
           n/=10;
       }
       return res;
   }
}


void sol(){
   string a,b; cin >> a >> b;
   long long int x = strToNum(a) , y = strToNum(b);
   if(x >= 33333330000000) x = 3000000003333333;
   else{
       auto it = upper_bound(v.begin(),v.end(),x);
       x = *it;
   }
   x = add(x,y);
   cout << NumToStr(x)<<"\n";
}

int main() {
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);
   for(int i=1;i<=7;i++) gen(i,i-1,3LL);
   sort(v.begin(),v.end());
   long long int t; cin >> t;
   while(t--) sol();
}

Tester's Solution 2

/*author : vidit shukla
          (valiant_vidit)*/
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long int
#define ld long double
#define bhaago ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define loop(a, b, i) for (ll i = a; i < b; i++)
#define loop1(a, b, i) for (ll i = a; i > b; i--)
#define printclock cerr << "Time : " << 1000 * (ld)clock() / (ld)CLOCKS_PER_SEC << "ms\n";
#define endl '\n'
#define yy cout << "YES" << endl
#define nn cout << "NO" << endl
#define fix(f, n) std::fixed << std::setprecision(n) << f
const double pi = std::acos(-1);
using namespace std;
const ll mod = 1000000000 + 7;

ll power(ll x, ll y, ll md)
{
   ll res = 1;
   x = x % md;
   if (x == 0)
       return 0;
   while (y > 0)
   {
       if (y & 1)
           res = (res * x) % md;
       y = y >> 1;
       x = (x * x) % md;
   }
   return res;
}

ll m_mul(ll a, ll b)
{
   a = a % mod;
   b = b % mod;
   return (a * b + mod) % mod;
}
ll m_add(ll a, ll b)
{
   a = a % mod;
   b = b % mod;
   return (a + b + mod) % mod;
}

ll spf[(ll)1e7 + 2] = {0};
void siv()
{
   spf[1] = 1;
   loop(1, 1e7 + 2, i)
       spf[i] = i;

   loop(2, 1e7 + 2, i)
       spf[i] = 2,
       i++;
   for (ll i = 3; i * i < (ll)1e7 + 2; i++)
   {
       if (spf[i] == i)
           for (ll j = i * i; j < (ll)1e7 + 2; j = j + i)
               if (spf[j] == j)
                   spf[j] = i;
   }
}

ll chk(string sm)
{
   if (sm.size() % 2 != 0)
       return 0;
   string str = "";

   loop(0, sm.size(), i)
   {

       if (str.size() < (sm.size()) / 2)
           str = str + "3";
       else
           str = str + "0";
   }

   if (sm.compare(str) > 0)
       return 1;
   else
       return 0;
}
string rec1(string ss, ll &zero, ll &th, ll mx)
{
   if (ss.size() == 0)
       return "";

   string str = "";
   ll cnt = 0;
   loop(0, ss.size(), i)
   {
       if (cnt > 0 && zero != mx)
       {
           str = str + "0";
           zero++;
       }
       else if (ss[i] == '0' && zero != mx)
       {
           ll az = zero + 1;
           ll ab = th;
           string sn = rec1(ss.substr(i + 1, ss.size() - i - 1), az, ab, mx);

           sn = "0" + sn;
           string snew = ss.substr(i, ss.size() - i);
           if (sn.size() == snew.size())
           {
               if (sn.compare(snew) >= 0)
               {
                   zero = az, th = ab;
                   return (str.substr(0, i) + sn);
               }
               else if (th != mx)
               {
                   str = str + "3";
                   cnt = '3' - ss[i];
                   th++;
               }
           }
           else if (th != mx)
           {
               str = str + "3";
               cnt = '3' - ss[i];
               th++;
           }
       }
       else if (th != mx)
       {
           str = str + "3";
           cnt = '3' - ss[i];
           th++;
       }
   }
   return str;
}
string cnv(string ss)
{

   string str = "";
   if (ss.size() % 2)
   {
       loop(0, ss.size() + 1, i)
       {
           if (i == 0)
               str = str + "3";
           else if (str.size() <= (ss.size() + 1) / 2)
               str = str + "0";
           else
               str = str + "3";
       }
   }
   else
   {

       ll th = 0;
       ll cnt = 0;
       ll ctt = 0;

       loop(0, ss.size(), i)
       {
           if (i == 0)
           {

               str = str + "3";
               cnt = '3' - ss[0];
               th++;
               continue;
           }

           if ((cnt > 0) && ctt != ss.size() / 2)
           {
               str = str + "0";

               ctt++;
           }
           else if (ss[i] == '0' && ctt != ss.size() / 2)
           {
               ll az = ctt + 1;
               ll bz = th;
               string s11 = rec1(ss.substr(i + 1, ss.size() - i - 1), az, bz, ss.size() / 2);

               string spk = ss.substr(i, ss.size() - i);
               s11 = "0" + s11;
               if (s11.size() == spk.size())
               {
                   if (s11.compare(spk) >= 0)
                   {
                       ctt = az;
                       th = bz;
                       str = str + s11;
                       return str;
                   }
                   else if (th != ss.size() / 2)
                   {
                       str = str + "3";
                       cnt = 3;
                       th++;
                   }
               }

               else if (th != ss.size() / 2)
               {
                   str = str + "3";
                   cnt = 3;
                   th++;
               }
           }
           else if (th != ss.size() / 2)
           {
               str = str + "3";
               cnt = '3' - ss[i];
               th++;
           }
       }
   }
   return str;
}
void add(string &str, string ss, string sl, ll ind, ll cnt)
{
   loop1(sl.size() - 1, -1, i)
   {
       ll diff = sl.size() - ss.size();
       ll az = 0;
       if (i - diff >= 0)
           az = (ss[i - diff] - '0');

       az = az + (sl[i] - '0') + cnt;
       cnt = az / 5;
       ll bk = az % 5;
       str = to_string(bk) + str;
   }

   {
       if (cnt > 0)
           str = to_string(cnt) + str;
       return; // str;
   }
   return;
}
int main()
{
   bhaago;

   ll tc = 1;
   cin >> tc;
   while (tc--)
   {
       ll n;
       string sm, sc;
       cin >> sm >> sc;

       map<char, char> mp;
       mp['!'] = '0';
       mp['#'] = '1';
       mp['%'] = '2';
       mp['*'] = '3';
       mp['@'] = '4';
       mp['0'] = '!', mp['1'] = '#', mp['2'] = '%', mp['3'] = '*', mp['4'] = '@';
       string smn = "", scn = "";

       loop(0, sm.size(), i)
       {
           smn = smn + mp[sm[i]];
       }
       loop(0, sc.size(), i)
       {
           scn = scn + mp[sc[i]];
       }

       string sstr = "";

       ll k1 = 0, k2 = 0;

       loop(0, smn.size(), i)
       {
           if (smn[i] == '0')
               k1++;
           else if (smn[i] == '3')
               k2++;
       }

       string sans = "";
       if (k1 == k2 && k1 + k2 == smn.size())
       {
           add(sans, "1", smn, 0, 0);
           smn = sans;
       }

       if (chk(smn) == 0)
           sstr = cnv(smn);
       else
       {
           smn = smn + '!';
           sstr = cnv(smn);
       }

       smn = sstr;
       string str = "";
       if (smn.size() < scn.size())
           add(str, smn, scn, smn.size() - 1, 0); ////to complete
       else
           add(str, scn, smn, scn.size() - 1, 0);

       loop(0, str.size(), i)
       {
           cout << mp[str[i]];
       }
       cout << endl;
   }

   return 0;
}

Tester's Solution 3 (in Python)
# abhinav42

import sys
def get_array(): return list(map(int , sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()
import math
from collections import defaultdict
from itertools import combinations_with_replacement,permutations
import bisect
import time


arr = []
d = defaultdict(list)
mask = defaultdict(int)
mask_inv = defaultdict(str)


def solve(s,no_of_mark,no_of_star):
   if(len(s)>17):
       return
   if(no_of_mark == no_of_star):
       arr.append(s)
   solve(s+"*",no_of_mark,no_of_star+1)
   if(len(s)>0):
       solve(s+"!",no_of_mark+1,no_of_star)


def pre_process():

   mask['!'] = 0
   mask['#'] = 1
   mask['%'] = 2
   mask['*'] = 3
   mask['@'] = 4

   mask_inv['0'] = '!'
   mask_inv['1'] = '#'
   mask_inv['2'] = '%'
   mask_inv['3'] = '*'
   mask_inv['4'] = '@'

   solve("",0,0)
   arr.sort()
   for i in arr:
       d[len(i)].append(i)



def add(a,b,base): 
   len_a = len(a) 
   len_b = len(b) 
 
   s = ""; 
   sum = ""; 
  
   diff = abs(len_a - len_b); 
   for i in range(1,diff+1): 
       s += "0"
   if (len_a < len_b): 
       a = s + a 
   else: 
       b = s + b; 
  
   carry = 0; 
   for i in range(max(len_a, len_b) - 1,-1,-1): 
       curr = carry + (ord(a[i]) -ord('0')) +( ord(b[i]) - ord('0')); 
       carry = curr // base 
       curr = curr % base; 
       sum = chr(curr + ord('0')) + sum
         
   if (carry > 0): 
       sum = chr(carry + ord('0')) + sum; 
   return sum
  

if _name_ == "_main_":

   start = time.time() 
   pre_process()
   # print("--- %s seconds ---" % (time.time() - start))
   next_magical_year=""
   for _ in range(int(input())):
       y = input()
       a = input()
       
       if(len(y)%2==1):
           next_magical_year = d[len(y)+1][0]
       
       elif(bisect.bisect( d[len(y)] , y ) == len(d[len(y)]) ):
           next_magical_year = d[len(y)+2][0]
       
       else:
           index = bisect.bisect(d[len(y)] , y)
           next_magical_year = d[len(y)][index]

       year = ""
       age = ""

       for i in next_magical_year:
           year+=str(mask[i])
       for i in a:
           age+=str(mask[i])

       ans = add(age,year,5)

       final_ans = ""
       for i in ans:
           final_ans+=mask_inv[i]
       print(final_ans)

9 Likes