C — Fibonacci Parity
Idea: Fremder
find pattern
In the defined Fibonacci sequence $$$s$$$, initially established with $$$s_0$$$ = ‘0’ and $$$s_1$$$ = ‘1’ , concatenating the last string with the second-to-last string yields alternating parity. consequently, for $$$s_i$$$ , if $$$i$$$ is even, the parity of $$$s_i$$$ is even, and if $$$i$$$ is odd, the parity of $$$s_i$$$ is odd.
Upon observation, it's evident that the function $$$f(s)$$$ generates the Fibonacci sequence starting from $$$f(s_2)$$$ . Given the established fact that every third Fibonacci number is even, we can conclude that $$$f(s)$$$ is even for $$$s$$$ = $$$s_{2+3i}$$$ and odd otherwise .
Now we got parity for nth element of both $$$s$$$ and $$$f(s)$$$ , compare parity of both and answer .
#include<bits/stdc++.h>
using namespace std;
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define int long long
#define pb push_back
#define ppb pop_back
#define MOD 1000000007;
const int N=1e5;
void solve(){
int n;
cin >> n;
bool s = ((n%2)==0);
bool fs = ((n%3)==2);
if(s == fs){
cout << "YES";
}else cout << "NO";
cout << endl;
}
signed main() {
fastio();
int t = 1;
cin >> t;
while(t--){
solve();
}
return 0;
}
D — Subsequence Query
Idea: Fremder
prefix and suffix
#include<bits/stdc++.h>
using namespace std;
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define int long long
#define pb push_back
#define ppb pop_back
#define MOD 1000000007;
const int N=1e5;
void solve(){
int m, n;
cin >> n >> m;
string s, t;
cin >> s >> t;
int index = 0;
s.insert(0, "0"); t.insert(0, "0");
vector<int> pre(n + 1), suff(n + 2);
for(int i = 1; i <= n; i++) {
if(s[i] == t[index + 1] and index<m)
index++;
pre[i] = index;
}
suff.back() = index = t.size();
for(int i = n; i > 0; i--) {
if(s[i] == t[index - 1] and index>1)
index--;
suff[i] = index;
}
int q;
cin >> q;
while(q--) {
int l, r;
cin >> l >> r;
if(suff[r + 1] - pre[l - 1] < 2)
cout << "YES\n";
else
cout << "NO\n";
}
}
signed main() {
fastio();
int t = 1;
while(t--){
solve();
}
return 0;
}
F — PAS Makeup
Idea: agrim07
Try to use DP to solve this problem
Let $$$dp[i][p][q][turn]$$$ denote the probability of Rajat winning the game, where:
- $$$i$$$ denotes the number of turns left,
- $$$p$$$ denotes the parity of Rajat’s score,
- $$$q$$$ denotes the parity of Dr. S’s score, and
- $$$turn$$$ is 0 if it is Rajat’s turn and 1 if it is Dr. S’s turn.
Let $$$p_{\text{even}}$$$ and $$$p_{\text{odd}}$$$ denote the probabilities of landing even and odd elements, respectively, among the first $$$n - 1$$$ elements of $$$a$$$. We will consider the scenario where $$$a_n$$$ is rolled on the die separately.
The transitions will be as follows:
If it is Rajat’s turn, then there are 2 additional cases:
Case 1: When $$$a_n$$$ is odd
Case 2: When $$$a_n$$$ is even
Similarly, for Dr. S’s turn:
Case 1: When $$$a_n$$$ is odd
Case 2: When $$$a_n$$$ is even
where $$$p_n$$$ is the probability of rolling $$$n$$$.