2173A-Sleeping Through Classes Idea & Solution: HHH666666
From the statement we can conclude that a class can be slept through $$$\textbf{if and only if}$$$:
- The class itself is not an important class.
- The class is not within $$$k$$$ classes after any important class.
Here's an $$$O(nk)$$$ approach:
We directly simulate the process: for each important class at position $$$i$$$, mark positions $$$i+1, i+2, \dots, \min(i+k, n)$$$ as “must stay awake”. After processing all important classes, count the classes that are neither important nor marked. This $$$O(nk)$$$ solution is acceptable under the constraints.
There's also an $$$O(n)$$$ solution:
For each unimportant class, we only need to focus on the nearest important class before it. Thus we maintain a variable $$$last$$$ storing the index of the most recent important class (or $$$-\infty$$$ if none seen yet), then for each $$$i$$$ from $$$1$$$ to $$$n$$$, if it's an important class we let $$$last = i$$$, otherwise if $$$last + k \lt i$$$, the class is able to be slept through and we add $$$1$$$ to the answer.
#include<bits/stdc++.h>
using namespace std;
int n,k;string s;
void solve(){
cin>>n>>k>>s;
int ans=0;
for(int i=0;i<n;i++){
if(s[i]=='0'){
int ok=1;
for(int j=max(0,(int)i-k);j<i;j++){
if(s[j]=='1'){
ok=0;
break;
}
}
ans+=ok;
}
}
cout<<ans<<endl;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T;cin>>T;
for(;T--;)solve();
return 0;
}
2173B-Niko's Tactical Cards Idea & Solution: HHH666666
Consider a simple greedy algorithm: For each turn, choose the option that gives the higher immediate score. That is, if our current score is $$$k$$$, it becomes $$$\max(k - a_i, b_i - k)$$$ after this turn. Why doesn't the algorithm work?
Try to improve the algorithm in Hint 1.
The greedy approach in Hint 1 fails because it assumes that if we know the maximum possible score after turn $$$i$$$ (denoted by $$$max_i$$$), we can determine $$$max_{i + 1}$$$ from it. However, this assumption is wrong and here is a counterexample:
$$$a = [2, 0], b = [1, 0]$$$
Here $$$max_1 = 1$$$ and $$$max_2 = 2$$$. The greedy approach takes the blue card in turn $$$1$$$. But to reach $$$max_2$$$, we must choose the red card in turn $$$1$$$, which turns our score into $$$-2$$$, and then choose the blue card in turn $$$2$$$. So in this example, $$$max_1$$$ does not give $$$max_2$$$.
We see that $$$max_1$$$ does not help us find $$$max_2$$$ if we choose the blue card in the second turn. The reason is, if we want to maximize our score when choosing a blue card, we want our current score to be as small as possible, so we are looking for the minimum possible score. To maximize $$$b_i - k$$$ we should minimize $$$k$$$.
From this we can see that if we have both the maximum possible score $$$max_{i - 1}$$$ and the minimum possible score $$$min_{i - 1}$$$ after turn $$$i - 1$$$, we can determine $$$max_{i} = \max(max_{i - 1} - a_i, b_i - min_{i - 1})$$$, because these two expressions cover the best outcomes from the red and blue options respectively. Similarly, the new minimum $$$min_{i} = \min(min_{i - 1} - a_i, b_i - max_{i - 1})$$$ comes from either taking the red card from the previous minimum, or the blue card from the previous maximum. And from $$$max_{i}, min_{i}$$$ we can move forward to $$$max_{i + 1}, min_{i + 1}$$$ and so on.
Thus, we start with $$$max_0 = min_0 = 0$$$ and calculate each $$$max_i, min_i$$$ throughout the process using the formulas above. The answer is $$$max_n$$$. This runs in $$$O(n)$$$ time complexity.
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e5 + 10;
int n;
int a[MAXN], b[MAXN];
int main() {
int t; cin >> t;
while (t--) {
int n; cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= n; ++i) cin >> b[i];
ll mx = 0, mn = 0;
for (int i = 1; i <= n; ++i) {
ll new_mx = max(mx - a[i], b[i] - mn);
ll new_mn = min(mn - a[i], b[i] - mx);
mx = new_mx, mn = new_mn;
}
cout << mx << endl;
}
return 0;
}
2173C-Kanade's Perfect Multiples Idea & Solution: paulzrm
Consider the cases $$$n = 1$$$ and $$$n = 2$$$. What do you observe?
Try to determine the "first" element that must belong to $$$B$$$.
Assume the minimum element in $$$A$$$ is $$$x$$$. We now prove that $$$x$$$ must be included in $$$B$$$.
There are no elements smaller than $$$x$$$, which means $$$x$$$ has no proper divisor (other than $$$x$$$ itself) inside $$$A$$$. If we do not put $$$x$$$ into $$$B$$$, then the second rule would be violated.
Thus we can determine the first element of $$$B$$$, and then check whether all its multiples $$$\le k$$$ are contained in $$$A$$$. We mark these multiples as "finished".
Now think greedily. We never need to process elements that are already marked "finished". Each time, we just find the smallest unfinished element in $$$A$$$, check it, and add it to $$$B$$$ if possible.
A loose upper bound on the running time is $$$O\bigl(n d(n) \log n\bigr)$$$, where $$$d(n)$$$ is the divisor function. However, this bound is rarely attained in practice: many operations are skipped thanks to the "finished" marks, so the algorithm runs much faster than this worst-case estimate.
#include<bits/stdc++.h>
using namespace std;
const int mxn=2e5+5;
set<int>s;
map<int,int>u;
int n,a[mxn],k;
void solve(){
s.clear(),u.clear();
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i],s.insert(a[i]),u[a[i]]=1;
vector<int>ans;ans.clear();
while(s.size()){
int t=*s.begin();
ans.push_back(t);
s.erase(s.begin());
for(int cur=t;cur<=k;cur+=t){
if(!u[cur]){
cout<<"-1\n";
return;
}
auto t=s.find(cur);
if(t!=s.end())s.erase(t);
}
}
cout<<ans.size()<<'\n';
for(int i:ans)cout<<i<<' ';cout<<'\n';
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T=1;
cin>>T;
for(;T--;)solve();
return 0;
}
2173D-Taiga's Carry Chains Idea: chen_zida Solution: paulzrm
What is the answer when $$$k \geq 32$$$?
We can use dynamic programming to solve it.
When $$$k \geq 32$$$, we can, at each step, add the smallest $$$t$$$ such that adding $$$2^{t}$$$ to the current $$$n$$$ produces a carry. After $$$k$$$ such steps, $$$n$$$ will become a power of $$$2$$$, and the answer will be $$$\operatorname{popcount}(n) + k - 1$$$.
Now we observe that the total number of carries in the end is $$$\operatorname{popcount}(n) + k - \operatorname{popcount}(n')$$$, where $$$n'$$$ is the final value of $$$n$$$ after all operations. To maximize this quantity, we want to minimize the final $$$\operatorname{popcount}(n')$$$.
To this end, let $$$dp[i][j][c]$$$ denote the optimal value we can obtain after processing the $$$i$$$ least significant bits, having used $$$j$$$ operations in total, where $$$c \in {0,1}$$$ indicates whether there is a carry from the $$$(i-1)$$$-th bit.
For the $$$i$$$-th least significant bit, we have two options: either select this bit (i.e., use one operation on this bit) or not select it.
Let $$$n_i$$$ be the $$$i$$$-th bit of the original $$$n$$$, and let $$$t_i$$$ be the sum at this bit after adding everything in. If we select this bit, then $$$t_i = 1 + c + n_i$$$; otherwise, $$$t_i = c + n_i$$$. From $$$t_i$$$, we can determine whether this bit produces a carry to the next position (the next carry is $$$c' = \lfloor t_i / 2 \rfloor$$$) and whether the $$$i$$$-th bit of $$$n'$$$ is $$$1$$$ or $$$0$$$ (the resulting bit is $$$t_i \bmod 2$$$), which allows us to perform the DP transition.
The time complexity is $$$O((\log_2 n)^2)$$$.
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e9+7;
const int mxb=64,mxk=32;
int dp[mxb+2][mxk+2][2];
void Min(int&x,int y){x=min(x,y);}
void solve(){
int n,k;cin>>n>>k;
int pc=__builtin_popcount(n);
if(n==0){
cout<<max(0ll,k-1)<<'\n';
return;
}
if(k>=32){
cout<<k+pc-1<<'\n';
return;
}
for(int i=0;i<=mxb;i++)for(int j=0;j<=k;j++)dp[i][j][0]=dp[i][j][1]=inf;
dp[0][0][0]=0;
for(int i=0;i<mxb;i++){
int ni=(n>>i)&1ll;
for(int u=0;u<=k;u++)for(int c=0;c<=1;c++){
int cur=dp[i][u][c];
if(cur>=inf)continue;
{
int sum=ni+c,bit=sum&1,nc=sum>>1;
Min(dp[i+1][u][nc],cur+bit);
}
if(u+1<=k){
int sum=ni+1+c,bit=sum&1,nc=sum>>1;
Min(dp[i+1][u+1][nc],cur+bit);
}
}
}
int bst=inf;
for(int u=0;u<=k;u++)for(int c=0;c<=1;c++){
int val=dp[mxb][u][c];
if(val<inf)Min(bst,val+c);
}
int ans=k+pc-bst;
cout<<ans<<'\n';
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T;cin>>T;
for(;T--;)solve();
return 0;
}
2173E-Shiro's Mirror Duel Idea & Solution: paulzrm It's my favourite problem :-)
$$$\lfloor 2.5n\rfloor$$$ is the expected number of operations. We add $$$800$$$ more to ensure that every correct solution would pass.
Think about how to solve it within $$$3n$$$, and how can we improve that.
We split the process into two phases. In the first phase, we make every pair $$$x$$$ and $$$n - x + 1$$$ symmetric; in the second phase, we turn the permutation into $$$1, 2, \dots, n$$$.
Let $$$pos[x]$$$ be the current position of $$$x$$$. We iterate $$$x$$$ from $$$1$$$ to $$$n$$$ in increasing order. If $$$pos[x] + pos[n + 1 - x] \neq n + 1$$$, then $$$x$$$ and $$$n + 1 - x$$$ are not symmetric. In this case, we query $$$(pos[x],\, n - pos[n + 1 - x] + 1)$$$. No matter whether the interactive judge mirrors the array and then swaps or not, this operation will always make $$$x$$$ and $$$n + 1 - x$$$ symmetric. When $$$n$$$ is odd, we should first move $$$(n+1)/2$$$ to the middle.
Next, we move these groups to their correct target positions in order. Suppose the target positions of a pair are $$$i$$$ and $$$n - i + 1$$$, while it is currently at $$$j$$$ and $$$n - j + 1$$$. We query $$$(i, j)$$$; this will surely place either the pair itself or its mirror into the correct positions.
Now we compute the expectation. Let $$$T$$$ be the expected number of queries spent in this second phase for a single group. After we query once, with probability $$$1/2$$$ the group is already correctly placed and we are done after $$$1$$$ query; with probability $$$1/2$$$ it is mirrored into another group’s target positions, in which case we have spent $$$1$$$ query and still expect $$$T$$$ more. Thus $$$T = 1 + \frac{1}{2} \cdot 1 + \frac{1}{2}(T + 1)$$$, which solves to $$$T = 4$$$.
There are $$$n/2$$$ groups, so this phase needs $$$2n$$$ queries in expectation. The first phase uses exactly $$$n/2$$$ queries (one per group), so the total expected number of queries is $$$5n/2$$$.
#include<bits/stdc++.h>
using namespace std;
const int mxn=40004;
int n,a[mxn],pos[mxn];
int mirror(int x){
return n-x+1;
}
pair<int,int>ask(int x,int y){
cout<<"? "<<x<<' '<<y<<endl;
fflush(stdout);
int u,v;cin>>u>>v;
return {u,v};
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
pos[a[i]]=i;
}
if(n%2==1){
int mid=(n+1)/2;
while(pos[mid]!=mid){
auto p=ask(mid,pos[mid]);
int u=p.first,v=p.second;
swap(a[u],a[v]);
pos[a[u]]=u,pos[a[v]]=v;
}
}
for(int i=1;i<=n/2;i++){
int x=pos[i],y=pos[mirror(i)];
if(x+y!=n+1){//not mirror
auto p=ask(x,mirror(y));
int u=p.first,v=p.second;
swap(a[u],a[v]);
pos[a[u]]=u,pos[a[v]]=v;
}
}
for(int i=1;i<=n/2;i++){
while(pos[i]!=i or pos[mirror(i)]!=mirror(i)){
if(pos[i]!=i){
auto p=ask(i,pos[i]);
int u=p.first,v=p.second;
swap(a[u],a[v]);
pos[a[u]]=u,pos[a[v]]=v;
}else{
auto p=ask(mirror(i),pos[mirror(i)]);
int u=p.first,v=p.second;
swap(a[u],a[v]);
pos[a[u]]=u,pos[a[v]]=v;
}
}
}
cout<<"!"<<endl;
fflush(stdout);
}
int main(){
int T=1;
cin>>T;
for(;T--;)solve();
return 0;
}
2173F-Isla's Memory Thresholds Idea & Solution: paulzrm
Consider the process. First note that, because the array $$$a$$$ is non-increasing, the length of each segment whose sum first reaches $$$\ge x$$$ and is then cleared is nondecreasing.
We use the square-root decomposition idea. We fix a threshold $$$B$$$ that separates “short” segments from “long” ones. For segments of length at most $$$B$$$, we handle them using precomputed data; for segments of length greater than $$$B$$$, we use a slower direct procedure.
Since there are at most $$$q$$$ distinct values of $$$x$$$, we can first collect all queries offline and discretize these values. Then we build a table $$$\text{f[i][len]}$$$ that records the rightmost starting position of a segment of length $$$\text{len}$$$ whose sum is at least the $$$i$$$-th largest value of $$$x$$$.
When answering a query, we simply enumerate $$$\text{len} = 1, 2, \dots, B$$$ and, starting from the current left endpoint, quickly skip over and process all segments of length $$$\text{len}$$$. The time complexity for this part is $$$O(B)$$$ per query.
For segments of length $$$ \gt B$$$, we directly binary search the ending position of each such segment. Since every such segment has length at least $$$B$$$, we make at most $$$n/B$$$ jumps, so this part runs in $$$O\bigl((n/B)\log n\bigr)$$$ time.
If we choose $$$B = \sqrt{n\log n}$$$, the two parts balance and the total time complexity becomes $$$O\bigl(n\sqrt{n\log n}\bigr)$$$.
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mxn=2e5+5;
const int B=512;
int T,f[B+3][mxn],n,a[mxn],q;
ll sum[mxn],N=1000000001;
int l_[mxn],r_[mxn],x_[mxn];
int id[mxn];
void solve(){
cin>>n>>q;
vector<int>v;v.clear();
for(int i=1;i<=n;i++)
cin>>a[i],
sum[i]=sum[i-1]+a[i];
for(int i=1;i<=q;i++)
cin>>l_[i]>>r_[i]>>x_[i],
v.push_back(x_[i]);
v.push_back(0);
v.push_back(1000000008);
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
for(int i=1;i<=q;i++)
id[i]=lower_bound(v.begin(),v.end(),x_[i])-v.begin();
for(int i=1;i<=B;i++){
int k=0;
for(int j=n-i;j>=0;j--)
for(;v[k]<=min(sum[j+i]-sum[j],N);k++)
f[i][k]=j+1;
}
for(int t=1;t<=q;t++){
int l,r,x,cnt=0;
l=l_[t],r=r_[t],x=x_[t];
for(int i=1;i<=B;i++)
if(f[i][id[t]]>=l){
int w=min(r-l+1,f[i][id[t]]-l+i)/i;
cnt+=w;
l+=w*i;
}l--;
while(1){
if(sum[r]-sum[l]<x){
cout<<cnt<<' '<<sum[r]-sum[l]<<'\n';
break;
}cnt++;
int t=x,lo=l-1,hi=n+1,md;
ll req=sum[l]+t;
for(;lo<hi-1;){
md=lo+hi>>1;
if(sum[md]<req)lo=md;
else hi=md;
}
l=hi;
}
}
for(int i=0;i<max(n,(int)v.size())+3;i++)sum[i]=0;
for(int j=0;j<B+3;j++)for(int i=0;i<max(n,(int)v.size())+3;i++)f[j][i]=0;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
T=1;cin>>T;
while(T--)solve();
return 0;
}
There exists an $$$O(n\sqrt{n})$$$ solution.
Auto comment: topic has been updated by paulzrm (previous revision, new revision, compare).
It's great to see another sqrt problem appearing in the round.
thanks for quick editorial and nice problems
.
If you ain't getting the code for C in editorial (if you are low like me idk) :
Refer this
Luckily I didn't waste time on D initially and skipped to E.
Solved E within 20 minutes ( including Logic + Coding ).
I went in wrong direction in D. kept using BFS, and tried to prune branches in BFS. but kept failing.
it's said in the editorial for F that x <= n even though x <= 10^9
sorry I pasted the old tutorial for F
Really sorry for the mistake. We are now fixing it.
Auto comment: topic has been updated by paulzrm (previous revision, new revision, compare).
Seems to me you forgot to mention fixing middle element in case of odd $$$n$$$ in E's tutorial. In current state editorial is factually incorrect, if $$$pos[x]$$$ is at exact middle, one of the two swaps doesnt make $$$x$$$ and $$$n+1-x$$$ symmetrical.
You're right. Thanks for the report, and we'll fix it soon.
For problem D: since $$$\log_2 n$$$ is small, dp is not needed. An $$$O(\sqrt{n})$$$ solution 352084821 can also pass.
Can you please explain your solution.
i think add 2^i is opt , the carries got = new zero , try with many i = "if n > 0 { ans = ans.max(solve(n >> n.trailing_zeros(), k))}" (don't care bit zero before i)
The worst situation is when n=(10101010...)2
Let the time complexity be T(l) when the length of n in binary is l
Note that one branch decreases the length of the number by 1, the other decreases it by 2. So T(l)=T(l-1)+T(l-2) which is Fibonacci sequence.
T(log2n) is close to sqrt(n) so I guess that's why the author said it was O(√n)
Auto comment: topic has been updated by paulzrm (previous revision, new revision, compare).
Can someone help me debug my E code: https://mirror.codeforces.com/contest/2173/submission/352087156
It gives me
wrong answer Test 13: finished but permutation is not identity. (test case 13)The idea i tried to implement is whenever i encounter an index when i!=p[i] i will keep query to swap i and p[i] till number of swaps for i and p[i] is odd so i put current p[i] in correct place and the number of swaps for n-i+1 and n-p[i]+1 is even i,e no change on there value
ik this solution would probably make more than intended number of queries but what i am not able to understand is how I am getting finished but permutation is not identity.
Any help is appreciated thanks!
This happens when one of the elements appears in the middle of the array.
Say you want to swap $$$a$$$ and $$$b$$$ in $$$[b, a, c]$$$.
Step 1: query 1 2 ans 2 3: $$$[b, c, a]$$$ c0=0 c1=1
Step 2: query 1 2 ans 1 2: $$$[c, b, a]$$$ c0=1 c1=1
Step 3: query 1 2 ans 2 3: $$$[c, a, b]$$$ c0=1 c1=2
c0 is odd and c1 is even, but the array becomes a total mess.
Yeah i had a dream that this is whats wrong Thanks
just try to fix 2 end point once they are fixed go to next. cz if you fixed any 2 end point they will never be swap again. code : 352120897
2173
Whats wrong with this solution of mine for problem D?
Idea: Maximum carries occur when adding to a long chain of consecutive 1s. Spend first (k-1) moves creating the longest possible chain of 1s by adding to zeros between 1-blocks. Last move: add 2^ℓ at chain start → carries = chain length.
Example:
n = 13 (1101), k = 2:
Move 1: Add 2^1 → 1111
Move 2: Add 2^0 → 10000 (4 carries, chain length 4).
Total = 4. Use sliding window to find max chain length with (k-1) flips, then compute total carries over all moves.
this is not always optimal counter example:
n=111001101 k=2
here max ans is 5 we should trigger both island of 1 and not flip 0
Thank you , Should have tried dp instead of greedy ,considering the fact that the length of that binary string is atmost 32 anyway.
yes thats a big hint
Try $$$n=409=(110011001)_2$$$ and $$$k=2$$$. The optimal is to choose to add $$$2^3$$$ and $$$2^7$$$ to achieve 4 carries.
D and E are amazing!!! I love them.
bro i couldnt even solve a single question in this contest. been grinding for past 10 days, this demotivated me a lot
keep going!
It's ok, keep going even if you feel stuck, one day it's going to click.
also, a very good advice someone told me is, when you are training try not just to learn how to solve this specific problem, but think of what general techniques used to solve this problem that can be used to solve other problems
for example, if a problem asks how many zeros you can take, you can "think in reverse" and say how many zeros I can't take? this is like a general idea that makes many problems easier, so try to catch those while training, and after a while, your mind works using the ideas you learned naturally
Can anyone please tell whats wrong with my greedy code (352103241) for Problem D.
Counter example n = 461 k = 2, answer should be 5 your code outputs 4
There is no need to flip 0s everytime, sometimes flipping all ones greedily gives optimum.
Problem F.
I’m interested in this solution. Are there any hints or references?
You can replace the binary search with the following approach: first perform exponential search to find the appropriate interval, and once the length is determined to lie between $$$2^k$$$ and $$$2^{k+1}$$$, perform a binary search within that interval. With this modification, the analysis yields a running time of $$$O(n\sqrt{n})$$$.
It took me a while to think why it works, but it actually works.
The proof uses 2138C2's theorem on sigma_{1...O(sqrt(n)} log(c_i).
We consider exponential search to be O(log i) (i is the position). Now in the first binary search phase, we denote b[i] being the difference between two distinct length candidates.
Thus, we want a bound for sigma(log(b[i])) under the condition of sigma{sigma{b[i]}} = O(n).
Now, we consider sigma{sigma{b[i]}} equals to
l*b[0]+(l-1)*b[1]+...+b[l-1]. Now, this reduces to sum_{1...sqrt} log(c_i) in 2138C2's editorial, which has been proven to be ~ sqrt NAbout the second binary search phase:
We consider l[i] being the number of occurrences of the length b[i]. Thus, the sum we want is sigma{log(l[i])} w.r.t sigma l[i]*b[i] == n. We should note that b[i] > i for all i, thus sigma {l[i] * b[i]} = n implies that sigma {l[i] * (i+1)} <= n. Reusing 2138C2's theorem again on l[i], we got the bound to be ~ sqrt N.
I think maybe we can just leave out the binary search in the second part as we know the length will be > sqrt(n) and we sum of length of each step is limited to n so we can move atmost sqrt(n) time
i missed the first one by one edge case damnn
thank you for this contest and fast editorial
In C, what if we have an array of all primes? Wouldn't this solution get tle?
No, as then our answer would be -1 (which we will get in our first iteration itself), so it won't give TLE
Love problem C !
can someone explain : finished but permutation is not identity . thanks
Presumably this is the verdict that you're getting for Div2E. The identity permutation is just the permutation with
p[i] = i, so this is just the checker saying that your permutation did not end up sorted at the end.sound like "sorted"
I’m looking to join a consistent and active CP peer group to practice regularly, discuss problem-solving approaches, and improve together.
There is a simpler idea for E. Let X be a number of correctly placed numbers. At each step just calculate for each pair of indices (i, j) a math expectation of X after a swap. Greedily select a pair of indices with best expectation. In order to don't get TL, don't try every pair, but for each index i try only "reasonable" indices j, which are: 1) an index at which current i's number should be; 2) an index at which number i stays now. That's it. Implementation: https://mirror.codeforces.com/contest/2173/submission/352126084
Problem E is so interesting! I thought I need to put smaller number on left part (after grouping), but that actually will result in limit excess.
Was I the only one who felt problem statement of A wasn't that clear? according to me 110 k=1, answer should've been 1 but problem statement meant different of what I understood.
nhi be lodu, tum hi galat ho — kuch samajh nhi aata hai tumheee!!!!
Loved Problem C!
I solved D with greedy : submission. Not the most optimal approach but i found it very intuitive.
So the main idea behind it was that if you pick a set of consecutive 0s and decide to set any one of these bits (by adding 2^x) then in the optimal case all of the 0s should be set (so that they connect 2 set of consecutive 1s). So i just brute forced using bitmasks by selecting which sets of 0s i will completely set, and then greedily took the biggest set of consecutive 1s from the new number formed based on how much k i have left after setting the selected consecutive 0s.
The max number of consecutive 0s can be 15 (alternate 0 1 0 1 => max = 30/2), so my code might take upto 15 * 2^15 * 1000 operations(as t <= 1000) which is roughly 5 * 10^8. It passed with a total time of 1.2s. Let me know if you are able to hack it!
I tried something like this but encountered too many corner cases
I had the same approach as you, but TLE. Then, I literally submitted your code post-contest (sorry), and it got TLE on test case 21.
dont say sorry lol. i did a few edits and submitted my code again and it passed in 1.3sec, weird.
Your solution is insane. I had a similar greedy idea, but didn't dare to dive in.
thanks:)
So, just repeatedly add 2^l on the biggest block of consecutive ones (with length len) to get len carries?
And at some point the entire thing will become 2^x in which case you just keep adding onto the most significant bit?
Thanks!
interesting contest. i could have solved D if i had passed C faster, but the time was limited. qwq
Can anyone explain the DP for D? I understand why we want to minimize the number of bits by the end, but I can't wrap my head around the DP to actually achieve that.
The point is to not think about how dp[i][j][k] is formed, but form the next states based on what you already have.
Notice that adding 2^j on the same index is never beneficial, coz we already know k < total_bits and once you use a 2^j there is definitely an other index where you can use to get more carries.
Suppose you are at the ith bit having used j operations of adding 2^j on bits before the ith bit, now there are two possible cases-
1) You use the operation(add a 2^j) on that bit which results in some carry. 2) You do not use operation on that bit.
Simulate whatever carry you get and whatever bit stays in that position based on the carry will be added to the next state of the dp, because you are calculating dp[i][j][k] as the number of set bits.
By the way dp[i][j][k] is defined as reaching the ith LSB using the addition of 2^l j times on bits before the ith one and having a carry of k. Note that k can never be greater than 1.
Effectively your dp is just (bits + 1) * (k + 1) * 2 states
Can you please explain how for n=197(11000101), k=3, the ans is 5?
1 operation on the last bit — 11000110 ( 1 carry)
1 operation on each of the 1 blocks — 100001000(2 + 2 carry)
I have a more concise way to write problem E that might be essentially the same as the editorial.
submission
If it is wrong, please tell me
I'm not sure why this solution for problem E works: 352146525
In Problem E, I wasn’t initially sure why my solution got accepted 352174671. My approach is to keep swapping until the permutation becomes sorted, but I only move to the next index when the swap makes either the current position correct or the corresponding mirror position correct.
Is there a greedy solution for D :
Along the following lines :
If K > number of zero between lsb and msb then we can always reach a power of 2 .
otherwise :
We know any blocks of 1 merging with another will only increase the size of the other block by 1 maximum .
so this leads to a greedy approach of always picking the maximum block length with careful tie breaking .
Implementation kind of seems to be hell , but logically seems sound to me.
If you want to get in-depth understanding of problem B's solution,
Here is my video solution : Link. (It's in Hindi lang).
I used a much more simple way to solve E.
My Code
The main part and the only part of mine is to place both i and n-i+1 in one round(caution here: not one operation), with just easily keeping swap them.
I think the expected times of this is 5m (m is the count of rounds).
After one (i, n-i+1) was done, I found that in the latter process(the part shown up there), we wouldn't adjust their position anymore when we optimize our operates.
Thus, all pairs of (i, n-i+1) pair is unrelated. And the last remained number can automatically get its position after other numbers are swapped to their own place, so m equals floor(n/2).
The total expected times of operates is 2.5n.
Proof is listed below:
Set expected operation of each round as E=E1+E2. (E1 is the expectation of swapping either i or n-i+1, while E2 is the expectation of another)
With some calculation, it's easy to find:
(1/2)+(1/2)*(E1+1)=E1
(1/2)+(1/2)*(E2+2)=E2
So E equals 5.
can u explain ur calculation a bit more precisely ?
sure. and also you did remind me that I made sth wrong :p
In the first step, the goal is to home one number.
The possibility to finish it is 1/2.
If it's not finished, it backed to the initial situation (and it requires another E1 operation in expectation).
That's how I got
1+(1/2)*E1=E1.(another form is:
(1/2)+(1/2)*(E1+1)=E1, and I made mistake on the(1/2)+)In the second step, the goal is to home the another number.
The possibility to finish it is also 1/2.
But when it's not finished, the homed number in step 1 was out of its position. Specially, the positions of the two number now mirror, so it needs exactly 1 operation.
That's how I got
1+(1/2)*(1+E2)=E2(another form is:(1/2)+(1/2)*(E2+2)=E2)I wrongly wrote my equation earlier. Sorry for the loose thinking.
For E, I was also trying to understand this (related) solution:
Analysis: Fix an iteration of the for loop. In expectation, we reach $$$p[\ell] = \ell$$$ after at most 2 swaps. After that, with probability $$$1/2$$$ we obtain $$$p[r] = r$$$ in 1 swap (in which case we are done), and with probability $$$1/2$$$ we go to a state such that $$$(\ell, \text{pinv}[\ell])$$$ and $$$(\text{pinv}[r], r)$$$ are mirrors of each other. In this special situation, it takes in expectation only 4 swaps to fix both $$$\ell$$$ and $$$r$$$. There are $$$n/2$$$ iterations of the main loop, so this is gives $$$\frac n 2 \cdot (2 + \frac 12(1 + 5)) =2.5n$$$ swaps in total.
Why is the complexity for C $$$O(nd(n)logn)$$$? I think, the worst case is input
[2,3,4,…,k]and the answer is all primes. So we get the Sieve of Eratosthenes, which works in O(n) (*logn for set/map).Absolutely GOATED contest.
Despite messing up, I loved the problems, and thanks to whoever answered the questions for not spamming "No comments" to everything(No, I was not chatting mid contest)
You should have made the problem rating button, E is brilliant
https://mirror.codeforces.com/contest/2173/submission/352285205 why is this solution accepted? if
k = 1e9anda[i] = 1this should give TLE right?it outputs
-1within $$$O(n)$$$ because there's no enough elements in the mapmpright, I have an immediate
return. Thanks.can someone explain how our answer is popcount(init_n) + k — popcount(final_n).(Problem D);
in problem D, my $$$O(n2^{n/2})$$$ solution passed it lmao
maybe you should change the datarange to $$$n \lt 2^{64}$$$ or give the binary representation of $$$n$$$ xd
In problem C, can someone provide suitable explanation on why finished cannot be element of the B. Let Assume x is still left and 2*x is not possible but there exist finished y which contain x as multiple this can be used..
D was a great one and took a lot of time to figure out the DP approach for it, was a bit lengthy too. The problem required to maximize the no of 1's with most bit flips for K bits, We calculate the maximum gain and the most no of 1s that we can get is k + the calculated gain..
While I was even streaming the whole contest and was even sharing my approach for each problem what I felt could be the best possible solution to it, it was a private stream supposed to be public when the contest was over even I dont know how my answer matched the same logic with 4-5 other participants...
Well I would keep this in my mind next time and would try to solve more since the only thing I feel that keeps me on the backfoot is the ability to solve under time pressure, if any of you guys can help me with that it would be great. Especially for problems that involve DP and in most common words with 2d DP it takes me much more time to reach an optimal state of solution as my answer.
During the thinking process for E, I came up with a naive idea similar to phase 2 in the editorial without phase 1 and the submission actually passed: Submission [without symmetry]. And I also found it hard to convince myself that phase 1 is really necessary, please hack or correct me!
If you skip first phase and try to arrange pairs directly like in second phase, expected number of operations per pair becomes 5 instead of 4, but that is okay as we don't do any operations to guarantee pairs symmetry and there are n / 2 pairs.
Another solution for E: If the prefix till L, excluded, is correct and the suffix till R=n-L+1, excluded, is correct, if we try to place L in the correct place, we can't ruin the prefix and the suffix. Let's calculate the expected number of operations in this case. T=1+0.5*0+0.5*T; T=2 (We do at least 1 operation, and if it's the wrong one, we're still expected to do T operations until the right one).
If we placed L, when we try to place R, we also can't ruin the prefix and the suffix, but we can move L to an incorrect place again. The expected number of operations in this case(if we want to not move L): T=1+0.5*0+0.5*0.5*(T+1)+0.5*0.5*(T+1); T=1+0.5(T+1); 0.5T=1.5; T=3 (We do at least 1 operation, and if it's the wrong one, after that we do either the wrong one again, cancelling it and using 1 operation, and again are expected do to another T operations, or the right one, using 1 operation, and again are expected to do another T operations, but in this case because we need to cancel the wrong one and not cancel the right one).
So for all L in total the expected number of operations is n/2*2=n, and for all R in total the expected number of operations is n/2*3=1.5n, n+1.5n=2.5n.
Sorry if this is a naive question, but regarding E, we assumed a fair probability of 0.5 for each flip. However, in practice, even after 4 or many more operations, it is possible that we still do not get the correct result. Of course, this will not happen for every n/2 pairs, but since the system tests a large number of participants and submissions, is it possible that some cases exceed the expected behavior?
For example, when tossing a fair coin, there is still a very small chance of getting tails 100 times in a row. I wonder how does the judge ensure that such extreme cases do not cause failures?
I'm quite late, but in case it ends up being useful to anyone later: I had another $$$O(n \sqrt{n \log n})$$$ solution to F that sidesteps the precomputation in the editorial. The idea is to split the lengths into three blocks such that the first block consists of all lengths up to some $$$k_1$$$ and the second consists of all lengths between $$$k_1$$$ and some $$$k_2$$$. Then, proceed as follows:
For the smallest lengths, we binary search for the last starting point for which the segment of the given length has weight at least $$$x$$$. This lets us count segments of each length in $$$O(\log n)$$$, so the complexity of this step is $$$O(k_1 \log n).$$$
For the middle lengths, we repeatedly check if an interval of the current length has weight at least $$$x$$$ and add it to our answer if so. Each interval has length at least $$$k_1$$$, so there are at most $$$\frac{n}{k_1}$$$ of them. Additionally, since we check each length individually, we take $$$O(k_2)$$$ time just iterating through all the lengths. Thus, the complexity of this step is $$$O((n / k_1) + k_2).$$$
Once the length is larger than $$$k_2$$$, we repeatedly binary search for the length of the next segment, as in the model solution. Since there are at most $$$n / k_2$$$ segments in this stage, the complexity of this step is $$$O((n \ k_2) \log n)$$$ (similar to the model solution).
Now, take $$$k_1 = \sqrt{n / \log n}$$$ and $$$k_2 = \sqrt{n \log n}.$$$ Then all three steps run in $$$O(n \sqrt{n \log n})$$$, as desired. My code passes in 1.5s by using $$$k_1 = 90$$$ and $$$k_2 = 1700.$$$
This solution differs from the model solution by removing the model's precomputation but adding the second step to process the larger lengths in the small group. Intuitively, we relatively quickly reach a point where the $$$n / x$$$ cost of iterating over many intervals of length $$$x$$$ is small enough that we'd rather pay it if needed than spend an extra $$$\log n$$$ factor doing binary search.
Thanks for the round!
Can someone explain in solution D why are we adding c to bst
Here's my understanding of the solution for Problem D.
1) We won't add where a bit is already 0. Carry is generated only when 1 interacts with 1, i.e. when $$$bit[l]=1$$$ and $$$2^l$$$ is added. Making a bit 0 to 1 wastes a move. We could have used that move to get a carry by adding at any other bit position that has 1.
2) We won't add the same $$$2^l$$$ twice. Because after one move $$$bit[l]=1$$$ to $$$bit[l]=0$$$ . And we don't add under 0, as mentioned in the point above.
3) After every move, the number of 1's either remain same or decrease. On each move, several 1's get converted to 0 and one 0 gets converted to 1. This is essential to understand
popcount(n) + moves - carries = popcount(n')4) After some moves when it reaches form $$$2^x$$$, meaning there's only one bit position has 1, remaining moves add one to the score for every move because every time we'll targets the only set bit present.
5) Since $$$n \lt 2^{30}$$$, 30 moves are enough to make the number reach form $$$2^x$$$. We can see this if we always add $$$2^l$$$ where l is the lowest set bit of the number.
6) For DP, we will ask a $$$bit[0...i]$$$ what's the max score without a carry out, and what's the max score with a carry out. Carry out can interact with next higher bit and might generate greater score.
Here's my submission
If you find anything wrong, or have any other perspective, I would love to discuss.
For F, you actually don't have to precompute anything apart from prefix sums. It's sufficient to do brute force with the same length idea as the editorial, but simply binary search for how many subarrays of the current length you can take, before the sum becomes too small. And you also have to binary search for the next length we take, if our current length is too small.
Then the code can be very short: https://mirror.codeforces.com/contest/2173/submission/374665396