Problem: Vultures Heist
Author: aarya110
Tester: ankit_907
EXPLANATION:
If q^{th} permutation doesn’t exist for n, that is, if q>n! then print -1.
Notice, that since q≤ 10^{18}, then at most 19 elements from right (suffix) will change. So, element from left of this part (prefix) will not change (then we can just find the count of spidey numbers on that range). To find result for the rest of the permutation (suffix) we need to find q^{th} permutation of the suffix part (from some number to n). After we find that permutation, we can just loop through that permutation and count result.
Now, the problem breaks down to two subproblems:
-
(count1) To find the count of Spidey numbers from 1 to n :- If n has d digits, the count till number with d-1 digits can easily be obtained since at each digit, there’s two choices, either 3 or 6. For numbers with d digits till n, count can be calculated by using some conditions.
-
(count2) To find the q^{th} permutation for the suffix part, and the count of spidey indices which don’t have a spidey number
Final answer would be count1 - count2.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll INF = 1e18;
vector<ll> getPermutation(vector<ll>s, ll n, ll k) {
k--;
ll i;
vector<ll>ans(n);
ll fact = 1;
for (i = 1; i <= n - 1; i++)fact = fact * i;
i = 0;
while (s.size()) {
ans[i++] = s[k / fact];
s.erase(s.begin() + k / fact);
k = k % fact;
if (s.size())fact = fact / (s.size());
}
return ans;
}
bool checkCool(ll n) {
while (n) {
ll a = n % 10;
if (a != 3 && a != 6)return false;
n = n / 10;
}
return true;
}
ll countCool(ll n) {
ll i, num = n, digits = 0, p = 1, ans = 0, cnt = 1;
while (num) {
num = num / 10;
digits++;
}
while (cnt <= digits - 1) {
p = p * 2;
ans += p;
cnt++;
}
string s = to_string(n);
for (i = 0; i < digits; i++) {
char c = s[i];
if (c < '3')break;
else if (c > '6') {
ans += (ll)pow(2, digits - i); break;
}
else if (c == '3')
continue;
else if (c == '6')
ans += (ll)pow(2, digits - i - 1);
else {
ans += (ll)pow(2, digits - i - 1);
break;
}
}
if (i == digits)ans++;
return ans;
}
int main() {
ll tt = 1;
cin >> tt;
while (tt--)
{
ll n, len = 0, k, i , fact = 1, f = 1, cnt = 0, ans, ind;
cin >> n >> k;
if (n <= 19) {
for (i = 1; i <= n; i++)f = f * i;
if (k > f)
{cout << -1 << endl; continue;}
}
ans = countCool(n);
while (fact < k) {
len++;
fact = fact * len;
}
vector<ll>v1(len);
for (i = 0; i < len; i++) {
v1[i] = n + 1 - len + i;
}
vector<ll>v2 = getPermutation(v1, len, k);
for (i = 0; i < len; i++) {
ind = n + 1 - len + i;
if (checkCool(ind) && !checkCool(v2[i]))
cnt++;
}
cout << ans - cnt << endl;
}
return 0;
}
Tester's Solution
#pragma GCC optimize("Ofast")
#pragma GCC target("avx")
using namespace std;
#define ll long long
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>ordered_set;
// using namespace chrono;
#include<bits/stdc++.h>
#define F first
#define S second
#define lld long double
#define vc vector<ll>
#define pb push_back
#define all(a) a.begin(),a.end()
const int MOD=(1e9 +7);
const ll inf=(1000000000000000000);
typedef pair<ll,ll> pairs;
#define varval(...) " [" << #_VA_ARGS_ ": " << (_VA_ARGS_) << "] "
ll mod(ll a){
return (a-MOD*(a/MOD));
}
ll power(ll a, ll b){ll res=1;a=mod(a);while(b>0){if(b&1){res=mod(res*a);b--;}a=mod(a*a);b>>=1;}
return res;}
vector<ll>fact;
vc nums{0};
void pre(){
fact.pb(1);
ll k=2;
while(inf/k>=fact.back())
fact.pb(fact.back()*k),k++;
return;
}
void rec(ll len){
if(len==18)
return;
ll n=nums.back();
nums.pb(10*n+3);
rec(len+1);
nums.pb(10*n+6);
rec(len+1);
return;
}
ll bin_nums(ll n){
ll l=0,r=nums.size()-1,ans=0;
while(l<=r){
ll mid=l+(r-l)/2;
if(nums[mid]>n)
r=mid-1;
else ans=mid,l=mid+1;
}
return ans;
}
ll bin_fact(ll n){
ll l=0,r=18,ans=0;
while(l<=r){
ll mid=l+(r-l)/2;
if(fact[mid]>n)
r=mid-1;
else ans=mid,l=mid+1;
}
return ans+1;
}
void shift(vc &v,ll i,ll j){
j+=i;
ll val=v[j];
for(;j>i;j--)
v[j]=v[j-1];
v[i]=val;
return;
}
bool check(ll n){
if(n==0)
return true;
return (((n%10==6)||(n%10==3))&&(check(n/10ll)));
}
int main() {
// your code goes here
std::ios::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
ll t,n,i,j,k,f;
pre();rec(0);
sort(all(nums));
// for(auto x:fact)
// cerr<<x<<" ";
// cerr<<fact.size();
cin>>t;
assert(t<=10000);
for(int tc=1;tc<=t;tc++){
ll q;
cin>>n>>q;
assert(n<=inf&&q<=inf);
assert(n>0&&q>0);
vc v;
ll N=min(20ll,n),cnt=1;
for(i=1;i<=N;i++)
v.pb(i);
if((n<20)&&(q>fact[n-1]))
cout<<-1<<"\n";
else{
q--;
ll ans=bin_nums(n-20);
while(q){
ll ind=bin_fact(q);
// cerr<<varval(ind)<<"\n";
ll qo=q/fact[ind-1];
// cerr<<fact[ind-1]<<"\n";
shift(v,N-ind-1,qo);
// for(auto x:v)
// cerr<<x<<" ";
// cerr<<"\n";
q-=qo*fact[ind-1];
}
// for(i=0;i<N;i++)
// cerr<<v[i]<<" ";
// N=min(N,19ll);
for(i=0;i<N;i++){
// cerr<<i+1<<" "<<v[i]<<"\n";
if((check(n-N+i+1))&&(check(v[i]+n-N)))
ans++;
cnt++;
}
cout<<ans<<"\n";
}
// cout<<"Case #"<<tc<<": ";
}
// cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
return 0;
}