PROBLEM LINK:
Author: Saranya Naha Roy
Tester: Hanlin Ren
Editorialist: Hanlin Ren
DIFFICULTY:
SIMPLE
PREREQUISITES:
Base conversion
PROBLEM:
We have some descriptions of a number. Each description is a pair (B,Y) where Y is a string of digits, and B means the number is Y written in base B. Unfortunately, some of the B's may be lost (then it’s equal to -1). Output the smallest possible number consistent with all descriptions, or determine there is no solution.
QUICK EXPLANATION:
For every pair (B,Y), we make a list of at most 35 numbers that is valid for it. We then find the smallest common number of these lists.
EXPLANATION:
Base Conversion
To solve this problem, we need to be able to convert numbers in any base to base 10. (If you know how to do it, you can skip this section.)
Suppose we have a string s and we know it’s a base-b representation of some number. Let’s scan the string from the first digit to the last digit. We maintain a number a denoting the base-10 value of the digits we currently scanned. Initially a is zero. Whenever we add a digit d to the end, we let a\gets a\cdot b+d. Then after scanning all digits, the value a is the base-10 value of the corresponding number.
For example, when we convert the base-5 number s=2143 to base 10:
- Initially we scanned nothing and a=0.
- Now we add the first character 2. We let a\gets 0\cdot 5+2=2.
- Now we add the second character 1. We let a\gets 2\cdot 5+1=11. Note that the base-10 number (11)_{10} is exactly the base-5 number (21)_{5}, i.e. the base-5 number formed by the first two digits of s.
- Now we add the third character 4. We let a\gets 11\cdot 5+4=59. Note that (59)_{10}=(214)_5.
- Finally we add the last character 3. We let a\gets 59\cdot 5+3=298. We’re done: (298)_{10}=(2143)_5.
Note that when b>10, some digits are between A
and Z
. When we need to map the character to a digit in [0,35], we have to divide it into two cases:
- If the character c is between
0
and9
, its value is c-48, where 48 is the ASCII code for0
. In this way0
,1
,…,9
are indeed mapped to 48-48, 49-48, \dots, 57-48, i.e. 0,1,\dots,9 respectively. - If the character c is between
A
andZ
, its value is c-55. The reason is that the ASCII code forA
is 65 and we want to mapA
to 10. In this wayA
,B
,…,Z
are indeed mapped to 65-55, 66-55, \dots, 90-55, i.e. 10, 11, \dots,35 respectively.
An implementation detail: in this problem if the actual value is greater than 10^{12}, we want to output something like “conversion failed”. However, due to integer overflow, we can’t simply check whether a>10^{12} at the end of conversion. (If you’re using unsigned 64-bit integers in languages such as C++, the value a you obtained is actually the real number modulo 2^{64}.) Therefore, we must check whether a>10^{12} after every intermediate steps, i.e. after performing every “a\gets a\cdot b+d”.
Pseudocode for base conversion
//input: a string s and a base b
a = 0
for i = 0 to length(s)
c = s[i] //the i-th character
if c >= '0' and c <= 'z' then digit = c - 48
else digit = c - 57
//"digit" is the digit in [0,35] converted from c
a = a * b + digit
if a > 1,000,000,000,000 then output "conversion failed"
return a
C++ code for base conversion
long long convert(char *s, int b) {
//returns converted value, or -1 if conversion failed
long long ans = 0;
int i;
for (i = 0; s[i]; i++) {
int c = s[i] - '0';
if (s[i] >= 'A' && s[i] <= 'Z') c = s[i] - 'A' + 10;
if (c >= b) return -1;
ans = ans * b + c;
if (ans > 1000000000000ll) return -1;
}
return ans;
}
Python code for base conversion
Hahaha, python has a builtin for this!
int(s, b) # returns the base-10 value of base-b integer s; e.g. int("2143",5)=298
Subtask 1
There is a pair with B\ne -1, therefore we can infer the hidden number. In other words, we simply find the pair (B,Y) where B\ne -1, and convert Y to base B.
However we still need to check that Y is consistent with every pair. For another pair (B',Y'), if B'\ne -1, we can also convert Y' to base B' and check whether it’s equal to Y. If B'=-1, we simply enumerate B' from 2 to 36, and check whether there is some B' such that Y' in base B' is equal to Y.
Subtask 2
For every pair (B,Y), we can make a list of at most 35 numbers that’s valid with respect to this pair.
- If B\ne -1, the list contains at most one number, which is Y converted from base B to base 10. If Y is not valid (e.g. greater than 10^{12}), then the list is empty (and thus the input has no solution).
- If B=-1, we can enumerate the real base b from 2 to 36. For each b, we check whether Y is a valid number in base b, and check whether the converted number is at most 10^{12}. If all checks pass, we add the number Y (converted from base b to base 10) to the list.
Pseudocode:
for i = 1 to N
list[i] = [] //empty list
for i = 1 to N
if B[i] = -1 then
for b = 2 to 35
Y0 = convert(Y, b) //Convert Y from base b to base 10
if Y0 is valid then
list[i].push(Y0)
else
Y0 = convert(Y, B[i])
if Y0 is valid then
list[i].push(Y0)
Then we simply find the smallest common element of these lists. We enumerate such element in the first list (there are at most 35 of them), and check whether it appears in every list. If it does, we can update our answer.
Pseudocode:
ans = 1000000000001 //10^{12}+1, any large enough number suffices
for x in list[1] : //iterate through all numbers in the first list
in_all_lists = True
for i = 1 to N :
if x not in list[i] then in_all_lists = False
if in_all_lists then
ans = min(ans, x)
//every element in list[1] is scanned
if ans <= 1000000000000 then //10^12
print ans
else print -1
ALTERNATE EXPLANATION:
Please feel free to share your approaches
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
#define dbg(i,j) cout<<"I am "<<i<<" = "<<endl<<j<<endl;
#define dbr(name,a) cout<<name<<endl;for(auto x:a)cout<<x<<" ";cout<<endl;
#define DBR(name,a) cout<<name<<endl;for(auto x:a){ for(auto y:x)cout<<y<<" ";cout<<endl;}
#define dbmp(name,a) cout<<name<<endl;for(auto x:a){ cout<<x.first<<"\t"<<x.second<<endl;}
#define dbp(name,a) cout<<name<<endl;cout<<a.first<<"\t"<<a.second<<endl;
#define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int big;
typedef long double fig;
big val(char c)
{
if (c >= '0' && c <= '9')
return (big)c - '0';
else
return (big)c - 'A' + 10;
}
big toDeci(string str, big base)
{
big num = 0; // Initialize result
big i;
for (i =0; i<str.size(); i++)
{
num = num*base + val(str[i]) ;
if(num>1000000000000)return -1;
}
return num;
}
int find_base(string s){
char ch='0';
int i;
for(i=0;i<s.size();i++){
if(s[i]>ch)ch=s[i];
}
if(ch<='9')return ch-'0'+1;
else{
return ch-'A'+11;
}
}
void print(map<big,vector<big>> mp){
for(auto it=mp.begin();it!=mp.end();it++){
cout<<it->first<<"--> ";
for(int i=0;i<it->second.size();i++){
cout<<it->second[i]<<" ";
}
cout<<endl;
}
}
bool is_present(vector<big> vt,big x){
for(int i=0;i<vt.size();i++){
if(vt[i]==x)return 1;
}
return 0;
}
void search(map<big,vector<big>> mp,big n){
if(mp.size()!=n){
cout<<-1<<"\n";
return;
}
auto it=mp.begin();
for(int i=0;i<it->second.size();i++){
big temp=it->second[i];
auto jt=it;
bool ok=1;
for(jt++;jt!=mp.end();jt++){
ok&=is_present(jt->second,temp);
}
//cout<<"ok----- "<<ok<<" "<<i<<"\n";
if(ok){
cout<<temp<<"\n";
return;
}
}
cout<<-1<<"\n";
}
int main(){
//freopen("test.txt","r",stdin);
big tt;
cin>>tt;
while(tt--){
big n,i,base,temp;
cin>>n;
string s;
map <big,vector<big> > mp;
for(i=0;i<n;i++){
cin>>base>>s;
//mp[i].push_back(0);
if(base==-1){
base=find_base(s); //find_base() finds the least base which is valid
//cout<<"base "<<base<<endl;
for(int j=base;j<=36;j++){
temp=toDeci(s,j); //toDeci() converts a string to it's decimal value
if(temp!=-1)mp[i].push_back(temp); //inserting all valid no's to the vector
}
}
else{
mp[i].push_back(toDeci(s,base));
}
}
//print(mp); //Prints the map
search(mp,n);
}
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, a;
char s[23333];
ll convert(int b) {
ll ans = 0;
int i;
for (i = 0; s[i]; i++) {
int c = s[i] - '0';
if (s[i] >= 'A' && s[i] <= 'Z') c = s[i] - 'A' + 10;
if (c >= b) return -1;
ans = ans * b + c;
if (ans > 1000000000000ll) return -1;
}
return ans;
}
int len;
set <ll> S[123];
void doit() {
cin >> n;
set <ll> empty;
for (int i = 1; i <= n; i++) S[i] = empty;
for (int i = 1; i <= n; i++) {
cin >> a >> s;
for (int b = 2; b <= 36; b++)
if (a == -1 || a == b) {
ll c = convert(b);
if (c != -1) S[i].insert(c);
}
}
for (set <ll> :: iterator it = S[1].begin(); it != S[1].end(); it++) {
int j; for (j = 2; j <= n; j++) if (S[j].find(*it) == S[j].end()) break;
if (j > n) {cout << (*it) << endl; return;}
}
cout << -1 << endl;
}
int main() {int t; cin >> t; while (t--) doit(); return 0;}
Tester's Solution in Python
for _ in range(input()) :
lst = []
for i in range(input()) :
a, b = raw_input().split()
z = max(list(b))
if z >= 'A': z = ord(z) - ord('A') + 11
else : z = ord(z) - ord('0') + 1
z = max(2, z)
a = int(a)
if a == -1: lst += [[int(b, c) for c in range(z, 37)]]
else: lst += [[int(b, a)]]
ans = -1
for j in sorted(lst[0]) :
if j >= 0 and j <= 10**12 :
if all([j in l for l in lst]) :
ans = j; break
print ans