#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;
}
We will solve this problem by using the sliding window trick. Let's assume $$$s_{i,j}$$$ as the substring inside $$$s$$$ from the $$$i$$$-th character to the $$$j$$$-th character from the left of the string $$$s$$$. First, create a window from the segment $$$[1,k]$$$ denoting the deletion window, which means $$$x=s_{k+1,|s|}$$$ for now. Now, we will slide this window by one index to the right each time and check if the new string formed by concatenating characters not covered by the window after sliding is weaker than current weakest string before sliding.
Notice that when we slide the window from the segment $$$[i,i+k-1]$$$ to $$$[i+1,i+k]$$$, the only difference between the resulting string from both deletion window result is the $$$i$$$-th character. Or more specifically, we override the $$$i$$$-th character in the result from $$$s_{i+k,i+k}$$$ to $$$s_{i,i}$$$. Furthermore, if $$$s_{i+k,i+k}$$$ is lexicographically smaller (or weaker) than $$$s_{i,i}$$$, that means the resulting string from all the deletion window placement after sliding it to the right from the segment $$$[i,i+k-1]$$$ will never be weaker than when the window is at the segment $$$[i,i+k-1]$$$, which means it is enough to keep sliding the deletion window to the right up until the point where $$$s_{i+k,i+k} < s_{i,i}$$$. Then, delete the segment $$$[i,i+k-1]$$$.
#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;
}
DP: $$$dp[d][s][b][0/1]$$$ is the number of ways to fix the first $$$d$$$ bits of the number $$$x$$$ bits so that we already have s pairs of adjacent non-equal bits, the $$$d_{th}$$$ bit from the left is $$$b$$$, and the entire number is already smaller than $$$n$$$ (when the last parameter is $$$0$$$) or yet equal to $$$n$$$ in the first d bits (when the last parameter is $$$1$$$).
https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics) let's call this Siala
X <= n As a result, there is a bit like $$$j$$$ which:
- Every bit k > j in x is equal to n. 2. The jth bit of n should be 1 and x should be 0. As if for the conditional condition x < n, the previous j bits have no effect. We fix c and count the number of x's: The suffix [j,61] in x is specified uniquely, thus the number of adjacent pairs of bits [1,j] is uniquely specified. Suppose the bits [1,j] They must have up to k2 distinct pairs. The JM bit is also 0. As a result, X bits are in the form: 0000,11111,00000..0,111..1, ... are defined as the number of consecutive bases equal to one. K2+1 should be. Masila was converted into a Siala average: a1+a2+…+a(k2+1) = j, a(i) >= 1 The number of solutions to the above equation is equal to: C(k2, j — 1) Finally, if f(n)=k, we increase the answer by one.
#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 have known $$$p$$$.Note $$$v=x_i + a_i + ... + a_{i + p}$$$,we also need $$$v+Sm=0(mod k)$$$.Use exgcd to get $$$m$$$.
Complexity:$$$O(n log n)$$$.
For C, I have been trying this dp solution but it seems to be failing for tc 14.
dp[i][0] means including the ith round no round has been skipped yet.
dp[i][1] means including the ith round exactly one round has been skipped.
dp[i][0] = dp[i-1][0] if current i is unrated
dp[i][0] = dp[i-1][0] + f((p[i] — dp[i-1][0])/4.0) if current i is rated
dp[i][1] = max(dp[i-1]) if current i is unrated
dp[i][1] = max(dp[i-1][0], dp[i-1][1] + f((p[i] — dp[i-1][1])/4.0))
216641777
Your solution is incorrect.
In case:
$$$500$$$ is expected but your code output $$$650$$$.
Thank you! I understand why it wouldn't work now.
Same works if we maintain separate states for 3 different things (<1900, <2100 and >=2100).
Can you please share the link of the group, if anyone wants to join it.
Here is a link of the discord. (Will work only for one week) https://discord.gg/W5wh8mvF