Idea:wakanda-forever
For any non-decreasing sequence $$$(b_1, b_2, \ldots, b_m)$$$, $$$b_1$$$ $$$|$$$ $$$b_2$$$ $$$|$$$ $$$b_3$$$ $$$|$$$ $$$\cdots$$$ $$$|$$$ $$$b_m$$$ $$$\ge$$$ $$$b_1$$$.
So, it is always better to consider subsequences of length $$$1$$$. Out of these, we can simply choose the smallest element and this is always optimal.
Time Complexity: $$$O(n)$$$.
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin >> t;
while(t--){
int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; i++) cin >> a[i];
cout << *min_element(a.begin(), a.end()) << '\n';
}
}
Idea:frostcat
We can observe that $$$f(i,1)=0$$$ for $$$i \ge 1$$$ and $$$f(1,i)$$$ for $$$i \ge 2$$$.
Thus, "1 n-1" is always a valid answer.
// By Auchenai01
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
const ll MOD = 998244353;
const ll MAXX = 1e16;
const int INF = 1e9 + 7;
void solve() {
int n;
cin >> n;
cout << 1 << " " << n - 1 << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
If $$$m=1$$$, the answer is "YES".
Otherwise, to make $$$f(x,i)=1$$$ for all $$$2 \le i \le n$$$, the valuse of $$$x$$$ must be at least $$$\lcm(2,3,\ldots,n)+1$$$. We can see it will exceed $$$10^{18}$$$ when $$$n$$$ is larger than $$$30$$$.
Thus, the solution is: When $$$m=1$$$, output "YES". Otherwise, run bruteforce when $$$n \le 30$$$ and output "NO" when $$$n \gt 30$$$,
// By Auchenai01
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
const ll MOD = 998244353;
const ll MAXX = 1e16;
const int INF = 1e9 + 7;
void solve() {
int n, m;
cin >> n >> m;
if (n <= 30) {
for (int i = 2; i <= n; i++) {
if (m % i != 1) {
cout << "NO" << endl;
return;
}
}
cout << "YES" << endl;
return;
}
cout << (m == 1 ? "Yes" : "no") << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Idea:wuhudsm
Let's assume $$$\operatorname{mex}(a_1, a3, \ldots, a{n-1}) = p$$$ and $$$\operatorname{mex}(a_2, a4, \ldots, a{n}) = q$$$. Now the condition becomes $$$\operatorname{mex}(p, q) = \operatorname{mex}(a_1, a_2, a_3, \ldots, a_n)$$$.
We can see that the inequality $$$\operatorname{mex}(p, q) \le 2$$$ holds for any value of $$$p$$$ and $$$q$$$. So, we can simply check the three possible cases:
Case I: $$$\operatorname{mex}(p, q) = 0$$$
Here, we should have $$$p \gt 0$$$ and $$$q \gt 0$$$, and this implies that there are at least two 0's in the array $$$a$$$. Then, we have $$$\operatorname{mex}(a_1, a_2, a_3, \ldots, a_n) \gt 0 = \operatorname{mex}(p, q)$$$.
So, the array is not good in this case.
Case II: $$$\operatorname{mex}(p, q) = 1$$$
Here, we should have $$$p = 0$$$ and $$$q \ne 1$$$, or $$$p \ne 1$$$ and $$$q = 0$$$. In any case, $$$\operatorname{mex}(a_1, a_2, a_3, \ldots, a_n) \ne 1 = \operatorname{mex}(p, q)$$$.
So, the array is not good in this case.
Case III: $$$\operatorname{mex}(p, q) = 2$$$
Here, we should have $$$p = 0$$$ and $$$q = 1$$$, or $$$p = 1$$$ and $$$q = 0$$$. For the array to be good, we should also have $$$\operatorname{mex}(a_1, a_2, a_3, \ldots, a_n) = 2$$$.
Thus, an array is good if it's $$$\operatorname{mex} = 2$$$ and $$$\operatorname{mex}$$$ of even and odd indexed values are $$$0$$$ and $$$1$$$.
So, any array of length $$$n$$$ can be rearranged into a good array if all the following conditions are satisfied: $$$\operatorname{mex}$$$ of array is $$$2$$$. number of 0's in the array $$$\le \frac{n}{2}$$$. number of 1's in the array $$$\le \frac{n}{2}$$$.
Time Complexity: $$$O(n)$$$.
#include <bits/stdc++.h>
using namespace std;
int n,m;
int solve(string s){
map<int,int> mp;
int x=0;
for(int i=0;i<m;i++)
{
if(s[i]=='L') x++;
else x--;
mp[x]=1;
}
mp.erase(0);
return mp.size()>=n;
}
int main() {
int t;
cin>>t;
while(t--)
{
cin>>n>>m;
string s;
cin>>s;
string T=s;
for(int i=0;i<m;i++) if(s[i]=='?') T[i]='L';
if(solve(T)) cout<<"YES\n"<<T<<"\n";
else
{
for(int i=0;i<m;i++) if(s[i]=='?') T[i]='R';
if(solve(T)) cout<<"YES\n"<<T<<"\n";
else cout<<"NO\n";
}
}
return 0;
}
Idea:wuhudsm
If $$$k$$$ is chosen for the first time, we can recalculate the answer using brute force. Otherwise, the answer can be updated in $$$O(1)$$$. Since all values on the diagonal are already the same, the update operation will only increase the answer by (new_value — old_value).
Time complexity: $$$O(n^3)$$$.
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <unordered_map>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=1010;
const int LOGN=28;
const ll TMD=1000000007;
const ll INF=2147483647;
int T,n,q;
ll ans;
ll a[N][N],dp[N][N];
ll DP()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j];
return dp[n][n];
}
void init()
{
cin>>n>>q;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j];
ans=DP();
}
void modify(int k,int v)
{
ll delta;
for(int i=min(k-1,n),j=k-i;i>=1&&j<=n;i--,j++)
{
delta=v-a[i][j];
a[i][j]=v;
}
ans+=delta;
}
void solve()
{
vector<int> tag(2*n);
for(int i=1;i<=q;i++)
{
int k,v;
cin>>k>>v;
modify(k,v);
if(!tag[k])
{
tag[k]=1;
ans=DP();
}
cout<<ans<<'\n';
}
}
//-------------------------------------------------------
void gen_data()
{
srand(time(NULL));
}
int bruteforce()
{
return 0;
}
//-------------------------------------------------------
int main()
{
fastio;
cin>>T;
while(T--)
{
init();
solve();
/*
//Stress Test
gen_data();
auto ans1=solve(),ans2=bruteforce();
if(ans1==ans2) printf("OK!\n");
else
{
//Output Data
}
*/
}
return 0;
}
Idea:wuhudsm
Note: $$$'('$$$ is $$$1$$$ and $$$')'$$$ is $$$-1$$$, with $$$S$$$ as the current sum.
If $$$a \geq 2b$$$, Alice always wins.
The strategy is: $$$S = b \xrightarrow{\text{Bob}} 0 \leq S \leq 2b \xrightarrow{\text{Alice}} S = b \xrightarrow{\text{Bob}} 0 \leq S \leq 2b \xrightarrow{\text{Alice}} \dots \xrightarrow{\text{Bob}} 0 \leq S \leq 2b \xrightarrow{\text{Alice}} S = 0$$$.
Otherwise, Bob always wins.
The strategy is: $$$S \geq b \xrightarrow{\text{Bob}} S \geq 2b \xrightarrow{\text{Alice}} S \geq b \xrightarrow{\text{Bob}} S \geq 2b \xrightarrow{\text{Alice}} \dots \xrightarrow{\text{Bob}} S \geq 2b \xrightarrow{\text{Alice}} S \gt 0$$$.
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <unordered_map>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll TMD=0;
const ll INF=2147483647;
int T;
int n,a,b;
/*
* stuff you should look for
* [Before Submission]
* array bounds, initialization, int overflow, special cases (like n=1), typo
* [Still WA]
* check typo carefully
* casework mistake
* special bug
* stress test
*/
void init()
{
cin>>n>>a>>b;
}
int cal(string s)
{
int sum=0;
for(int i=0;i<s.length();i++)
sum+=(s[i]=='('?1:-1);
return sum;
}
void solve()
{
string s;
if(a>=2*b)
{
cout<<1<<'\n'<<flush;
for(int i=1;i<=n;i+=2)
{
int cur=cal(s)-a;
string t,tt;
if(i==n)
{
for(int j=1;j<=a;j++)
{
if(cur<0) cur+=2,t+='(';
else t+=')';
}
cout<<t<<'\n'<<flush;
s+=t;
}
else
{
for(int j=1;j<=a;j++)
{
if(cur<b) cur+=2,t+='(';
else t+=')';
}
cout<<t<<'\n'<<flush;
s+=t;
cin>>tt;
s+=tt;
}
}
}
else
{
cout<<0<<'\n'<<flush;
for(int i=1;i<=n;i+=2)
{
string t,tt;
cin>>t;
s+=t;
if(i==n) break;
if(cal(s)<b)
{
for(int j=1;j<=b;j++) tt+=')';
cout<<tt<<'\n'<<flush;
}
else
{
for(int j=1;j<=b;j++) tt+='(';
cout<<tt<<'\n'<<flush;
}
s+=tt;
}
}
}
//-------------------------------------------------------
void gen_data()
{
srand(time(NULL));
}
int bruteforce()
{
return 0;
}
//-------------------------------------------------------
int main()
{
fastio;
cin>>T;
while(T--)
{
init();
solve();
/*
//Stress Test
gen_data();
auto ans1=solve(),ans2=bruteforce();
if(ans1==ans2) printf("OK!\n");
else
{
//Output Data
}
*/
}
return 0;
}
Idea:wuhudsm
For fixed $$$m$$$, we can construct intervals for $$$n \in [mL, mR]$$$. Let $$$m = \left\lfloor \frac{n}{L} \right\rfloor$$$. If $$$n \gt mR$$$, output $$$-1$$$; otherwise, we can always construct a valid solution.
Now, let's consider constructing a solution with the minimum $$$\gcd$$$. Let $$$minlen$$$ be the minimum length of all intervals. We can observe that all scores $$$(l[i] \cdot (l[i] + 1) \cdots \cdot r[i])$$$ in the intervals are multiples of $$$(minlen!)$$$.
Let's prove it in one line:
$$$\frac{r \cdot (r-1) \cdots (r-minlen+1)}{minlen!} = \frac{r!}{(r-minlen)! minlen!} = C(r, minlen)$$$.
Thus, we can simply choose $$$[1, minlen]$$$ to minimize the gcd. For construction, we choose the scheme that minimizes the value of $$$minlen$$$.
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <unordered_map>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll TMD=998244353;
const ll INF=2147483647;
ll T,n,L,R;
ll fac[N];
/*
* stuff you should look for
* [Before Submission]
* array bounds, initialization, int overflow, special cases (like n=1), typo
* [Still WA]
* check typo carefully
* casework mistake
* special bug
* stress test
*/
void init_fac()
{
fac[0]=1;
for(int i=1;i<N;i++) fac[i]=(fac[i-1]*i)%TMD;
}
void init()
{
cin>>n>>L>>R;
}
void solve()
{
ll mn=INF,m=0;
for(int i=1;i<=n;i++)
{
if(i*L<=n&&n<=i*R)
{
ll res=max(0LL,n-(L+R*(i-1)));
if(L+res<mn) mn=L+res,m=i;
}
}
if(!m)
{
cout<<"-1\n";
return ;
}
vector<ll> len(m+4);
for(int i=1;i<=m;i++) len[i]=L;
n-=m*L;
for(int i=m;i;i--)
len[i]+=min(R-L,n),n-=min(R-L,n);
cout<<m<<' '<<fac[mn]<<'\n';
for(int i=1,cur=1;i<=m;i++)
{
cout<<cur<<' '<<cur+len[i]-1<<'\n';
cur+=len[i];
}
}
//-------------------------------------------------------
void gen_data()
{
srand(time(NULL));
}
int bruteforce()
{
return 0;
}
//-------------------------------------------------------
int main()
{
fastio;
init_fac();
cin>>T;
while(T--)
{
init();
solve();
/*
//Stress Test
gen_data();
auto ans1=solve(),ans2=bruteforce();
if(ans1==ans2) printf("OK!\n");
else
{
//Output Data
}
*/
}
return 0;
}
Idea:wuhudsm
One key observation is that only the last operation of type $$$2$$$ matters.
The answer is $$$x + \max(b[j] + a[j+1:r[i]])$$$. There are two other cases: $$$x$$$ and $$$x + \sum(a[l[i]:r[i]])$$$. To simplify, let’s define $$$c[i] = b[i] + a[i+1:]$$$, and then build a sparse table on $$$c$$$ to maintain the answer.
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll TMD=0;
const ll INF=2147483647;
int T,n,q;
int a[N],b[N];
ll presum[N];
//-------------------------------------------------
int lg2[N];
ll mx[N][LOGN];
void init()
{
for(int i=1;i<=n;i++) lg2[i]=(int)log2(i);
for(int i=1;i<=n;i++) mx[i][0]=b[i]-presum[i];
for(int i=1;i<LOGN;i++)
{
for(int j=1;j<=n;j++)
{
int p=j+(1<<(i-1));
if(p>n)
{
mx[j][i]=mx[j][i-1];
}
else
{
mx[j][i]=max(mx[j][i-1],mx[p][i-1]);
}
}
}
}
ll getmax(int L,int R)
{
int t=lg2[R-L+1];
return max(mx[L][t],mx[R-(1<<t)+1][t]);
}
//-------------------------------------------------
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
for(int i=1;i<=n;i++) a[i]=max(0,a[i]);
for(int i=1;i<=n;i++) presum[i]=presum[i-1]+a[i];
init();
for(int i=1;i<=q;i++)
{
int k,l,r;
//ll ans;
scanf("%d%d%d",&k,&l,&r);
printf("%I64d\n",max(k+presum[r]-presum[l-1],presum[r]+getmax(l,r)));
//ans=presum[r]-presum[l-1];
}
}
//fclose(stdin);
return 0;
}




