 # RSIGNS - EDITORIAL

Practice

Contest: Division 1

Contest: Division 2

Setter: Danylo Mocherniuk

Editorialist: Teja Vardhan Reddy

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.

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

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;

for _t in range(T):
answer = 5 * pw(2, K) % mod
``````
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

// 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. 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. 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).