RSIGNS - EDITORIAL

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Danylo Mocherniuk

Tester: Radoslav Dimitrov

Editorialist: Teja Vardhan Reddy

DIFFICULTY:

Simple

PREREQUISITES:

Math, fast exponentiation

PROBLEM:

Among all numbers from 0 through 10^K - 1 (lets say i is a number in that range),number of i values having exactly two distinct digits considering all the digits in i and 10^K-i-1.

EXPLANATION

Firstly lets notice that 10^K-1 is 99999.... k times.

Lets say p th digit of i is j. We can now see that p th digit of 10^K-1-i will be 9-j.

Lets say 1st digit (one’s place) of i is j. Now 1st digit of 10^K-i-1 (one’s place) will be 9-j. We can see that j and 9-j are never equal. So now, the two distinct digits must be j and 9-j.

So now from here, we can conclude that digits of i can be j or 9-j only. Now lets prove that all such numbers of this form have exactly 2 digits.

Proof: Wherever i has digit j,10^K-1-i has 9-j. and when i has digit 9-j then 10^K-1-i has j. Also since 1st digit (one’s place) of both numbers cannot be same as seen above. Hence,both j and 9-j occur in both the numbers combined and they are not same.

Now we want to count all such numbers,for each choice of first digit from 0 to 9, rest of the digits have 2 choices each, Hence, with j as 1st digit ,there are 2^{k-1} such number.

Therefore, total numbers that satisfy are (10* 2^{k-1}).

Now we can use fast exponentiation to find 2^{k-1} modulo 10^9+7.

TIME COMPLEXITY

O(log(k))

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int mod = 1000 * 1000 * 1000 + 7;
int main()
{
	int T;
	cin >> T;
	while(T--)
	{
		int K;
		cin >> K;
		LL ans = 5;
		LL dwa = 2;
		while(K)
		{
			if(K & 1)
			{
				ans *= dwa;
				ans %= mod;
			}
			dwa *= dwa;
			dwa %= mod;
			K >>= 1;
		}
		cout << ans << endl;
	}
}
Tester's Solution
import sys
 
def read_line():
    return sys.stdin.readline()[:-1]
 
def read_int():
    return int(sys.stdin.readline())
 
def read_int_line():
    return [int(v) for v in sys.stdin.readline().split()]
 
############
# Solution #
 
mod = 1000000007
 
def pw(x, p):
    ret = 1
    while p:
        if p & 1:
            ret = ret * x % mod
        x = x * x % mod
        p >>= 1
    return ret;
 
T = read_int()
for _t in range(T):
    K = read_int()
    answer = 5 * pw(2, K) % mod
    print(answer)
Editorialist's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val
 
using namespace std;
using namespace __gnu_pbds;
 
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout) 
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
// find_by_order()  // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
 
ll powe(ll a,ll b){
	ll ans=1;
	while(b){
		if(b%2){
			ans*=a;
			ans%=mod;
		}
		a*=a;
		a%=mod;
		b/=2;
	}
	return ans;
}
int main(){
    std::ios::sync_with_stdio(false); cin.tie(NULL);
    int t;
    cin>>t;
    while(t--){
    	int k;
    	cin>>k;
    	ll ans=powe(2,k);
    	ans*=5;
    	ans%=mod;
    	cout<<ans<<endl;
    }
    return 0;   
}

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile:

6 Likes

I wrote a python script which iterated to small k. I observed the pattern And BOOM. Green tick.

1 Like

Could you share the Py script?

with j as 1st digit ,there are 2^k-1 such number.and total number satisfy are 10*2^(k-1)??
can you please assist me with this ,i am newbie. @teja349 .can you help me with topic also?similar type of question and discussion.

why there is multiplication with 10

because there are ten options for j i.e 0,1,2,…9.

1 Like

I also did the same.:sweat_smile:

Correct me if I am wrong, for k=2 there will be 100 signs indexing from 0 to 99. We have to find out i and 10^k - i - 1 such that i and 10^k - i - 1 have two distinct digits. So the digits are
0,1,2,3,4,5,6,7,8,9
All 10 digits from 0 to 9.Therefore count= 10.
i 10^k - i - 1
11 88
18 81
22 77
27 72
33 66
44 55
45 54
so the count is 26 but according to editorial the ans of count is 20
How is it possible?

The 20 Possible signs are -
00 99
09 90
11 88
18 81
22 77
27 72
33 66
36 63
44 55
45 54
54 45
55 44
63 36
66 33
72 27
77 22
81 18
88 11
90 09
99 00

1 Like

Because there are 10 such j’s (0 to 9).