NUM239 - Editorial

cakewalk
editorial
isaf27
likecs
ltime61
prefix-sum
#1

Problem Link

Practice

Contest

Author: Ivan Safonov

Tester: Hasan Jaddouh

Editorialist: Bhuvnesh Jain

Difficulty

CAKEWALK

Prerequisites

Prefix sums

Problem

You are given to integers L and R. Find the number of integers which have the last digit as 2, 3 or 9 and lie in the range [L, R].

Explanation

As the constrainsts are small on L and R, we can pre-calculate all good numbers. Then each test case just asks to find out how many good numbers lie within the given range. This can be easily answered using prefix-sums. If you don’t know about prefix-sums, you can read it here. Basically the idea is the following:

\sum_{i=l}^{i=r} A_i = \sum_{i=1}^{i=r} A_i - \sum_{i=1}^{i=l-1} A_i
\sum_{i=l}^{i=r} A_i = ext{(Prefix-sum at i=r)} - ext{(Prefix-sum at i=l-1)}

Below is a pseudo-code for it:


	def init():
		for i in [1, 1000000]:
			last_digit = i % 10
			if last_digit == 2 or last_digit == 3 or last_digit == 9:
				good* = 1
			else:
				good* = 0

		# Build prefix sum
		for i in [1, 1000000]:
			good* += good[i-1]

	def solve(l, r):
		ans = good[r] - good[l-1]
		return ans

The time complexity of the above approach will be O(N + T), where N = 100000 is for pre-computation and T is for answering every test case in O(1) using prefix-sums. The space complexity of the above approach will be O(N) for storing the prefix array of good elements.

Bonus Problem

Solve the problem without any pre-computation and in O(1) memory.

Idea:

Click to view

Note that every consecutive number from “x…0” to “x…9” has 3 good numbers.

Feel free to share your approach, if it was somewhat different.

Time Complexity

O(N + T)

Space Complexity

O(N)

Solution Links

Setter’s solution

Tester’s solution

Editorialist solution

#2

Since constraints were easy there was no need to define an array to hold good/pretty numbers.

a simple brute force from l to r and checking the last digit would yield the same result.

See my submission: https://www.codechef.com/viewsolution/19019309

Time Complexity: O(N)

Space Complexity: O(1)

#3

My Solution:

Time Complexity : O(T)

Space Complexity : O(1)

It will be useful if no. of test case is quite large.

/* Written By : Anish Ray */

#include <bits/stdc++.h>

#define ll long long
#define v(k) vector
#define mod 1000000007
#define m(a,b) map <a,b>
#define ull unsigned long long
#define fi first
#define se second

using namespace std;

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

int t;
cin>>t;

while(t--)
{
	int l,r;
	cin>>l>>r;
	
	int c=0;
	int f=0;
	
	for(int i=0;i<10;i++)
	{
		if(l==r)
		{
			if(l%10==3||l%10==9||l%10==2)
				c+=1;
				
			f=1;
			break;
		}
	
		if(l%10==2)
		{
			break;
		}
		else if(l%10==3||l%10==9)
			c++;
		
		l++;
	}
	
	if(f!=1)
	{
		for(int i=0;i<10;i++)
		{
			if(r==l)
			{
				if(l%10==3||l%10==9||l%10==2)
					c+=1;
				
				f=1;
				break;
			}
	
			if(r%10==1)
			{
				break;
			}
			else if(r%10==9||r%10==3||r%10==2)
				c++;
		
			r--;
		}
	}
	
	if(f!=1)
	{
		c+=((r-l+1)/10)*3;
	}
	
	cout<<c<<endl;
}

return 0;

}

#4

Its a simple Brute Force application. Amazed to see such a simple problem in LTIME61B.
My code goes here…(in cpp).## Heading ##


#include 
using namespace std;

int main()
{
     int t,cnt,digit,l,r;
     cin>>t;
     while(t--)
    {
        cnt = 0;
        cin>>l>>r;
        for(int i=l;i<=r;i++)
        {
            digit = i % 10;
            if(digit == 2 || digit == 3 || digit == 9)
                cnt++;
        }
        cout<<cnt<<endl;
    }
    return 0;
}
#5

Wtf… I wasted a lot of time on this question due to some connection issue and due to some problem with codechef IDE…
Didn’t knew that 1st question is that low in div2 (as I was in div2 before contest and I was in div1 before previous contest)…
This is completely brute Force…

#6

I did O(1) space approach

#7

@l_returns Pro tip #1 (#nooffence) Never use codechef ide in short contest for testing soln. It will ~1 min to give verdict. And sometimes it also shows “Submission Limit Reached” . Alternative offline ide(Best Option), CodeForces Ide (A bit slower but can be used) both are relatively faster. I personally use these options for testing purpose.