DIVPERMS - Editorial

PROBLEM LINK:

Practice
Contest: Division 2
Contest: Division 1

Author: Ildar Gainullin
Tester: Alexander Morozov
Editorialist: Aman Dwivedi

DIFFICULTY:

MEDIUM-HARD

PREREQUISITES:

Dynamic Programming, Inclusion-Exclusion Principle, Bitmasking

PROBLEM:

For each k between 0 and N−1 (inclusive), we need to find the number of permutations of length N with cost k. Cost is defined as the number of adjacent pairs which are divisible and the quotient lies in the given set.

QUICK EXPLANATION:

  • Masking on first N/2 numbers is done for building Dynamic Programming states.
  • DP states is represented as (x,y), representing the number of permutations of length x which has a masked cost y, where cost is defined as the number of adjacent pairs which are divisible and the quotient lies in the given set.
  • DP state is calculated in order from 1 to N, every combination of masked is checked and the number of ways are added accordingly,
  • Finally output the number of permutations of length N which has a cost k where k lies between 0 and N-1 (inclusive).

EXPLANATION:

The main ideas is to use Inclusion-Exclusion Principle to find for each number of chains, the number of ways to divide numbers 1,2,3....N into chains such that in each of them, the adjacent pairs are divisible and the quotient lies in the given set.

Let us try to visualize it with using with the sample case:

  • Here we have N=5 and the given set is S=10001. Now the total number of the permutations will be N!.
  • The total number of the permutations such that their cost is 1 can be calculated as follows, we will try to put (P_{i-1},P_{i}) consecutively such that P_{i} is divisible by P_{i}. Hence we will make (P_{i-1},P_{i}) as a packet and now the number of permutations such that (P_{i-1},P_{i}) occurs consecutive will be 4!.
  • Hence the total number of permutations with cost 1 are 4!.
  • Now we will exclude all the all the permutation which has cost 1. Then we will be able to find the number of permutations whose cost is 0, which is 5!-4!.

Claim: We claim that P_{i}/P_{i-1} is never equal to 1.

Proof

It is quite obvious as P is permutation and hence there will be no two such values which would be equal. Hence we say that the quotient is never equal to 1, which leads us to further observation that P_{i}/P_{i-1} \ge 2

Claim: We claim that P_{i-1} \le N/2.

Proof

From the previous inequality we see that:

P_{i}/P_{i-1} \ge 2
P_{i}/2 \ge P_{i-1}

The maximum value a permutation of length N is N. Hence the maximum value that P_{i} can take is N. That leads us to our claim:

P_{i-1} \le N/2

Now, lets move towards Dynamic Programming.

We can slightly re-frame our task to: Find the values of P_{i} and P_{i-1} such that they form a valid pair, where valid pairs means such that P_{i} is divisible by P_{i-1} and the quotient lies in the given set.

No lets create our DP as (N,mask), which is defined as follows:

DP(N,mask) is defined as number of permutation of length N which have valid pairs (P_{i},P_{i-1}), such that P_{i-1} belongs to mask. The x^{th} bit is set in mask when x=P_{i-1}.

DP[0][0]=1, because there is only 1 such permutation as this is empty mask.

Let’s proceed forward and we will try to find DP(N,mask). Suppose that we have DP(N-1,mask), which means the permutation of length N-1. Now in this permutation of length N-1, we will try to insert N and where we place N depends on the type of mask that we get.

Consider that we have some permutation where (x,y) occurs consecutively. Since we are inserting N between (x,y), it can affect the x in the following way:

  • x was valid in permutation of length N-1 and is also valid in permutation of length N.
  • x was valid in permutation of length N-1 and is now invalid in permutation of length N.
  • x was invalid in permutation of length N-1 and is now valid in permutation of length N.
  • x was invalid in permutation of length N-1 and is also invalid in permutation of length N.

Let us see how these four types of masks effects the value of DP(N,mask).

Now for each x (1 \le x \le N-1) after which N is inserted and we will try to check for every insertion how does it effect for the above cases.

Case 1

x was valid x is still valid.

Here N is inserted after x such that after insertion (x,N,y). Basically previously y/x belongs to the set and now N/x belongs to the set. So x is still valid. We can say that for DP(N-1,mask) and DP(N,mask) the mask remains same.

DP(N,mask)+=DP(N-1,mask)

because the addition of N doesn’t make change in the mask.

Case 2

x was valid but x is not valid now.

Here N is inserted after x such that after insertion (x,N,y). Basically previously y/x belongs to the set and now N/x doesn’t belongs to the set or N is not divisible by x. So x is not valid anymore. So now we need to remove x from the mask.

Mask can be changed by using xor to unset the x^{th} bit, so now:

DP(N,mask ⊕ (1<<x))+=DP(N-1,mask)

because the addition of N make change in the mask.

Case 3

x was invalid but x is valid now.

This case is just opposite of the Case 2. Here y/x doesn’t belongs to the set but now N/x belongs to the set. So x is now valid and we need to add x to the mask.

Mask can be changed by using or to set the x^{th} bit, so now:

DP(N,mask | (1<<x))+=DP(N-1,mask)

because the addition of N make change in the mask.

Case 4

x was invalid and x is still invalid now.

This case is similar to the Case 1. Here y/x doesn’t belongs to the set and also N/x doesn’t belongs to the set. So x was invalid and is still invalid. We can say that for DP(N-1,mask) and DP(N,mask) the mask remains same.

DP(N,mask)+=DP(N-1,mask)

because the addition of N doesn’t make change in the mask.

Finally, we can calculate the number of permutations whose cost equals to k, where k lies between 0 and N-1 (inclusive) by unmasking.

TIME COMPLEXITY:

For the transition of DP states we need to start from the permutation of length 1 to permutation of length N and while generating a new permutation of length x, we need to check whether x is divisible by the previous numbers. Hence, this thing requires O(N^{2}) complexity.

We only need to store the mask for first N/2 numbers and hence at max we need to iterate for only 2^{N/2}.

Hence the Time Complexity will be O(N^{2} * 2^{N/2}).

SOLUTIONS:

Setter's Solution
#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>

using namespace std;

typedef long long ll;

#ifdef iq
  mt19937 rnd(228);
#else
  mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

const int mod = 998244353;

void add(int &a, int b) {
  a += b;
  if (a >= mod) a -= mod;
  if (a < 0) a += mod;
}

int mul(int a, int b) {
  return (a * (ll) b) % mod;
}

const int N = 50;

int comb[N][N];
int fact[N];

int main() {
#ifdef iq
  freopen("a.in", "r", stdin);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);
  unordered_map <ll, int> dp;
  int n;
  cin >> n;
  comb[0][0] = 1;
  for (int i = 0; i<= n; i++) {
    for (int j = 0; j <= n; j++) {
      if (i) add(comb[i][j], comb[i - 1][j]);
      if (i && j) add(comb[i][j], comb[i - 1][j - 1]);
    }
  }
  fact[0] = 1;
  for (int i = 1; i <= n; i++) fact[i] = mul(fact[i - 1], i);
  string t;
  cin >> t;
  dp[0] = 1;
  for (int i = 1; i <= n; i++) {
    unordered_map <ll, int> ndp;
    for (auto c : dp) {
      add(ndp[c.first | (1ll << i)], c.second);
    }
    for (int j = 1; j <= i; j++) {
      if (i % j == 0 && t[i / j - 1] == '1') {
        ll sw = (1ll << j) ^ (1ll << i);
        for (auto c : dp) {
          if ((c.first >> j) & 1) {
            add(ndp[c.first ^ sw], c.second);
          }
        }
      }
    }
    dp = ndp;
  }
  vector <int> ret(n);
  for (auto c : dp) {
    int chains = __builtin_popcountll(c.first);
    int k = n - chains;
    add(ret[k], mul(c.second, fact[chains]));
  }
  for (int i = n - 1; i >= 0; i--) {
    for (int j = 0; j < i; j++) {
      add(ret[j], -mul(ret[i], comb[i][j]));
    }
  }
  for (int i = 0; i < n; i++) {
    cout << ret[i] << ' ';
  }
  cout << endl;
}
Editorialist Solution
#include<bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)
#define repa(i,a,n) for(int i=a;i<=n;i++)
#define repb(i,a,n) for(int i=a;i>=n;i--)
#define trav(x,a) for(auto &x: a)
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x).size()
#define fst first
#define snd second
#define pb push_back
#define mp make_pair
#define vt vector
typedef long double ld;
typedef pair <int,int> pii;
typedef vector <int> vi;
typedef long long ll;

template<class A> void read(vt<A>& v);
template<class T> void read(T& x){
  cin>>x;
}

void read(double &d){
  string t;
  read(t);
  d=stod(t);
}
void read(long double &d){
  string t;
  read(t);
  d=stold(t);
}

template<class H, class... T> void read(H &h, T&...t){
  read(h);
  read(t...);
}

template <class A> void read(vt<A> &x){
  trav(a,x)
    read(a);
}

string to_string(char c){
  return string(1,c);
}

string to_string(bool b){
  return b?"true":"false";
}

string to_string(const char* s){
  return string(s);
}

string to_string(string s){
  return string(s);
}

string to_string(vt<bool> v){
  string res;
  rep(i,sz(v)){
    res+=char('0'+v[i]);
  }
  return res;
}

template<class T> string to_string(T v){
  bool f=1;
  string res;
  trav(x,v){
    if(!f)
      res+=' ';
    f=0;
    res+=to_string(x);
  }
  return res;
}

template<class A> void write(A x){
  cout<<to_string(x);
}

template<class H, class...T> void write(const H& h, const T&...t){
  write(h);
  write(t...);
}

void print(){
  write("\n");
}

template<class H, class...T> void print(const H& h, const T&...t){
  write(h);
  if(sizeof...(t))
    write(' ');
  print(t...);
}

/* -----------------------------------------------------------------------------------------------*/

const int mod=998244353;
const int len=2097155;
const int N=41;

int dp[N][len];

void add(int &x, int y){
	x += y;
	if(x>=mod)
		x-=mod;
}

void pre(){

}

void solve(){
	int n; read(n);
	string s; read(s);


	for(int i=0;i<=n;i++){
		for(int j=0;j<len;j++){
			dp[i][j]=0;
		}
	}

	dp[0][0]=1;

	for(int i=1;i<=n;i++){
		int stop=i/2;
		for(int mask=0;mask<(1<<(stop+1));mask++){
			for(int j=0;j<i;j++){
				if(j && (i%j==0) && s[i/j-1]=='1')
					add(dp[i][mask|(1<<j)],dp[i-1][mask]);
				else{
					if(j>stop)
						add(dp[i][mask],dp[i-1][mask]);
					else
						add(dp[i][(mask|(1<<j))^(1<<j)],dp[i-1][mask]);
				}
			}
		}
	}

	vi ans(n);

	for(int i=0;i<len;i++){
		if(__builtin_popcount(i)<n)
			add(ans[__builtin_popcount(i)],dp[n][i]);
	}

	print(ans);
}

int main(){
  ios_base::sync_with_stdio(0); cin.tie(0);
  pre();
  int t=1;
  // read(t);
  rep(i,t) solve();
  return 0;
}

VIDEO EDITORIAL:

23 Likes

Please have a look at this https://www.codechef.com/viewsolution/40314801

3 Likes

Nice one @cherry0697… You always amaze us with your work…

1 Like

Keep it up @cherry0697 bro

1 Like

@gainullinildar @ildar_adm, were the test cases so weak that people found them? Similar was the case with CALCULUS.

1 Like

Elaborate… Thanks man!

1 Like

Nice

1 Like

Please have a look at this. I don’t know DP properly, so I thought in another direction.
https://www.codechef.com/viewsolution/40348400

Basically, I find all valid subsets for a given permutation number “N” and the string “S”. for example, if N = 5, and S = 11010, Then I precalculate the following array

precalculate = [[1, 2], [1, 4], [2, 4], [1, 2, 4]]

Now note that these arrays follow the property that is mentioned in the problem statement.

These are all the possible combinations that come together, or in other words, I can move [1, 2] together like

3, 5, 4, (1, 2) or 4, (1, 2), 5, 3.

(i.e) I am counting (1, 2) by considering it as one element.
similarly, I do this for [1, 4], [1, 2, 4], [2, 4]

NOTE: when I count [1, 2], I don’t want permutations involving [1, 2, 4], Because that’s a case of double counting. So I want pure permutations of [1, 2], [1, 4], [2, 4] and [1, 2, 4]

The cost can be calculated directly using the counting principles, as the number of indices is basically the size of each array.

The problem is that I’m not able to proceed that way, or in other words, I’m not able to count the pure permutation costs.

Please let me know if this was the right direction to think and please give some idea about how to count those pure permutations

1 Like

I understood your approach. I think you are calculating one thing many times.
like (2,4) is a subset of (1,2,4). while calculating for (2,4) you are calculating (1,2,4) also.
which is you were calculating again.

Heyy!

Yes exactly! I am double counting, But I’m not able to figure out a way to eliminate this double-counting algorithmically.

@cherry0697 Nice explanation :+1: , but one remark

The definition fo DP(N,mask) should clearly be defined as the -

The number of permutations of lenght N with numbers from 1 to N (including 1 and N) such that each permutation satisfy the following condition.

1. For every valid pair ( Pi-1 , Pi ) , Pi-1 belongs to mask
2. For every pi-1 in mask we have a valid pair ( pi-1 ,pi ) in the given permutation.

This may be obvious to many , but not for me.

3 Likes

The setter’s Solution is soo fast , can any one explain what the program logic was ??

How about using some unknown test cases at last to verify the solutions?

Anyone help me where i am getting wrong

Code

UPD: got the mistake, thanks @cherry0697

1 Like

Hi !!

In your code you are not checking the condition of p > i/2. If (p>i/2) then the mask will remain same as the values greater than i/2 won’t affect the mask. Secondly, in Case 3 to set the bit you should prefer OR operation.

Here is your code after doing these two changes.

yeah , thanks.

1 Like

Why we are using (mask|(1<<j))^(1<<j) this over here?