I hope you enjoyed any number of problems in the contest!
Solution codes will be posted after the open hack phase. They have now been added.
2195A - Sieve of Erato67henes
Editorial
Tutorial is loading...
Code
for _ in range(int(input())):
n=int(input())
a=[*map(int,input().split())]
if 67 in a:
print("YES")
else:
print("NO")
2195B - Heapify 1
Editorial
Tutorial is loading...
Code
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main()
{
cin.tie(0)->sync_with_stdio(0);
int t;cin>>t;
while(t--)
{
int n;cin>>n;
vector<int>a(n+1);
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i+=2)
{
for(int j=i;j<=n;j*=2)
{
for(int k=i*2;k<=n;k*=2)
{
if(a[k/2]>a[k])swap(a[k/2],a[k]);
}
}
}
if(is_sorted(begin(a),end(a)))cout<<"YES\n";
else cout<<"NO\n";
}
}
2195C - Dice Roll Sequence
Editorial
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
int ans = 0;
for (int i = 1; i < n; i++) {
if (a[i] + a[i-1] == 7 or a[i] == a[i-1]) ans++, i++;
}
cout << ans;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
ll tc = 1;
cin >> tc;
for (ll i = 1; i <= tc; i++) {
solve();
cout << '\n';
}
}
2195D - Absolute Cinema
Editorial
Tutorial is loading...
Code
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
vector<ll>solve(ll n,vector<ll>f)
{
vector<ll>vec(n);
for(int i=1;i+1<n;i++)
{
if((f[i+1]+f[i-1]-2*f[i])%2!=0)return {};
vec[i]=(f[i+1]+f[i-1]-2*f[i])/2;
if(abs(vec[i])>1000)return {};
}
auto g=[&](ll j)
{
ll w=f[j];
for(int i=1;i+1<n;i++)
{
w-=vec[i]*abs(i-j);
}
return w;
};
ll g1=g(0),gn=g(n-1);
if(gn%(n-1)!=0)return {};
if(g1%(n-1)!=0)return {};
vec[0]=gn/(n-1);
vec[n-1]=g1/(n-1);
if(abs(vec[0])>1000||abs(vec[n-1])>1000)return {};
return vec;
}
int main()
{
int t;cin>>t;
while(t--)
{
ll n;cin>>n;
vector<ll>f(n);
for(ll&i:f)cin>>i;
auto a=solve(n,f);
assert(a.size()==n);
for(int i=0;i<n;i++)cout<<a[i]<<" \n"[i+1==n];
}
}
2195E - Idiot First Search
Editorial
Tutorial is loading...
Code
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll md=1000000007;
int main()
{
int t;cin>>t;
while(t--)
{
ll n;cin>>n;
vector<ll>L(n),R(n);
for(int i=0;i<n;i++)
{
cin>>L[i]>>R[i];
L[i]--;R[i]--;
}
vector<ll>dp(n);
auto dfs1=[&](auto dfs1,int x)->ll
{
if(L[x]==-1)return dp[x]=1;
else return dp[x]=(dfs1(dfs1,L[x])+dfs1(dfs1,R[x])+3)%md;
};
dfs1(dfs1,0);
auto dfs2=[&](auto dfs2,int x)->void
{
if(L[x]==-1)return;
else
{
dp[L[x]]=(dp[L[x]]+dp[x])%md;
dp[R[x]]=(dp[R[x]]+dp[x])%md;
dfs2(dfs2,L[x]);
dfs2(dfs2,R[x]);
}
};
dfs2(dfs2,0);
for(int i=0;i<n;i++)cout<<dp[i]<<" \n"[i+1==n];
}
}
2195F - Parabola Independence
Editorial
Tutorial is loading...
Code
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
struct Quad{ll a,b,c;}; // ax^2+bx+c
// f(x) < g(x) for all x
bool comp(Quad f,Quad g)
{
if(f.a>g.a)return false;
else if(f.a==g.a)return f.b==g.b&&f.c<g.c;
else
{
Quad Q{g.a-f.a,g.b-f.b,g.c-f.c};
return Q.b*Q.b-4*Q.a*Q.c<0;
}
}
int main()
{
cin.tie(0)->sync_with_stdio(0);
int t;cin>>t;
while(t--)
{
int n;cin>>n;
vector<Quad>vec(n);
for(Quad&Q:vec)cin>>Q.a>>Q.b>>Q.c;
vector<vector<int>>adj1(n),adj2(n);
vector<int>id1(n),id2(n),dp1(n,1),dp2(n,1);
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(comp(vec[i],vec[j]))
{
adj1[i].push_back(j);
id1[j]++;
adj2[j].push_back(i);
id2[i]++;
}
}
}
queue<int>Q;
for(int i=0;i<n;i++)if(id1[i]==0)Q.push(i);
while(!Q.empty())
{
int a=Q.front();Q.pop();
for(int i:adj1[a])
{
id1[i]--;dp1[i]=max(dp1[i],dp1[a]+1);
if(id1[i]==0)Q.push(i);
}
}
for(int i=0;i<n;i++)if(id2[i]==0)Q.push(i);
while(!Q.empty())
{
int a=Q.front();Q.pop();
for(int i:adj2[a])
{
id2[i]--;dp2[i]=max(dp2[i],dp2[a]+1);
if(id2[i]==0)Q.push(i);
}
}
for(int i=0;i<n;i++)cout<<dp1[i]+dp2[i]-1<<" \n"[i+1==n];
}
}
2195G - Idiot First Search and Queries
Editorial
Tutorial is loading...
Code
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main()
{
ll t;cin>>t;
while(t--)
{
ll n,q;cin>>n>>q;
vector<ll>L(n),R(n),P(n,-1);
for(int i=0;i<n;i++)P[i]=i;
for(int i=0;i<n;i++)
{
cin>>L[i]>>R[i];
L[i]--;R[i]--;
if(L[i]!=-1)
{
P[L[i]]=i;
P[R[i]]=i;
}
}
vector<ll>dp(n);
vector<array<int,20>>lift(n);
auto dfs1=[&](auto dfs1,int x)->ll
{
if(L[x]==-1)return dp[x]=1;
else return dp[x]=(dfs1(dfs1,L[x])+dfs1(dfs1,R[x])+3);
};
dfs1(dfs1,0);
vector<ll>euler,tin(n);
auto dfs2=[&](auto dfs2,int x)->void
{
tin[x]=euler.size();
lift[x][0]=P[x];
for(int j=1;j<20;j++)
{
lift[x][j]=lift[lift[x][j-1]][j-1];
}
if(L[x]==-1)
{
euler.push_back(x);
return;
}
else
{
dp[L[x]]=(dp[L[x]]+dp[x]);
dp[R[x]]=(dp[R[x]]+dp[x]);
euler.push_back(x);
dfs2(dfs2,L[x]);
euler.push_back(x);
dfs2(dfs2,R[x]);
euler.push_back(x);
}
};
dfs2(dfs2,0);
while(q--)
{
ll v,k;cin>>v>>k;
v--;
ll w=v;
for(int j=19;j>=0;j--)
{
if(dp[v]-dp[lift[w][j]]<=k)w=lift[w][j];
}
k-=dp[v]-dp[w];
cout<<euler[tin[w]+k]+1<<" \n"[q==0];
}
}
}
2195H - Codeforces Heuristic Contest 001
Editorial
Tutorial is loading...
Code
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
string base[9]=
{
"AABBCCDEE",
"ABFFCDDGE",
"HHFIJKLLG",
"MHIJJKKLG",
"MMINNOOPP",
"QRNSOTTUP",
"QRRSSTVUU",
"WQXXYVVZ_",
"WWXYYZZ__"
};
struct Point
{
ll x,y;
Point(ll xx,ll yy):x(xx),y(yy){}
};
ostream& operator<<(ostream&os,const Point& P)
{
os<<P.x<<" "<<P.y;
return os;
}
using Pgon=vector<Point>;
vector<Pgon>basis(string b[],int n)
{
vector<Pgon>res;
map<char,Pgon>mp;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
mp[b[i][j]].emplace_back(i+1,j+1);
}
}
for(auto[c,v]:mp)res.push_back(v);
return res;
}
void solve(int n)
{
if(n==1)
{
cout<<"2\n";
cout<<"1 1 1 2 2 1\n";
cout<<"2 3 3 2 3 3\n";
}
else if(n%2==0)
{
cout<<3*n*n<<"\n";
int cnt=0;
for(int i=1;i<=3*n;i+=3)
{
for(int j=1;j<=3*n;j+=2)
{
cout<<Point(i,j)<<" "<<Point(i,j+1)<<" "<<Point(i+1,j)<<"\n";
cout<<Point(i+1,j+1)<<" "<<Point(i+2,j+1)<<" "<<Point(i+2,j)<<"\n";
cnt+=2;
}
}
assert(cnt==3*n*n);
}
else
{
cout<<3*n*n<<"\n";
int cnt=0;
for(auto p:basis(base,9))
{
cout<<p[0]<<" "<<p[1]<<" "<<p[2]<<"\n";
cnt++;
}
for(int i=1;i<=9;i+=3)
{
// 3*n-9=3*(n-3)=even
for(int j=10;j<=3*n;j+=2)
{
cout<<Point(i,j)<<" "<<Point(i,j+1)<<" "<<Point(i+1,j)<<"\n";
cout<<Point(i+1,j+1)<<" "<<Point(i+2,j)<<" "<<Point(i+2,j+1)<<"\n";
cnt+=2;
}
}
for(int i=10;i<=3*n;i+=2)
{
for(int j=1;j<=3*n;j+=3)
{
cout<<Point(i,j)<<" "<<Point(i,j+1)<<" "<<Point(i+1,j)<<"\n";
cout<<Point(i+1,j+1)<<" "<<Point(i+1,j+2)<<" "<<Point(i,j+2)<<"\n";
cnt+=2;
}
}
assert(cnt==3*n*n);
}
}
int main()
{
cin.tie(0)->sync_with_stdio(0);
int t;cin>>t;
while(t--)
{
int n;cin>>n;
solve(n);
}
}
Thank you for participating, and hope to see you again soon!
How to solve F?
Sort according to values of a .Then just see let i and j (i < j) satisfy condition then consider a k > j so if k and j also satisfies then i and k also satisfied on own(because if discriminant of q[i] — q[j] < 0 and q[j] — q[k] < 0 then both are always positive for all x , so their sum is also). So just make a dag with edge between i and j if discriminant of q[i] — q[j] < 0 or first two coeff of difference is zero. Now find the largest size of path that contain the edge using dp on graph and reverse graph/
I never thought the problem can be solved at the angle of graph！I thought it was disjointset but I failed
You can also sort all the parabloas acc to their 'c'. As x reaches 0 all that's left of parabolas is c. After sorting we are sure that all the parabolas that are shorter would be behind. This would save us the work find longest chains in dag and turn it into LIS. Submission link https://mirror.codeforces.com/contest/2195/submission/363443366
chromate00 — all tutorial is showing as "Tutorial is not available"
probably a codeforces cache issue, it should load soon
Loaded now — Thanks
Couldn't solve G in the last 30 minutes (I couldn't participate in the first like 2 hours, thought to give G and H a try in the last roughly 30 mins) I was thinking of a Heavy-Light Decomposition kind of solution, but couldn't figure out the whole solution in time (in 30 minutes anyway lol)
Edit: Editorial just loaded, at least I was thinking in the correct way lol
i used bitmask for 1st,DSU for 2nd,Dp for 3rd :) overkilled all of them
:skull:
bro you solved about 600 problems and you still at 1100 what wrong are you doing
doing everything wrong bro, last year i was at peak, but this year everything inversed and I also started to do "JOB" :( so its hard to solve new problems and improve.
But i planned to reach expert by this year.
good luck bro wish you best
bro try to do 1400 level problems instead of grinding 800-1100 ones take hints in editorial if you are stuck for 30mins without any insight or you can even ask AI for hints.
it's all about what type of problem do you solve, like if you will solve only 800 rated problems you won't improve
I mean using dsu in 2 isn't that bad is it
i think it's not, but it's definitely overKILL
But using bitmask for A is more than just overkill xD
i always think "just implement don't think" for div3 A's
can you kindly guide, how is DSU plausible for B?
loved F
Agree, although I didnt manage to solve it on contest because my code was a bug ridden hell
Cool problems, my approaches to some of them.
B. Find connected components by looping over all multiples of 2, sort the values in each component, and check if the resulting array is strictly increasing.
C. You count the size of consecutive elements that cannot be adjacent, and the answer is the sum of half of each group size.
E.You can use a postorder traversal to compute the dp values, and then a preorder traversal to compute the answer for each node. The dp value of a node is the sum of dp values of its children plus 2 for each child, (because you will travel down and back up to get to back to this node u) and the answer for a node is the sum of its dp value plus 1 and the answer for its parent (because you will still have to perform all the operations from its parent)
Can you please point out where my code fails in Problem C?363179540
wtv cancer youre doing is wrong check my submission for the same question its a greedy run through some exmaples youll eventually get to the approach
Thank you
Try. The answer should be 2
Thanks a lot
With this condition Op_cnt++; add one more condition that is i++ because if there are 2 continuous wrong index then you have to solve one
Hey, I want to know that , did you think the same way the editorial is given for the problem C(means the whole approach as given in the editorial).
For G, Wouldn't the time for finding u (lowest ancestor of v st dp2[u]-dp2[v] <= k) by doing the naive step up only be 30ish steps because dp2[v] roughly doubles when you step upwards?
It would be $$$\mathcal{O}(n)$$$-ish steps if the tree is like extremely skewed. I haven't proven the exact worst case with respect to $$$t$$$ but it's definitely not that small
I think it would be around 30-40 steps, although I could be wrong here. This is my explanation: Even in a very skewed tree, a parent node's dp1 value would HAVE to be larger (even a little bit larger) than the largest dp1 value among its children. Therefore, as you add dp1 values when going up the tree from a node, the sum must be at least doubling, so you would need about log(N) steps to get from v to u? Maybe I'm wrong, but that's how I calculated it
Edit: I was wrong lol, my calculations were incorrect. I was calculating the next parent's node with the sum of the nodes below it (its descendants), not the values of its children. After recalcuating, yes, it definitely isn't a small number
The sum of values from vertex to root is definitely not doubling in a completely skewed binary tree. If anything, its growth is quadratic at best
Yeah, the sum isn't doubling. I was talking about the dp1 values for parents. My mistake was making the parent value equal to some x + the SUM of the descendants down some path when it should have been equal to some x + the maximum sum among its children (assuming we are talking about a very skewed tree)
Oh. Ya. Sorry I don't know where I got the idea that it was doubling each time haha. Thanks, and nice problems!
I think it's actually true.
Assume that we had E(v) seconds to exit the subtree of v. Then we are now in P(v). Now I want to show that exiting the subtree of P(v) needs at least 2×E(v) seconds.
Edit : sorry for mistake. The goal is this: Exiting the subtree of P(v) will double the number of moves.
Let v be the right child. When we are at P(v) for the first time, there is nothing written on P(v). So we move to the left child. After that, when we reach P(v) again, we have the letter L on it. So we move to the right child (which is v). We have to do the same E(v) moves that we did when we wanted to exit the subtree of v.
similarly if v is the left child, We do those E(v) moves just when we move from P(v) to its left child (and some other moves when we go to the right child).
Edit : since we do those E(v) move for any valid tree in the subtree of P(v) (no matter what is the tree), we have done atleast 2×E(v) moves and now we are going to exit the subtree of P(v), the situation of P(v) is like v when we exited its subtree. So we can prove the goal for P(v) like v.
Since we are always doubling our moves to exit a subtree, there would be O(log) moves to reach the vertex that we were looking for.
Yeah, I think your logic was definitely wrong about something.
Yes you are right. I misunderstood what I meant. I edited it, can you tell me why is my proof wrong again please?
For skwwed tree, let the nodes have a left child which is leaf Now assume we are at the right down leaf. For exiting this subtree we do 1 move. For its parent we must have done 6 moves. For its parent we must have done 16 moves and so on... The number of moves is atleast doubled each time.
In a VERY skewed tree, the parent would only be 4 + the maximum dp1 value between its two children. This case would be where each parent (except for the root node) has two children, and the left child is a leaf node while the right node is the rest of the tree. Then, the parent node would have the dp1 value of 4 + dp1[right node]. It would not double each time
Assume that you reach this node(let it be v) from its right child. So you already did dp1[right child] moves. Now as you said, you have to do dp1[right child]+4 moves again. So for exiting this subtree, you must have done 2×dp1[right child]+4. So you doubled dp1[right child]. In the next move you have to do 2×dp1[v]+4, as the you said. So the number of moves are doubling each time. Because when you exit a subtree, you have done atleast 2×dp1[right child].
Remember that dp1[v] is not the sum on all dp1 values of its descendants. dp1[v] is the number of moves required to go from v to its parent when you start at v. So it doesn't double.
Also, if you start at v, you would only visit the right child once (except for the operations inside the right child's subtree). Therefore, dp1[v] = dp1[right child] + 4 (in the very skewed tree).
Got it. Thank you very much <3
Recall that the tree does not need to be complete! It is possible that the left child of P(v) is a leaf. In this case, the amount of operations to clear P(v) is 4 + E(v) < 2 * E(v) for big enough E(v).
Yes, I edited it. Can you check it again please?
It would be n/2 steps up in a skewed tree.
Maths + DP forces! Thanks for the contest.
Shouldn't the editorial be published AFTER the hacking phase?
One could compare the results of your code and someone else's code on random cases to hack the that guy's code
I didn't attach the code?
Oh, yeah, sorry. Though one could argue that it could help, since you could write the code using AI, and though that's against the rules you have to take into account people that don't follow them
I don't understand this. Wouldn't it be 3x4 rectangle?
he probably meant three
oh yes I meant three
The odd construction in problem H can be simplified once you remember the classic problem of splitting a $$$5\times 9$$$ rectangle into corners of 3 cells (I was surprised to learn that it was not the intended solution)
I can confidently say that I was definitely not aware of the classic problem when I had set this problem (but good approach!)
Do you have any simpler solution for a 5x9 rectangle?
cool
I had the same construction, an easy way to think about it is that you have to match either 2 cells in current row with the one cell in the row below/above it or 1 cell in current row with the two cells in the row below/above it.
So, i just chose to match 8 cells in row 1 with 4 cells in row 2 and 1 cell in row 1 with 2 cells in 2, same for row 5 to 4. Now you are left with 3 cells in both row 2 and 4 and 9 cells in row 3. Match 4 out of these 6 cells with 2 cells each in row 3 and then match the remaining two cells in row 2/4 with one cell in row 3. You can then draw 1-2 times to get the exact ways to place the triangles according to the matching.
Can someone please help me with where Im going wrong in my approach for Problem C?
My Approach
Basically in the context of the problem the number 1 and number 6 are equivalent because anything adjacent to 1 is also adjacent to 6 and both 1 and 6 nor 1 and 1 can be adjacent to each other. The same is true for (3,4) and (2,5) pairs.
So we for any number > 3 in the given sequence, we can convert it to its equivalent number in its pair. After this, the sequence should contain ony 1,2 or 3. and now the problem boils down to the min operations needed to make adjacent elements distinct.
For eg the given sequence 6 6 1 6 3 3 4 2 5 can be converted to 1 1 1 1 3 3 3 2 2
363180232 -> Getting a WA. Appreciate any help, Thanks
6 6 1 6 3 3 4 2 5
For this test case you can convert this to 6 3 1 2 6 3 6 2 3 where you only need 5 operations but your given ans 1 1 1 1 3 3 3 2 2 needed >= 5
for the first 3 element 6 6 1 ,only replacing the middle would be enough like : 6 2 1 . no need for 2 replacement
I think you missed out that
1 1is not a valid sequence as1face is not adjacent to1face (it's the same and that's wrong). Thus one of the1's has to be changed. This makes your approach a wrong approach.Also I would suggest you solve for the case of
4 4 4as I did during the contest.It's correct answer is $$$\text{cost} = 1$$$ by doing the following:- change $$$2^\text{nd}$$$ index to anything except
3and4, let's say we change it to2$$$\implies$$$4 4 4$$$\rightarrow$$$4 2 4in $$$1$$$ move.You will realize that this requres one to solve for possibly all combinations. This is a pretty famous place to use DP to compress exponential calculations into managable time complexity.
I found the optimal DP solution in the given constraints. There is another solution which is based on a simple mathematical pattern as pointed out above, but I am yet to do it myself.
You should try to figure out the DP solution by yourself, and see the below solution
And the final solution would be
363179540
Can you please point me where my code failed?
try this one
4
1 2 5 2
The code gives 2 but ans should be 1.
Can I ask you a question if you don't mind? I thought about that test case for most of the time of the contest, but it didn't come to my mind. Is it the problem with not solving enough problems or something else?
I don't know about your problem, but I can explain how I came up with the test. During my solve I noticed that 1 position can fix two positions at once, and when I saw your code I noticed that you only look at odd indices, so you can definitely skip even indices that fix two positions at once
My thoughts:
A: Nice problem
B: Nice problem, although I didn't sort at all. I just pushed each number I saw into std::set and then checked if they were all there in O(n log log n).
C: Nice problem, DP was most intuitive for me
D: I found the sum using f(1) + f(n), and then using f(2) + f(n), f(3) + f(n), ... you can extract each variable. Implementing it was a little involved but I think it was still a good problem overall.
E: Funny concept and nice DP
F: The DAG/"above/below" trick I thought was very cool. I was so close to finding it contest but I did not see it :( (I thought this problem was NP hard for a while lol)
G: Feel like there was some advanced topics in here but I could just be saying that because I didn't know them.
H: I found the reduction to the 9x9 grid with very little time remaining but didn't realize that there was a way to get all 27 triangles. It might've been a little gimmicky expecting us to just draw it out on paper and try things until we find the perfect solution, but I could also be coping again.
oh, yeah. cheater has his own thoughts
What?
how?
why do you think he's cheating?
my goat could never
Another simple solution to B. Heapify 1 problem. the i should exists at either i, 2 * i or 2 * (2 * i) ... all multiple of 2
or i/2, (i/2)/2 ... so on. because we can replace i with 2 * i or i, 2/i
code:
https://www.youtube.com/live/mtLQh6f86ZA?si=ayhaoCuUk9XePnLv
Check timestamp of video. Were we having a live stream of contest during the contest?
cf problem authors don't have any control over youtube
Great and high quality problems. Thx for the contest.
so much math in D
Asum+Bsum and Asum-Bsum it's not much
More of patience problem than maths ig :)
Yeah
Is D that hard or I am just bad at math? I was able to solve E but not D :)
Why is G not referred to as E2? :(
well they technically ask for different things
but aren't they part of the same question (i.e. easy version and hard version) ? I feel that people who didn't solve F, if they had known that G is similar to E, they would have done G rather than spending time on F :(
Well, the title existed
yeah, probably makes sense
but I doubt that people (including me) read problem titles during contest.
Although, the problems were quite good, Thanks !!
Problem A: I'll get a lot of downvotes here but a testcase like
should not result in a
"yes".We get a product only if we multiply 2 or more items. Only one
67without a1in the testcase shouldn't lead to a product of67.ngl i first assumed the same thing got wa took me 5 minutes to realise this thing
Do you think that $$$\prod_{i=1}^{n} a_i$$$ doesn't make sense if n=1? What if it's a sum instead?
Thank you for your explanation.
Now, let me ask you a question. What is a product of
67?You might say
67& that's okay-but everyone knows it's a weird and wrong question. You need another number beside67to get a product. Same for sum.well it is weird in plain English, because we usually view multiplication as an operation between two numbers, but when we talk about a product of some sequence or subset it is standard to define a product of single number as the number itself
i think u are right.the product must use at least 2 elements to get the result.i don't know why so many people think that only 1 element can find the answer
yes, that is why I had first tried submitting with a (if 1 in arr and 67 in arr) type of check, but I got WA. Seems like the problem also defines self-products as valid.
Very easy O(n) solution for B: for each i-th (counting from 1) element a[i] divide it while possible by 2. Do the same for index i. If remainders are not equal — permutation is not sortable. This check can be done in constant time, divide larger value by smaller, check if remainder is not zero or if result is not a power of two.
its nlogn
You can still do it in O(n) by precalcing the array a, where a[i] is a result of a process -- dividing a[i] by 2 while possible. It can be done with some sort of dp: if i is odd, a[i]=i, else a[i]=a[i/2]
Code snippet of my O(N) solution:
I got AC for this code , but I couldn't prove if its correct! Can anyone prove if this is correct or incorrect?
chromate i love your contests man idk why, ive solved good amount of problems from you. idk am just happy cause i solved f. f is something that i first believe that i wont be able to solve but i smh did after lot of debugging lmao b was bit tricky. i didnt try e tho will try tomorrow morning as i was busy so left ocntest in betweeb
question D was great in my opinion, just pure math. though i couldn't solve it in time.
Problem B can be solved in O(n) because a valid permutation only has indices = 1,2,4,8,16 to mutually swap,also like 3,6,12,24 and 5,10,20,40.So checking every position if a[i] / i = 2 ^ k or i / a[i] = 2 ^ k is enough
Solved in the same way. Very nice problem
Another solufion for D. Call the sum of all variables S. Call S_i the partial sum from a1 to ai. First notice that S = (f(1)+f(n))/(n-1)
Notice that f(i-1)-f(i)= S — 2 * S_{i-1} Using i=2,...,n and maintaining S_i we find a1,...,a_{n-1} Finally, a_n = S — S_{n-1}
yeah, solved it similar way
beatiful solution, thanks
Hint to solve b
Since, we can only swap i,2*i,4*i... So, 1,2,4,8... 3,6,12,24... 5,10,20,40,...
Let's call each of them groups I.e consider (1,2,4...) Group 1 So, all the elements of each group are interchangeable that is they can be brought to any place inside the group. Same for other groups as well. But can they be swapped to the elements of other groups? Think in this way and maybe try to think how to implement it efficiently you will get it.
Missed opportunity to put "Epic" in problem D rating as "Absolute Cinema"
I... I sleep in the middle of the contest... almost 2 days without sleep, I just woke up now...
My body gave up, maybe I'm not as strong as I thought
thanks for mathforces contest
I upsolved with a DP approach for H. First, convince yourself with some math that the only possible triangles are those with a base of adjacent points, and the third point one unit away in the other dimension. Observe that you can always solve with at most 3 dots leftover in the last row: even $$$n$$$ is trivial, odd $$$n$$$ leaves a run of 3 via $$$(3n-1)\times 3$$$ block and a $$$(3n)\times(3n-3)$$$ block. So we need only search the space where some are leftover in the last row. For the leftover dots, we can characterize entirely by the number of one-point-on-top and two-point-on-top cases. Let $$$dp_{i,r}$$$ be the best configuration if there remain $$$r$$$ full rows of unused dots and a partial row with $$$i$$$ unused dots; all possibilities can be checked in $$$O(n)$$$ time, leading to an $$$O(n^3)$$$ overall time.
Amazing solution. Thankyou.
My submission using this approach: 363470727
can anyone explain to me how the solution in B works?
Well we can only sort the subsequnce of odd indices
for eg : 1 2 4 8...
3 6 12 ..
5 10 15 ..
this are the indices position on which we can apply operations
so sort the values at this positons according to its subsequnce
for eg : a = [4, 2, 5, 2, 6, 1,]
so here we will have
i = 1 -> 1, 2, 4 (4, 2, 2)
after sorting (2,2,4)
similarly for i = 3 and 5
i = 3 -> 3 6 (5,1) -> (1,5)
i = 5 -> 6
then store it in vector and check if the final vector is sorted or not
2 2 1 4 6 5 -> False
solution — hashmap is not needed though, because it is permutation anyway, the number itself is the required index.
I didn't understand the logic for B
Well we can only sort the subsequnce of odd indices
for eg : 1 2 4 8...
3 6 12 ..
5 10 15 ..
this are the indices position on which we can apply operations
so sort the values at this positons according to its subsequnce
for eg : a = [4, 2, 5, 2, 6, 1,]
so here we will have
i = 1 -> 1, 2, 4 (4, 2, 2)
after sorting (2,2,4)
similarly for i = 3 and 5
i = 3 -> 3 6 (5,1) -> (1,5)
i = 5 -> 6
then store it in vector and check if the final vector is sorted or not
2 2 1 4 6 5 -> False
Lets see from an already increasing permutation.You can swap two indices i and 2*i ,also 2*i and 4*i , 4*i and 8*i....(all not beyond n),so elements in those indices can be casually exchanged.Such as indices = 1,2,4,8,16... , 3,6,12,24,48... and 5,10,20,40,80... We can conclude that for a valid permutation : a[i] / i = 2 ^ k or i / a[i] = 2 ^ k always holds. check if all elements and the indices meet the demand.
try to implement the swapping process in person from increasing premutation,which is effective
Took me a while to realize how to check the condition for F efficiently, good problem
G is wonderful. Great contest, happy chinese new year!
happy new year
E was a beautiful dfs problem. I'll teach it to my young padawans.
I thought a product required at least two numbers... sorry :(
For anyone wondering the dp solution:
Let $$$dp[i][j]$$$ be the i-th element with $$$a_i = j$$$ (obviously, $$$1 \le j \le 6$$$, and $$$j$$$ is an integer). To form a legal dice sequence, $$$dp[i][j] = \min (dp[i-1][k])$$$, where $$$\{1 \le k \le 6 \} \cap \{\{j \ne k\} \cup \{j+k \ne 7\}\}$$$ (Simply, $$$j+k$$$ is not $$$7$$$ and $$$j$$$ is not equal to $$$k$$$ for $$$1 \le k \le 6$$$). Don't forget the $$$+1$$$ if $$$j \ne arr[i]$$$. The basic state is $$$dp[0][i] = 0$$$.
This is quite a good dp problem ngl.
Hello, thanks for the contest!
Could somebody please hack my solution to G where I forgot that euler tours existed and instead ended up making a second binary lifting that simulates the euler tour by storing three states per vertex (down left state, down right state, and up state)?: 363179346
For problem C, the greedy approach is more than enough.It’s basically just a special case of DP — we don’t need to remember what we picked last, so we don’t even need DP
363235397
For problem C ,I dont use dp method. Consider iterating from 1 to n — 1 to check every i and i + 1,if any (i,i + 1) is invalid,change i + 1,then i + 1 and i + 2 always can be valid. Proof follows: for invalid pair(i,i + 1),if a[i] = A,then we change a[i + 1] to 1 to 6 except A and 7 — A. But we can consider further to i + 2. If a[i + 2] = A or 7 — A, then pair (i + 1,i + 2) is valid,too.If a[i + 2] != A and 7 — A,we can still choose one from 1 to 6 except A,7 — A,B,7 — B (2 number left),to make pair(i + 1,i + 2) valid.Thats to say,we can change i + 1 for (i,i + 1),and just skip to check(i + 2,i + 3) then. The advantage is that u dont have to know which digit you should choose.
Bro, we’re thinking exactly the same! For this problem, there’s no point in tracking overlapping subproblems at all—greedy is all you need. This is just DP with some special optimizations, basically!
great to share the same idea!
for e you can have simple and other solution is to kind kids of each kid and derive the formula ans[v]=ans[u]+2*kids+1 initialze ans[1] as 2*n-1 or you can simply start dfs from 0 and use the formula itll be same
how to solve b , i couldnt solve it. I tried implementing it but got WA for test case 2.
observe that with what values we can swap a number at index i?
it is easy to see that the value at index i can be swapped only with values at indices at 2*i, 4*i, 8*i .... basically at indices of the form (2^k)*(i) for k>=0, it is also meant that the value at index i can be swapped with the value a index (2^k)*(i) and with no other index which is not of this form.
that means the indices can form a group with pattern satisfying (2^k)*i
now sort the array with their index values and check the current index in sorted array and it's original index, if they have the same pattern they are swappable, otherwise we cannot swap them and the answer is no. check my submission for b — 363077312
thanks
for B，a monotonically increasing timestamp is exactly what we need to check the equivalence classes,solved in O(n):
363240459
For B, what I thought was this:
Family-1: a[1], a[2], a[4], ... should have values among 1,2,4,... only (and in any order)
Family-2: a[3], a[6], a[12], ... should have values among 3,6,12,... only (and in any order) and so on...
The lowest value of each family is an odd number. Now, if index 'i' from some family has value from other family, the array cannot be rearranged in increasing order. The values allotted to each of the indices in the family must be reducible to the corresponding lowest index of that family, only then that array can be rearranged to increasing order. Can someone suggest the time complexity of this solution? Thank you!
My solution: 363142713
This solution is so cool! It’s strictly O(n) in time complexity
For D, my approach was the same as the official editorial. I found the pattern by comparing linear structures, and after reading it, I realized it’s just about slope change rate. The function is a piecewise linear graph, and the second derivative of the sum gives the pattern. Really great editorial! 363183695
Nice approach on problem D, very simple but I didn't get that on contest.. Instead I'm directly using linear algebra and inverse matrix and pattern guessing to derive the formula to get array A[] back from array F[]! Here is my note showing how long the process to get final formula:
Yes I'm indeed too overkill on problem D, I spent more time solving it than problem E >,<
Great contest
Yes I agree!
How to solve problem C in DP？
https://mirror.codeforces.com/contest/2195/submission/363137687
dp submission of mine
i got idea of dp because there similar problem in cses dp section on dice
NICE BRO !!!
but i have just taken part in 2 games,maybe my rating is a little low so i cant read your code (sad).
Why rating change is much later than other contest .I know there are hacking phase , but the system test finished hours ago .So..
we(both of us) arent going to be rated. our total contest are below 5. sad. I solved a, b, c, e and would n't get any rating point
How did you know about this ? I think there is no such rule bro ??
Yeah ,my bad . I asked chatgpt and he told me that lol, sucks. Well, I was wrong , rating is out
nice problems
bro anyone can explain G how to optimize this solution 
can anyone please explain me
the topic of trees is very complex. +1 please, if I'm right
E was the best div 3 problem of 2026 imo
Why did E ask for answer modulo 1e9+7? Wouldn't it fit in long long? G requires the same transitions.
Hey when will the contests rating be updated? Or is it still showing unrated only for me?
Sorry, but can anyone give me the solution/proof of how we can check if f(x) < g(x) for parabolas, in F.
If f(x) < g(x), then g(x) − f(x) > 0 for all x. Define h(x) = g(x) − f(x). So h(x) must have no real roots, i.e. its discriminant b² − 4ac < 0.
Special case: If g.a = f.a and g.b = f.b, the two parabolas have the same shape and differ only by a vertical shift.
If a > 0 (opens upward), the one with larger c is always above.
If a < 0 (opens downward), the one with smaller c is always above.
This special case does not need to be checked when one parabola opens upward and the other opens downward.
I already got the first part but, i still didn't got the second part, and what if g.a = f.a but g.b != f.b?
then they are differently shaped parabolas. the special case i talk about is 2 similar-ish parabolas in the fact that if u superimposed one on top of the other theyd match up. for the special case u can have one parabola 'inside' the other, but the b² − 4ac determinant is 0, since their difference is a constant, so u have to consider that in the special case. my solution for this question was quite long and ugly u shud probably read through the editorial
i solved B in O(n)
code :- ~~~~~
int n; bool poss = true; cin >> n; for(int i = 1; i <= n; i++){ int x; cin >> x; int k = 0; if (x >= i) { if (x % i == 0) k = x / i; } else { if (i % x == 0) k = i / x; } if (k == 0 || (k & (k - 1)) != 0) { poss = false; }} if(poss) cout <<"YES"<< endl; else cout << "NO" << endl; ~~~~~
Another way to solve problem B without much of implementation using observation 363074518
Loved problem F :)
F is one of the best problems i have ever seen >.<
Please someone explain the solution for question H. I am not getting the editorial solution.
Thanks in advance.
in problem B we don't have to do bubble sort we can just check in the possible positions whether there exists a required number to be placed at the required pos for the sequence to be sorted
here's the code i wrote and it got accepted 363087125
I also thought of the same approach, bro, but failed to implement it within the time.
as it is my second contest Div 3
Give me some tips to improve.
i am not that good either bro i am trying to improve myself too
I think problem F can be extended to higher orders but the implementation may have poor numerical stability and might not work? I am thinking of Newton's method to find the roots of the derivative, so the time complexity is $$$O((nd)^2\log(\epsilon^{-1}))$$$.
Also sorting by $$$f(0)$$$ and doing the DP up/down iteratively is enough. The DAG explanation is generalizable though.
How does the author guarantee, that $$$D = dp_2[v] - dp_2[u]$$$ makes sense, if $$$dp_2[v]$$$ or $$$dp_2[u]$$$ can overflow in problem G? For example, it could make $$$D \lt 0$$$ and on the $$$k \mathrel{-}= D$$$ step $$$k$$$ could actually increase.
Ok, I showed it can not overflow. The max value for $$$dp_1[v]$$$ we can get is less then $$$2^{20}$$$. We can obtain it by constructing the smallest possible balanced binary tree on $$$n \gt 300001$$$ vertices.
Then, the largest value for the $$$dp_2[v]$$$ is less than $$$300001 \cdot 2^{20} \lt 2^{40}$$$, which fits in long long.
Can anyone explain what's wrong with my solution for C. 363820342
Not sure if its the correct place to ask, but ive not been able to see the answers of other participants. In the code section of accepted solutions, it just shows N/A. Does anyone have any ideas why this might be happening and how to fix it?
F really cool !
Has anyone tried Bron-Kerbosch algorithm to solve problem F? My solution which implements BK with pivoting exceeds the time limit on test 6. https://mirror.codeforces.com/contest/2195/submission/364416119
Would love to know if anyone else succeeded with different approaches than the one given on the editorial...
You can hardly solve the maximum clique problem for $$$n\leq 3000$$$ in a reasonable time limit (especially hard instances). It's probably a dead end, and you'll probably realize the graph is a DAG before thinking of different algorithms.
defeated by F, good problem
67
Alternative solution for H: Submit any code that passes the first test case. Look at the report for the second test case, it contains the Jury answer for $$$n = 3$$$. However, it only contains the first 24 out of 27 triangles, the last three are truncated. Draw these 24 triangles using a vibe coded script or whatever. Manually add the remaining three triangles. Use this $$$9 \times 9$$$ solution to reduce the problem to the form $$$2n \times 3m$$$.
i got a mail regarding coinciding solution for the problem f(parabola independence). I apologize for the similarity. I made a mistake by not following the rules properly during this contest. I will ensure to solve problems independently in the future and follow Codeforces guidelines.
Wrt Problem F:
Post Construction of DAG, solving for the longest path each node belongs to in can be done in O(n + m): https://mirror.codeforces.com/contest/2195/submission/368097273
Am curious if an efficient DAG Construction can be done in subquadratic time complexity wrt n, probably some DP optimization involving CHT maybe?
hello,i want to know why my code is not correct.i paste it below.it is problem b. ~~~~~~~~~~~ //this is the code
include
include
include
using namespace std; int main() { int t;cin>>t; while (t--) { int n;cin>>n; vector a(n); for (int i = 0; i < n; i++) cin>>a[i];
for (int i = 2; i <= n; i++) { if (i%2==0&&a[i-1]<a[i/2-1]) { int temp=i; while (temp>1&&temp%2==0&&a[temp-1]<a[temp/2-1]) { swap(a[temp-1],a[temp/2-1]); temp/=2; } } } vector<int> b(a); sort(b.begin(),b.end()); int i; for (i=0;i<n;i++) { if (a[i]!=b[i]) break; } if (i==n) cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0;} ~~~~~~~~~~~~~
题解很清晰，要的就是这种效果
I approached 2195C (Dice Roll Sequence) using a greedy observation instead of DP.
Key idea: We can treat adjacent invalid pairs (same or opposite faces) as "bad edges". In a consecutive block of bad edges of length L, one operation can fix up to two edges, so the minimum operations needed is ceil(L / 2).
So we just scan the array and count bad edges, pairing them greedily.
This gives an O(n) time and O(1) space solution.
Code: ~~~~~ `#include <bits/stdc++.h> using namespace std;
typedef long long ll;
int main() { ios_base::sync_with_stdio(false); cin.tie(NULL);
int t; cin >> t; while (t--) { int n, num, prev, cnt = 0; bool chang = true; cin >> n; cin >> prev; while (--n) { cin >> num; if (num == prev || num == 7 - prev || !chang) { cnt = chang ? cnt + 1 : cnt; chang = !chang; } prev = num; } cout << cnt << "\n"; } return 0;} ` ~~~~~