PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: alpha_ashwin, shanmukh29
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Dynamic programming
PROBLEM:
Chef and Chefina play tetris together. Chef starts first.
A player can clear between 1 and 4 lines on each move. If they clear only one line, the turn passes to the other player.
The game ends when at least L lines have been cleared.
Count the number of sequences of moves that end with Chef finishing the game with a “Tetris”, i.e, clearing 4 lines.
EXPLANATION:
Let f(x) denote the number of sequences such that exactly x lines have been cleared, and it’s currently Chef’s turn.
Similarly, let g(x) denote the number of sequences with x lines cleared, and it’s Chefina’s turn.
As base cases, we have f(0) = 1 and g(0) = 0, since Chef starts the game.
Also, f(x) = g(x) = 0 when x \lt 0.
Notice that functions f and g can be computed recursively:
by conditioning on the last move made: if \geq 2 lines were cleared the player doesn’t change; if 1 line was cleared it must’ve been done by the other player.
Now, Chef wants to be the one to the end the game, and do it by clearing 4 lines.
Since the game ends when L lines are cleared, just before Chef’s last move the number of lines cleared must’ve been \geq L-4 and it should be Chef’s turn.
So, the answer we’re looking for is just
All the f(x) and g(x) values from 0 to 10^5 can be precomputed in linear time with dynamic programming, after which each testcase can be answered in \mathcal{O}(1) time.
TIME COMPLEXITY:
\mathcal{O}(1) per testcase after \mathcal{O}(\max L) precomputation.
CODE:
Author's code (C++)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define int long long int
#define vi vector<int>
int mod= 1e9+7;
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int zero=0;
vi dpchef(1e5,0), dpchefina(1e5,0);
dpchefina[1]=1;
dpchef[2]=1;
dpchef[3]=1;
dpchef[4]=1;
for(int i=1;i<1e5;i++)
{
dpchef[i]+=(dpchefina[max(zero,i-1)] + dpchef[max(zero,i-2)] + dpchef[max(zero,i-3)] + dpchef[max(zero,i-4)])%mod;
dpchefina[i]+=(dpchef[max(zero,i-1)] + dpchefina[max(zero,i-2)] + dpchefina[max(zero,i-3)] + dpchefina[max(zero,i-4)])%mod;
}
int _t=1;
cin>>_t;
for(int test=1;test<=_t;test++)
{
int n;
cin>>n;
int answer=(dpchef[max(zero,n-1)]+dpchef[max(zero,n-2)]+dpchef[max(zero,n-3)]+dpchef[max(zero,n-4)])%mod;
if(n<=4)
answer++;
cout<<answer<<"\n";
}
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
struct input_checker {
string buffer;
int pos;
const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";
input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
buffer.push_back((char) c);
}
}
int nextDelimiter() {
int now = pos;
while (now < (int) buffer.size() && !isspace(buffer[now])) {
now++;
}
return now;
}
string readOne() {
assert(pos < (int) buffer.size());
int nxt = nextDelimiter();
string res;
while (pos < nxt) {
res += buffer[pos];
pos++;
}
return res;
}
string readString(int minl, int maxl, const string &pattern = "") {
assert(minl <= maxl);
string res = readOne();
assert(minl <= (int) res.size());
assert((int) res.size() <= maxl);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}
int readInt(int minv, int maxv) {
assert(minv <= maxv);
int res = stoi(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
long long readLong(long long minv, long long maxv) {
assert(minv <= maxv);
long long res = stoll(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
auto readInts(int n, int minv, int maxv) {
assert(n >= 0);
vector<int> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readInt(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
auto readLongs(int n, long long minv, long long maxv) {
assert(n >= 0);
vector<long long> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readLong(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
};
input_checker inp;
const int T = 1e5;
const int N = 1e5;
const int mod = 1e9 + 7;
int dp[N + 1][2];
vector <int> a = {1, 2, 3, 4};
void pre(){
int n = N;
for (int i = 0; i <= n; i++){
dp[i][0] = dp[i][1] = 0;
}
dp[0][1] = 1;
dp[0][0] = 1;
for (int i = 1; i <= n; i++){
for (int j = 0; j < 2; j++){
for (auto x : a){
int l = i - x;
if (l < 0) l = 0;
if (l == 0 && (x != 4 || j != 1)) continue;
dp[i][j] += dp[l][j ^ (x == 1)];
dp[i][j] %= mod;
}
}
}
}
void Solve()
{
int n = inp.readInt(1, N); inp.readEoln();
// int n; cin >> n;
cout << dp[n][1] << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
t = inp.readInt(1, T);
inp.readEoln();
//cin >> t;
pre();
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
inp.readEof();
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Editorialist's code (Python)
mod = 10**9 + 7
N = 10**5 + 10
dp = [ [0, 0] for _ in range(N) ]
# dp[i][0] -> exactly i lines cleared, and it's now Chef's turn
dp[0][0] = 1
for i in range(1, N):
for j in range(2, 5):
if i-j >= 0:
dp[i][0] += dp[i-j][0]
dp[i][1] += dp[i-j][1]
dp[i][0] += dp[i-1][1]
dp[i][1] += dp[i-1][0]
dp[i][0] %= mod
dp[i][1] %= mod
for _ in range(int(input())):
n = int(input())
ans = 0
for x in range(1, 5):
if n-x >= 0: ans += dp[n-x][0]
print(ans % mod)
