Save the position of each character in the corresponding vector, and then select the smallest value each time.
That way, all strings can be generated. The complexity is $$$\Theta(n|c|^2)$$$, we can also use the priority queue do it in $$$\Theta(n|c|\log|c|)$$$.
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
const int MOD=998244353;
void Delta() {
string s,answer;cin >> s;
vector<vector<int>> Q(26,vector<int>{});
for(int i=0;i<(int)s.size();++i)
Q[s[i]-'a'].push_back(i);
for(int i=0;i<26;++i)
reverse(Q[i].begin(),Q[i].end());
while(true) {
bool flag=true;
for(int i=0;i<26;++i)
if(!Q[i].empty()) flag=false;
if(flag) break;
vector<bool> Flag(26,false);
string temp;
for(int j=0;j<26;++j) {
int mnidx=-1,mnvalue=2147483647;
for(int i=0;i<26;++i)
if(!Flag[i]&&!Q[i].empty()&&Q[i].end()[-1]<mnvalue) {
mnvalue=Q[i].end()[-1];
mnidx=i;
}
if(mnidx==-1) break;
Q[mnidx].pop_back();
temp.push_back(s[mnvalue]);
Flag[mnidx]=true;
}
answer=temp;
}
cout << answer << endl;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;cin >> T;
while(T--) Delta();
}
Using Greed to solve this problem.
If two points are on a straight line, they can be directly reached through the line. This must be the shortest.
Otherwise, we hope to follow as many curves as possible. Because the arc of a unit is $$$\frac{\pi}{2}$$$, it can replace the effect of $$$2$$$ straight lines.
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define int long long
const long double pi=3.141592653589793238462643383279L;
void Delta() {
long double x1,y1,x2,y2,answer;
cin >> x1 >> y1 >> x2 >> y2;
if((x1==0&&x2==0)||(y1==0&&y2==0))
answer=abs(x1+y1-x2-y2);
else {
x1=abs(x1);y1=abs(y1);x2=abs(x2);y2=abs(y2);
answer=pi/2*min(x1+y1,x2+y2)+max(x1+y1,x2+y2)-min(x1+y1,x2+y2);
}
if(abs(answer)>100000000) cout << (int)answer << endl;
else cout << fixed << setprecision(20) << answer << endl;
}
signed main() {
cin.tie(0);
int T;cin >> T;
while(T--) Delta();
}
Another problem of greed.
Let's first consider the situation of the last position. Obviously, the last position can only be modified by manipulating the entire string.
Therefore, we first change the last position, and then change the last two positions until all strings are the same.
For each position, there are some strings that are either $$$0$$$ or $$$1$$$. Each time we select fewer strings to change. Because the answer only requires comparing the strings, modifying more or fewer will not affect subsequent operations.
To facilitate the calculation of flipping, flip tags can be used for maintenance. It's $$$\Theta(nm)$$$
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define int long long
const int MOD=998244353;
string a[100001];
bool flip[100001];
void Delta() {
int n,m,answer=0;
cin >> n >> m;
for(int i=1;i<=n;++i) {
cin >> a[i];
flip[i]=false;
}
for(int i=m-1;i>=0;--i) {
vector<int> c[2];
for(int j=1;j<=n;++j)
c[(a[j][i]-'0')^flip[j]].push_back(j);
for(int j:(c[0].size()>c[1].size()?c[1]:c[0])) {
answer++;
flip[j]^=true;
}
}
cout << answer << endl;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;cin >> T;
while(T--) Delta();
}
For this problem we can use binary serach to solve it.
Firstly, if there is a square of size $$$x$$$, then there must also be a square of size $$$x-1$$$, so we can use binary serach.
To verify the existence of a square of size $$$x$$$, we use a sliding window for maintenance. In a sliding window, we place all soldiers in their positions. If there is an adjacent position difference greater than $$$x$$$, then we can place a square of size x at this position.
For calculating sliding windows, we can use multiset for maintenance. Use one multiset to maintain all soldier positions and query adjacent soldiers, while another multiset is used to maintain all adjacent differences and find the maximum value.
That way, we can make single modifications in $$$\Theta(\log n)$$$, The total complexity is $$$\Theta(n\log^2n)$$$.
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
long long isqrt(int x){long long a=x,b=(x+1)/2;while(a>b){a=b;b=(b+x/b)/2;}return a;}
const int MOD=998244353;
int n,a[50001];
void ins(multiset<int> &P,multiset<int> &Q,int x) {
auto itr=Q.insert(x),nxt=next(itr,1),pre=prev(itr,1);
P.erase(P.lower_bound(*nxt-*pre-1));
P.insert(*itr-*pre-1);
P.insert(*nxt-*itr-1);
}
void del(multiset<int> &P,multiset<int> &Q,int x) {
auto itr=Q.lower_bound(x),nxt=next(itr,1),pre=prev(itr,1);
P.insert(*nxt-*pre-1);
P.erase(P.lower_bound(*itr-*pre-1));
P.erase(P.lower_bound(*nxt-*itr-1));
Q.erase(itr);
}
bool check(int x) {
int answer=0;
multiset<int> Q={0,n+1},P={n};
for(int i=1;i<=x;++i) ins(P,Q,a[i]);
answer=max(answer,*P.rbegin());
for(int i=x+1;i<=n;++i) {
ins(P,Q,a[i]);
del(P,Q,a[i-x]);
answer=max(answer,*P.rbegin());
}
return answer>=x;
}
void Delta() {
cin >> n;
for(int i=1;i<=n;++i) cin >> a[i];
int l=1,r=n,m,s=0;
while(l<=r) {
m=(l+r)/2;
if(check(m)) {
l=m+1;s=m;
} else r=m-1;
}
cout << s << endl;
if(s==isqrt(n-1)) cout << "NO" << endl;
else cout << "YES" << endl;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
Delta();
}
Interesting problem.
First, this $$$69$$$ is not special, so we first subtract all of $$$a_i$$$ from $$$69$$$ and then turn the problem into at most $$$0$$$.
Consider, if we already know a sequence, how do we decide whether it can become $$$0$$$? For some prefix and suffix operations, we can translate this into the sum of an ascending sequence and a descending sequence.
Here is a greedy observation. Because a falling sequence cannot rise again once it has fallen, and can fall at any time, we want the value of the falling sequence to be as large as possible. The same goes for an ascending sequence, the smaller the better.
So we would set the first value of the ascending sequence to $$$0$$$ and the first value of the descending sequence to $$$a_1$$$. (assuming $$$a_1$$$ is the first number to become $$$0$$$)
It is easy to find that the sum of the ascending and descending sequences must equal the last number taken, and that each number taken must degrade the sequence value. So there is monotonicity here.
Since $$$n$$$ is small and $$$a_i$$$ is large, you can set the dp state to "$$$x$$$ numbers are taken from $$$1$$$ to $$$i$$$ and last is $$$a_i$$$, and the minimum value of the ascending sequence at that point is $$$dp_{i,x}$$$".
For the initial value we have $$$dp_{i,1}=0$$$, and the transfer has $$$dp_{i,x}=\text{min}_{j<i\text{ and }dp_{j,x-1}\le a_i}(\max(0,a_i-a_j)+dp_{j,x-1})$$$. It's $$$\Theta(n^3)$$$, not fast enough, so it needs optimization.
First, $$$a_i$$$ is discretized, and then stored $$$\min dp_j$$$ and $$$\min dp_j-a_j$$$ with segment tree. The values of max in dp transitions are classified and then calculated separately. Then the total complexity is $$$\Theta(n^2\log n)$$$.
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
struct node {int mndp,mndpa;};
node merge(node a,node b) {return {min(a.mndp,b.mndp),min(a.mndpa,b.mndpa)};}
template <class T> class segment {
private:
int id(int l,int r){return (l+r)|(l!=r);}
void change(int l,int r,int x,T &y){if(l==r){seg[id(l,r)]=y;return;}int mid=(l+r)/2;if(x<=mid)change(l,mid,x,y);else change(mid+1,r,x,y);seg[id(l,r)]=merge(seg[id(l,mid)],seg[id(mid+1,r)]);}
T query(int L,int R,int l,int r){if(l<=L&&R<=r)return seg[id(L,R)];int mid=(L+R)/2;if(l<=mid&&r>mid)return merge(query(L,mid,l,r),query(mid+1,R,l,r));if(l<=mid)return query(L,mid,l,r);return query(mid+1,R,l,r);}
public:
vector<T> seg;int siz;
segment(int n){siz=n;seg.resize(2*n+4);}
void change(int x,T y){change(1,siz,x,y);}
T query(int l,int r){return query(1,siz,l,r);}
};
const int MOD=998244353;
int n,a[2001],b[2001],dp[2001][2001],answer;
void Delta() {
cin >> n;vector<int> Q;
for(int i=1;i<=n;++i) {
cin >> a[i];a[i]-=69;
Q.push_back(a[i]);
}
Q.push_back(-2147483647);sort(Q.begin(),Q.end());
Q.resize(unique(Q.begin(),Q.end())-Q.begin());
for(int i=1;i<=n;++i) {
dp[i][1]=0;
b[i]=lower_bound(Q.begin(),Q.end(),a[i])-Q.begin();
}
for(int x=2;x<=n;++x) {
segment<node> P(n);
for(int i=1;i<=n;++i) dp[i][x]=2147483647;
for(auto &i:P.seg) i={2147483647,2147483647};
for(int i=1;i<=n;++i) {
dp[i][x]=min(dp[i][x],P.query(b[i],n).mndp);
dp[i][x]=min((long long)dp[i][x],(long long)P.query(1,b[i]).mndpa+a[i]);
P.change(b[i],{dp[i][x-1],dp[i][x-1]-a[i]});
}
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(dp[i][j]<=a[i])
answer=max(answer,j);
cout << answer << endl;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
Delta();
}
anyone explain me C can't understand editorial
The approach is: To start from the last and greedily choose whether the final string (i.e. once the flips are done and all strings are the same) has a 0 or a 1 in this position. Now, say at position i from the beginning, if the count of 0 is less than the count 1 then we flip the strings that have 0 in this position. We also keep a note of all the strings we have flipped and how many times so that when we move positions lesser than i we know whether it is the same bit as given or whether it has been flipped.
When the count of 0 and 1 is the same it does not matter which one we choose to have in the final string as it does not affect the subsequent count of 0 or 1. (i.e what we choose in position i, in this case, results in the same count for 0 and 1 in i-1 position).
if count of 0 is less than count of 1 at position i then wont we flip strings with 0 at i?
You are right. Sorry, it was a typo. My bad. Will edit it.
Can someone prove that the minimum weakness in $$$D$$$ will always be $$$\sqrt{n-1}$$$? I was able to guess this from dry running up to $$$n=5$$$ but wasn't sure about it.
I had a very simple dp solution for C
please explain your dp state and transitions also. Will be helpful
$$$dp[i][0]$$$ stores the min cost required to make every string equal uptill index $$$i$$$ with the character of $$$i^{th}$$$ index being 0.
For the $$$(i+1)^{th}$$$ index we have 4 cases, I'll explain one of them, let's say the character chosen at the last index was 0 and for the current index you want to choose 1, then
$$$dp[i+1][1] = dp[i][0] + 2 \times $$$(no of strings in which last character was 0 and current character is 0),
because you want to retain the previous character and change the current character, which would require 2 flippings for each such string.
thanks