Author: loud_mouth
Idea: Bignubie
Editorial
Tutorial is loading...
Solution (Loud_mouth)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int last=0;
for(int i=0; i<30; ++i)
{
if(((n>>i)&1) == 1)
{
last=i;
}
}
cout<<(1<<last)-1<<"\n";
}
return 0;
}
Solution (the_nightmare)
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define pb push_back
#define ppb pop_back
#define endl '\n'
#define mii map<ll,ll>
#define msi map<string,ll>
#define mis map<ll, string>
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,a,b) for(ll i=b-1;i>=a;i--)
#define trav(a, x) for(auto& a : x)
#define pii pair<ll,ll>
#define vi vector<ll>
#define vii vector<pair<ll, ll>>
#define vs vector<string>
#define all(a) (a).begin(),(a).end()
#define F first
#define S second
#define sz(x) (ll)x.size()
#define hell 1000000007
#define lbnd lower_bound
#define ubnd upper_bound
#define DEBUG cerr<<"/n>>>I'm Here<<</n"<<endl;
#define display(x) trav(a,x) cout<<a<<" ";cout<<endl;
#define what_is(x) cerr << #x << " is " << x << endl;
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace __gnu_pbds;
using namespace std;
#define PI 3.141592653589793
#define N 200005
void solve()
{
ll n;
cin >> n;
ll cnt=0;
while(n!=0){
cnt++;
n=n/2;
}
cout << (1<<(cnt-1))-1 << endl;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen ("input.txt","r",stdin);
#endif
ll int TEST=1;
cin >> TEST;
//init();
while(TEST--)
{
solve();
}
}
1527B1 - Palindrome Game (easy version)
Author: DenOMINATOR
Idea: shikhar7s
Editorial
Tutorial is loading...
Solution (DenOMINATOR)
#include<bits/stdc++.h>
using namespace std;
void solve(){
int n;
cin >> n;
string s;
cin >> s;
bool is_palindrome=1;
int cnt_0 = 0;
for(int i=0;i<n;i++){
cnt_0 += s[i]=='0';
}
if(cnt_0 == 1){
cout << "BOB\n";
return;
}
if(cnt_0%2){
cout << "ALICE\n";
return;
}
cout << "BOB\n";
return;
}
signed main()
{
int t;
cin >> t;
while(t--){
solve();
}
return 0;
}
Solution (shikhar7s)
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define mp(a,b) make_pair(a,b)
#define vi vector<int>
#define mii map<int,int>
#define mpi map<pair<int,int>,int>
#define vp vector<pair<int,int> >
#define pb(a) push_back(a)
#define fr(i,n) for(i=0;i<n;i++)
#define rep(i,a,n) for(i=a;i<n;i++)
#define F first
#define S second
#define endl "\n"
#define fast std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define mod 1000000007
#define dom 998244353
#define sl(a) (int)a.length()
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define mini 2000000000000000000
#define time_taken 1.0 * clock() / CLOCKS_PER_SEC
//const long double pi = acos(-1);
//mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
//primes for hashing 937, 1013
template<typename T, typename U> static inline void amin(T &x, U y)
{
if (y < x)
x = y;
}
template<typename T, typename U> static inline void amax(T &x, U y)
{
if (x < y)
x = y;
}
void shikhar7s(int cas)
{
int n,i;
cin>>n;
string s;
cin>>s;
int f=1,z=0;
fr(i,n)
{
if(s[i]=='0')
z++;
}
int x=0;
fr(i,n/2)
{
if(s[i]!=s[n-1-i])
{
f=0;
x++;
}
}
if(f)
{
if(z==1||z%2==0)
cout<<"BOB"<<endl;
else
cout<<"ALICE"<<endl;
}
else
{
if(x==1&&z==2)
cout<<"DRAW"<<endl;
else
cout<<"ALICE"<<endl;
}
}
signed main()
{
fast;
//freopen("input.txt", "rt", stdin);
//freopen("output.txt", "wt", stdout);
int t=1;
cin>>t;
int cas=1;
while(cas<=t)
{
//cout<<"Case #"<<cas<<": ";
shikhar7s(cas);
cas++;
}
return 0;
}
1527B2 - Palindrome Game (hard version)
Author: DenOMINATOR
Idea:DenOMINATOR
Editorial
Tutorial is loading...
Solution(Greedy) (DenOMINATOR)
#include<bits/stdc++.h>
using namespace std;
void solve(){
int n;
cin >> n;
string s;
cin >> s;
bool is_palindrome=1;
int cnt_0 = 0, cnt_1 = 0;
for(int i=0;i<n;i++){
cnt_0 += s[i]=='0';
}
for(int i=0;i<n/2;i++){
if(s[i]!=s[n-1-i]) is_palindrome = 0;
if( (s[i]=='1' || s[n-1-i]=='1') && s[i]!=s[n-1-i]){
cnt_1++;
}
}
if(is_palindrome){
if(cnt_0 == 1){
cout << "BOB\n";
return;
}
if(cnt_0%2){
cout << "ALICE\n";
return;
}
cout << "BOB\n";
return;
}
if(cnt_0==2 && cnt_1==1){
cout << "DRAW\n";
return;
}
cout << "ALICE\n";
return;
}
signed main()
{
int t;
cin >> t;
while(t--){
solve();
}
return 0;
}
Solution(DP) (DenOMINATOR)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
double pi = acos(-1);
#define _time_ 1.0 * clock() / CLOCKS_PER_SEC
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) a.begin(),a.end()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int dp[505][505][2][2];
void precompute(){
for(int i=0;i<=500;i++){
for(int j=0;j<=500;j++){
for(int k=0;k<2;k++){
for(int l=1;l>=0;l--){
dp[i][j][k][l] = 1e9;
}
}
}
}
dp[0][0][0][0]=0;
dp[0][0][0][1]=0;
for(int i=0;i<=500;i++){
for(int j=0;j<=500;j++){
for(int k=0;k<2;k++){
for(int l=1;l>=0;l--){
if(l==0 && j>0) dp[i][j][k][l] = min(dp[i][j][k][l],-dp[i][j][k][1]);
if(i>0) dp[i][j][k][l] = min(dp[i][j][k][l],1-dp[i-1][j+1][k][0]);
if(j>0) dp[i][j][k][l] = min(dp[i][j][k][l],1-dp[i][j-1][k][0]);
if(k==1) dp[i][j][k][l] = min(dp[i][j][k][l],1-dp[i][j][0][0]);
}
}
}
}
}
void solve(){
int n;
cin >> n;
string s;
cin >> s;
int cnt00=0,cnt01=0,mid=0;
for(int i=0;i<n/2;i++){
if(s[i]=='0' && s[i]==s[n-i-1]) cnt00++;
if(s[i]!=s[n-i-1]) cnt01++;
}
if(n%2 && s[n/2]=='0') mid=1;
if(dp[cnt00][cnt01][mid][0]<0){
cout << "ALICE";
}else if(dp[cnt00][cnt01][mid][0]>0){
cout << "BOB";
}else{
cout << "DRAW";
}
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#ifdef SIEVE
sieve();
#endif
#ifdef NCR
init();
#endif
precompute();
int t;
cin >> t;
while(t--){
solve();
cout << "\n";
}
return 0;
}
Author: sharabhagrawal25
Idea: rivalq
Editorial
Tutorial is loading...
Solution (sharabhagrawal25)
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin >> t;
while(t--){
int n;
cin >> n;
int a[n];
for (int i = 0 ; i < n; i++){
cin >> a[i];
}
vector <long long> dp(n, 0);
map <long long,long long> value;
long long final_ans = 0;
for (long long i = 0 ; i < n ; i++){
if (i > 0) dp[i] = dp[i - 1];
if (value.count(a[i])){
dp[i] += value[a[i]];
}
value[a[i]] += (i + 1);
final_ans += dp[i];
}
cout << final_ans << endl;
}
}
Solution (mallick630)
t = int(input())
for j in range(t):
n = int(input())
a = list(map(int,input().split()))
value = {}
fa, ca = 0, 0
for i in range(n):
if a[i] in value:
ca += value[a[i]]
else:
value[a[i]]=0
value[a[i]] += i+1
fa += ca
print(fa)
Author: mallick630
Idea: CoderAnshu
Editorial
Tutorial is loading...
Solution (shikhar7s)
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define mp(a,b) make_pair(a,b)
#define vi vector<int>
#define mii map<int,int>
#define mpi map<pair<int,int>,int>
#define vp vector<pair<int,int> >
#define pb(a) push_back(a)
#define fr(i,n) for(i=0;i<n;i++)
#define rep(i,a,n) for(i=a;i<n;i++)
#define F first
#define S second
#define endl "\n"
#define Endl "\n"
#define fast std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define mod 1000000007
#define dom 998244353
#define sl(a) (int)a.length()
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define mini 2000000000000000000
#define time_taken 1.0 * clock() / CLOCKS_PER_SEC
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//const long double pi = acos(-1);
//mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
//primes for hashing 937, 1013
template<typename T, typename U> static inline void amin(T &x, U y)
{
if (y < x)
x = y;
}
template<typename T, typename U> static inline void amax(T &x, U y)
{
if (x < y)
x = y;
}
vector<int> adj[200005];
int vis[200005],c[200005],t;
pii p[200005];
void dfs(int x)
{
vis[x]=1;
c[x]=1;
int i;
p[x]=mp(t,t);
t++;
fr(i,sz(adj[x]))
{
if(!vis[adj[x][i]])
{
dfs(adj[x][i]);
c[x]+=c[adj[x][i]];
p[x].S=p[adj[x][i]].S;
}
}
}
void shikhar7s(int cas)
{
int n,i;
cin>>n;
t=0;
fr(i,n)
{
vis[i]=0;
adj[i].clear();
}
int x,y;
fr(i,n-1)
{
cin>>x>>y;
adj[x].pb(y);
adj[y].pb(x);
}
dfs(0);
int ans=0;
fr(i,sz(adj[0]))
{
int x=c[adj[0][i]];
x=(x*(x-1))/2;
ans+=x;
}
cout<<ans<<" ";
int s=0,ss=0,got=1;
y=-1;
fr(i,sz(adj[0]))
{
int x=c[adj[0][i]];
if(p[adj[0][i]].F<=p[1].F&&p[adj[0][i]].S>=p[1].S)
{
y=adj[0][i];
x-=c[1];
}
if(adj[0][i]!=y)
got+=x;
s+=x;
x*=x;
ss+=x;
}
ans=(s*s-ss)/2;
ans+=s;
cout<<ans<<" ";
i=2;
int l=0,r=1,j,b=0;
while(i<n)
{
if((p[i].F<=p[l].F&&p[i].S>=p[l].S)||(p[i].F<=p[r].F&&p[i].S>=p[r].S))
{
cout<<0<<" ";
i++;
continue;
}
if(!l)
{
int f=2;
ss=c[r];
if(p[r].F<=p[i].F&&p[r].S>=p[i].S)
{
f=1;
ss-=c[i];
}
if(!(p[y].F<=p[i].F&&p[y].S>=p[i].S))
{
ans=1;
fr(j,sz(adj[0]))
{
int x=adj[0][j];
if(x==y)
continue;
int su=c[x];
if(p[x].F<=p[i].F&&p[x].S>=p[i].S)
{
f=0;
su-=c[i];
}
ans+=su;
}
}
else
ans=got;
ans*=ss;
cout<<ans<<" ";
if(!f)
l=i;
else if(f==1)
r=i;
else
{
i++;
b=1;
break;
}
}
else
{
int f=2;
s=c[l];
ss=c[r];
if(p[l].F<=p[i].F&&p[l].S>=p[i].S)
{
f=0;
s-=c[i];
}
if(p[r].F<=p[i].F&&p[r].S>=p[i].S)
{
f=1;
ss-=c[i];
}
ans=s*ss;
cout<<ans<<" ";
if(!f)
l=i;
else if(f==1)
r=i;
else
{
i++;
b=1;
break;
}
}
i++;
}
if(!b)
cout<<1<<" ";
else
{
while(i<=n)
{
cout<<0<<" ";
i++;
}
}
cout<<endl;
}
signed main()
{
fast;
//freopen("output.txt", "rt", stdin);
//freopen("output.txt", "wt", stdout);
int t=1;
cin>>t;
int cas=1;
while(cas<=t)
{
//cout<<"Case #"<<cas<<": ";
shikhar7s(cas);
cas++;
}
return 0;
}
Solution (the_nightmare)
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define pb push_back
#define ppb pop_back
#define endl '\n'
#define mii map<ll,ll>
#define msi map<string,ll>
#define mis map<ll, string>
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,a,b) for(ll i=b-1;i>=a;i--)
#define trav(a, x) for(auto& a : x)
#define pii pair<ll,ll>
#define vi vector<ll>
#define vii vector<pair<ll, ll>>
#define vs vector<string>
#define all(a) (a).begin(),(a).end()
#define F first
#define S second
#define sz(x) (ll)x.size()
#define hell 1000000007
#define lbnd lower_bound
#define ubnd upper_bound
#define DEBUG cerr<<"/n>>>I'm Here<<</n"<<endl;
#define display(x) trav(a,x) cout<<a<<" ";cout<<endl;
#define what_is(x) cerr << #x << " is " << x << endl;
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace __gnu_pbds;
using namespace std;
#define PI 3.141592653589793
#define N 200005
ll add(ll x,ll y){return (x+y)%hell;}
ll mul(ll x,ll y){return (x*y)%hell;}
vector <ll> adj[N];
ll subtree[N];
ll min1[N];
ll ans[N];
ll vis[N];
ll le;
int v;int u;
ll n;
int prevv;int prevu;
void init(){
rep(i,0,n){
adj[i].clear();
subtree[i]=0;
min1[i]=n;
ans[i]=0;
vis[i]=0;
}
le=n*(n-1)/2;
v=0;u=0;
prevv=-1;
prevu=-1;
}
void dfs(int v,int prev=-1){
subtree[v]=1;
min1[v]=v;
for (auto it: adj[v]){
if (it==prev) continue;
dfs(it,v);
subtree[v]+=subtree[it];
min1[v]=min(min1[v],min1[it]);
}
}
void find(int val){
//cout << v << " " << u << " " << prevv << " " << prevu << " " << val << endl;
if (v==val or u==val){
ll a,b;
if (subtree[prevv]>subtree[v] or prevv==-1) a=subtree[v];
else a=n-subtree[prevv];
if (subtree[prevu]>subtree[u] or prevu==-1) b=subtree[u];
else b=n-subtree[prevu];
ans[val]=le-a*b;
//cout << a << " " << b << endl;
le=a*b;
return;
}
for (auto it: adj[v]){
if (it==prevv) continue;
if (min1[it]==val){
if (v==u) prevu=it;
prevv=v;
v=it;
vis[it]=1;
find(val);
return;
}
}
for (auto it: adj[u]){
if (it==prevu) continue;
if (min1[it]==val){
prevu=u;
u=it;
vis[it]=1;
find(val);
return;
}
}
ans[val]=le;
le=0;
}
void solve()
{
cin >> n;
init();
rep(i,0,n-1){
int x,y;
cin >> x >> y;
adj[x].pb(y);
adj[y].pb(x);
}
dfs(0);
//cout << le << endl;
for (auto it: adj[0]) {ans[0]+=(subtree[it]*(subtree[it]-1))/2;}
//cout << endl;
//cout << ans[0] << endl;
le-=ans[0];
rep(i,1,n){
if (vis[i]==1 or le==0) ans[i]=0;
else find(i);
}
ans[n]=le;
rep(i,0,n+1) cout << ans[i] << " ";
cout << endl;
return;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen ("input.txt","r",stdin);
#endif
ll int TEST=1;
cin >> TEST;
while(TEST--)
{
solve();
}
}
Editorial
Tutorial is loading...
Solution (rivalq)
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define ll long long
//#define int long long
#define pb push_back
#define all(v) v.begin(),v.end()
#define endl "\n"
#define x first
#define y second
#define gcd(a,b) __gcd(a,b)
#define mem1(a) memset(a,-1,sizeof(a))
#define mem0(a) memset(a,0,sizeof(a))
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define hell 1000000007
#define elasped_time 1.0 * clock() / CLOCKS_PER_SEC
template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;}
template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;}
const int N = 5e4+5;
struct node{
int a=0;
node (int val=0){
a=val;
}
void merge(node &n1,node &n2){
this->a=min(n1.a,n2.a);
}
};
struct update{
int val=0;
update(int t=0){
val=t;
}
void combine(update &par,int tl,int tr){
val+=par.val;
}
void apply(node &node){
node.a+=val;
val=0;
}
};
template<typename node,typename update>
struct segtree{
node t[4*N];
bool lazy[4*N];
update zaker[4*N];
int tl[4*N];
int tr[4*N];
node nul;
inline void pushdown(int v){
if(lazy[v]){
apply(zaker[v],v);
lazy[v]=0;
zaker[v].apply(t[v]);
}
}
inline void apply(update &u,int v){
if(tl[v]!=tr[v]){
lazy[2*v]=lazy[2*v+1]=1;
zaker[2*v].combine(u,tl[2*v],tr[2*v]);
zaker[2*v+1].combine(u,tl[2*v+1],tr[2*v+1]);
}
}
void build(int v,int start,int end,int arr[]){
tl[v]=start;
tr[v]=end;
lazy[v]=0;
zaker[v].val = 0;
if(start==end){
t[v].a=arr[start];
}
else{
int m=(start+end)/2;
build(2*v,start,m,arr);
build(2*v+1,m+1,end,arr);
t[v].merge(t[2*v],t[2*v+1]);
}
}
void zeno(int v,int l,int r,update val){
pushdown(v);
if(tr[v]<l || tl[v]>r)return;
if(l<=tl[v] && tr[v]<=r){
t[v].a+=val.val;
apply(val,v);
return;
}
zeno(2*v,l,r,val);
zeno(2*v+1,l,r,val);
t[v].merge(t[2*v],t[2*v+1]);
}
node query(int v,int l,int r){
if(tr[v]<l || tl[v]>r)return node(hell);
pushdown(v);
if(l<=tl[v] && tr[v]<=r){
return t[v];
}
node a=query(2*v,l,r);
node b=query(2*v+1,l,r);
node ans;
ans.merge(a,b);
return ans;
}
public:
node query(int l,int r){
return query(1,l,r);
}
void upd(int l,int r,update val){
return zeno(1,l,r,val);
}
};
segtree<node,update>seg;
int dp[101][N];
int solve(){
int n,k; cin >> n >> k;
vector<int>a(n+1);
rep(i,1,n+1){
cin >> a[i];
}
for(int i = 0; i <= n; i++){
for(int j = 0; j <= k; j++){
dp[j][i] = hell;
}
}
dp[0][0] = 0;
seg.build(1,0,n,dp[0]);
for(int j = 1; j <= k; j++){
vector<int>last(n+1);
dp[j][0] = 0;
for(int i = 1; i <= n; i++){
if(last[a[i]] == 0){
last[a[i]] = i;
}
else{
seg.upd(0,last[a[i]]-1,i-last[a[i]]);
last[a[i]] = i;
}
dp[j][i] = seg.query(0,i-1).a;
}
seg.build(1,0,n,dp[j]);
}
cout << dp[k][n] << endl;
//cout << elasped_time << endl;
return 0;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("test.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#ifdef SIEVE
sieve();
#endif
#ifdef NCR
init();
#endif
int t=1;//cin>>t;
while(t--){
solve();
}
return 0;
}
Solution (the_nightmare)
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define pb push_back
#define ppb pop_back
#define endl '\n'
#define mii map<ll,ll>
#define msi map<string,ll>
#define mis map<ll, string>
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,a,b) for(ll i=b-1;i>=a;i--)
#define trav(a, x) for(auto& a : x)
#define pii pair<ll,ll>
#define vi vector<ll>
#define vii vector<pair<ll, ll>>
#define vs vector<string>
#define all(a) (a).begin(),(a).end()
#define F first
#define S second
#define sz(x) (ll)x.size()
#define hell 1000000007
#define lbnd lower_bound
#define ubnd upper_bound
#define DEBUG cerr<<"/n>>>I'm Here<<</n"<<endl;
#define display(x) trav(a,x) cout<<a<<" ";cout<<endl;
#define what_is(x) cerr << #x << " is " << x << endl;
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace __gnu_pbds;
using namespace std;
#define PI 3.141592653589793
#define MAXN 35005
int tree1[4*MAXN];
int lazy[4*MAXN];
int s[MAXN];
void build(int node, int start, int end)
{
lazy[node]=0;
if(start == end)
{
// Leaf node will have a single element
tree1[node] = s[start];
//cout << tree1[node] << " ";
}
else
{
int mid = (start + end) / 2;
// Recurse on the left child
build(2*node, start, mid);
// Recurse on the right child
build(2*node+1, mid+1, end);
// Internal node will have the sum of both of its children
tree1[node] = min(tree1[2*node],tree1[2*node+1]);
}
}
void updateRange(int node, int start, int end, int l, int r, int val)
{
if (l>r) return;
if(lazy[node] != 0)
{
// This node needs to be updated
tree1[node] = tree1[node]+lazy[node]; // Update it
if(start != end)
{
lazy[node*2] += lazy[node]; // Mark child as lazy
lazy[node*2+1] += lazy[node]; // Mark child as lazy
}
lazy[node] = 0; // Reset it
}
if(start > end or start > r or end < l) // Current segment is not within range [l, r]
return;
if(start >= l and end <= r)
{
// Segment is fully within range
tree1[node] = tree1[node]+val;
if(start != end)
{
// Not leaf node
lazy[node*2] += val;
lazy[node*2+1] += val;
}
return;
}
int mid = (start + end) / 2;
updateRange(node*2, start, mid, l, r, val); // Updating left child
updateRange(node*2 + 1, mid + 1, end, l, r, val); // Updating right child
tree1[node] = min(tree1[node*2],tree1[node*2+1]); // Updating root with max value
}
ll queryRange(int node, int start, int end, int l, int r)
{
if(start > end or start > r or end < l)
return hell; // Out of range
if(lazy[node] != 0)
{
// This node needs to be updated
tree1[node] = tree1[node]+lazy[node]; // Update it
if(start != end)
{
lazy[node*2] += lazy[node]; // Mark child as lazy
lazy[node*2+1] += lazy[node]; // Mark child as lazy
}
lazy[node] = 0; // Reset it
}
if(start >= l and end <= r) // Current segment is totally within range [l, r]
return tree1[node];
int mid = (start + end) / 2;
ll p1 = queryRange(node*2, start, mid, l, r); // Query left child
ll p2 = queryRange(node*2 + 1, mid + 1, end, l, r); // Query right child
return min(p1,p2);
}
void solve()
{
ll n,k;
cin >> n >> k;
int a[n];
rep(i,0,n) cin >> a[i];
int lastoc[n];
map <int,int> m1;
rep(i,0,n){
if (m1.find(a[i])==m1.end()) lastoc[i]=-1;
else lastoc[i]=m1[a[i]];
m1[a[i]]=i;
}
int dp[n][k+1];
dp[0][1]=0;
rep(i,1,n){
dp[i][1]=dp[i-1][1];
if (lastoc[i]!=-1) dp[i][1]+=i-lastoc[i];
}
rep(i,2,k+1){
rep(j,0,n) s[j]=dp[j][i-1];
build(1,0,n-1);
rep(j,0,i-1) dp[j][i]=hell;
dp[i-1][i]=0;
rep(j,i,n)
{
int lastj=lastoc[j];
if (lastj>0 and (i-2)<(lastj)) {
updateRange(1,0,n-1,i-2,lastj-1,j-lastj);
}
dp[j][i] = queryRange(1,0,n-1,i-2,j-1);
}
}
cout << dp[n-1][k] << endl;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen ("input.txt","r",stdin);
#endif
ll int TEST=1;
//cin >> TEST;
//init();
while(TEST--)
{
solve();
}
}
}
contest was the_nightmare
haha, nice one XD
nightmare round
How to solve E using divide and conquer DP? (and especially how to maintain the cost around?)
link here is my code for divide and conquer technique
i took the idea from the code given below and understood it link
basically what we are doing here is we are maintaining a persistent segment tree on every ith index which will provide us with the information that if we consider a segment of [i,j] then what will be its cost. The basic idea here is to use segment tree with range updates and point query.You could see from my code how to update ranges its pretty straightforward.
now that we can find out the cost of any segment in log(n)complexity all we have to do is calculate the dp which can be calculated with the help of divide and conquer the only hard part of this method was the persistent segment tree part which was difficult to understand and actually think by yourself(atleast for me it was very new idea)
In problem B1, when all the elements of the string is 1, then how Bob wins?
It is given in the input section that string $$$s$$$ contains at least one $$$0$$$
Thanks bro!
But for this, why Draw is not the correct answer?
Yes, technically it should be DRAW but to avoid confusion we omitted that case
Now I am clear. Thanks
i have implemented dp for B2, but it's giving me incorrect output, pls help me find the bug
I managed to solve only 1 problem, but i love all the problem upon upsolving. Indian contest are on another level.
Bro will u please explain the first problem I am a newbie:( and not able to understand it
if string is 1011 then your solution fails.
orz
Does someone know of any problem similar to C?
what is the time complexity in B2 dp approach. 1.is it O(n^2) for one test case as it depends on no of 00 pairs and no of 01 pairs? 2.also if n^2 per test case how it passes the judge in 1 sec as n^2*t=1e9 ?
We precompute the dp and use it to answer all test cases
understood thank you.
Dp is pre-computed not run for each test case
thank you.got it
but i think it is simple implementation problem with O(n) time complexity
ya,but i wanted to try dp approach and got doubt that as strings are different we may need to compute eveytime. but understood that structure of string wont matter as we only need 00 and 01 pairs.therefore we can precompute for 501,501 and answer queries directly after getting 00 and 01 pairs from given string.
Alternative solution to A:
Keep doing $$$n=n$$$ & $$$(n-1)$$$ while $$$n$$$ & $$$(n-1)>0$$$. Print $$$n-1$$$.
Интересно! Вы очень смелы, чтобы сделать что-то столь суровое.
I think this will TLE in python
It does not. PyPy 3 submission: 116877296
Yes, you can do that too, but it would take too much time and result in TLE
The complexity is logn for this so it won't TLE. At each iteration, you're setting at least 1 set bit to 0.
Or you could just take the log base 2, and return 2^(this value)-1. O(1) approach.
Hey! I am not able to understand why I am getting TLE for this solution :(
This is my submission : 116759121
as limit of n was 10^9 no of operation for this limit of n is around 1/2*(10^9); which is will take higher time than Time limit given.
In A, 2^msb can also be calculated using log
int msb = (int)(Math.log(n)/Math.log(2));
ok when the number of zeros are even for example
isn't this optimal here every 4 changes means DRAW and extra 1,2,3 means BOB wins
And when zeros are odd:
Alice will change s[n/2] from '0' to '1' and play with the same strategy as Bob did in the above case. This way Bob will spend 1 dollar more than Alice resulting in Alice's win.
in this case every 2 means DRAW and its repeating pattern of pay1 as
AB BA AB BA
then if cnt_of_0 is odd and cnt_of_0/2 is odd we will have 1 zero extra which will be paid by B means ALICE wins.but if cnt_of_0/2 is even we will have 1 zero extra which will be paid by A means BOB wins.
PLEASEEEEE HELPPPPPPP!!
UPD:
Understood!!How to solve this.
Thanks everyoneIf no of 0s is 4 (even)
0000
Alice spends 0100
Bob spends 0110
Alice spends 1110
Bob reverses 0111
Alice spends 1111
Bob wins
If no of 0s is 5 (odd)
00000
Alice spends 00100
Bob spends 00101
Alice spends 10101
Bob spends 11101
Alice reverses 10111
Bob spends 11111
Alice wins
Hope it helps !
0000
0001
Alice +11000
Bob +01001
Alice +11101
Bob +11011
Alice +01111
Bob +1DRAW!
yes, this is a possibility, but the question states that both of them make the best move possible, if bob flips then it is a draw, if he doesn't then he wins
Alice has no such option available to her
Actually, for example $$$000000$$$ game goes-
$$$A$$$ pay $$$1$$$ $$$100000$$$
$$$B$$$ pay $$$1$$$ $$$100001$$$
$$$A$$$ pay $$$1$$$ $$$100101$$$
$$$B$$$ pay $$$1$$$ $$$101101$$$
$$$A$$$ pay $$$1$$$ $$$111101$$$
$$$B$$$ reverse $$$101111$$$
$$$A$$$ pay $$$1$$$ $$$111111$$$
$$$B$$$ wins
Now, analyse $$$010101010$$$
example 0 0 0 0 0 0
A pay1 1 0 0 0 0 0
B pay1 1 0 0 0 0 1
A pay1 1 1 0 0 0 1
B pay1 1 1 0 0 1 1
A pay1 1 1 1 0 1 1
B reverse 1 1 0 1 1 1
A pay1 1 1 1 1 1 1
This is the optimal strategy discussed in the editorial. In each step except the last one, try to make the string palindrome again and in the last reverse the string. Yours is the same strategy I used during the contest but guess I needed to think more.
In the 2nd step y does "B" pay 1? He can just reverse the string and give it back to "A" right?
After spending about 20-25 minutes I understood the logic of problem C ( yes I'm still a noob), but I was wondering how does one come up with that logic during contests ( I know practice, practice practice) but I suck at dp and I've been trying to improve it, so if anyone has dp sheets that can build my foundation it'll be of great help thanks :), I've been doing classic dp problems like knapsack, longest common subsequence type questions and even started with matrix chain multiplication recently.
The states are easier to come up during contests if you really try to, most probably you just take what the problem asks and derive subtasks as a prefix, eg: Kadane-ish (or multiple prefixes across multiple sequences, eg: LCS), suffix, subarray of the original sequence, eg: matrix chain multiplication. I'm sure after a lot of $$$practice$$$, things would become somewhat more intuitive and reflexive.
okay thanks
Alternative solution to E:
First steps are also coming up with the $$$dp$$$ and writing the brute-force transition formula. Then, by considering $$$last(a_{r + 1})$$$, we can prove the following property:
Therefore, $$$c$$$ satisfies Quadrilateral Inequality, where a divide-and-conquer solution works in $$$O(nk\log n)$$$ time.
Note that calculating $$$c$$$ needs a two pointers trick similar to 868F - Yet Another Minimization Problem.
I am using divide and conquer dp optimization for problem E. can you help me why i am getting TLE code
$$$k$$$ should be enumerated from $$$optr$$$ to $$$optl$$$, not $$$mid$$$ to $$$optl$$$. Otherwise, the parameter optr is unused.
How to prove complexity of two pointers trick?
Anyone please, help me to understand..
For problem B1 help me to figure out the answer for this test case 00100
ALICE — 10100 BOB — 10101 ALICE- 10111 BOB — 11101 (REVERSE) ALICE — 11111
ALICE --> 3 BOB -->1 BOB WINS
Why it is not possible?
ALICE — 10100 BOB — 00101(REVERSE) ALICE- 10101 BOB — 11101 ALICE — 10111(REVERSE) BOB — 11111
ALICE --> 2 BOB -->2 DRAW
Exactly my confusion.
it's not that you can't do that . you can .But you know what , the word optimal is mentioned in the question, means if i got a chance to play then i tried my best to win , so if bob put a 1 in the string instead of reversing he will land in the winning position , instead of a draw. You can't just brute force and say bob or alice win or its a draw. its not mandiatory that if i have a chance to reverse the string then i have to reverse it , so that i will be relived from that 1 dollar penalty, you can't do that .
Yes finally understood, the greedy approach of reversing anytime possible is where I was thinking wrong. Thanks a lot for taking the time to explain.
Yes, definitely this can be the case. But, here every player is trying to win right, so as BOB is second player, he will make moves such that he can win. Here this is surely one of the ways the game can proceed, but not optimal.
Optimal can be- String: 00100 Alice: 01100 Bob: 01110 Alice: 11110 Bob: reverses -> 01111 Alice: 11111
So, finally Bob spends 1 whereas Alice spends 3. It's not always optimal to greedily reverse the string whenever possible. Hope it helps. Sorry if I did something wrong.
Yes finally understood, the greedy approach of reversing anytime possible is where I was thinking wrong. Thanks a lot for taking the time to explain.
rivalq the_nightmare I am confused in the editorial for E. Aren't the k mentioned in the dp transitions and the k mentioned in the big oh notation different?
Yes they are different. The one in dp transitions you can regard as a temp variable.
Alice can win this way:
A pays -> 1001
B pays -> 1101
A reverses -> 1011
B pays -> 1111
B = 2 A = 1, so Alice wins. Bob has no other moves.
According to you Alice wins..But according to Jyotirmaya Bob wins...So what is the exact ans...Both of you correct.
Alice wants to win right? So she would do exactly what I stated. Bob has no other move than just to lose. It is not logical to make a move that will allow your oponent to win.
Yes finally understood, the greedy approach of reversing anytime possible is where I was thinking wrong. Thanks a lot for taking the time to explain.
By this explanation, I think we need to think of a solution with the least number of moves overall rather than a greedy approach of reversing whenever possible. Is my interpretation correct?
In Problem B1 in case of string s= 111001 Alice is winning even though no. of zeroes are even
string is already palindrome lol got it nvm
In fact , some users of the Chinese online judge : Luogu said that the difficulty of these problems is not monotonically increasing and they suggested that you should have changed the order of problem B and C. the_nightmare
There is only one additional case to be dealt in B2 if you look at the editorial. That would explain why they considered B2 as easier probably..
and dp is not what most div 2 contestants used.
Basically, we have to put together B1 and B2 due to contest restrictions due to which we are not able to swap B2 and C. But we have provided the scoring according to difficulty B(750+1500) total 2250 and C only 1500.
In problem D's editorial shouldn't it be "We will always break before or on reaching root" instead of "Note that we will always break at the root as it is marked visited in the initial step."
The term "Contiguous Subarray" is much more quicker to grasp than "Subsegment".
Hope future authors see this :) Nice Contest btw
but you know what you got something to learn.
I mixed subsegment with subsquence, and it wasted me lots of time to solve this problem in a wrong way
Could someone please write a simpler edit for Problem-C, I have gone over it a lot of times but am still confused as to why the question creator went for:
value[a[i]] += (i + 1);
please help me out with the logic. I understood the task but couldn't implement it that well and now I'm even more confused.
I think
(i+1)
refers to the total number of subarrays ending ati
. Since we are using0
indexing, so+1
for the adjustment.Consider and element
i
. Now if take an element j such thata[i]==a[j]
andj < i
then subarraya[j-i]
will occur as part of all subarray's fromi = 0 to j
i.e j + 1 times. Sovalue[a[i]] += i + 1
Oh now i get it, thank you so much
Happy to help
I was confused over this part. Thanks now,I got it.
Suppose there is an element at an index that comes before i, and value of both indexes is same, then how many times will value at index that came before will pair with value at index i ? The answer is the number of times that former element is present in subsegments that END at index i. Now think how many such subsegments are possible ? (hint- index of former element).
check my solution
Can someone help me with my solution :
My idea:
Maintain a path and its endpoints.
Maintain a 'visited' array which denotes whether or not this node is in current path.
Consider 0 as base case and mark it visited and initialize both the endpoints to 0.
Iterate from 0 to i
In order to find if there can be a path having all nodes [0, i] we just need to check if the endpoints of path having all of [0, i-1] can be extended to i, so move from ith node to its parent till we find a node that is in the path that includes the nodes [0, i-1], that is first visited node.
If this node happens to be one of the endpoints then extend the path and update endpoints else there can be no such path that includes all of [0, i] nodes and we dont need to check this for following i's.
I am unable to figure out why this gives TLE !
https://codeforces.com/contest/1527/submission/116924323
My code is giving wrong answer. Please someone help !!
include<bits/stdc++.h>
using namespace std;
int main(){
}
This is my logic, you can use to improve your code 116814530
please give some another approach for problem D
Nice explanation of problem B2
Can someone give a small test for those codes which fail test case 5 by printing 1 instead of 0 at 1923rd position for problem D? Submission
I got that error by incorrectly calculating in the tree "0 -- 2 -- 1" the number of pairs with mex == 2 (there are 0).
In problem A I am getting
wrong output format Expected integer, but "2.68435e+008" found
What does the pow function in c++ return? In some previous questions also the I got WA because of pow function return type, so can anyone tell
how it works, what it return and what are its constraints
??Probably, pow() doesn't work well with integers- (I was stuck here too) read this.
pow()
returns a double, while the expected output is an integer, hence the WA. Also as anubh4v stated,pow()
(andlog2()
too) can be imprecise at times, leading to incorrect rounding of the number.I will keep that in mind. Thanks
If you are doing competitive coding don't rely on pow function because it is not intended for integer .
The actual formulation that c++ uses is :
a^b=e^(b*log(a)).
This type of floating point calculation is error prone, and is recommended never to use. Built your own code of logarithmic time multiplication or directly copy from internet like gfg.
Some C++'s function on which you can rely (at least I had experience no error ) is:
- sqrt
- log10,log2,log10
How to solve c using DP. Suppopse that TL is 3 sec. I am not getting how to solve it using DP. can it be solved using the same idea as for count palindromic substring.
For problem B1, why should Bob spend $1 to restrict Alice from doing operation 2 ?? He himself can simply perform operation 2 whenever possible and that will force Alice to do operation 1 on next step. By this, DRAW will happen only when no. of 0s is divisible by 4. In all other cases, BOB will win. Can someone explain what's wrong in this concept??
i thought exactly same as you. but we should concern about when the zero is at center.(it meanse the count of zeros is odd)
Can someone explain me how does the dynamic programming solution for B2 works?
From my understanding of the problem when we consider alice we add positively, when we consider bob we add negatively. But how does that happen in code? How does the code distinguish bob from alice? And how does it simulate turns?
In other words: can someone explain me how the simulation of the game occurs during the bottom up transitions of the editorial / given code?
Thanks in advance.
Because dp[i][j][k][l] is the optimal answer for a state where i is the number of 00, j is the number of 01 or 10, and k = 1 denotes if the middle position in case of odd length string is 0 and l = 1 denotes that in the last turn other person reversed the sting thus we can not reverse.
For all the states, we will assume that the current turn is of Alice and to compute the answer for that state, we will add negative of the transition states, which will denote Bob's optimal score.
So each move is assumed to be alice, to simulate bob we just make it negative. On the other hand when it's bob, the negative of a negative is positive, so it's alice. This also mean that the concept of turn doesn't really exist in this case, because in dynamic programming we only care about the previous state's value, but not the actual move of a simulation.
I think I kinda understood, thank you!
In problem C "This is just the sum of prefix sums of indexes of the element having the same value as that of a[i] which has occurred before index i" What does prefix sums of indexes mean here???
We are standing at position
i
, assuming there is avalue
at positionj
( j < i ) that is equal tothe value
ati
, so in all subsegments whichend at i
, the pair(j, i)
will be counted how many times ? It will be the number of subsegments containing bothi
andj
whichend at i
. So how many subsegments are there? The answer isj
, yes, it isj
. It will include subsegments[j, i]
;[j - 1, i]
;[j - 2 , i]
.....[1, i]
. In the explanation, the author isj + 1
because they start at index0
So calculated
the sums of indexes of the element having the same value as that of a[i]
is to calculatedthe numbers of new pairs when we add i
Thnx a lot man!!!! This helped loads!!!
Thanks man!!
I cannot understand Problem D at all! I went through the code of people who solved it, and could understand broadly what they do, but couldn't get the intuition still. Can someone please help !
In the question B2,why can we print "DRAW" when we find that cnt_0==0&&cnt_1==1 instead of cnt_0==0&&cnt_1%2==1 ? And why both of them are right?(Please forgive my poor English QAQ)
can anyone pls tell why i am getting time limit exceeded on test case 7 in problem D MEX TREE i am just doing a dfs traversal once to calculate subtree sizes and then iterating from 1 to n and marking not visited nodes as visited in my current path and calculating answer for each mex value.
my submission link https://codeforces.com/contest/1527/submission/116996030
In Problem D: as mentioned in the editorial that we need to "update the subtree sizes as we move up to parent recursively", we don't need to do this. When (l!=r) we will always choose the other parent. Only when we are calculating MEX1 (the previous l was equal to r) so we have to update the size of 0 subtree only once.
Nice Solution Man!
Yoir solution simplified the question mqnyfolds. Thanks anadii!
Thanx for ur imsights anadiii!!
Good one
Extremely wierd contest ! Please don't do these more ! Bring some good ones ! Problems were not intresting to solve !
I do not know if this approach has been covered for E using divide and conquer dp. To get cost of current interval, maintain global 2 pointers on the array, sum variable and array of deque. Fit the pointer for each query. Amortized complexity over per level of dp should be N*log(N). So with K layers it becomes K*N*log(N).
In problem B1, when all the elements of the string is 0, then how Bob wins?
eg 0000
when all the elements of the string are 0, bob will not always win. for ex,
00000
in the case of
0000
though:in total, alice used $3, bob used $1
thank you so much !
for problem B2 (hard version), the game will only ever end in a draw if the middle number of an odd non-palindromic sequence is a 0 and there is exactly one other 0.
this is because alice will have to fill in the "other 0" for the first turn to keep bob from taking control of the second operation, but the next turn will end the game when bob fills in the center 0 (due to the sequence becoming palindromic), resulting in a draw.
example: 001
every other sequence that does not start as a palindrome will result in alice's win
my solution
for problem A https://codeforces.com/contest/1527/submission/116832364 in this 2nd test case calculate int r=log(8)/log(2) as 2 but i have tried it everywhere it is 3.
i`m idiot.. i finally understood what i miss.
in problem C consider an example 3,1,4,1,5,1,6(1 based indexing)....consider index 2 and 4 both are "1"..so elements on right side of index 4 and on the left side of index 2..... is (7-4+1)*(2) = 8... my confusion is among these 8 segments one possible segment is 3,1,4,1,5,1....but here we counted only for index 2 and 4 which is only for two "1" how it is taking the 3rd 1 which is at index 6.....please someone help...very poooor at this :(
If we are up for some golf coding my solution for A used property that x and x-1 differ in a single bit so the last bit remaining will be MSB
Can somebody explain B2(dp version)? I am not getting how transition is done.
the_nightmare's solution for D will TLE for the following case. https://drive.google.com/file/d/1K-1sb5ls2PP0lKiGQf5dy9BVuqMBvReG/view?usp=sharing
Can some one tell me why this approach won't work for Problem A? n&n-1 will set the last "1" bit to 0. So the number of times I do that will set all bits to 0.
Does anyone know why test case 2 for question A is timing out? 122251733
Because time complexity of your solution is O(n). To solve the problem you need to get O(1)
I'm confused on A. In the notes it says "In the second testcase, the maximum value for which the continuous & operation gives 0 value, is 3. No value greater then 3, say for example 4, will give the & sum 0." If we plug in 4, it still gives 0 and also 5 gives 0, I don't understand why it stops at 3? To my understanding 5&4&3=0 0%2%1 = 0 since it is zero then any number we plug in will automatically be 0 as well.
Problem 1527C - Sequence Pair Weight could have been done greedily (and imo it's easier). Let $$$d(x, y)$$$ denote the number of segments which contain elements at indices $$$x$$$ and $$$y$$$ (indices start from 0 so $$$x,y \in {0, 1, 2, \dots, n-1}$$$). It is easy to see that if $$$y > x$$$ then $$$d(x, y) = (x+1)*(n-y)$$$. This allows obvious $$$O(n^2)$$$ solution, but it can be done faster in $$$O(n)$$$. Let's say we have a vector $$$v$$$ and we are at it's $$$i$$$-th element.
Then, we can calculate the answer as:
which is just
and this can be simplified to:
Which you can easily calculate while iterating through the vector. Code: 124839948
I did not understand why we need to count the prefix indexes in sequence pair weight problem. can someone explain?
I think more short solution for A: https://codeforces.com/contest/1527/submission/127546267
@DenOMINATOR B1 will fail if our string is 1011. In this case alice should win but according to you Bob is winning.
I have a simpler solution for A:
in b1 can anyone explain output for this string 01011010 i am getting draw