LightOj 1060 (nth Permutation)

#lightoj #cp #problem_solving #dp #combinatorics

Idea

DP

  • First of all we check maximum number of permutations possible from the
    given string … if it is < n than answer is impossible.
  • Now we have to fix character at each position starting from MSB position
  • For fixing the character at any position initially we try to fix smallest character
    at that position if by placing that character number of permutation formed >= remaining
    required permutation than fix this charter at that position ,
    and decrease the frequency of this character since this character is used at this
    position and move to next position , else if no of permutation formed by placing this
    character is less than the required remaining permutation than decrease remaining
    permutation by the number of permutation formed by placing this character at that
    position ( since this count times number of permutations comes in between current
    to final permutation ) and try to find next character for this position .
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

/**Which of the favors of your Lord will you deny ?**/

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

#define LL long long
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define MP make_pair
#define F first
#define S second
#define INF INT_MAX

inline void optimizeIO()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int nmax = 1e6+7;
const LL LINF = 1e17;

string to_str(LL x)
{
    stringstream ss;
    ss<<x;
    return ss.str();
}

LL nCr[30][30];
int cnt[30];
int len;


LL count_perm(int n)
{
    LL ret = 1;

    for (int i = 0; i < 26; i++)
    {
        ret *= nCr[n][cnt[i]];
        n -= cnt[i];

    }
    return ret;
}

LL solve(int pos,int rem)
{
    if(pos>=len)
        return 0;

    int i;

    for(i=0;i<26;i++)
    {
        if(cnt[i])
        {
            cnt[i]--;

            LL use = count_perm(len-pos-1);

            //cout<<i<<"  -->  "<<use<<endl;

            if(use>=rem)
                break;

            cnt[i]++;
            rem -= use;
        }
    }

    cout<<char(i+'a');

    solve(pos+1,rem);
}

int main()
{
    for(int i=0; i<=20; i++)
    {
        nCr[i][0]=1;
        nCr[i][i]=1;
        for(int j=1; j<=i; j++)
        {
            nCr[i][j]=nCr[i-1][j]+nCr[i-1][j-1];
        }
    }

    int tc;
    cin>>tc;

    for(int q=1; q<=tc; q++)
    {

        memset(cnt,0,sizeof cnt);

        string s;
        int nth;
        cin>>s>>nth;

        len = s.size();

        for(int i=0; i<len; i++)
            cnt[s[i]-'a']++;

        cout<<"Case "<<q<<": ";

        if(count_perm(len)<nth)
        {
            cout<<"Impossible";
        }
        else
            solve(0,nth);

        cout<<endl;

    }

    return 0;
}