ONOZ - Editorial

PROBLEM LINK:

Contest
Practice

Authors: Jaub Safin
Testers: Vasya Antoniuk
Translators: Vasya Antoniuk (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Praveen Dhinwa

DIFFICULTY:

Cakewalk

PREREQUISITES:

String processing

PROBLEM:

You have a clock which ticks H hours. It ticks M minutes in an hour. Let h:m denote the time shown by the clock at some instant, where h is an integer without leading zeros denoting the current hour and M denoting the current minute. Note that both h and m don’t have leading zeros.

We define a duration h:m good if both h and m contain a single digit in their decimal representation. e.g. 2:22 is good where 2:3 is bad.
Note that the duration 02:22 is also good as it will be represented as 2:22 when we write h without leading zeros.

Find out number of good durations h:m such that 0 \leq h < H, 0 \leq m < M.

QUICK EXPLANATION:

As values of H and M (\leq 100) are very small. We can simply use a brutefore approach.

Let us iterate over hour h from 0 to H - 1 and m from 0 to M-1, we represent h and m as strings and check whether both the strings are made of a unique character or not.

EXPLANATION:

As stated in previous section, we can iterate over h from 0 to H - 1 and m from 0 to M-1, we represent h and m as strings and check whether both the strings are made of some unique character or not.

Pseudo Code

int ans = 0;
for (int h = 0; h < H; h++) {
    for (int m = 0; m < M; m++) {
        if (isGood(toString(h) + toString(m))) {
            ans++;
        }
    }
}

Now, let us learn few tricks of how to convert an integer into a string.

General method (not specific to any language)

We extract the digits of the number one by one and append to our answer string. See the code below.

string ans = ""
while (n > 0) {
	ans += (char) (n % 10 + '0');
	n /= 10;
}
reverse(ans.begin(), ans.end())

C specific method

We can use itoa() function for converting an integer to a string.

char * s = itoa(n)

C++ specific methods

In C++ 11, you can use to_string method.

string s = to_sring(n)

You can also make use of string streams.

ostringstream os;
os << n;
string s = os.str()

Java specific methods

String ans = String.valueOf(n);

Checking whether all the digits of a string are equal or not
We can iterate over each character of the string and check whether it is equal to previous or not. If all the digits of the string are not equal, then there would be a character whose previous charater is not equal to that.

for (int i = 1; i < s.size(); i++) {
	if (s[i] != s[i - 1]) {
		return false;	
	}
}
return true;

Alternatively, you can insert the characters into a set and check whether size of set is one or not.

set<char> st;
for (int i = 0; i < s.size(); i++) {
	st.insert(s[i]);
}
return st.size() == 1;

Time Complexity:

We spend \mathcal{O}(H \cdot M) for iterating over h and m, then converting h and m to strings and the later processing requires operations equal to number of digits in both h and m. As we note that h and m can not be larger than 100. So, it can be at max 3 + 3 = 6, which is \mathcal{O}(1).

So total time will be \mathcal{O}(H \cdot M) which is around 10^4 operations for each test case. There are around 50 test cases. So, we will make around 5 * 10^5 operations overall which will easily run under 1 secs as normally we have around 3 * 10^8 operations in a second.

AUTHOR’S AND TESTER’S SOLUTIONS:

setter
tester

1 Like

My easy to understand solution

int h , m , j;
	cin>>h>>m;
	int ans = 0;
	floop(i , 0 , h)
	{
		floop(j , 0 , m)
		{
			if(i<10 && j<10 && i == j)ans++;
			else if(i == (j*10+j) || j == (i*10)+i)ans++;
			else if(i>=10 && j>=10 && i==j){
				string si = to_string(i);
				string sj = to_string(j);
				if(si[0] == sj[1] && si[1] == sj[0])
			    ans++;
			
		}
	}
	
}
cout<<ans<<endl;
}

Alternate solution with O(1) complexity :

int H_11,H_09,M_11,M_09 ;

H_09=min(10,H); //no. of single digit hours 

M_09=min(10,M); //no. of single digit minutes

H_11=(H-1)/11; //no. of hours which are between 0..H-1 & multiple of 11

M_11=(M-1)/11; //no. of minutes which are between 0..M-1 & multiple of 11

ans= min(H_09,M_09) + min(H_09-1,M_11) + min(H_11,M_09-1) + min(H_11,M_11); //find all combinations

Link: CodeChef: Practical coding for everyone

6 Likes

My solution:

#include <bits/stdc++.h>
using namespace std;

int f(int x, int d) {
	int a = 0, b = 1;
	while (b*d<x) {
		a++;
		b*=10;
		b++;
	}
	return a;
}

int main() {
	int T, H, M, i, x;
	cin>>T;
	while (T--) {
		cin>>H>>M;
		x = 1;
		for (i=1; i<=9; i++) {
			x += f(H, i)*f(M, i);
		}
		cout<<x<<"\n";
	}
	return 0;
}

My approach:

InputReader inputReader = new InputReader(System.in);
	int cases = inputReader.readInt();
	
	while(cases>0){
		int hours = inputReader.readInt();
		int mins = inputReader.readInt();
		// Counting 0:0
		int res = 1;
		
		for(int i=1;i<10;i++) {
			int curr = i;
			int hoursFactors = 0;
			int minsFactors = 0;
			for(int j=0;j<2;j++) {
				if(hours-1>=curr)
					hoursFactors++;
				if(mins-1>=curr)
					minsFactors++;
				curr = curr*10+i;
			}
			res += hoursFactors*minsFactors;
		}
		System.out.println(res);
		cases--;
	}

My approach :

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	long long int t,i,j,h,m,res,temp,temp2;
	cin>>t;
	while(t--)
	{
	    res=0;
	    cin>>h>>m;
	    for(i=0;i<h;i++)
	    {
	        // for all the digits to be same it should be divisible by 11 or
	        // it should be a single digit
	        if(i%11!=0 && i>9)
	        continue;
	        // digit which is same in 'i' is stored in temp2
	        temp2=i%10;
	        for(j=0;j<m;j++)
	        {
	            if(j%11!=0 && j>9)
	            continue;
	            
	            temp=j%10;
	            
	            // now checking if the digit of 'j' matches with 'i' 
	            if(temp==temp2)
	            res++;
	        }
	    }
	    cout<<res<<endl;
	}
	return 0;
}

Problem code origin:

A recurring type of problems in ACM contests are problems which require hardwiring a lot of stuff. One of the most common things is the ASCII art representation of a digital clock display. (There was one in the last CERC regionals, for example.) AFAIK, skilled algorithmic programmers hate that type of problems because it’s just a lot of rewriting and no algorithms.

http://cs.urbandictionary.com/define.php?term=onoz

1 Like

It was a simple problem, decided to choose Python for it.

Brute Force :
ACed solution

Using SET :

#include<bits/stdc++.h>

using namespace std;

int main(){

cin.sync_with_stdio(false);

int t;

cin >> t;

while( t-- )
{

 int h , m;
 cin >> h >> m;
int ans = 0;
for(int i = 0 ; i < h ; ++i ){
  for(int j = 0 ; j < m ; ++j ){
   set< int > s;
    int n = i;
    if(!n)
    s.insert(i);
    while(n){
    s.insert(n%10);
    n/=10;
    }
    n = j;
    if(!n)
    s.insert(j);
    while(n){
    s.insert(n%10);
    n/=10;
    }
    if(s.size()==1){
    ans++;
 }
  }
}
cout << ans << endl;

}
}

i have submitted following solution to this problem , but judge response is wrong , i have checked all possible test cases and my program is working correctly
https://www.codechef.com/viewsolution/9710018
can anyone tell me why it is giving wrong answer

Good work, really thought about it, but then constraints were Ok for brute force.

Hey @sharad07 …can you pleas explain the last time.
Why did you took the min(H_09-1, M_11) and not min(H_09, M_11); where does -1 come from. I would be grateful if you can explain me about how you arrived to this solution… Thanks for spending your time here

@nickzuck_007 … -1 is just to exclude the digit ‘0’ from our consideration…as ‘0’ is not going to pair up with anyone.

Hence we only consider combination pairs between (1,2…H09-1) & (11,22…M_11) instead of (0,1,2…H09-1) & (11,22…M_11)

Check my Solution still learning though.

I used something like a bfs approach, although that turned out to be an overkill. :stuck_out_tongue:
https://www.codechef.com/viewsolution/31901190

Why my solution is giving WA ?
https://www.codechef.com/viewsolution/36145862

#include
#define ll long long
using namespace std;

int main() {
int t;
cin>>t;
while(t–)
{
ll int h,m;
cin>>h>>m;
ll int count=0;
for(ll int i=0;i<min(h,10LL);i++)
{
if(i<m)
{
count++;
}
if(i!=0)
{
if((i*10)+i <m)
{
count++;
}
}
}

    for(ll int i=11;i<h;i=i+10)
    {
        if(i<m)
        {
            count=count+1;
        }
        if((i%10)<m)
        {
            count++;
        }
        
    }
    
    cout<<count<<endl;
    
}
return 0;

}

what is error?