104802A - Submission Bait Writer: wuhudsm
We use two pointers to solve this problem.
Set $$$l=1$$$ and $$$r=n$$$ initially.
- If $$$a_l=a_r$$$,
l++,r--;
- If $$$a_l<a_r$$$,split $$$a_r$$$ into $$$a_r-a_l$$$ and $$$a_l$$$,
r--;
- If $$$a_l>a_r$$$,split $$$a_l$$$ into $$$a_r$$$ and $$$a_l-a_r$$$,
l++;
When $$$l \geq r$$$,the process ends.
104802B - Snowy Bus Writer: pavlekn
Let $$$M$$$ be the initial mass of the bus with all passengers: $$$M = w + \sum_{i = 1}^{n}{m_i}$$$. Let $$$F$$$ be the total force of the pushers, initially, $$$F=0$$$.
Imagine getting out the $$$i$$$-th passenger out of the bus, then $$$M$$$ is decreased by $$$m_i$$$, while $$$F$$$ is increased by $$$f_i$$$. Hence, $$$M - F$$$ is decreased by $$$m_i + f_i$$$. Clearly, we want to make $$$F \ge M$$$, i.e. $$$M - F \le 0$$$.
Therefore, that lead us to the greedy approach: let us sort passengers by $$$m_i + f_i$$$ in descending order and start getting the passengers out of the bus, one by one, according to their order, until the bus is able to be moved, i.e. $$$F \ge M$$$.
104802C - Nafis and Strings Writer: BF_OF_Priety
$$$Hint 1$$$ : What's the minimum frequency of the most frequent character of a decimal string?
$$$Hint 2$$$ : What's the minimum size of $$$LCS$$$ between two strings of length $$$K$$$ required to make a string of size $$$19k/10$$$?
We can observe one thing that as there are only $$$\tt{10}$$$ possible different characters in a string of length $$$K$$$ then it's obvious that the frequency of the most frequent character in it is $$$\ge K/10$$$ , let's assume that character is $$$\tt{0}$$$ in the first string that we observe.All we need to solve this problem is finding a $$$LCS$$$ of size atleast $$$K/10$$$ between two strings.So we already have a string where there are $$$K/10$$$ $$$\tt{0}$$$s.Now let's observe any other $$$9$$$ strings where the most frequent characters suppose are : $$$1$$$ $$$2$$$ $$$\dots$$$ $$$9$$$ . Notice that we are assuming that there are no same characters among the first $$$10$$$ observed strings' most frequent characters co-incidentally. If there are duplicates we already have our answer. Assuming there are no duplicates in the first $$$\tt{10}$$$ observed strings, it is guaranteed the most frequent character appearing in the $$$11th$$$ string must have appeared before as there are $$$\tt{10}$$$ possible characters only.Then we have our answer , we will construct our answer by merging two strings with same most frequent character.It's basically the $$$pigeonhole$$$ principle like if we have $$$\tt{10}$$$ types of chocolates in $$$\tt{11}$$$ boxes , there has to be duplicates.So we prove that $$$11$$$ strings are enough to generate an answer , so we always have an answer as we have $$$20$$$ decimal strings
Time complexity of optimal implementation of this problem : $$$O(20 * K)$$$ , although there are $$$O(20^2 * K)$$$ solutions which may also pass which takes advantage of the fact that there has to be a pair of strings which have $$$LCS$$$ of length >= $$$K/10$$$
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
#define pb push_back
#define pf push_front
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int k;
cin>>k;
vector<string> v;
string s;
vector<ll> adj[10];//to store indices of string where a particular character is most frequent
for(int i=1;i<=20;i++){
cin>>s;
v.push_back(s);
}
int l=-1;
int r=-1;
char aa='Z';
for(int i=0;i<=19;i++){
ll m[10]={};//character frequency array
for(auto u : v[i]){
int kk=u-'0';
m[kk]++;
}
ll best=0;
ll yy=-1;
for(char xx='0';xx<='9';xx++){
ll xx1=xx-'0';
if(m[xx1]>best){
best=m[xx1];
ll pal=xx-'0';
yy=pal;
}
}
adj[yy].push_back(i);
if(adj[yy].size()==2){
aa='0';
aa+=yy;
l=adj[yy][0];
r=adj[yy][1];
break;
}
}
deque<ll> v2,v3;//used for storing indices of LCS of two optimal strings
string ans="";
//string merging process starts
ll kk=-1;
for(auto u : v[l]){
kk++;
if(u==aa) v2.pb(kk);
}
v2.pf(-1);
kk=-1;
for(auto u : v[r]){
kk++;
if(u==aa) v3.pb(kk);
}
v3.pf(-1);
for(ll aa1=1;aa1<=k/10;aa1++){
for(ll bb=v2[aa1-1]+1;bb<=v2[aa1]-1;bb++){
ans+=v[l][bb];
}
for(ll bb=v3[aa1-1]+1;bb<=v3[aa1]-1;bb++){
ans+=v[r][bb];
}
ans+=aa;
}
for(ll aa1=v2[k/10]+1;aa1<=(k)-1;aa1++) ans+=v[l][aa1];
for(ll aa1=v3[k/10]+1;aa1<=(k)-1;aa1++) ans+=v[r][aa1];
cout<<ans<<endl;
}
104802D - Rudraksh's Sleepiness Writer: Ashutosh.Singh
First, let's find the minimum number of the stops Rudraksh will make. There are 4 different cases. Let's say the school coordinates are $$$(x, y)$$$.
$$$1)$$$ The manhattan distance of $$$(x,y)$$$ from $$$(0,0)$$$ (means $$$x+y$$$) is itself a prime number. So we can directly jump to the school, making only one-stop.
$$$2)$$$ If the $$$x+y-2$$$ is a prime number so we should first travel distance 2 i.e any of {(1,1),(0,2),(2,0)} as per the school coordinates, and then the next stop will be the school coordinate.
$$$3)$$$ If the $$$x+y$$$ is even, then as per Goldbach Conjecture, it can be written as the sum of two prime numbers. So the stops can be determined based on that prime numbers.
$$$4)$$$ If the $$$x+y$$$ is odd, then we may move to some coordinate whose Manhattan distance is odd and that is prime (for simplicity we can use 3), too. Now this became a similar problem to type $$$3$$$.
For identifying the exact stops, you can iterate over every prime number.
104802E - Anuj's Longest Subarray Writer: Ashutosh.Singh
For each index $$$i$$$, $$$a_i$$$ should be the greater than or equal to the $$$k^{th}$$$ maximum element in the subarray. So, to make the subarray longest, $$$a_i$$$ should be as least as possible therefore,it should be $$$x^{th}$$$ maximum $$$(x \leq k)$$$, where $$$x$$$ should be the maximum possible value.
If $$$a_i$$$ is $$$x^{th}$$$ maximum in the subarray $$$a[l...r]$$$, then there are $$$x-1$$$ elements greater than $$$a_i$$$. Suppose there are $$$p$$$ $$$(0 \leq p \leq k-1)$$$ elements from $$$l$$$ to $$$i-1$$$, that are greater than $$$a_i$$$, then there will be $$$(x-1)-p$$$ elements greater than $$$a_i$$$ in $$$i+1$$$ to $$$r$$$ (all elements are distinct) .As $$$k \leq 10$$$, therfore for every index $$$i$$$, we can find the minimum $$$l$$$ and maximum $$$r$$$ for every $$$p$$$, and find the maximum of $$$(r-l+1)$$$, which will be our answer.
For implementing, we can use set or ordered set (policy-based data structure), and can start inserting the index of elements from $$$n$$$ to $$$1$$$, after every insertion, we can iterate $$$k$$$ indices in the set in both directions — previous the current element's index in set and after the current element's index in set.
See code for detailed implementation.
104802F - Nafis and Mex Writer: BF_OF_Priety
$$$hint 1$$$ : Maximum possible score of a subsequence is $$$n$$$ as in an array of size $$$n$$$ $$$\rm{mex}$$$ can't be greater than $$$n$$$
$$$hint 2$$$ : Calculating number of subsequences where $$$score$$$ is $$$i$$$ for each $$$0 \le i \le n$$$ is enough
First let's calculate for each $$$0 \le i \le n$$$ the number of subsequences where score is $$$i$$$.How to calculate that?Well when is mex of a subsequence a positive integer $$$i$$$?How does the subsequence look like?In that subsequence there can be arbitrary integers greater than $$$i$$$ ,no appearance of $$$i$$$ and every integer from $$$\tt{0}$$$ to $$$i-1$$$ is present in the subsequence each arbitrary number of times.So if $$$f_i$$$ is the value of number of subsequences where $$$mex$$$ is $$$i$$$ , $$$f_i$$$ : $$$ 2^X * (2^{a_0}-1) * (2^{a_1}-1) * (2^{a_2}-1)* \dots * (2^{a_{i-1}}-1)$$$ where $$$X$$$ is count of elements greater than $$$i$$$ and $$$a_j$$$ is count for j in the array.If subsequence count for some $$$i$$$ crosses $$$K$$$ we minimise it to $$$K$$$.In case of $$$0$$$ : $$$f_0$$$ = $$$2^y$$$ where $$$y$$$ is count of elements greater than $$$0$$$. But we subtract $$$\tt{1}$$$ from that count as we are considering $$$non-empty$$$ subsequences only. Now when we pick and arrange $$$K$$$ subsequences it's obvious that we have to pick $$$(k+1)/2$$$ subsequences with $$$minimum$$$ scores and $$$k/2$$$ subsequences with $$$maximum$$$ scores. As the range of possible $$$scores$$$ is very low $$$[0 \dots n]$$$ we just iterate greedily from the beginning of the range to add scores of $$$odd$$$ indices and after that we iterate from the end greedily to subtract the scores of $$$even$$$ indices.
Time complexity of optimal implementation of this solution : $$$O(N)$$$
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll t=1;
cin>>t;
ll m[100002];//subsequence count array
ll m2[100002]={};//frequency array
ll fact[100002];//array for storing values of 2^i
for(int j=1;j<=t;j++){
ll n,k;
cin>>n>>k;
ll i,x;
vector<ll> v;
fact[0]=1;
m2[0]=0;
for(i=1;i<=n;i++){
m2[i]=0;
fact[i]=fact[i-1];
fact[i]*=2;
fact[i]=min(fact[i],k+1);
}
ll sum=0;
for(i=1;i<=n;i++){
cin>>x;
if(x<=n) m2[x]++;
}
sum=n;
ll dal=1;
for(ll i=0;i<=n;i++){
m[i]=dal;
sum-=m2[i];
m[i]*=fact[sum];
if(i==0) m[i]-=1;
m[i]=min(m[i],k);
dal*=(fact[m2[i]]-1);
dal=min(dal,k+1);
}
ll ans=0;
ll jh=(k+1)/2; // odd
ll jk=k/2; // even
for(i=0;i<=n;i++){
ll kk=min(m[i],jh);
ans+=(i*kk);
jh-=kk;
m[i]-=kk;
}
for(i=n;i>=0;i-=1){
ll kk=min(m[i],jk);
ans-=(i*kk);
jk-=kk;
m[i]-=kk;
}
cout<<ans<<endl;
}
}
#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,t,tt;
int main()
{
//freopen("test.in","r",stdin);
scanf("%d",&T);
while(T--)
{
printf("? 1\n");
fflush(stdout);
scanf("%d",&t);
printf("? %d\n",t*2);
fflush(stdout);
scanf("%d",&tt);
printf("! %d\n",t*2-(tt!=t*2));
fflush(stdout);
}
//fclose(stdin);
return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
int main(){
fast;
ll t;
cin>>t;
while(t--){
ll n,m,x,y,k;
cin>>n>>m>>x>>y>>k;
ll a1=(n*m)-(n*y);
ll a2=(n*m)-(m*x);
ll a3=(n*m)-(n*(m-y+1));
ll a4=(n*m)-(m*(n-x+1));
if(k==0) cout<<0<<endl;
else if(k==1) cout<<max({a1,a2,a3,a4})<<endl;
else if(k==2){
ll b1=a1+max((n-x)*y,(x-1)*y);
ll b2=a2+max(x*(y-1),x*(m-y));
ll b3=a3+max((m-y+1)*(x-1),(m-y+1)*(n-x));
ll b4=a4+max((n-x+1)*(m-y),(n-x+1)*(y-1));
ll b5=a1+a3;
ll b6=a2+a4;
cout<<max({b1,b2,b3,b4,b5,b6})<<endl;
}
else if(k==3){
a1=n-x;
a2=x-1;
a3=m-y;
a4=y-1;
cout<<n*m-1-min({a1,a2,a3,a4})<<endl;
}
else cout<<(n*m-1)<<endl;
}
}
#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) {
int n;
cin >> n;
map<int, int> cnt;
vector<pair<int, int>> a;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
cnt[x] += 1;
a.push_back({x, i});
}
sort(a.begin(), a.end(), [&](pair<int, int> x, pair<int, int> y) {
if (x.fi != y.fi) return x.fi < y.fi;
return x.se > y.se;
});
vector<int> fen(n + 1);
auto upd = [&](int x, int val) {
for (; x <= n; x += x & -x) fen[x] += val;
};
auto get = [&](int x) {
int res = 0;
for (; x > 0; x -= x & -x) res += fen[x];
return res;
};
for (int i = 1; i <= n; i++) upd(i, 1);
int lst = 0, cur = 0;
vector<int> ans(n + 1);
for (int p = 0; p < n; p++) {
auto [x, i] = a[p];
if (p == 0) {
cur += (x - 1) * n;
lst = x - 1;
} else if (a[p - 1].fi != x) {
cur += (x - lst - 1) * get(n);
cur += cnt[lst + 1];
lst = x - 1;
}
ans[i] = cur + get(i);
upd(i, -1);
}
for (int i = 1; i <= n; i++) cout << ans[i] << " \n"[i == n];
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, m;
cin >> n >> m;
vector<vector<pair<int, int>>> g(n);
for (int i = 0; i < m; ++i) {
int u, v, c;
cin >> u >> v >> c;
--u; --v; --c;
g[u].push_back({v, c});
}
vector<int> ans(n);
vector<vector<int>> colors(n);
colors[0].push_back(-1);
colors[0].push_back(-1);
vector<int> Q;
Q.push_back(0);
while (!Q.empty()) {
int u = Q.back();
Q.pop_back();
ans[u] = true;
if (colors[u].size() == 2) {
for (auto el : g[u]) {
int v = el.first;
int c = el.second;
if (colors[v].size() == 2) {
continue;
}
if (colors[v].empty()) {
colors[v].push_back(c);
Q.push_back(v);
continue;
}
if (colors[v][0] != c) {
colors[v].push_back(c);
Q.push_back(v);
}
}
} else if (colors[u].size() == 1) {
int cur = colors[u][0];
for (auto el : g[u]) {
int v = el.first;
int c = el.second;
if (c == cur) {
continue;
}
if (colors[v].size() == 2) {
continue;
}
if (colors[v].empty()) {
colors[v].push_back(c);
Q.push_back(v);
continue;
}
if (colors[v][0] != c) {
colors[v].push_back(c);
Q.push_back(v);
}
}
}
}
for (int i = 0; i < n; ++i) {
if (ans[i]) {
cout << i + 1 << " ";
}
}
cout << "\n";
}
int32_t main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
int t;
cin >> t;
for (int _ = 0; _ < t; ++_) {
solve();
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
using pi=pair<int,int>;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while(t>0){
t--;
int n;
cin >> n;
vector<int> a(n);
for(auto &nx : a){cin >> nx;}
vector<int> b(n);
for(auto &nx : b){cin >> nx;}
vector<int> c(n);
for(auto &nx : c){cin >> nx;}
// 0 ... nothing
// 1 ... cc...caa...acc...
// 2 ... cc...caa...a
vector<vector<long long>> dp(n,vector<long long>(3,-8e18));
vector<vector<pi>> pre(n,vector<pi>(3));
dp[0][0]=b[0];
pre[0][0]={-1,1};
dp[0][1]=c[0];
pre[0][1]={-1,2};
for(int i=1;i<n;i++){
// from 0
if(dp[i][0] < dp[i-1][0]+b[i]){
dp[i][0]=dp[i-1][0]+b[i];
pre[i][0]={0,1};
}
if(dp[i][1] < dp[i-1][0]+c[i]){
dp[i][1]=dp[i-1][0]+c[i];
pre[i][1]={0,2};
}
// from 1
if(dp[i][2] < dp[i-1][1]+a[i]){
dp[i][2]=dp[i-1][1]+a[i];
pre[i][2]={1,0};
}
if(dp[i][1] < dp[i-1][1]+b[i]){
dp[i][1]=dp[i-1][1]+b[i];
pre[i][1]={1,1};
}
if(dp[i][1] < dp[i-1][1]+c[i]){
dp[i][1]=dp[i-1][1]+c[i];
pre[i][1]={1,2};
}
// from 2
if(dp[i][2] < dp[i-1][2]+a[i]){
dp[i][2]=dp[i-1][2]+a[i];
pre[i][2]={2,0};
}
if(dp[i][2] < dp[i-1][2]+b[i]){
dp[i][2]=dp[i-1][2]+b[i];
pre[i][2]={2,1};
}
if(dp[i][1] < dp[i-1][2]+c[i]){
dp[i][1]=dp[i-1][2]+c[i];
pre[i][1]={2,2};
}
}
// for(auto &nx : dp){
// for(auto &ny : nx){cout << ny << " ";}
// cout << "\n";
// }
vector<int> pt;
int tg;
if(dp[n-1][0]<dp[n-1][2]){tg=2;}else{tg=0;}
// cout << max(dp[n-1][0],dp[n-1][2]) << "\n";
vector<int> his(n);
for(int i=n-1;i>=0;i--){
his[i]=pre[i][tg].second;
tg=pre[i][tg].first;
}
vector<int> p(n);
int ofs=0;
vector<int> sft;
// for(auto &nx : his){cout << nx << " ";}cout << "\n";
his.push_back(2);
int phs=0;
for(int i=0;i<=n;i++){
if(his[i]==2){
if(phs==2){
int sz=sft.size();
for(int i=0;i<sz;i++){
p[sft[(i+ofs)%sz]]=sft[i];
}
ofs=0;
sft.clear();
}
sft.push_back(i);
ofs++;
phs=1;
}
else if(his[i]==1){p[i]=i;}
else if(his[i]==0){
if(phs==1){phs=2;}
sft.push_back(i);
}
}
long long act=0;
for(int i=0;i<n;i++){
if(p[i]<i){act+=a[i];}
else if(p[i]==i){act+=b[i];}
else{act+=c[i];}
}
// cout << act << "\n";
for(int i=0;i<n;i++){
if(i){cout << " ";}
cout << p[i]+1;
}cout << "\n";
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const long double PI=acosl(-1);
const int MAXN=2e5+2;
pair<long double,long double> xy[MAXN];
vector<pair<long double,bool>> sweep;
int main() {
int t;
cin >> t;
while (t--) {
int n,m;
cin >> n >> m;
long double x,y,ang,rot=2*PI/m,maxDist=0;
for (int i=1;i<=n;i++) {
cin >> x >> y;
ang=atan2l(y,x);
ang-=floorl(ang/rot)*rot;
xy[i]={sqrtl(x*x+y*y),ang};
maxDist=max(maxDist,xy[i].first);
}
long double l=maxDist,r=3*maxDist,mid;
int cnt,cnt2;
while (r-l >= 1e-10) {
cnt=0;cnt2=0;sweep.clear();
mid=(l+r)/2; // bin search on size
for (int i=1;i<=n;i++) {
if (xy[i].first <= mid*cosl(rot/2)) continue;
cnt++;
ang=rot/2-acosl(mid*cosl(rot/2)/xy[i].first);
if (xy[i].second < ang) {
sweep.push_back({rot+xy[i].second-ang,0});
sweep.push_back({ang+xy[i].second,1});
sweep.push_back({0,0});
}
else if (xy[i].second >= rot-ang) {
sweep.push_back({0,0});
sweep.push_back({ang-rot+xy[i].second,1});
sweep.push_back({xy[i].second-ang,0});
}
else {
sweep.push_back({ang+xy[i].second,1});
sweep.push_back({xy[i].second-ang,0});
}
}
sort(sweep.begin(),sweep.end());
for (auto &i : sweep) {
if (i.second) cnt2--;
else cnt2++;
if (cnt2 == cnt) break;
}
if (cnt2 != cnt) l=mid;
else r=mid;
}
cout << setprecision(10) << l << endl;
}
}