Greetings everyone! We hope you enjoyed the problems. Here is the editorial of the contest. We will be adding editorial of remaining problem soon. Sorry for delay!.
A — Construct a subsequence
Check if $$$i$$$-th bit of the cost can be $$$0$$$?
Let's say the cost $$$2^{30} - 1$$$, we will try to set the $$$i$$$-th bit of the cost to $$$0$$$ while iterating $$$i$$$ from $$$29$$$ to $$$0$$$.
We are iterating in reverse because if we can construct a subsequence with cost that has $$$i$$$-th bit $$$0$$$, then even if all bits $$$j$$$, $$$j < i$$$ are $$$1$$$ it would still have less cost.
You can pick an index $$$i$$$ in your subsequence if $$$a_i$$$ is a sub-mask of the cost you are currently constructing.
Now greedily club indices that have distance $$$\leq k$$$ between them. Note that if you can make a subsequence we length $$$l'$$$, $$$(l' \gt l)$$$, you also make a subsequence with length $$$l$$$ (simply delete starting or the ending indexes of the subsequence).
If the length of any of these group of indices is greater than or equal $$$l$$$, you can set the corresponding bit to $$$0$$$ in cost.
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
int n, k, l;
cin >> n >> k >> l;
vector<int> a(n);
for(auto &x: a) cin >> x;
int mask = (1ll << 32) - 1;
vector<vector<int>> subsequences;
vector<int> dummy;
for(int i = 0; i < n; i++) dummy.push_back(i);
subsequences.push_back(dummy);
for(int bit = 31; bit >= 0; bit--) {
mask ^= (1ll << bit);
vector<vector<int>> new_subsequences;
for(auto &x: subsequences) {
vector<int> current;
for(int i = 0; i < x.size(); i++) {
if((a[x[i]] | mask) == mask) {
current.push_back(x[i]);
}
}
if(current.size() == 0) continue;
vector<int> carry;
carry.push_back(current[0]);
int lst = current[0];
for(int i = 1; i < current.size(); i++) {
if(current[i] - lst > k) {
if(carry.size() >= l)
new_subsequences.push_back(carry);
carry.clear();
}
carry.push_back(current[i]);
lst = current[i];
}
if(carry.size() >= l) new_subsequences.push_back(carry);
}
if(new_subsequences.size()) {
swap(subsequences, new_subsequences);
}
else {
mask ^= (1ll << bit);
}
}
int ans = a[subsequences[0][0]];
for(int i = 1; i < subsequences[0].size(); i++) {
ans |= a[subsequences[0][i]];
assert(subsequences[0][i] - subsequences[0][i - 1] <= k);
}
assert(ans == mask);
assert(subsequences[0].size() >= l);
cout << mask << "\n";
}
int32_t main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int t = 1;
cin>>t;
while(t--) solve();
}
C — is this segment tree?
Is there any benefit of taking a subarray which contains more than 2 occurence of val?
Let us prove that the answer is an subarray which contains only two occurence of val, where the first and last element are val.
Firstly, any subarray which does not contain val as first/last element is not optimal as this subarray can be trimmed to such a state which improves the ratio.
Let $$$a$$$ be the smallest distance between any two occurrence of val in the array. The answer for this subarray is 2/(a+2).
It is easy to see that adding any occurence at a distance >$$$a$$$ can never give better answer.
Now it is needed to prove that adding more occurence at distance $$$a$$$ also does not improve the answer.
Let us add y occurence of val at a distance $$$a$$$.
The new ratio is (2 + y ) / (y*a + y + 2).
If this ratio is better, (2 + y ) / (y*a + y + 2 + a) > 2 / a+2
2*a + y*a + 2*y + 4 > 2*y*a + 2y + 4 + 2*a
0 > y*a
0 > y
By contradiction, it is shown that we must not add any more occurrences.
//Author Solution
#include<bits/stdc++.h>
using namespace std;
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin>>n;
map<int,set<int>>m;
map<int,set<pair<int,int>>>track;
int a[n+1];
for(int i=0;i<n;i++)
{
int x;
cin>>x;
a[i]=x;
m[x].insert(i);
}
for(auto &it:m)
{
int temp=-1;
for(auto &trav:it.second)
{
if(temp==-1)
temp=trav;
else
{
track[it.first].insert({trav-temp,temp});
temp=trav;
}
}
}
int q;
cin>>q;
while(q--)
{
int check;
cin>>check;
if(check==1)
{
int x;
cin>>x;
if(track[x].empty())
{
cout<<-1<<'\n';
continue;
}
auto it=*track[x].begin();
cout<<it.second<<" "<<it.second+it.first<<endl;
}
else
{
int indx,y;
cin>>indx>>y;
int temp=a[indx];
auto it=m[temp].find(indx);
int left=-1,right=-1;
if(it!=m[temp].begin())
{
auto it1=it;
it1--;
left=(*it1);
track[temp].erase(track[temp].find({((*it)-(*it1)),(*it1)}));
}
auto it1=it;
it1++;
if(it1!=m[temp].end())
{
right=(*it1);
track[temp].erase(track[temp].find({((*it1)-(*it)),(*it)}));
}
if(left!=-1&&right!=-1)
{
track[temp].insert({right-left,left});
}
m[temp].erase(it);
m[y].insert(indx);
it=m[y].find(indx);
left=-1,right=-1;
if(it!=m[y].begin())
{
auto it1=it;
it1--;
track[y].insert({((*it)-(*it1)),(*it1)});
left=(*it1);
}
it1=it;
it1++;
if(it1!=m[y].end())
{
track[y].insert({((*it1)-(*it)),(*it)});
right=(*it1);
}
a[indx]=y;
if(left!=-1&&right!=-1)
{
track[y].erase(track[y].find({right-left,left}));
}
}
}
return 0;
}
//Another solution
#include<bits/stdc++.h>
using namespace std;
vector<int>a;
unordered_map<int,set<int>>m1;
unordered_map<int,multiset<pair<int,pair<int,int>>>>m2;
void query1(int value){
if(m2.count(value)==0){
cout<<-1<<endl;return;
}
cout<<m2[value].begin()->second.first<<' '<<m2[value].begin()->second.second<<endl;
}
void query2(int x,int y){
auto it=m1[a[x]].find(x);auto it1=it,it2=it;
if(it1!=m1[a[x]].begin()){
it1--;
m2[a[x]].erase({*it-*it1,{*it1,*it}});
}
if(it2!=(--m1[a[x]].end())){
it2++;
m2[a[x]].erase({*it2-*it,{*it,*it2}});
}
if(it2!=it&&it1!=it)
{
m2[a[x]].insert({*it2-*it1,{*it1,*it2}});
}
m1[a[x]].erase(it);
if(m1[a[x]].size()==0)m1.erase(a[x]);
if(m2[a[x]].size()==0)m2.erase(a[x]);
a[x]=y;
m1[y].insert(x);
it=m1[y].find(x);it1=it,it2=it;
if(it1!=m1[y].begin()){
it1--;
m2[a[x]].insert({*it-*it1,{*it1,*it}});
}
if(it2!=(--m1[y].end())){
it2++;
m2[a[x]].insert({*it2-*it,{*it,*it2}});
}
if(it2!=it&&it1!=it)
{
m2[a[x]].erase({*it2-*it1,{*it1,*it2}});
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin>>n;
a.resize(n);
for(int &it:a)cin>>it;
for(int i=0;i<n;i++){
m1[a[i]].insert(i);
}
for(auto &it:m1){
multiset<pair<int,pair<int,int>>>&itr=m2[it.first];
vector<int>temp(it.second.begin(),it.second.end());
for(int i=0;i+1<temp.size();i++){
itr.insert({temp[i+1]-temp[i],{temp[i],temp[i+1]}});
}
}
int q;cin>>q;
for(int i=0;i<q;i++){
int type;cin>>type;
if(type==1){
int x;cin>>x;
query1(x);
}else{
int x,y;cin>>x>>y;
query2(x,y);
}
}
}
D — Subarray mysteries
Pbds
Let Array $$$B$$$ store indices of an element x in the array.
For two indices i and j where i < j, if A[i..j] is good, then (j-i+1)/(A[j]-A[i]+1)>=K/1000.
1000*j-A[j]>=1000*i-A[i]+K-1
For each index we can find the number of indices which make a good subarray by using pbds or segment tree.
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define int long long
#define ll __int128
using namespace __gnu_pbds;
using namespace std;
typedef tree<pair<long double,int>, null_type,
less<pair<long double,int>>, rb_tree_tag,
tree_order_statistics_node_update>
Pbds;
const char nl = '\n';
bitset<1000010> iscomp;
int highest[1000010];
void sieve()
{
for (int i = 2; i < 1000010; i++)
{
if (!iscomp[i])
{
highest[i]=i;
for (int j = i * i; j < 1000010; j += i)
{
highest[j]=i;
iscomp[j] = 1;
}
}
}
}
int n,k;
void yes() { cout << "Yes" << endl; }
void no() { cout << "No" << endl; }
void YES() { cout << "YES" << endl; }
void NO() { cout << "NO" << endl; }
void solve(int testcase)
{
cin>>n>>k;
vector<int>a(n);
for(int &it:a)cin>>it;
map<int,vector<int>>m;
for(int i=0;i<n;i++){
m[a[i]].push_back(i);
}
long double K=k;
for(auto &it:m){
cout<<it.first<<' ';
if(it.second.size()==1){
cout<<0<<endl;continue;
}
Pbds s;
s.insert({K-1000-K*it.second[0],0});
int ans=0;
for(int i=1;i<it.second.size();i++){
int p=s.order_of_key({i*1000-K*it.second[i],INT_MAX});
ans+=p;
s.insert({K-1000-K*it.second[i]+i*1000,i});
}
cout<<ans<<' ';
cout<<endl;
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//sieve();
int t = 1;
//cin >> t;
for (int p = 1; p <= t; p++)
{
solve(p);
}
}
E — Travelling Salesman Problem
Try doing something with the lowest common ancestor of $$$i$$$ and $$$i + 1$$$.
Prefix sums on tree?
Since we have to answer the problem offline, let's try to do something similar to difference arrays.
First root the tree on an arbitrary vertex — say $$$1$$$.
Say the lowest common ancestor of $$$i$$$ and $$$i + 1$$$ be $$$LCA$$$. We will add $$$1$$$ to $$$score[parent_i]$$$ and $$$score[i + 1]$$$, and subtract $$$1$$$ from $$$score[LCA]$$$ and $$$score[parent_{LCA}]$$$. A Now if we add up scores going from bottom to top, we will get the number of times each vertex is visited.
Each vertex in the path from $$$parent_i$$$ to $$$LCA$$$ and $$$i + 1$$$ to $$$LCA$$$ will get $$$+1$$$ to the score. Note that the $$$LCA$$$ is considered twice, so we have subtracted $$$1$$$ from $$$score[LCA]$$$. Also to prevent any addition to parents of $$$LCA$$$, we have subtracted $$$score[parent_{LCA}]$$$ as well.
#include<bits/stdc++.h>
using namespace std;
#define int long long
// LCA code source - usaco.guide
int depth[200010];
int up[200010][20];
int score[200010];
vector<int> adj[200010];
void dfs(int v) {
for(int i = 1; i < 20; i++) { up[v][i] = up[up[v][i - 1]][i - 1]; }
for (int x : adj[v]) {
if (x != up[v][0]) {
depth[x] = depth[up[x][0] = v] + 1;
dfs(x);
}
}
}
int jump(int x, int d) {
for(int i = 0; i < 20; i++) {
if ((d >> i) & 1) x = up[x][i];
}
return x;
}
int LCA(int a, int b) {
if (depth[a] < depth[b]) swap(a, b);
a = jump(a, depth[a] - depth[b]);
if (a == b) return a;
for(int i = 19; i >= 0; i--) {
int aT = up[a][i], bT = up[b][i];
if (aT != bT) a = aT, b = bT;
}
return up[a][0];
}
void clear(int n) {
for(int i = 0; i < n; i++) {
score[i] = 0;
depth[i] = 0;
adj[i].clear();
for(int j = 0; j < 20; j++)
up[i][j] = 0;
}
}
int32_t main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int t; cin >> t;
while(t--) {
int n; cin >> n;
clear(n + 5);
for(int i = 0; i < n - 1; i++) {
int a, b; cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(1);
for(int i = 1; i < n; i++) {
int par = LCA(i, i + 1);
score[up[i][0]]++, score[i + 1]++;
score[par]--, score[up[par][0]]--;
}
vector<pair<int,int>> vp;
for(int i = 2; i <= n; i++) {
vp.push_back({-depth[i], i});
}
sort(vp.begin(), vp.end());
for(int i = 0; i < vp.size(); i++) {
score[up[vp[i].second][0]] += score[vp[i].second];
}
score[1]++; // initial stand
for(int i = 1; i <= n; i++) cout << score[i] << " ";
cout << "\n";
}
return 0;
}
H — Group Project
find the groups in which you and your crush are placed .
use ceil
function .
As You want that you and your crush will be in same group , find out Group number for both $$$G_a$$$ = ceil(a/x) (group number where you are placed) , $$$G_b$$$ = ceil(b/x) (group number where your crush is placed) . there are total of n diffrent value of x(group size) which is equiprobable. Hence Probability = P/Q . P = Number of group size's in which $$$G_a == G_b$$$ , Q = n .
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define ppb pop_back
#define MOD 998244353
const int N=1e5;
int binexp(int a, int b) {
int res = 1;
while (b > 0) {
if(b&1)
res = ((res%MOD)*(a%MOD))%MOD;
a = ((a%MOD)*(a%MOD))%MOD;
b >>= 1;
}
return res;
}
void solve(){
int n;
string a,b;
cin >> n >> a >> b;
int an = stoi(a.substr(7,3));
int bn = stoi(b.substr(7,3));
int ans = 0;
for(int i=1;i<=n;i++){
if((an-1)/i == (bn-1)/i){
ans++;
}
}
ans *= binexp(n,MOD-2);
ans %= MOD;
cout << ans << endl;
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("test0.in", "r", stdin);
freopen("test0.out", "w", stdout);
#endif
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}