About the Problem
| Setter(s) | Pruthvi Raju |
| Tester(s) | Vichitr Gandas |
| Difficulty | Medium |
| Topics | Simulation, Maths, Matrix Expo |
| Practice | Link |
| Contest | Link |
Solution Idea
This problem was an extension of this. We increase the constraint on k. After simulating the solution for increasing values of k for a fixed n, we make an observation that after k=330, the expected value does not change. We are yet to prove it but looks like it works! So basically the expected value converges for a fixed n, and convergence is different for even and odd k, hence if k>330, you can do,
k=331, if k is odd,
k=300, if k is even.
This helps us solve the problem in given TL with matrix expo.
Team Unbreakable submitted a fast \mathcal{O}(n^6 * \log{k}) solution which passed after we increased TL to 3s & removed testcases with n=20. We removed n=20 on purpose because we were not able to prove the bound hence we let fast \mathcal{O}(n^6 * \log{k}) solutions pass.
Complexity Analysis
Time Complexity: \mathcal{O}(n^4 * min(k, 330)) .
Space Complexity: \mathcal{O}(n^4).
Codes
Setter's Code
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// macros
#define int long long
#define ll long long
#define ld long double
#define TIME clock() * 1.0 / CLOCKS_PER_SEC
#define all(c) c.begin(), c.end()
#define PB push_back
#define MP make_pair
#define bitcount __builtin_popcount
#define watch(x) cerr<< (#x) << " is " << (x) <<"\n";
#define sz(x) ((int)((x).size()))
#define UNIQUE(c) (c).resize(unique(all(c)) - (c).begin())
#define pii2ll(p) ((ll)(p).first<<32 | (p).second)
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string& s) {
return '"' + s + '"';
}
string to_string(const char* s) {
return to_string((string) s);
}
string to_string(bool b) {
return (b ? "1" : "0");
}
string to_string(vector<bool> v) {
bool first = true;
string res = "{";
for (int i = 0; i < static_cast<int>(v.size()); i++) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(v[i]);
}
res += "}";
return res;
}
template <size_t N>
string to_string(bitset<N> v) {
string res = "";
for (size_t i = 0; i < N; i++) {
res += static_cast<char>('0' + v[i]);
}
return res;
}
template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
using vi = vector<int>;
using vvi = vector<vi >;
using vld = vector<ld>;
using vvld = vector<vld >;
using pii = pair<int, int>;
template <typename T1, typename T2>
inline auto mini(T1 a, T2 b) { return (a < b ? a : b); }
template<typename T, typename... Args>
inline auto mini(T a, Args... args) { return mini(a, mini(args...)); }
template <typename T1, typename T2>
inline auto maxi(T1 a, T2 b) { return (a > b ? a : b); }
template<typename T, typename... Args>
inline auto maxi(T a, Args... args) { return maxi(a, maxi(args...)); }
template<typename T>
T gcd(T a, T b) { if(a==0 or b==0) return a+b; return gcd(b, a%b) ; }
template<typename T>
T lcm(T a, T b) { if(a==0 or b==0) return 0; return a/gcd(a, b)*b; }
// random number generation
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); // use mt19937_64 for 64 bit
// constants
const long double eps = LDBL_EPSILON;
const int inf = 1e15;
const int modn = 1e9+7;
const int maxn = 2e5+3;
int dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dy[8] = {1, -1, 2, -2, 2, -2, 1, -1};
bool chk(int i, int j, int N) {
return i >= 0 and i < N and j >= 0 and j < N;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// Your code here
// solution for knight without going out of the board.
cout << fixed << setprecision(7);
int N, K;
cin >> N >> K;
assert(N >= 4 and N <= 20);
assert(K >= 1 and K <= 1000000);
if(K > 331) {
if(K & 1) {
K = 331;
}
else {
K = 330;
}
}
vector<vector<vvld>> dp(N, vector<vvld>(N, vvld(N, vld(N))));
vector<vector<vvld>> ndp(N, vector<vvld>(N, vvld(N, vld(N))));
vvi cnt(N, vi(N));
vector<vector<vector<array<int, 2>>>> child(N, vector<vector<array<int, 2>>>(N));
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
dp[i][j][i][j] = 1;
for(int k = 0; k < 8; k++) {
int ni = i + dx[k];
int nj = j + dy[k];
if(!chk(ni, nj, N)) continue;
cnt[i][j]++;
child[i][j].push_back(array<int, 2>{ni, nj});
}
}
}
for(int it = 0; it < K; it++) {
// memset(ndp, 0, sizeof(ndp));
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
for(int ni = 0; ni < N; ni++) {
for(int nj = 0; nj < N; nj++) {
ndp[i][j][ni][nj] = 0;
}
}
}
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
for(int ni = 0; ni < N; ni++) {
for(int nj = 0; nj < N; nj++) {
for(auto p : child[i][j]) {
ndp[i][j][ni][nj] += dp[p[0]][p[1]][ni][nj] / cnt[i][j];
}
}
}
}
}
swap(dp, ndp);
}
ld ans = 0;
for(int i = 0 ; i < N; i++) {
for(int j = 0; j < N; j++) {
ld cur = 1;
for(int ni = 0; ni < N; ni++) {
for(int nj = 0; nj < N; nj++) {
cur *= 1 - dp[ni][nj][i][j];
}
}
ans += cur;
// cout << cur << " ";
}
// cout << "\n";
}
// cout << "\n";
cout << ans << "\n";
debug(TIME);
return 0;
}
Team Unbreakable submitted a fast \mathcal{O}(n^6 * \log{k}) solution which passed after we increased TL to 3s & removed testcases with n=20.
Team Unbreakable Code
#include <algorithm>
#include <array>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;
template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename T, size_t size> ostream& operator<<(ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#ifdef NEAL_DEBUG
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
// Using `long double` is more accurate, but it can be 50-60% slower than `double`.
using matrix_float = double;
struct float_column_vector {
int rows;
vector<matrix_float> values;
float_column_vector(int _rows = 0) {
init(_rows);
}
template<typename T>
float_column_vector(const vector<T> &v) {
init(v);
}
void init(int _rows) {
rows = _rows;
values.assign(rows, 0);
}
template<typename T>
void init(const vector<T> &v) {
rows = int(v.size());
values.resize(rows);
for (int i = 0; i < rows; i++)
values[i] = v[i];
}
matrix_float& operator[](int index) { return values[index]; }
const matrix_float& operator[](int index) const { return values[index]; }
};
// Warning: very inefficient for many small matrices of fixed size. For that, use float_matrix_fixed_size.cc instead.
struct float_matrix {
int rows, cols;
vector<vector<matrix_float>> values;
float_matrix(int _rows = 0, int _cols = -1) {
init(_rows, _cols);
}
template<typename T>
float_matrix(const vector<vector<T>> &v) {
init(v);
}
void init(int _rows, int _cols = -1) {
rows = _rows;
cols = _cols < 0 ? rows : _cols;
values.assign(rows, vector<matrix_float>(cols, 0));
}
template<typename T>
void init(const vector<vector<T>> &v) {
rows = int(v.size());
cols = v.empty() ? 0 : int(v[0].size());
values.assign(rows, vector<matrix_float>(cols, 0));
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
values[i][j] = v[i][j];
}
vector<matrix_float>& operator[](int index) { return values[index]; }
const vector<matrix_float>& operator[](int index) const { return values[index]; }
bool is_square() const {
return rows == cols;
}
void make_identity() {
assert(is_square());
for (int i = 0; i < rows; i++) {
values[i].assign(cols, 0);
values[i][i] = 1;
}
}
float_matrix operator*(const float_matrix &other) const {
assert(cols == other.rows);
float_matrix product(rows, other.cols);
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
if (values[i][j] != 0)
for (int k = 0; k < other.cols; k++)
product[i][k] += values[i][j] * other[j][k];
return product;
}
float_matrix& operator*=(const float_matrix &other) {
return *this = *this * other;
}
float_column_vector operator*(const float_column_vector &column) const {
assert(cols == column.rows);
float_column_vector product(rows);
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
product[i] += values[i][j] * column[j];
return product;
}
float_matrix pow(int64_t p) const {
assert(p >= 0);
assert(is_square());
float_matrix m = *this;
float_matrix result(rows);
result.make_identity();
while (p > 0) {
if (p & 1)
result *= m;
p >>= 1;
if (p > 0)
m *= m;
}
return result;
}
void print() const {
cout << rows << ' ' << cols << '\n';
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
cout << values[i][j] << (j < cols - 1 ? ' ' : '\n');
}
};
int BOARD;
int MATRIX;
const int DIRS = 8;
const int DR[DIRS] = {-1,-1,-2,-2,1,1,2,2};
const int DC[DIRS] = {2,-2,1,-1,-2,2,-1,1};
bool valid(int r, int c) {
return 0 <= r && r < BOARD && 0 <= c && c < BOARD;
}
int main() {
cout << fixed << setprecision(6);
cin >> BOARD;
MATRIX = BOARD*BOARD;
float_matrix move(MATRIX);
for (int r = 0; r < BOARD; r++)
for (int c = 0; c < BOARD; c++) {
int neighbors = 0;
for (int dir = 0; dir < DIRS; dir++) {
int nr = r + DR[dir];
int nc = c + DC[dir];
neighbors += valid(nr, nc);
}
for (int dir = 0; dir < DIRS; dir++) {
int nr = r + DR[dir];
int nc = c + DC[dir];
if (valid(nr, nc))
move[BOARD * r + c][BOARD * nr + nc] = matrix_float(1) / neighbors;
}
}
int K;
cin >> K;
float_matrix result = move.pow(K);
matrix_float answer = 0;
for (int a = 0; a < MATRIX; a++) {
matrix_float empty = 1;
for (int b = 0; b < MATRIX; b++)
empty *= 1 - result[b][a];
answer += empty;
}
cout << answer << '\n';
}
If you have used any other approach, share your approach in comments!
If you have any doubts, ask them in comments!