Codeforces Round 1080 (Div. 3) Editorial

#	User	Rating
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3603
4	jiangly	3583
5	turmax	3559
6	tourist	3541
7	strapple	3515
8	ksun48	3461
9	dXqwq	3436
10	Otomachi_Una	3413

#	User	Contrib.
1	Qingyu	157
2	adamant	153
3	Um_nik	147
4	Proof_by_QED	146
5	Dominater069	145
6	errorgorn	141
7	cry	139
8	YuukiS	135
9	TheScrasse	134
10	chromate00	133

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

Rate the problem!

Editorial

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

Rate the problem!

Editorial

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

Rate the problem!

Editorial

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

Rate the problem!

Editorial

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

Rate the problem!

Editorial

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

Rate the problem!

Editorial

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

Rate the problem!

Editorial

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

Rate the problem!

Editorial

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!

bool flag = true; for(int i = 1;i <= n;i++) { // i value should exists in this i or 2 * i or 2 * 2 * i.. or dividing by 2 bool exists = false; int j = i; while( j <= n) { if(A[j-1] == i) { exists = true; break; } j = 2 * j; } j = i; while( j >= 1) { if(A[j-1] == i) { exists = true; break; } if(j % 2 == 0) { j = j / 2; } else break; } if(!exists) { flag = false; break; } } if(flag) cout << "YES\n"; else cout << "NO\n";

int n; cin >> n; vi v(n); cin >> v; vector<bool> visited(n + 1, 0); bool ok = true; for (size_t i = 1; i <= n and ok; i++) { if (visited[i] == false) { ll sumi = 0, sumv = 0, xori = 0, xorv = 0; for (size_t j = i; j <= n; j *= 2) { visited[j] = true; sumi += j; sumv += v[j - 1]; xori ^= j; xorv ^= v[j - 1]; } ok &= (sumi == sumv and xori == xorv); } } const char *result[2] = {"YES\n", "NO\n"}; cout << result[1 - ok];

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; }

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;

} ~~~~~~~~~~~~~

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;

Comments (184)

Write comment?

khba

2 months ago, hide # |

← Rev. 3 →

How to solve F?

→ Reply

Hacker_Dt

2 months ago, hide # ^ |

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/

johnmayer.wong

I never thought the problem can be solved at the angle of graph！I thought it was disjointset but I failed

suryanshrathore19

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

pop1912

chromate00 — all tutorial is showing as "Tutorial is not available"

chromate00

probably a codeforces cache issue, it should load soon

Loaded now — Thanks

DonutMaster

← Rev. 2 →

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

nem-E-sis

i used bitmask for 1st,DSU for 2nd,Dp for 3rd :) overkilled all of them

d1amondzz

:skull:

kaiyaljawad

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

EliteGamer01

7 weeks ago, hide # ^ |

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.

Metall1cA

it's all about what type of problem do you solve, like if you will solve only 800 rated problems you won't improve

riasat.ahon

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

codemastervansh

can you kindly guide, how is DSU plausible for B?

loved F

kristo31

Agree, although I didnt manage to solve it on contest because my code was a bug ridden hell

theRealChainman

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)

WH1T3B34RD

Can you please point out where my code fails in Problem C?363179540

i_hate_pahadans

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

hiroc

Try. The answer should be 2

1
9
3 2 2 5 1 4 5 3 4

Thanks a lot

Sujal_Gound

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

harshXshinchan

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).

xndr

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?

← Rev. 4 →

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!

beny_kh

← Rev. 9 →

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.

Assume $$$n=50\,000$$$ with a very skewed tree
Every subtree inside takes no longer than $$$2n-1 \approx 10^5$$$ seconds to escape
If I give you $$$k=10^9$$$, that would take at least $$$\frac{k}{2n-1} \approx 10^4$$$ steps upward for the check

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

von_arrow

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?

888krishnam

It would be n/2 steps up in a skewed tree.

sushant4599

Maths + DP forces! Thanks for the contest.

DarkDevilVaqif

-10

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

+13

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

Andimeo

Also, by placing two (3×2)-s horizontally, you can get a 3×6 rectangle.

I don't understand this. Wouldn't it be 3x4 rectangle?

he probably meant three

oh yes I meant three

Golovanov399

+26

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)

+18

I can confidently say that I was definitely not aware of the classic problem when I had set this problem (but good approach!)

ItsNotMeItsYou

Do you have any simpler solution for a 5x9 rectangle?

Spoiler

+23

Yes

vasuganesha1

cool

shorya1835

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.

vinith_katariya

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

tanmoy003

for the first 3 element 6 6 1 ,only replacing the middle would be enough like : 6 2 1 . no need for 2 replacement

windTunnel

I think you missed out that 1 1 is not a valid sequence as 1 face is not adjacent to 1 face (it's the same and that's wrong). Thus one of the 1's has to be changed. This makes your approach a wrong approach.

Also I would suggest you solve for the case of 4 4 4 as 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 3 and 4, let's say we change it to 2 $$$\implies$$$ 4 4 4 $$$\rightarrow$$$ 4 2 4 in $$$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

DP solution structure

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
#define nl '\n'
#define INF (LLONG_MAX/4)

void solve() {
    int n; cin>>n;
    vector<int> a(n+1); for(int i=1;i<=n;i++) cin >> a[i];
    vector<vector<int>> dp(n+1,vector<int>(7,INF));
    for(int x=0;x<7;x++) dp[0][x]=0;
    for(int x=0;x<=6;x++) if(x==a[1]) dp[1][x]=0; else dp[1][x]=1;
    for(int i=2;i<=n;i++){
        for(int x=1;x<7;x++){
            int mi = INF;
            for(int y=1;y<7;y++){
                if (y==x || x==7-y) continue;
                mi = min(dp[i-1][y]+(x==a[i]? 0:1), mi);
            }
            dp[i][x]=mi;
        }
    }
    // for(int x=1;x<=6;x++){
    //     for(int i=0;i<=n;i++) cout<<dp[i][x]<<' ';
    //     cout<<nl;
    // }
    int mi = INF;
    for(int x=1;x<=6;x++) mi=min(mi,dp[n][x]);
    cout<<mi<<nl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

363179540

Can you please point me where my code failed?

try this one

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

greateric

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.

Tomwsc

-35

oh, yeah. cheater has his own thoughts

What?

thearyanshrivastav

-28

how?

arvindr9

why do you think he's cheating?

hyprox

+11

my goat could never

sk921815

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:

residue

https://www.youtube.com/live/mtLQh6f86ZA?si=ayhaoCuUk9XePnLv

Check timestamp of video. Were we having a live stream of contest during the contest?

nik_exists

cf problem authors don't have any control over youtube

mhnd01s

Great and high quality problems. Thx for the contest.

mad_scientist

so much math in D

KurtHasan

Asum+Bsum and Asum-Bsum it's not much

sandeep31

More of patience problem than maths ig :)

sarveshdhake

Yeah

Hussain_Elemam

Is D that hard or I am just bad at math? I was able to solve E but not D :)

Rakshit_1

+17

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 :(

if they had known that G is similar to E

Well, the title existed

+12

yeah, probably makes sense

but I doubt that people (including me) read problem titles during contest.

Although, the problems were quite good, Thanks !!

121822

-8

Problem A: I'll get a lot of downvotes here but a testcase like

2
2 67

should not result in a "yes".

We get a product only if we multiply 2 or more items. Only one 67 without a 1 in the testcase shouldn't lead to a product of 67.

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 beside 67 to 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

Missa220311

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

shivangkeshri3

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.

frag_

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

Maxxx239

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]

Jrd

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

SiyamX7

question D was great in my opinion, just pure math. though i couldn't solve it in time.

Lyr1c

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}

rishuvaiya_12

yeah, solved it similar way

ucupsurucupp

beatiful solution, thanks

Abo-Elnor

Hint to solve b

sc3developer

Missed opportunity to put "Epic" in problem D rating as "Absolute Cinema"

kg1122

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

rockyJoe23

thanks for mathforces contest

dooglius

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.

mnnit.prakharg

Amazing solution. Thankyou.

My submission using this approach: 363470727

tranba

can anyone explain to me how the solution in B works?

realisticXO

gowthamsagar

5 weeks ago, hide # ^ |

the example that you took is not a permutation from 1 to n.
I dont see how sorting the subsequence indices and then adding them to a list will solve this problem.
for each element, if it is not already in intended position, we can simply check if the required index (use a hashmap, numbers are distinct) and current index are in Geometric progression (GP) sequence with r=2.
we can check if two (one based) indices are in GP just by dividing max_index/min_index and checking this it is power of 2.

solution — hashmap is not needed though, because it is permutation anyway, the number itself is the required index.

chetan69

I didn't understand the logic for B

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

a_frog_named_yossy

Took me a while to realize how to check the condition for F efficiently, good problem

esc_qwq

G is wonderful. Great contest, happy chinese new year!

happy new year

saelcc03

E was a beautiful dfs problem. I'll teach it to my young padawans.

PiSiJiangWan

I thought a product required at least two numbers... sorry :(

porkchop_yt

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.

for(ll i = 1; i <= n; i++){
    for(ll j = 1; j <= 6; j++){
	for(ll k = 1; k <= 6; k++) if(j+k != 7 && j != k) dp[i][j] = min(dp[i][j], dp[i-1][k]);
        if(arr[i] != j) dp[i][j]++;
    }
}

fisher199

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

dargonburn

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

sreenir

how to solve b , i couldnt solve it. I tried implementing it but got WA for test case 2.

s_tapan099

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

astubbornlad

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

actualtsg

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 >,<

raiseIQUnderflow

Great contest

attacker

Yes I agree!

How to solve problem C in DP？

invictus_07

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).

afterzero

Why rating change is much later than other contest .I know there are hacking phase , but the system test finished hours ago .So..

yomaiwo

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

kevin_0911

bro anyone can explain G how to optimize this solution ![](https://mirror.codeforces.com/contest/2195/submission/363274256)

can anyone please explain me

AbdGraph

the topic of trees is very complex. +1 please, if I'm right

E was the best div 3 problem of 2026 imo

Mutammim_Irtiza

Why did E ask for answer modulo 1e9+7? Wouldn't it fit in long long? G requires the same transitions.

SanG_05

Hey when will the contests rating be updated? Or is it still showing unrated only for me?

ChineseBheL

Sorry, but can anyone give me the solution/proof of how we can check if f(x) < g(x) for parabolas, in F.

doodoodakkadakka

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

Shoaib01

i solved B in O(n)

code :- ~~~~~

} if(poss) cout <<"YES"<< endl; else cout << "NO" << endl; ~~~~~

Kshitiz9975

Another way to solve problem B without much of implementation using observation 363074518

Senku

Loved problem F :)

munkyy9

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.

balaji.nani12345

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

TheMan2030

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.

revelcoS

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.

Daemon_

Can anyone explain what's wrong with my solution for C. 363820342

i2h6

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?

srrow_xhr

F really cool !

alexiuscp

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.

SRLN_JYLQY

defeated by F, good problem

NuclearSoap

7 weeks ago, hide # |

ivan100sic

6 weeks ago, hide # |

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$$$.

sabarikrishna2024

5 weeks ago, hide # |

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.

sidlad

4 weeks ago, hide # |

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?

MRCoetzee

3 weeks ago, hide # |

hello,i want to know why my code is not correct.i paste it below.it is problem b. ~~~~~~~~~~~ //this is the code

AC_first

题解很清晰，要的就是这种效果

maver7

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);

} ` ~~~~~