PROBLEM LINK:
Idea: mihil2701
Author: rivalq
Tester: shikhar7s
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Dynamic Programming, Expected value.
PROBLEM:
Given a rectangle of size N and M. Until the area of the rectangle is not equal to one, we perform the following operation:-
- Make a random cut on the rectangle either horizontally or vertically parallel to the side of the rectangle and continue the process with a rectangle of a larger area. That is if the current dimensions of the rectangle are N and M, and we choose to cut horizontally at a distance i (1 \leq i \lt N ) from the bottom then there will be now two rectangles one with size (i, M) and other with size (N-i, M). We will continue the process with rectangle (max(i,N-i),M).
Let T denotes the number of steps it takes to reduce the size of the rectangle to (1,1).
We want the value of E(T^2).
QUICK EXPLANATION:
Let X denotes the number of horizontal cuts, and Y denotes the number of vertical cuts.
E(T^2) = E((X+Y)^2)
E((X+Y)^2) = E(X^2 + Y^2 + 2 \cdot X \cdot Y)
Now by using linearity of expectation.
E((X+Y)^2) = E(X^2) + E(Y^2) + 2 \cdot E(X \cdot Y)
Since X and Y are independent E(X \cdot Y) = E(X) \cdot E(Y)
Now we can just problem in one dimension using Dynamic Programming and combine the result.
EXPLANATION:
Let’s first solve an easy problem that involves only one dimension. Currently, we are at some position n and have to go 1, using similar types of operation performed on reducing the dimension of the rectangle.
Suppose currently you are at position n, then from n you can go to [\frac {n}{2}, \frac {n}{2}+1,...,n-1].
Let E[X \mid n] be the expected number of steps to reach 1 , if we start from n.
{E}[X \mid n] = 1 + \sum_{i = \frac{n}{2}}^{i = n-1}p_i*E[X \mid i]
If n is odd for every i, p_i is just \frac{2}{n-1}. In case of even p_\frac{n}{2} = \frac{1}{n-1} and for i \gt \frac{n}{2} , p_i is \frac{2}{n-1}.
We can easily compute E[X \mid n] using prefix sums.
Now let’s look at E[X^2 \mid n].
{E}[X^2 \mid n] = \sum_{i = \frac{n}{2}}^{i = n-1}p_i*E[(X + 1)^2 \mid i]
E[(X+1)^2] = E[X^2] + 1 + 2 \cdot E[X]
{E}[X^2 \mid n] = \sum_{i = \frac{n}{2}}^{i = n-1}p_i + \sum_{i = \frac{n}{2}}^{i = n-1}p_i*E[X^2 \mid i] + 2 \cdot \sum_{i = \frac{n}{2}}^{i = n-1}p_i*E[X \mid i]
Using the above recurrence we easily calculate E[X^2 \mid n] using prefix sums.
For two dimensions we just have to combine the result using the fact that the number of cuts in the horizontal and vertical directions is independent of each other.
We can preprocess the dp values for N \leq 10^6 and answer each test case in O(1)
SOLUTIONS:
Setter's Solution
// Jai Shree Ram
#include<bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
struct mod_int {
int val;
mod_int(long long v = 0) {
if (v < 0)
v = v % MOD + MOD;
if (v >= MOD)
v %= MOD;
val = v;
}
static int mod_inv(int a, int m = MOD) {
int g = m, r = a, x = 0, y = 1;
while (r != 0) {
int q = g / r;
g %= r; swap(g, r);
x -= q * y; swap(x, y);
}
return x < 0 ? x + m : x;
}
explicit operator int() const {
return val;
}
mod_int& operator+=(const mod_int &other) {
val += other.val;
if (val >= MOD) val -= MOD;
return *this;
}
mod_int& operator-=(const mod_int &other) {
val -= other.val;
if (val < 0) val += MOD;
return *this;
}
static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
#if !defined(_WIN32) || defined(_WIN64)
return x % m;
#endif
unsigned x_high = x >> 32, x_low = (unsigned) x;
unsigned quot, rem;
asm("divl %4\n"
: "=a" (quot), "=d" (rem)
: "d" (x_high), "a" (x_low), "r" (m));
return rem;
}
mod_int& operator*=(const mod_int &other) {
val = fast_mod((uint64_t) val * other.val);
return *this;
}
mod_int& operator/=(const mod_int &other) {
return *this *= other.inv();
}
friend mod_int operator+(const mod_int &a, const mod_int &b) { return mod_int(a) += b; }
friend mod_int operator-(const mod_int &a, const mod_int &b) { return mod_int(a) -= b; }
friend mod_int operator*(const mod_int &a, const mod_int &b) { return mod_int(a) *= b; }
friend mod_int operator/(const mod_int &a, const mod_int &b) { return mod_int(a) /= b; }
mod_int& operator++() {
val = val == MOD - 1 ? 0 : val + 1;
return *this;
}
mod_int& operator--() {
val = val == 0 ? MOD - 1 : val - 1;
return *this;
}
mod_int operator++(int32_t) { mod_int before = *this; ++*this; return before; }
mod_int operator--(int32_t) { mod_int before = *this; --*this; return before; }
mod_int operator-() const {
return val == 0 ? 0 : MOD - val;
}
bool operator==(const mod_int &other) const { return val == other.val; }
bool operator!=(const mod_int &other) const { return val != other.val; }
mod_int inv() const {
return mod_inv(val);
}
mod_int pow(long long p) const {
assert(p >= 0);
mod_int a = *this, result = 1;
while (p > 0) {
if (p & 1)
result *= a;
a *= a;
p >>= 1;
}
return result;
}
friend ostream& operator<<(ostream &stream, const mod_int &m) {
return stream << m.val;
}
friend istream& operator >> (istream &stream, mod_int &m) {
return stream>>m.val;
}
};
const int N = 1e6+5;
mod_int dp[N];
mod_int dp2[N];
mod_int pre[N];
mod_int pre2[N];
void intend(int n = 1e6){
dp[1] = dp2[1] = 0;
for(int i = 2; i <= n; i++){
pre[i] = pre[i - 1];
pre2[i] = pre2[i - 1];
if(i & 1){
dp[i] = 2*(pre[i - 1] - pre[i / 2]);
dp2[i] = 4*(pre[i - 1]-pre[i / 2]) + 2*(pre2[i - 1]-pre2[i / 2]);
}
else{
dp[i] = 2*(pre[i - 1] - pre[i / 2]) + dp[i / 2];
dp2[i] = 4*(pre[i - 1] - pre[i / 2]) + 2*dp[i / 2] + 2*(pre2[i - 1] -pre2[i / 2]) + dp2[i / 2];
}
dp[i] /= (i-1);
dp[i] += 1;
dp2[i] /= (i-1);
dp2[i] += 1;
pre[i] += dp[i];
pre2[i] += dp2[i];
}
}
int solve(){
int t; cin >> t;
while(t--){
int n,m;
cin >> n >> m;
cout << dp2[n] + dp2[m] + 2*dp[n]*dp[m] << endl;
}
return 0;
}
signed main(){
int t = 1; //cin >> t;
intend();
while(t--){
solve();
}
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define mp(a,b) make_pair(a,b)
#define vi vector<int>
#define mii map<int,int>
#define mpi map<pair<int,int>,int>
#define vp vector<pair<int,int> >
#define pb(a) push_back(a)
#define fr(i,n) for(i=0;i<n;i++)
#define rep(i,a,n) for(i=a;i<n;i++)
#define F first
#define S second
#define endl "\n"
#define fast std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define mod 1000000007
#define dom 998244353
#define sl(a) (int)a.length()
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define mini 2000000000000000000
#define time_taken 1.0 * clock() / CLOCKS_PER_SEC
//const long double pi = acos(-1);
//mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
//primes for hashing 937, 1013
template<typename T, typename U> static inline void amin(T &x, U y)
{
if (y < x)
x = y;
}
template<typename T, typename U> static inline void amax(T &x, U y)
{
if (x < y)
x = y;
}
int dp1[1000005],dp2[1000005],s1[1000005],s2[1000005],in[1000005];
void shikhar7s(int cas)
{
int n,m,i;
cin>>n>>m;
int ans=(dp2[n]+dp2[m])%dom;
ans=(ans+2*dp1[n]*dp1[m])%dom;
cout<<ans<<endl;
}
signed main()
{
fast;
//freopen("input.txt", "rt", stdin);
//freopen("output.txt", "wt", stdout);
int t=1;
in[0]=1;
in[1]=1;
for(t=2;t<=1000000;t++)
{
in[t]=in[dom%t]*(dom-dom/t)%dom;
}
rep(t,2,1000001)
{
int a=(s1[t-1]-s1[t/2]+((t-1)/2)+dom)%dom;
a=(a*2)%dom;
if(t%2==0)
a=(a+dp1[t/2]+1)%dom;
a=(a*in[t-1])%dom;
dp1[t]=a;
s1[t]=(s1[t-1]+a)%dom;
}
rep(t,2,1000001)
{
int a=(s2[t-1]-s2[t/2]+dom)%dom;
int b=(s1[t-1]-s1[t/2]+dom)%dom;
b=(b*2)%dom;
a=(a+b+((t-1)/2))%dom;
a=(a*2)%dom;
if(t%2==0)
{
a=(a+dp2[t/2])%dom;
a=(a+2*dp1[t/2]+1)%dom;
}
a=(a*in[t-1])%dom;
dp2[t]=a;
s2[t]=(s2[t-1]+a)%dom;
}
cin>>t;
int cas=1;
while(cas<=t)
{
shikhar7s(cas);
cas++;
}
return 0;
}
TIME COMPLEXITY:
O(max(N,M) + T)