#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
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;
int a[N];

int main()
{
	//freopen("test.in","r",stdin);
	
	scanf("%d",&T);
	while(T--)
	{
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    	sort(a+1,a+n+1);
    	for(int i=1;i<=n;i++) printf("%d%c",a[i]*(i&1?1:-1),i==n?'\n':' ');
	}
	
	//fclose(stdin);
	return 0;
}

We just sort the array and set $$$a_i:=-a_i$$$ for all even $$$i$$$.

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int t;
        cin >> t;

        while (t --> 0) {
                string s;
                int k;
                cin >> s >> k;

                int n = (int)s.length();
                int mn = n - k;
                for (int i = n - k - 1; i >= 0; i--) {
                        if (s[i] > s[i + k]) {
                                mn = i;
                        }       
                }

                string ans = s.substr(0, mn) + s.substr(mn + k);

                cout << ans << '\n';
        }
        
        return 0;
}

Coming soon...

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
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,k,ans;
int  p[N],d[N],pre[N];
int  dp[N][2];

int main()
{
	//freopen("test.in","r",stdin);
	
	T=1;
	//scanf("%d",&T);
	while(T--)
	{
    	scanf("%d%d",&n,&k);
    	for(int i=1;i<=n;i++) scanf("%d",&p[i]);
    	for(int i=1;i<=n;i++) scanf("%d",&d[i]);
    	ans=0;
    	pre[0]=k; 
	    for(int i=1;i<=n;i++)
	    {
    		if((d[i]&&pre[i-1]>=1900)||((!d[i])&&pre[i-1]<=2100)) pre[i]=(p[i]-pre[i-1])/4+pre[i-1];
			else pre[i]=pre[i-1];
    	}
    	ans=max(pre[n-1],pre[n]);
    	for(int i=0;i<=4000;i++) dp[i][(n+1)&1]=i;
    	for(int i=n;i>=2;i--)
    	{
			for(int j=0;j<=4000;j++) 
			{
				if((d[i]&&j>=1900)||((!d[i])&&j<=2100)) dp[j][i&1]=dp[(p[i]-j)/4+j][(i+1)&1];
				else dp[j][i&1]=dp[j][(i+1)&1];
			}
			ans=max(ans,dp[pre[i-2]][i&1]);
	    }
    	/*for(int i=0;i<=4000;i++) dp[n+1][i]=i;
    	for(int i=n;i;i--)
    	{
	    	for(int j=0;j<=4000;j++)
	    	{
	    		if((d[i]&&j>=1900)||((!d[i])&&j<=2100)) dp[i][j]=dp[i+1][(p[i]-j)/4+j];
	    		else dp[i][j]=dp[i+1][j];
	    	}
	    }
	    ans=dp[1][k];kk=k;
	    for(int i=1;i<=n;i++)
	    {
    		ans=max(ans,(int)dp[i+1][k]);
    		if((d[i]&&k>=1900)||((!d[i])&&k<=2100)) k=(p[i]-k)/4+k;
    	}*/
    	printf("%d\n",k-ans);
	}
	
	//fclose(stdin);
	return 0;
}

The key to solving the problem is to notice that $$$k$$$ is small ($$$k \leq 4000$$$).The intended solution is $$$O(nk)$$$.

We note $$$dp_{i,j}$$$ as the final rating when current score is $$$j$$$, participating in the $$$i, i+1,...,n_{th}$$$ contest.

We can enumerate the skipped contest and update the answer with the $$$dp$$$ array.

To avoid exceeding the memory limit, you need to use a scrolling array.

/**
 *  @the_hyp0cr1t3
 *  30.07.2023 20:42
**/
#include <bits/stdc++.h>

template <int P> struct modint {
    static int mod_;
    int v;

    constexpr modint() : v{} {}
    constexpr modint(long long u) {
        if (u < 0) u = u % get_mod() + get_mod();
        if (u >= get_mod()) u %= get_mod();
        v = u;
    }

    constexpr int val() const { return v; }
    constexpr static int get_mod() {
        if constexpr (P > 0)
            return P;
        else
            return mod_;
    }
    constexpr static void set_mod(int m) {
        mod_ = m;
    }
    explicit constexpr operator int() const { return v; }
    friend constexpr std::istream& operator>>(std::istream& in, modint& m) {
        long long u; in >> u;
        m = modint(u);
        return in;
    }
    friend constexpr std::ostream& operator<<(std::ostream& os, const modint& m) {
        return os << m.v;
    }

    static int inv(int a, int m) {
        int g = m, x = 0, y = 1;
        while (a != 0) {
            int q = g / a;
            g %= a;
            std::swap(g, a);
            x -= q * y;
            std::swap(x, y);
        }
        return x < 0 ? x + m : x;
    }

    constexpr static unsigned fast_mod(uint64_t x, unsigned m = get_mod()) {
#if !defined(_WIN32) || defined(_WIN64)
        return unsigned(x % m);
#endif  // x must be less than 2^32 * m
        unsigned x_high = unsigned(x >> 32), x_low = unsigned(x), quot, rem;
        asm("divl %4\n" : "=a"(quot), "=d"(rem) : "d"(x_high), "a"(x_low), "r"(m));
        return rem;
    }

    constexpr modint inv() const { return modint(inv(v, get_mod())); }
    constexpr modint operator-() const { return modint(v ? get_mod() - v : 0); }
    constexpr modint& operator+=(const modint& o) {
        v += o.v;
        if (v >= get_mod()) v -= get_mod();
        return *this;
    }
    constexpr modint& operator-=(const modint& o) {
        v -= o.v;
        if (v < 0) v += get_mod();
        return *this;
    }
    constexpr modint& operator*=(const modint& o) {
        v = fast_mod(uint64_t(v) * o.v);
        return *this;
    }
    constexpr modint& operator/=(const modint& o) { return *this *= o.inv(); }
    friend constexpr modint operator+(const modint& a, const modint& b) {
        modint res = a; res += b;
        return res;
    }
    friend constexpr modint operator-(const modint& a, const modint& b) {
        modint res = a;
        res -= b;
        return res;
    }
    friend constexpr modint operator*(const modint& a, const modint& b) {
        modint res = a;
        res *= b;
        return res;
    }
    friend constexpr modint operator/(const modint& a, const modint& b) {
        modint res = a;
        res /= b;
        return res;
    }
    friend constexpr bool operator==(const modint& a, const modint& b) {
        return a.val() == b.val();
    }
};

template <typename T>
constexpr T expo(T A, long long B) {
    T res{1};
    while (B) {
        if (B & 1) res *= A;
        B >>= 1;
        A *= A;
    }
    return res;
}

template <>
int modint<0>::mod_ = 1;

constexpr int mod = 1'000'000'007;
using Z = modint<mod>;
// using Z = double;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int tests;
    std::cin >> tests;
    while (tests--) {
        int n;
        std::array<Z, 3> p;
        std::cin >> n;
        int pmx = -1;
        for (int k : {2, 1, 0}) {
            std::cin >> p[k];
            pmx = std::max(pmx, p[k].val());
            p[k] /= 100;
        }

        if (pmx == 100) {
            std::cout << (n == 1 ? 0 : -1) << '\n';
            continue;
        }

        --n;

        auto P = p;
        std::array<Z, 2> ans{};
        std::array<std::vector<std::array<Z, 2>>, 3> dp;
        for (int k : {0, 1, 2}) {
            dp[k].reserve(n + 1);
            dp[k].push_back({0, p[k]});
        }

        for (int i = 1; i <= n; i++) {
            ans = {};
            for (int k : {0, 1, 2}) {
                for (int j = 0; j < i; j++) {
                    Z mul = p[(k + 1) % 3] * (i + 1) / (i - j);
                    for (int t : {0, 1}) {
                        dp[k][j][t] *= mul;
                        ans[t] += dp[k][j][t];
                    }
                }
            }
            ans = {(1 + ans[0]) / ans[1], 1};
            for (int k : {0, 1, 2}) {
                P[k] *= p[k];
                dp[k].push_back({});
                for (int t : {0, 1})
                    dp[k][i][t] = ans[t] * P[k];
            }
        }

        std::cout << ans[0] << '\n';
    }

}

For convenience, let $$$A=\frac{a}{100}$$$, $$$B=\frac{b}{100}$$$, $$$C=\frac{c}{100}$$$.

First, let's deal with some corner cases. When $$$n=1$$$, the answer is $$$0$$$. When $$$[A=0] + [B=0] + [C=0] = 2$$$, the answer is $$$-1$$$, because no one can leave if only one move is possible. Make sure to deal with these two cases in this particular order, because the answer when $$$n=1$$$ and $$$[A=0] + [B=0] + [C=0] = 2$$$ are both satisfied is $$$0$$$.

Then, let's solve the problem with DP. Let $$$f_i$$$ be the expected number of rounds it takes to result in $$$1$$$ person, starting from $$$i$$$ people. In the base case, we have $$$f_1 = 0$$$. Then, the transition would be:

where $$$P(i, j)$$$ is the probability of transitioning from $$$i$$$ people to $$$j$$$ people in one round. Rearranging, that is,

$$$P(i, i)$$$ basically translates to the probability of having one type or three types of moves in the room in one round. Thus,

To calculate $$$P(i, j)$$$ where $$$i > j$$$, we can also count cases in which $$$j$$$ winning moves and $$$i - j$$$ losing moves are made. That is,

Then, our answer would just be $$$f_n$$$.

Overall, the complexity is $$$O(n^2\log n)$$$ if techniques like fast-power are used to calculate the powers and combination values. However, the constant can be very big. By precomputing these values, the complexity would be $$$O(n^2)$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=63;
const ll  TMD=0;
const ll  INF=2147483647;
int T;
ll  n,k,ans;
int dif[N];
ll  f[LOGN][LOGN][2];
vector<int> v;

void init()
{
	f[0][0][0]=f[1][0][0]=f[1][0][1]=1;
	for(int i=2;i<LOGN;i++)
	{
	    for(int j=0;j<i;j++)
	    {
	        for(int k=0;k<=1;k++) 
	        {
				f[i][j][k]=f[i-1][j][k];
				if(j) f[i][j][k]+=f[i-1][j-1][k^1];
	        }
	    }
	}
		
}

void DP(int bt)
{
	if(bt<0) 
	{
		ans+=(dif[0]==k);
		return ;
	}
	if(v[bt])
	{
		if(bt==(int)v.size()-1) 
		{
			for(int i=bt;i;i--) ans+=f[i][k][1];
		}
		else 
		{
			int diff=dif[bt+1]+v[bt+1];
			if(k-diff>=0)   ans+=f[bt][k-diff][0];
			if(k-diff-1>=0) ans+=f[bt][k-diff-1][1];
		}
	}
	DP(bt-1);
}

int main()
{
	//freopen("test.in","r",stdin);
	
	init();
	scanf("%d",&T);
	while(T--)
	{
    	scanf("%I64d%I64d",&n,&k);
    	v.clear();
    	while(n) v.push_back(n&1),n>>=1;
    	dif[(int)v.size()-1]=0;
    	for(int i=(int)v.size()-2;i>=0;i--) dif[i]=dif[i+1]+(v[i]^v[i+1]);
    	ans=0;
    	DP((int)v.size()-1);
		printf("%I64d\n",ans%1000000007); 
	}
	
	//fclose(stdin);
	return 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>
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=0;
const ll  INF=2147483647;
int T,n,tt,ans;
int t[N],s[N],dt[N],ds[N];
int dp[N][N];

int main()
{
	//freopen("test.in","r",stdin);
	
	scanf("%d",&T);
	while(T--)
	{
    	scanf("%d%d",&n,&tt);
    	for(int i=1;i<=n;i++) scanf("%d%d%d%d",&t[i],&s[i],&dt[i],&ds[i]);
    	ans=0;
    	for(int i=1;i<=tt;i++)
    	{
    		vector<pair<int,int> > v;
	    	for(int j=1;j<=n;j++) 
			{
				if(i+dt[j]>tt) v.push_back(make_pair(s[j],j));
				else           v.push_back(make_pair(ds[j],j));
			}
			sort(v.begin(),v.end());
			for(int j=1;j<=n;j++)
				for(int k=0;k<=i;k++)
					dp[i][j]=-INF;
			dp[0][0]=0;
			for(int j=1;j<=n;j++)
			{
				int num=v[j-1].second;
				if(i-t[num]>=0) ans=max(ans,dp[j-1][i-t[num]]+s[num]-v[j-1].first);
				for(int k=0;k<=i;k++)
				{
					dp[j][k]=dp[j-1][k];
					if(k-t[num]>=0) dp[j][k]=max(dp[j][k],dp[j-1][k-t[num]]+s[num]);
				}
			}
	    }
    	printf("%d\n",ans);
	}
	
	//fclose(stdin);
	return 0;
}

Consider:for a fixed problem set you choose,which problem will the hacker hack?

For problem $$$i$$$,$$$f_i \leq T-Σt$$$,hack it will decrease you score by $$$p_i$$$.

However,for problem $$$i$$$,$$$f_i >T-Σt$$$,hack it will decrease you score by $$$a_i$$$,since you don't have enough time to fix the bug.

Note $$$decrease_i$$$ as the score that actually decreased for the i-th hacked problem.Hacker'll hack the problem with the max $$$decrease$$$ value.

We find $$$decrease$$$ is depend on the value of $$$Σt$$$.

Enumeration $$$Σt$$$ from $$$0$$$ to $$$T$$$,calculate the corresponding $$$decrease$$$,then do classic knapsack DP.It's $$$O(n^2T)$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
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,k,ls,lt;
ll  ans;
int x[N],a[N],S[N],s[N],t[N],nxt[N];
vector<int> p;

//

void build_nxt(int s[],int l)
{
	for(int i=1;i<l;i++)
	{
		int j=i;
		while(s[nxt[j-1]]!=s[i]&&j!=0) j=nxt[j-1];
		nxt[i]=(s[i]==s[nxt[j-1]])?nxt[j-1]+1:0;
	}
	//for(int i=0;i<l;i++) printf("%d ",nxt[i]);
	//printf("\n");
}

void KMP(int s[],int t[],int ls,int lt,vector<int> &v)
{
	build_nxt(t,lt);
	int ps=0,pt=0;
	while(1)
	{
		if(pt>=lt) 
		{
			v.push_back(ps-lt);
			pt=nxt[pt-1];
		}
		if(ps==ls) break;
		while(s[ps]!=t[pt])
		{
			if(!pt) break;
			else pt=nxt[pt-1];
		}
		if(s[ps]==t[pt]) ps++,pt++;
		else ps++,pt=0;
	}
}

//

//

ll md(ll a,ll b)	//a mod b
{
	if(a>0) return a%b;
	return (-(-a)%b+b)%b;	
}
		
void exgcd(ll &x,ll &y,ll a,ll b){
    if(!b){
        x=1;y=0;
        return ;
    }
    exgcd(x,y,b,a%b);
    ll xx=x,yy=y;
    x=yy;y=xx-(a/b)*yy;
}

ll solve_equation(ll a,ll b,ll k)	//solve ax=b(mod k),x>=0 and x is minimal
{
	ll x,y,g;
	md(a,k);md(b,k);
	exgcd(x,y,a,k); 	//ax+ky=gcd(a,k)
	g=a*x+k*y;
	if(b%g) return -1;
	return md(x*(b/g),k/g);
}

int check()
{
	for(int i=1;i<=n;i++) if(x[i]%k) return 0;
	return 1;
}

//


int main()
{
	//freopen("test.in","r",stdin);
	
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&k);
    	for(int i=1;i<=n;i++)  scanf("%d",&x[i]);
    	for(int i=1;i<=n;i++)  scanf("%d",&a[i]);
    	if(check())
		{
			printf("0\n");
			continue;
		} 
    	for(int i=1;i<=n;i++)  S[i]=(S[i-1]+a[i])%k;
 		ls=2*n-2;lt=n-1;
 		for(int i=1;i<n;i++)   s[i-1]=a[i+1]%k;
 		for(int i=n;i<2*n;i++) s[i-1]=a[i-n+1]%k;
 		for(int i=1;i<n;i++)   t[i-1]=md(a[i]+x[i]-x[i+1],k);
 		p.clear();
    	KMP(s,t,ls,lt,p);
    	ans=INF*INF;
    	for(int i=0;i<p.size();i++)
    	{
	    	ll y=x[1]+S[1+p[i]],sol=solve_equation(S[n],-y,k);
	    	if(sol==-1) continue;
	    	ans=min(ans,sol*n+p[i]+1);
	    }
	    if(ans==INF*INF) printf("-1\n");
	    else printf("%I64d\n",ans);
	}
	
	//fclose(stdin);
	return 0;
}

Let's say $$$t = nm+p (0 \leq p<n)$$$ and $$$S$$$ is sum of all $$$a_i$$$.

We get $$$x_i + a_i + ... + a_{i + p} = x_{i + 1} + a_{i + 1} + ... + a_{i + p + 1}=-Sm$$$ (mod $$$k)$$$

Thus $$$x_i + a_i = x_{i + 1} + a_{i + p + 1} ($$$mod $$$k)$$$ for $$$1\leq i \leq n-1$$$.

So we need to find $$$a_i + x_i - x_{i + 1}$$$ shifted in $$$a$$$, this is KMP.

Assume we get p.Note $$$v=x_i + a_i + ... + a_{i + p}$$$,we also need $$$v+Sm=0(mod$$$ k$)

Unable to parse markup [type=CF_MATHJAX]

Complexity:$$$O(n log n)$$$.