MATCHES - Editorial

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Hasan

Tester: Roman Bilyi

Editorialist: Taranpreet Singh

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Given two values A and B, Find the number of matches required to write S = A+B as explained in the problem statement.

EXPLANATION

Since matches used for each digit is independent, we just need to write each digit of A+B separately and count the number of matches required for each digit. From the image
image

We can see that 6 matches are needed to write 0 on display, 2 matches are needed to write 1 on display and so on. We can count this for all digits and store it in an array, say count. count[x] denotes the number of matches required to write digit x on display.

Now, to obtain digits of S = A+B, we can see that taking remainder by 10 gives the last digit of S and dividing S by 10 removes the last digit. These two observations give us a way to get all digits of S.

while S > 0:
       D = S%10 //D is the least significant digit of S
       ANS = ANS + count[D]
       S = S/10 //Least significant digit is discarded

Bonus problem
Count the number of Matches needed to write A+B in base x using matches where 2 \leq x \leq 10

TIME COMPLEXITY

For each test case, time taken is the number of digits of A+B in base 10, which is log_{10}(A+B), so time complexity per test case is O(log_{10}(A+B))

SOLUTIONS:

Setter's Solution
#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
using namespace std;
 
 
 
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
		
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			assert(cnt>0);
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}

int T;
int A,B;

int num[10]={6,2,5,5,4,5,6,3,7,6};


int main(){
	//freopen("00.txt","r",stdin);
	//freopen("00o.txt","w",stdout);
	T=readIntLn(1,1000);
	while(T--){
		A=readIntSp(1,1000000);
		B=readIntLn(1,1000000);
		int s= A+B;
		int ans = 0;
		while(s>0){
			ans += num[s % 10];
			s /= 10;
		}
		cout<<ans<<endl;
	}
	assert(getchar()==-1);
}
Tester's Solution
#include "bits/stdc++.h"
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
using namespace std;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair

typedef long long Int;
typedef vector<int> VI;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000;
const Int LINF = INF * (Int) INF;
const int MAX = 100007;

const int MOD = 1000000007;

const double Pi = acos(-1.0);

int d[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

int f(int x)
{
	int res = 0;
	while(x)
	{
	    res += d[x % 10];
	    x /= 10;
	}
	return res;
}

int main(int argc, char* argv[])
{
	// freopen("in.txt", "r", stdin);
	//ios::sync_with_stdio(false); cin.tie(0);

	int t;
	cin >> t;
	assert(t <= 1000);
	FOR(tt,0,t) {
	    int a, b;
	    cin >> a >> b;
	    assert(a >= 1 && a <= 1000000);
	    assert(b >= 1 && b <= 1000000);
	    cout << f(a + b) << endl;
	}   

	cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;

	
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class MATCHES{
	//SOLUTION BEGIN
	int[] mp = new int[]{6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    int s = ni()+ni(), ans = 0;
	    while(s>0){
	        ans+=mp[s%10];
	        s/=10;
	    }
	    pn(ans);
	}
	//SOLUTION END
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	DecimalFormat df = new DecimalFormat("0.00000000000");
	static boolean multipleTC = true;
	FastReader in;PrintWriter out;
	void run() throws Exception{
	    in = new FastReader();
	    out = new PrintWriter(System.out);
	    //Solution Credits: Taranpreet Singh
	    int T = (multipleTC)?ni():1;
	    pre();for(int t = 1; t<= T; t++)solve(t);
	    out.flush();
	    out.close();
	}
	public static void main(String[] args) throws Exception{
	    new MATCHES().run();
	}
	int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
	void p(Object o){out.print(o);}
	void pn(Object o){out.println(o);}
	void pni(Object o){out.println(o);out.flush();}
	String n()throws Exception{return in.next();}
	String nln()throws Exception{return in.nextLine();}
	int ni()throws Exception{return Integer.parseInt(in.next());}
	long nl()throws Exception{return Long.parseLong(in.next());}
	double nd()throws Exception{return Double.parseDouble(in.next());}

	class FastReader{
	    BufferedReader br;
	    StringTokenizer st;
	    public FastReader(){
	        br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    public FastReader(String s) throws Exception{
	        br = new BufferedReader(new FileReader(s));
	    }

	    String next() throws Exception{
	        while (st == null || !st.hasMoreElements()){
	            try{
	                st = new StringTokenizer(br.readLine());
	            }catch (IOException  e){
	                throw new Exception(e.toString());
	            }
	        }
	        return st.nextToken();
	    }

	    String nextLine() throws Exception{
	        String str = "";
	        try{   
	            str = br.readLine();
	        }catch (IOException e){
	            throw new Exception(e.toString());
	        }  
	        return str;
	    }
	}
}

Feel free to share your approach, if you want to. (even if its same :stuck_out_tongue: ) . Suggestions are welcomed as always had been. :slight_smile:

Can someone explain, why log10 came in the time complexity? i thought complexity is just O(A+B)

Please tell me what is the time complexity for my code below.
https://www.codechef.com/viewsolution/26725257

one liner: CodeChef: Practical coding for everyone

3 Likes

it’s same log10(A+B).

Hint: ceil( log10(A+B) ) corresponds to number of digits in decimal number system-1

@ eiseinstein

Can you explain how complexity is O(log (A+B))?

Because A+B has log(A+B) digits

https://www.codechef.com/viewsolution/26734947
Can anybody help me out I have stored each digit into map.Sample test cases have been passed .

@dlswing Everything is fine, but you have to change your map initialization for 9. For 9, you need to use 6 matches (not 3 matches).

Here is the defect =>
:x: {9, 3}
:white_check_mark: {9, 6}

Its should be:

map<ll,ll> mymap = {
    {0,6},{1,2},{2,5},{3,5},{4,4},{5,5},{6,6},{7,3},{8,7},{9,6}  };
2 Likes

idk what to discuss more . i just did this hope beginners can understand.

int aa[] = { 6,2,5,5,4,5,6,3,7,6 };
  int t;
  cin >> t;
  while(t--){
      int a , b;
      cin >> a >> b;
      a+=b;
      string s = to_string(a);
      int ans =0;
      for(char c : s){
          ans+= aa[c-'0'];
      }
      cout << ans << "\n";
  }
1 Like

simple cpp solution: CodeChef: Practical coding for everyone

@romawhite I don’t know much about coding but after studying your code as my practice ,being tester your code should have less error
I think you should not use endl with cerr :sweat_smile:
If I am wrong then tell me too :grimacing:

//A little different approach
#include <bits/stdc++.h>
using namespace std;

int main() {
int t;
cin>>t;
while(t–){
int a,b,match=0;
cin>>a>>b;
a+=b;
while(a!=0){
switch(a%10){
case 1:
match+=2;
break;
case 7:
match+=3;
break;
case 4:
match+=4;
break;
case 2:
case 5:
case 3:
match+=5;
break;
case 0:
case 6:
case 9:
match+=6;
break;
case 8:
match+=7;
break;
}
a/=10;
}
cout<<match<<"\n";
}
return 0;
}

Cool Problem to solve as a beginner. Here the new thing i learned is to find elements present in the number any BIG. Thanks for discussions it always helps me.

This is brute force solution for beginners in java by using String and char.

import java.util.Scanner;
public class PlayingWithMatch {

public static void main(String arg[]) {
	try {
	Scanner sc = new Scanner(System.in);
	
	int t = sc.nextInt();
	while(t-- != 0) {
		
		long a = sc.nextLong();
		long b = sc.nextLong();
		int count = 0;
		long c = a + b;
		String s = ""+c;
		
		
		for(int i = 0;i<s.length();i++) {
			char rem = s.charAt(i);
			
			if(rem == '0') {
				{ count = count + 6;}
			}
			else if(rem == '1') { count = count + 2;}
			else if(rem == '2') { count = count + 5;}
			else if(rem == '3') { count = count + 5;}
			else if(rem == '4') { count = count + 4;}
			else if(rem == '5') { count = count + 5;}
			else if(rem == '6') { count = count + 6;}
			else if(rem == '7') { count = count + 3;}
			else if(rem == '8') { count = count + 7;}
			else if(rem == '9') { count = count + 6;}
			
			
		}
		System.out.println(count);
		
	}
	}catch(Exception e) {}
}

}

@cheetha I don’t know why am I getting the wrong answer.Pls help.
solution link: CodeChef: Practical coding for everyone

My simple c++ code, very short and even I could understand it :stuck_out_tongue: CodeChef: Practical coding for everyone

l = [6,2,5,5,4,5,6,3,7,6]

for _ in range(int(input())):

a,b=map(int,input().split())

sum = str(a+b)

ans = 0

for i in sum:

    ans += l[int(i)]

print(ans)

t = int(input())
l = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

for z in range(t):
a, b = map(int, input().split())
n = inta + b
print(n)
st = 0
while n != 0:
d=n%10
st += l[int(d)]
print(st)
n = n//10
print(st)

please explain where i did wrong.Its showing runtime error.

t = int(input())
l = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

for z in range(t):
a, b = map(int, input().split())
n = inta + b
print(n)
st = 0
while n != 0:
d=n%10
st += l[int(d)]
print(st)
n = n//10
print(st)

please explain where i did wrong.Its showing runtime error!!!.

By Using Maps We can Easily Solve the problem:-
Use The .at( ) function to access the mapped element.
For More details about .at( ) function in maps Google it.

#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
int sum=0,sum1;
map<int,int>digitsMap={{0,6},{1,2},{2,5},{3,5},{4,4},{5,5},{6,6},{7,3},{8,7},{9,6}};
int n,n1;
cin>>n>>n1;
int num=n+n1;
while(num!=0)
{
int search=num%10;
sum1=digitsMap.at(search);
sum=sum+sum1;
num=num/10;
}
cout<<sum<<endl;
}
return 0;
}