MSNG - Editorial

PROBLEM LINK:

Div 1
Div 2
Practice

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 and 9, its value is c-48, where 48 is the ASCII code for 0. In this way 0,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 and Z, its value is c-55. The reason is that the ASCII code for A is 65 and we want to map A to 10. In this way A,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 :slight_smile:

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
6 Likes

WHAT DID I DO WRONG

https://www.codechef.com/viewsolution/27319196

Stored all the possibilities in different lists and took intersection 4 them
if the reuslting had size more 0 then print min else -1

Please tell why this code fails
https://www.codechef.com/viewsolution/27360516

Or this one

https://www.codechef.com/viewsolution/27362095

Both being different approach

i’m getting WA and not able to get the error.Someone help
This is my code https://www.codechef.com/viewsolution/27376152

Your code does not handle the case when number is greater than 10^12

Please tell me why I’m getting wrong answer in second sub-task:
https://www.codechef.com/viewsolution/27367501

@jarvisnaharoy May we please have the test cases for this problem? Or, could it be possible for the problem to be posted on codeforces? It is really frustrating to not know what you did wrong. Tried it a lot of times. Seeing the test cases would help a lot. :slightly_smiling_face:

10 Likes

I second this.

if i evaluate string from left to right it as mentioned in the editorial pseudocode it gives accepted verdict.
But on evaluating string from right to left it gives WA. Can someone help?
https://www.codechef.com/viewsolution/27377282
https://www.codechef.com/viewsolution/27377426

2 Likes

Used the same Logic as Mentioned above.
Little more optimization can be done by knowing the fact that we can eliminate some values by finding the max value present in the string, for ex- if string is ‘1A5’ so its base must be in range(11,36) both inclusive. if string is ‘1CD7’ its base must be in range(14,36)
Link to the solution:-
https://www.codechef.com/viewsolution/27326104

Can anyone please tell me why did i got tle in this solutionhttps://www.codechef.com/viewsolution/27334420

Hello,
I’m expecting to hear from the author or tester. I am not understanding some of the points. I have got lots of trouble with this problem.
Before checking the number whether it’s greater than 1e12 we are performing some operations every time. Can you guarantee that those operation doesn’t occur any overflow ? If does it can also return negative number which is also less than 1e12.

My next concern is about some of the test cases. I know leading zero doesn’t matter. But I found some solution got accepted though they return different answer(0 or -1) for same test cases.
Can you please clearify these test cases ?
5
3
-1 0000000000000000000000000000000
36 0000000000000000000000000000000
10 0
3
-1 0000000000000000
36 0000000000000000
10 0
3
10 0
20 0
30 0
3
-1 00
-1 00
-1 00
2
-1 00000000000000000000000000000011
10 37

1 Like

Take this example:

n = 5
-1 0
-1 0
-1 4

You get an infinite loop in Intersection function

Can you guarantee that those operation doesn’t occur any overflow ?

If you execute the statement a\gets a\cdot b+d, and

  • a\le 10^{12}
  • b,d\le 35

then the value a after this statement is at most (10^{12}+1)\cdot 35\ll 10^{18}, so no need to worry about overflow.

Can you please clearify these test cases ?

But some solution may not handle leading zeroes correctly. This problem does not require you to handle leading zeroes, so it’s entirely okay if they fail on your test case.

Can anyone please tell me why do I get runtime error(SIGSEGV) for problem MSNG.This code works fine in my computer but getting this error in codechef compiler…

link to my solution: https://www.codechef.com/viewsolution/27379717

Used a similar approach as the setter, still got WA. Can anyone help me over in my code ?

https://www.codechef.com/viewsolution/27247929

10^12 is the limit for the decimal value of the number

Can someone please explain why this statement is required?

This is to make sure that the input number is a valid base-b number. (In a valid base-b number, only digits in 0\sim(b-1) are allowed, so if c\ge b we should return “Invalid number”.)

1 Like

Why this solution (in Python) is getting WA?
https://www.codechef.com/viewsolution/27386394