• Epic
• Good
• Moderate
• Bad
• Horrendous

• Epic
• Good
• Moderate
• Bad
• Horrendous

for _ in range(int(input())):
  n=int(input())
  a=[*map(int,input().split())]
  if 67 in a:
    print("YES")
  else:
    print("NO")

• Epic
• Good
• Moderate
• Bad
• Horrendous

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

• Epic
• Good
• Moderate
• Bad
• Horrendous

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

• Epic
• Good
• Moderate
• Bad
• Horrendous

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

• Epic
• Good
• Moderate
• Bad
• Horrendous

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

• Epic
• Good
• Moderate
• Bad
• Horrendous

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

• Epic
• Good
• Moderate
• Bad
• Horrendous

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

• Epic
• Good
• Moderate
• Bad
• Horrendous

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

• Epic
• Good
• Moderate
• Bad
• Horrendous

• Epic
• Good
• Moderate
• Bad
• Horrendous

First, let $$$m=\operatorname{mex}(A)$$$. We can ignore all elements that are greater than $$$m$$$. This is because since $$$m$$$ is the mex, $$$m$$$ does not appear in $$$A$$$, and consequently it also cannot appear in any of the partitions. Thus, which of the partitions each element goes to does not matter.

Now, let's consider the number $$$0$$$. Suppose there is at least one $$$0$$$ in $$$A$$$. Then, at least one multiset in the partition must contain $$$0$$$ (because each element in $$$A$$$ must be in one multiset in the partition). This also implies that all multisets must contain $$$0$$$, as otherwise the $$$\operatorname{mex}$$$ of all multisets cannot be the same (it is $$$0$$$ for some, but greater than $$$0$$$ for others).

Once we reach the conclusion that $$$0$$$ must be present in all partitions, we can make the same conclusion for $$$1,2,\ldots,m-1$$$. That is, $$$m$$$ is the only possible score.

343539998

• Epic
• Good
• Moderate
• Bad
• Horrendous

For simplicity, let's denote $$$f(a[l,r])$$$ as $$$f(l,r)$$$.

First, notice that $$$f(l,r)\leq f(l,r+1)$$$. This is trivially true because each unique element that appears in the range $$$(l,r)$$$ must appear in $$$(l,r+1)$$$ also. Now, $$$f(l,r+1)$$$ is either equal to $$$f(l,r)$$$ if $$$a_{r+1}$$$ already appeared, or $$$f(l,r)+1$$$ if $$$a_{r+1}$$$ does not appear in $$$[l,r]$$$.

Now, expanding $$$b_i-b_{i-1}$$$ yields $$$f(i,i) + (f(i-1,i)-f(i-1,i-1))+(f(i-2,i)-f(i-2,i-1))+\ldots+(f(1,i)-f(1,i-1))$$$. From the above, we know that $$$f(l,i) \neq f(l,i-1)$$$ only when $$$a_i$$$ does not appear in $$$[l,i-1]$$$. Let $$$x$$$ be the largest integer such that $$$f(x,i-1)=f(x,i)$$$. Note that this implies that $$$a_x=a_i$$$. For all $$$y \gt x$$$, we have $$$f(y, i) - f(y,i-1) = 1$$$. Thus, we have $$$b_i-b_{i-1}=i-(i-x) = x$$$, because all terms of the expansion above are $$$1$$$ except for the ones corresponding to indices $$$x$$$ to $$$i-1$$$. Since we know that $$$a_x = a_i$$$, and $$$x = b_i - b_{i-1}$$$, we should set $$$a_i$$$ to be the same as $$$a_{b_i-b_{i-1}}$$$. There is one more case where $$$x$$$ is undefined, because $$$f(y,i) \neq f(y,i-1)$$$ for all $$$y \geq 1$$$. This implies $$$a_i$$$ did not appear before in the array. We can just set $$$a_i$$$ to any unused number arbitrarily.

343541349

• Epic
• Good
• Moderate
• Bad
• Horrendous

Let's view $$$x$$$, $$$f(x)$$$, and $$$x \oplus f(x)$$$ each as $$$y$$$-bit numbers (where $$$y$$$ is the smallest integer with $$$2^y \gt x$$$). We can see that $$$x \oplus f(x)$$$ is necessarily a palindrome. This is because the last bit of $$$x \oplus f(x)$$$ is the XOR of the last bit of $$$x$$$ and the first bit of $$$f(x)$$$. But since $$$f(x)$$$ is just $$$x$$$ reversed, this simplifies to the last bit of $$$x$$$ XOR'ed with the first bit of $$$x$$$. Now, look at the first bit. It is the XOR of first bit of $$$x$$$ and the first bit of $$$f(x)$$$. By similar reasoning, this also simplifies to the first bit of $$$x$$$ and the last bit of $$$x$$$. We can use the same argument to argue that the second and second to last, third and third to last bit, etc. are all the same. This is what a palindrome is.

One caveat is that although $$$x$$$ is not allowed to have leading zeroes (by our definition of $$$y$$$), both $$$f(x)$$$ and $$$x \oplus f(x)$$$ is. Thus, if we let $$$z$$$ be the smallest integer with $$$2^z \gt n$$$, then $$$y$$$ is not necessarily equal to $$$z$$$. Fortunately, using our palindrome condition, we can find the number of leading zeroes $$$n$$$ must have (it is the same as the number of trailing zeroes in the binary representation of $$$n$$$). This is how we can find $$$y$$$. There is one more trick — suppose $$$z$$$ is odd and there exists a middle. If the middle digit is $$$1$$$, then we cannot find an integer $$$x$$$ with $$$x \oplus f(x)=n$$$. This is because the middle digit is the result of XOR between a bit and itself in $$$x$$$ (since it is in the middle), and both $$$1 \oplus 1$$$ and $$$0 \oplus 0$$$ results in $$$0$$$. Note all other digits are allowed to be either $$$1$$$ or $$$0$$$. If the result is $$$0$$$, we can place a $$$1$$$ in both the corresponding left bit and corresponding right bit. If the result is $$$1$$$, we can arbitrarily place a $$$1$$$ in the left bit and a $$$0$$$ in the right bit, and this is possible if the left bit and right bit are not the same.

343541478

• Epic
• Good
• Moderate
• Bad
• Horrendous

It is not hard to see that the following property holds:

• For some subsequence $$$T$$$ and index $$$i$$$ such that $$$i \notin T$$$, let the query results be $$$0$$$ for $$$T$$$ and $$$x \neq 0$$$ for $$$T \cup {i}$$$. Then, we gain the information that $$$a_i=x$$$.

To use this property to our advantage, let's maintain a subsequence $$$S$$$ whose query result is known to be $$$0$$$. Consider the following subroutine:

• Query the subsequence $$$S \cup {i}$$$ and gain the result $$$x$$$.
• If the result is nonzero, then we know that $$$a_i=x$$$.
• Otherwise, let's assign $$$S \leftarrow S \cup {i}$$$.

If we perform this subroutine for $$$i=1,2,\ldots,2n$$$, we gain the information about all $$$a_i$$$ such that its value appeared for the second time. We now need to find the other $$$n$$$ elements' values.

Notice that currently the subsequence $$$S$$$ contains each of $$$1,2,\ldots,n$$$ exactly once, and so does $$$[1,2n] \setminus S$$$. Therefore, we assign $$$S \leftarrow ([1,2n] \setminus S)$$$ and perform the subroutine over all undiscovered indices again. Each run of the subroutine will give you a nonzero result, and give you the values of the $$$n$$$ undiscovered elements in $$$n$$$ additional queries.

Thus, this solution uses exactly $$$3n$$$ queries (or $$$3n-1$$$ if you would) to discover the values of all $$$2n$$$ elements.

343541838

• Epic
• Good
• Moderate
• Bad
• Horrendous

Let us define an minimal set of rectangles as a set of rectangles on the grid that satisfy the following conditions:

• For all rectangles $$$(u,d,l,r)$$$ in the set, there is no other rectangle $$$(u,d,l',r')$$$ on the grid such that $$$l \le l' \le r' \le r$$$ and $$$r'-l' \lt r-l$$$.

Then, let us call the minimal set of rectangles with maximum cardinality the exhaustive minimal set $$$\mathbb{S}$$$.

This set $$$\mathbb{S}$$$ satisfies the following conditions:

• The set $$$\mathbb{S}$$$ is unique.

• $$$|\mathbb{S}| \le {{n}\choose{2}}\cdot m$$$

• $$$\sum_\limits{(u,d,l,r) \in \mathbb{S}} {(r-l+1)} \le 2 \cdot {{n}\choose{2}} \cdot m$$$

• For each covered cell $$$(x,y)$$$ on the rectangle, there is at least one rectangle in $$$\mathbb{S}$$$ that covers $$$(x,y)$$$ with minimum area.

Elements of $$$\mathbb{S}$$$ can be enumerated in $$$\mathcal{O}(n^2m)$$$ time by the following algorithm:

• For all pairs $$$u,d$$$ of rows, enumerate columns $$$i_1,i_2,\ldots,i_k$$$ such that $$$G_{u,i_j}=G_{d,i_j}$$$ for all $$$j$$$.

• Then, $$$(u,d,i_j,i_{j+1})$$$ is an element of $$$\mathbb{S}$$$ for all $$$1 \le j \lt k$$$.

It can be shown that the algorithm finds all elements of $$$\mathbb{S}$$$.

Then, it suffices to propagate the area of each rectangle $$$(u,d,l,r) \in \mathbb{S}$$$ to all cells covered by it.

This can be done in multiple ways, but the simplest out of all such ways is keeping a range DP for each column and propagating the values based on $$$\text{dp}[u][d] \le \text{dp}[u][d+1]$$$ and $$$\text{dp}[u][d] \le \text{dp}[u-1][d]$$$. Then, the value of $$$\text{dp}[i][i]$$$ on column $$$j$$$ becomes the answer for cell $$$(i,j)$$$.

Finally, the conditions satisfied by $$$\mathbb{S}$$$ are also satisfied when the grid is transposed, so if $$$n \gt m$$$ you can simply compute the same way on the transposed grid. This gives us a solution with $$$\mathcal{O}(nm \min(n,m))=\mathcal{O}(nm\sqrt{nm})$$$ complexity.

Enumerating all elements of $$$\mathbb{S}$$$ and saving it in memory might take $$$\mathcal{O}(nm \min(n,m))$$$ memory, but it may still pass if sufficiently optimized. There is a way to modify the solution to use only $$$\mathcal{O}(\min(n,m)(n+m))$$$ memory, which is left as a practice for the reader.

343541956

• Epic
• Good
• Moderate
• Bad
• Horrendous

Let's solve the easy version first: all $$$a_i = -1$$$.

We can convert the condition to: for $$$0 \leq i \leq n$$$, $$$a_i = \sum_{a_j=i} j$$$.

Since $$$a_0=-1$$$, we can only consider $$$j \gt 0$$$ and get $$$a_0 = \sum_{a_j=0}j$$$ automatically.

We have a claim: for a cool polynomial and all $$$i \gt 0$$$, there are only three cases:

• Case $$$1$$$: $$$a_i = 0$$$.

• Case $$$2$$$: $$$a_i = i$$$.

• Case $$$3$$$: $$$a_i = j$$$ and $$$a_j = i$$$, where $$$i \neq j$$$.

Thus, we can write an easy DP:

$$$dp_i=2dp_{i−1}+(i−1)dp_{i−2}$$$

Now, let’s return to the original problem. For all $$$a_i \neq -1$$$, we need to check whether they form "valid coefficients"(if the coefficients can represent at least one cool polynomial). After that, the problem reduces to the easy version.

There are several ways to check validity. Cases $$$1$$$ and $$$2$$$ are trivial. For Case $$$3$$$, we can use DSU to merge $$$i$$$ and $$$j$$$, and then check the size of each connected component.

343542108

• Epic
• Good
• Moderate
• Bad
• Horrendous

For this problem there exist two versions of a core observation required for solutions:

• When you discard all elements other than suffix minimums, the optimal total cost does not change. (1.a)
• Denoting optimal total cost for sequence $$$b_l,b_{l+1},\ldots,b_r$$$ as $$$\operatorname{opt}(l,r)$$$, it can be shown that $$$\operatorname{opt}(l-1,r) \ge \operatorname{opt}(l,r)$$$ for all $$$1 \lt l \le r \le n$$$. (1.b)

(1.a) can be shown by exchange arguments. Assume a partition consists mainly of two subarrays (and some irrelevant others), $$$[\dots,[x_1,\dots,x_p],\dots,[y_1,\dots,y_q,\dots,y_r],\dots]$$$. Then, if $$$x_p \ge y_q$$$, you can find a partition $$$[\dots,[x_1,\dots,y_q],[y_{q+1},\dots,y_r],\dots]$$$ which is at least good as the original one. Likewise, if $$$x_p \ge y_r$$$, you can find a partition $$$[\dots,[x_1,\dots,y_r],\dots]$$$ which is at least as good as the original one. Repeating this exchange process on any "optimal" partition, you will now have another "optimal" partition whose endpoints all belong to suffix minimums. And because then the denominator of $$$\mathtt{cost}$$$ will always lie on a suffix minimum, you can discard all of the rest without changing the total cost.

(1.b) can be shown much easier. Consider the $$$\mathcal{O}(n^2)$$$ algorithm to compute $$$\operatorname{opt}$$$. We know that $$$\operatorname{opt}(l,r)=\min\limits_{i=l}^{r}{(\operatorname{opt}(i+1,r)+c[l,i])}$$$ where $$$c[l,r]\ge 0$$$ for all $$$1 \le l \le r \le n$$$. Also, observe $$$c[l,r] \ge c[l+1,r]$$$ for all $$$l \lt r$$$. As all terms that constitute the minimum possible value of $$$\operatorname{opt}(l,r)$$$ are no less than that of $$$\operatorname{opt}(l+1,r)$$$, $$$\operatorname{opt}(l,r) \ge \operatorname{opt}(l+1,r)$$$ indeed does hold.

Both observations hold similar implications, and all subsequent observations for subtask 1 can be shown for both observations. While (1.a) is much convenient for implementing the solution for subtask 1, we will prove all subsequent observations using (1.b) because it will be reused in subtask 2 also.

We give you three solutions to solve subtask 1, two of which are helpful in solving subtask 2, while the other one is not.

For the first solution of subtask 1, we show the following.

• The optimal total cost is no greater than $$$2\log_2(a_n)$$$. (2.1.a)

We will show this by an approximate algorithm that constructs a partition that might be suboptimal.

Consider the following method to partition the sequence.

Starting from the last element of the sequence, we expand the left border of the leftmost subarray greedily:

• If it is possible to use a subarray of cost $$$2$$$, then do use it.
• Otherwise, use a subarray of cost $$$1$$$.

In either event, the rightmost element of the leftmost subarray must be strictly less than the one on the previous leftmost subarray. By contradiction, this event cannot happen more than $$$\log_2(a_n)$$$ times. As we only used subarrays of cost no greater than $$$2$$$, this algorithm always constructs a partition with total cost no greater than $$$2 \log_2(a_n)$$$.

As now we know that the optimal total cost is no greater than $$$C = 128 \ge 2 \log_2(a_n)$$$, we can optimize the $$$\mathcal{O}(n^2)$$$ DP into a solution that resembles two-pointers, but we will use $$$C$$$ pointers on one side for each possible cost. This is possible due to the monotonicity that we proved either as a corollary of (1.a) or by (1.b).

This solution has a time complexity of $$$\mathcal{O}(nC)=\mathcal{O}(n \log a)$$$.

For the second solution of the first subtask, we show the following.

• There is always an optimal solution which only uses subarrays with cost at most $$$3$$$. (2.2.a)

We will show this by exchange arguments.

Observe that for any $$$X \ge 4$$$ there exists a pair of integers $$$(x,y)$$$ that satisfies the following conditions:

• $$$x \cdot y \ge X$$$
• $$$x + y \le X$$$
• $$$1 \le x,y \lt X$$$

The proof for the above is simple; $$$x=\left \lceil {\frac{X}{2}}\right \rceil$$$ and $$$y=2$$$ satisfies the conditions for all $$$X \ge 4$$$. Then, it is possible to divide a subarray $$$A$$$ into two subarrays $$$P$$$, $$$Q$$$ such that $$$\mathtt{cost}(P) \le x$$$ and $$$\mathtt{cost}(Q) \le y$$$. Formally, assume a subarray $$$A=[A_1,A_2,\ldots,A_k]$$$ where $$$\mathtt{cost}(A)=X$$$. Let $$$A_i$$$ be the unique element for which $$$y \cdot A_i \lt A_k$$$ and $$$y \cdot A_j \ge A_k$$$ for all $$$i \lt j \le k$$$. Here, $$$A_i$$$ may be $$$A_1$$$. This element $$$A_i$$$ always exists, and we can divide $$$A$$$ into $$$P=[A_1,A_2,\ldots,A_i]$$$ and $$$Q=[A_{i+1},A_{i+2},\ldots,A_k]$$$. Then, it is easy to show that $$$\mathtt{cost}(P) \le x$$$ and $$$\mathtt{cost}(Q) \le y$$$. This defines an "exchange scheme" which will never worsen the total cost while decreasing the maximum subarray cost used.

Repeating this process on an optimal partition, the new partition has a total cost not worse than the original, and will only use subarrays with cost at most $$$3$$$.

We can show that this bound is tight by construction. Namely, the sequence $$$[3,4,8,9]$$$ has total cost $$$3$$$, and splitting it into any $$$2$$$ or more subarrays will have total cost at least $$$4$$$.

Applying this to the solution outlined in 2.1, you get a solution with time complexity $$$\mathcal{O}(n)$$$. Alternatively, you can use data structures such as segment tree for a solution with time complexity $$$\mathcal{O}(n \log n)$$$.

The third solution of the first subtask strays away from using any observation and abuses the cost function directly.

Recall that the cost function is as follows:

Considering $$$\min(a_{j+1},\ldots,a_{i})$$$ as a constant, $$$\mathtt{cost}([a_{j+1},\ldots,a_i])+\operatorname{opt}(1,j)$$$ can be regarded a linear function of $$$a_i$$$ rounded up. Therefore, we can consider using Convex Hull Trick to optimize our $$$\mathcal{O}(n^2)$$$ DP. The only caveat is how to use Convex Hull Trick with changing values of $$$\min(a_{j+1},\ldots,a_{i})$$$.

This can be resolved by maintaining values of $$$\min(a_{j+1},\ldots,a_{i})$$$ using a monotone stack. We can simply keep the minimum value of $$$\operatorname{opt}(1,j)$$$ for same values of $$$\min(a_{j+1},\ldots,a_{i})$$$. The updates that might happen on the CHT structure are maintainable if you can roll back the CHT structure (like we did the monotone stack); and a Li-Chao Tree can be rolled back quite easily as its inner behaviour is not different from a segment tree.

This leads us to a solution with time complexity $$$\mathcal{O}(n \log {1/\epsilon})$$$. Certain solutions with too big constants can get MLE under the given constraints, but there exist solutions with small enough constants that use double instead of whatever other type you might want to use. Why such solutions are still correct is left as a practice for the reader (seriously, you should be able to take a guess if you understood the other "more elegant" solutions).

Before reading, please read the solutions to the first subtask (and hopefully identify the two solutions that are helpful in solving the second subtask).

Directly applying the most optimal DP solution to the first subtask, we have a solution with $$$\mathcal{O}(n^2)$$$ time complexity. However, it seems hard to improve further as even our optimal DP has $$$\mathcal{O}(n)$$$ states and it looks like that can't be helped with.

However, we somehow already have enough resources to improve it even further; there is a way to know all values $$$\operatorname{opt}(1,r),\operatorname{opt}(2,r),\ldots,\operatorname{opt}(r,r)$$$ without using $$$\mathcal{O}(n)$$$ states.

Recall the following:

• There will be only at most $$$2\log_2(a_r)$$$ different values of $$$\operatorname{opt}(i,r)$$$. (Direct consequence of 2.1.a)
• Our DP to compute $$$\operatorname{opt}(1,r)$$$ is monotonic, i.e. $$$\operatorname{opt}(i,r) \ge \operatorname{opt}(i+1,r)$$$. (= 1.b)

Using the above, we can infer the following.

• We can model another DP by swapping the places of cost and index, and this new DP will only have at most $$$C=128 \ge 2\log_2(a_r)$$$ states.

This "swapping cost and index" might sound like it's so unexpected, but surely you may have seen such a DP formulation if you have solved many DP problems. Namely, this technique is used in Knapsack problems when the cost is small and the capacity is huge.

So, how would we formulate this DP? Let us define a new function:

• $$$\operatorname{opt}'(c,r)$$$: minimum value of $$$l$$$ such that $$$\operatorname{opt}(l,r) \le c$$$ ($$$0 \le c \le C$$$, $$$1 \le r \le n$$$).

Then, we can see by 1.b that $$$\operatorname{opt}'(c+1,r) \le \operatorname{opt}'(c,r)$$$ for all $$$0 \le c$$$. Also, after we know $$$\operatorname{opt}'(c,r)$$$ and $$$\operatorname{opt}'(c+1,r)$$$, we can compute the range of $$$l$$$ such that $$$\operatorname{opt}(l,r) = c$$$, and it lets us find the sum of $$$\operatorname{opt}(l,r)$$$ over all $$$1 \le i \le r$$$ in $$$\mathcal{O}(C)$$$ time.

So let's think of how we will compute values of $$$\operatorname{opt}'(c,r)$$$ for one $$$r$$$ in $$$\mathcal{O}(C)$$$ time.

Let us first precompute the minimum $$$l$$$ such that $$$\mathtt{cost}([a_l,a_{l+1},\ldots,a_i]) \le c$$$ for all $$$i$$$ and $$$c$$$. By 2.2.a, it suffices to compute this for only $$$1 \le c \le 3$$$. We will denote this as $$$L(i,c)$$$. These values can be easily preprocessed using walk on segment tree in $$$\mathcal{O}(n \log n)$$$ time. This will come in handy for our new DP formulation.

In the formulation of our original $$$\mathcal{O}(n)$$$ DP for the first subtask, we required a pointer for each cost $$$1 \le c \le 3$$$ on one side. On the new formulation, however, we will need some transition directly for indices. This is where the values $$$L(i,c)$$$ comes in handy.

We can find the following correct DP transition:

• $$$\operatorname{opt}'(c,r)=r+1$$$ (when $$$c \le 0$$$)
• $$$\operatorname{opt}'(c,r)= \min_\limits{1 \le k \le 3} \left ({\min_\limits{\max(\operatorname{opt}'(c-k,r)-1,0) \le i \le r}{L(i,k)}}\right )$$$ (when $$$c \gt 0$$$)

The correctness of this DP transition is shown by 1.b and 2.2.a.

Because we have already preprocessed the values of $$$L(i,1)$$$, $$$L(i,2)$$$, $$$L(i,3)$$$ in $$$\mathcal{O}(n \log n)$$$ time, we can now construct a RMQ data structure for these values in $$$\mathcal{O}(n \log n)$$$ time for $$$\mathcal{O}(1)$$$ query time. This allows us to process all values of $$$\operatorname{opt}'(c,r)$$$ for one $$$r$$$ in $$$\mathcal{O}(C)$$$ time according to the transition described above.

Computing this for each $$$r$$$ independently, we have now computed the sum of $$$\operatorname{opt}(l,r)$$$ over all $$$1 \le l \le r \le n$$$ in $$$\mathcal{O}(n \log n + n \log a)$$$ time. The problem is solved.

343542209

343542358

• Epic
• Good
• Moderate
• Bad
• Horrendous

First, we will solve the easier problem of computing just single coefficients $$$[x^k] F(n)$$$. For this, observe the following facts.

• It takes $$$\Theta((n+m) \log (n+m))$$$ time to multiply two polynomials of size $$$n$$$ and $$$m$$$ using FFT.

• However, it takes $$$\Theta(\min(n,m))$$$ time to retrieve only one coefficient from their product.

Let's consider how we can make a tradeoff between these two time complexities.

To make a meaningful tradeoff in time complexity, we can use something that resembles the Baby Step-Giant Step algorithm.

Formally, consider the following method:

• Select a constant $$$B \gt 1$$$ arbitrarily.

• For all $$$kB \le N$$$, precompute the polynomial $$$\mathcal{F}(k)=F(kB)$$$. This takes $$$\mathcal{O}(N \log N \cdot \frac{N}{B}) = \mathcal{O}(\frac{N^2}{B} \log N)$$$ time.

• For all $$$0 \le k \le B$$$, precompute $$$F(k)$$$. This takes $$$\mathcal{O}({B}^2)$$$ time.

• For each query, find the respective coefficient of $$$F(n)=\mathcal{F}({\left \lfloor{n/B}\right \rfloor}) F(n \bmod B)$$$. This takes $$$\mathcal{O}(\min(N,B))=\mathcal{O}(B)$$$ time.

Then, we achieve an algorithm that runs in $$$\mathcal{O}(\frac{N^2}{B}\log N + B^2 + QB)$$$ time. By adjusting $$$B$$$ to $$$B \approx \sqrt{N \log N}$$$, we can achieve an algorithm that runs in $$$\mathcal{O}((N+Q)\sqrt{N \log N})$$$ time.

We only have two issues left:

• We have to compute the prefix sum of $$$[x^i]F(n)$$$ instead of just $$$[x^k]F(n)$$$.
• Our algorithm is going to be slow, especially under the modulus $$$10^9+7$$$ which makes FFT quite inconvenient.

For the first issue, observe the following:

• Define a polynomial $$$G(n)$$$ of infinite degree such that $$$[x^k]G(n)=\sum_\limits{i=0}^{k}[x^i]F(n)$$$. Then, $$$G(n+m) = G(n) F(m)$$$ holds for all $$$n,m \ge 0$$$.

The proof is left as a practice for the reader.

Then, we can transform $$$\mathcal{F}(k)=F(kB)$$$ to $$$\mathcal{G}(k)=G(kB)$$$ easily in $$$\mathcal{O}(N)$$$ time for each, and then the algorithm can compute the respective coefficient of $$$G(n)=\mathcal{G}({\left \lfloor{n/B}\right \rfloor})F(n \bmod B)$$$ in $$$\mathcal{O}(\min(\infty,B))=\mathcal{O}(B)$$$ time likewise. It is not required to save infinitely many coefficients of $$$G(n)$$$; the coefficients $$$[x^k]G(n)$$$ are constant for $$$k \gt 2n$$$. Thus we have resolved the first issue.

For the second issue, observe the following:

• By expressing $$$(F(n+1))'$$$ in two ways, we can conclude that $$$n F(n) (F(1))' = (F(n))'F(1)$$$.

• Then, comparing the coefficients of both sides, we can derive the coefficients of $$$F(n)$$$ in $$$\mathcal{O}(nk)$$$ time where $$$k=\operatorname{deg}(F(1))=\mathcal{O}(1)$$$.

This gives us an alternative way to precompute polynomials $$$\mathcal{F}(k)=F(kB)$$$, and using this, the algorithm will run in $$$\mathcal{O}(\frac{N^2}{B} + B^2 + QB)$$$ time. By adjusting $$$B$$$ to $$$B \approx \sqrt{N}$$$, we achieve an algorithm that runs in $$$\mathcal{O}((N+Q)\sqrt{N})$$$ and does not use FFT. This fits nicely in the given time limit of $$$7$$$ seconds.

Depending on implementation, some smaller values of $$$B$$$ might lead to a MLE verdict. However, if this happens, your submission should fail on the first test case as the precomputation itself uses the most amount of memory. It is fine to adjust the value of $$$B$$$ larger as there is quite some margin in the time limit. Slower programming languages might also get a TLE verdict, but the implementation for the intended solution should be simple enough to be translated to C++ in a few minutes.

343542463

• Epic
• Good
• Moderate
• Bad
• Horrendous

An important observation is that $$$f(l, p+i)$$$ is unimodal for $$$1 \le i \le l$$$.

Proof: If $$$f(l, x) \lt f(l, x+1)$$$, then the snake head at time $$$T = x+1$$$ is the maximum value, and this value will not leave the snake's body until at least $$$l$$$ seconds later.

Thus, for a snake of length $$$l$$$, we can divide it into $$$\lfloor \frac{n}{l} \rfloor$$$ segments and perform ternary search on each segment. The total number of segments is $$$O(n \log n)$$$, and the total number of queries is $$$O(n \log^2 n)$$$.

We also need to handle the case where $$$f(l, M_1) = f(l, M_2)$$$. Suppose $$$i \gt 1$$$ and $$$a_{i,j} = f(l, M_1) = f(l, M_2)$$$, the snake reaches $$$a_{i,j}$$$ at time $$$T = i + j - 1$$$. We determine whether $$$M_1$$$ is in the increasing or decreasing half by querying $$$f(l, i + j - 2)$$$. A similar approach is used for $$$i = 1$$$.

After this, we obtain several monotonic contiguous segments. The classic priority queue method is used to obtain the top $$$m$$$ smallest values.

343542554

It was a segtree! Everyone who guessed segtree, good job!

It is indeed a std::map! I hope you're getting the hang of the game now.

It was a std::priority_queue! That was quite a tough one to guess.

At some point you can pretty much figure out most of the answers just by looking at the memory usage. It's actually so predictable it's really even funny! And this game even aids catching the cheaters on the list; isn't it funny for you also?

for i in range(int(input())):
    l,r,d,u=map(int,input().split())
    if l==r==d==u:
        print("Yes")
    else:
        print("No")

t = int(input())
for _ in range(t):
    n = int(input())
    sm = sum(map(int, input().split()))
    print(sm - n + 1)

t = int(input())
for _ in range(t):
    x = int(input())
    ans = -1
    for i in range(30):
        for j in range(30):
            y = (1 << i) | (1 << j)
            if y < x and x + y > (x ^ y) and y + (x ^ y) > x:
                ans = y
    print(ans)

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
 
int main()
{
    int t;cin>>t;
    for(int i=0;i<t;i++)
    {
        int n,m;cin>>n>>m;
        map<ll,ll>cnt;
        auto isqrt=[&](ll x)
        {
            ll val=sqrtl(x)+5;
            while(val*val>x)val--;
            return val;
        };
        vector<ll>a(n),r(n);
        for(ll&i:a)cin>>i;
        for(ll&i:r)cin>>i;
        for(int i=0;i<n;i++)
        {
            ll aa=a[i],rr=r[i];
            for(ll x=aa-rr;x<=aa+rr;x++)
            {
                cnt[x]=max(cnt[x],2*isqrt(rr*rr-(x-aa)*(x-aa))+1);
            }
        }
        ll ans=0;
        for(auto[x,c]:cnt)ans+=c;
        cout<<ans<<"\n";
    }
}

#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    mt19937 mt(727);
    uniform_int_distribution uni(1,3);
    int tc;cin>>tc;
    while(tc--)
    {
        int n;cin>>n;
        if(n<0)return 0;
        vector<int>vec(n);
        for(int i=0;i<n;i++)vec[i]=i+1;
        shuffle(begin(vec),end(vec),mt);
        int ii=vec[0],jj=vec[1],kk=vec[2];
        cerr<<n<<endl;
        while(1)
        {
            cout<<"? "<<ii<<" "<<jj<<" "<<kk<<endl;
            int id;cin>>id;
            if(id<0)return 0;
            if(id==0)break;
            int sw=uni(mt);
            if(sw==1)ii=id;
            else if(sw==2)jj=id;
            else kk=id;
        }
        cout<<"! "<<ii<<" "<<jj<<" "<<kk<<endl;
    }
}

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
 
int main()
{
    int t;cin>>t;
    for(int i=0;i<t;i++)
    {
        int l1,r1,l2,r2;cin>>l1>>r1>>l2>>r2;
        vector<pair<ll,ll>>it1,it2;
        auto rec=[&](auto rec,int L,int R,int l,int r,vector<pair<ll,ll>>&v)->void
        {
            if(r<=L||l>=R)return;
            if(l<=L&&R<=r)
            {
                v.emplace_back(L,R);
                return;
            }
            rec(rec,L,(L+R)/2,l,r,v);
            rec(rec,(L+R)/2,R,l,r,v);
        };
        rec(rec,0,1<<25,l1,r1,it1);
        rec(rec,0,1<<25,l2,r2,it2);
        ll ans=0;
        for(auto[al,ar]:it1)
        {
            for(auto[bl,br]:it2)
            {
                ll a=ar-al,b=br-bl;
                if(a<b)swap(a,b);
                ans+=a/b;
            }
        }
        cout<<ans<<"\n";
    }
}

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
 
ll dp[505][505];
 
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int t;cin>>t;
    for(int tc=0;tc<t;tc++)
    {
        ll n;cin>>n;
        vector<ll>vec(n);
        for(ll&i:vec)cin>>i;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)dp[i][j]=-1e18;
        }
        auto value=[&](ll i,ll j,ll k)
        {
            return i*j*k;
        };
        for(int len=1;len<=n;len++)
        {
            for(int L=0;L<n;L++)
            {
                ll ans=0;
                ll R=(L+len-1)%n;
                if(len<=2)
                {
                    dp[L][R]=0;
                    continue;
                }
                if(len==3)
                {
                    dp[L][R]=max(0LL,value(vec[L],vec[(L+1)%n],vec[R]));
                    continue;
                }
                for(int i=(L+1)%n;i!=R;i=(i+1)%n)
                {
                    ll val=value(vec[L],vec[i],vec[R]);
                    if(i!=(L+1)%n)val+=dp[(L+1)%n][(i+n-1)%n];
                    if(i!=(R+n-1)%n)val+=dp[(i+1)%n][(R+n-1)%n];
                    ans=max(ans,val);
                }
                for(int i=L;i!=R;i=(i+1)%n)
                {
                    ans=max(ans,dp[L][i]+dp[(i+1)%n][R]);
                }
                dp[L][R]=ans;
            }
        }
        ll ans=0;
        for(int i=0;i<n;i++)
        {
            ans=max(ans,dp[i][(i+n-1)%n]);
        }
        cout<<ans<<"\n";
    }
}

OpenAI o1 only solved 1 problem.

Well, we gave you enough hints in the examples. I believe you can already guess it.

for i in range(int(input())):
    x,y=map(int,input().split())
    if x==y==1:
        print(1)
    else:
        print(y-x)

Assume that you chose some two indices $$$i$$$ and $$$j$$$ included in the subsequence, such that $$$i \lt l$$$ and $$$j \gt r$$$. Does this actually help decrease the answer in any way?

import sys
input=lambda:sys.stdin.readline().rstrip()
 
for _ in range(int(input())):
    n,l,r=map(int,input().split());l-=1
    arr=[*map(int,input().split())]
    brr=arr[:l]+sorted(arr[l:])
    crr=sorted(arr[:r])[::-1]+arr[r:]
    print(min(sum(brr[l:r]),sum(crr[l:r])))

The answer after choosing two vertices is decided by the degrees of the two vertices, and whether the two vertices are adjacent. Can you find a clean solution where you don't have to care about the latter?

Sure, you can do DP on tree, but that's not what we want you to use. Think easier.

import sys
input=lambda:sys.stdin.readline().rstrip()
for i in range(int(input())):
    n=int(input())
    deg=[0]*n
    adj=[[] for i in range(n)]
    for i in range(n-1):
        u,v=map(int,input().split())
        u-=1;v-=1
        deg[u]+=1
        deg[v]+=1
        adj[u].append(v)
        adj[v].append(u)
    ans=1
    mans=0
    sdeg=sorted(deg)
    for i in range(n):
        ans=deg[i]
        ideg=[]
        for v in adj[i]:
            ideg.append(deg[v])
        ideg.append(deg[i])
        ideg.sort(reverse=True)
        rem=[]
        mx=-1
        for d in ideg:
            if sdeg[-1]==d:
                sdeg.pop()
                rem.append(d)
        rem.reverse()
        if sdeg:
            mx=max(mx,sdeg[-1])
        for v in adj[i]:
            mx=max(mx,deg[v]-1)
        for d in rem:
            sdeg.append(d)
        mans=max(ans+mx-1,mans)
    print(mans)

The maximum score $$$g(x_a,x_b)$$$ after performing $$$x_a$$$ times with two points on $$$y=0$$$, and $$$x_b$$$ times with two points on $$$y=2$$$, can be easily computed in $$$\mathcal{O}(1)$$$ time. But naively checking all possible number of operations takes $$$\mathcal{O}(nm)$$$ time. Is there a property we can abuse so that we can solve for each $$$k$$$ faster?

$$$g(x_a,x_b)$$$ is a function consisting of two prefix sums, each for a strictly decreasing sequence.

#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,m;cin>>n>>m;
    vector<ll>arr(n),brr(m);
    for(ll&i:arr)cin>>i;
    for(ll&i:brr)cin>>i;
    sort(begin(arr),end(arr));
    sort(begin(brr),end(brr));
    vector<ll>asum(n+2),bsum(m+2);
    for(int i=1;i<=n;i++)asum[i]=asum[i-1]+(arr[n-i]-arr[i-1]);
    for(int i=1;i<=m;i++)bsum[i]=bsum[i-1]+(brr[m-i]-brr[i-1]);
    vector<ll>ans{0};
    // maximize asum[ka]+bsum[kb]
    // s.t. ka+kb = x
    //      ka*2+kb <= n -> ka*2+(x-ka) <= n -> ka+x <= n   -> ka <= n-x
    //      ka+kb*2 <= m -> ka+2*(x-ka) <= m -> 2*x-ka <= m -> ka >= 2*x-m
    //      ka >= 0, x-ka >= 0
    for(int x=1;2*x-m<=n-x;x++)
    {
      ll L=max(0,2*x-m),R=min(x,n-x);
      if(L>R)break;
      auto f=[&](int ka){return asum[ka]+bsum[x-ka];};
      while(R-L>3)
      {
        ll mL=(L*2+R)/3,mR=(L+R*2)/3;
        if(f(mL)>f(mR))R=mR;
        else L=mL;
      }
      ll mans=0;
      for(int i=L;i<=R;i++)
      {
        mans=max(mans,f(i));
      }
      ans.push_back(mans);
    }
    int kmax=(int)size(ans)-1;
    cout<<kmax<<"\n";
    for(int i=1;i<=kmax;i++)cout<<ans[i]<<" \n"[i==kmax];
  }
}

When $$$(u,v)$$$ is a good pair, $$$f(u,v)$$$ is actually simply represented as follows.

Naively calculating this for all good pairs takes $$$\mathcal{O}(n^2)$$$ time. Can you find a different representation where we can count wiser?

#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--)
    {
        ll n;cin>>n;
        vector<ll>d(n,0),s(n),dc(n),dcs;
        vector<vector<ll>>adj(n);
        for(int i=1;i<n;i++)
        {
            int u,v;cin>>u>>v;
            u--;v--;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        auto dfs1=[&](auto dfs1,int v,int p=-1)->void
        {
            dc[d[v]]++;
            ll sz=1;
            for(int w:adj[v])if(w!=p)
            {
                d[w]=d[v]+1;
                dfs1(dfs1,w,v);
                sz+=s[w];
            }
            s[v]=sz;
        };
        dfs1(dfs1,0);
        dcs=dc;
        for(int i=n-2;i>=0;i--)dcs[i]+=dcs[i+1];
        ll ans=0,ans2=0;
        auto dfs2=[&](auto dfs2,int v,int p=-1)->void
        {
            // v is min
            ans+=2*d[v]*(dcs[d[v]]-s[v]);
            // v is lca
            ll subcnt=s[v]-1,lcnt=0;
            for(int w:adj[v])if(w!=p)
            {
                lcnt+=(subcnt-s[w])*s[w];
                dfs2(dfs2,w,v);
            }
            ans2+=(2*d[v]+1)*(lcnt/2);
        };
        dfs2(dfs2,0);
        for(int i=0;i<n;i++)
        {
            ans2+=i*dc[i]*(dc[i]-1);
        }
        cout<<ans-ans2<<"\n";
    }
}

The subproblem where you find the number of different balanced bracket sequences of length $$$2k$$$ is already well-known.

Now recall everyone's favorite data structure to solve problems related to balanced bracket sequences — the stack!

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll md=998244353;
 
int main()
{
    int t;cin>>t;
    vector<ll>ctl(5050);
    ctl[0]=1;
    for(int n=1;n<5050;n++)
    {
        for(int i=1;i<=n;i++)
        {
            ctl[n]=(ctl[n]+ctl[i-1]*ctl[n-i]%md)%md;
        }
    }
    while(t--)
    {
        int n;cin>>n;
        ll ans=ctl[n];
        cout<<ans<<" ";
        string s(2*n+2,'.');
        s[0]='(';s[2*n+1]=')';
        for(int a=0;a<n;a++)
        {
            int i,j;cin>>i>>j;
            ans=1;
            s[i]='(';
            s[j]=')';
            string stk;
            for(char c:s)
            {
                if(c==')')
                {
                    int cnt=0;
                    while(stk.back()!='(')
                    {
                        cnt++;
                        stk.pop_back();
                    }
                    stk.pop_back();
                    ans=(ans*ctl[cnt/2])%md;
                }
                else stk+=c;
            }
            cout<<ans<<" \n"[a+1==n];
        }
    }
}

In the solution of the easy subtask, we manually enumerated the minimal balanced subsequences, each time in $$$\mathcal{O}(n)$$$.

You can show that most minimal balanced subsequences do not change when a new clue is added. What data structure will you choose in order to utilize this fact as much as possible?

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll nil=-1;
const ll md=998244353;
 
ll pw(ll a,ll b)
{
    ll c=1;
    while(b>0)
    {
        if(b&1)c=c*a%md;
        a=a*a%md;
        b>>=1;
    }
    return c;
}
 
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    vector<ll>fac(1010101,1),ctl(505050);
    for(int i=1;i<1010101;i++)fac[i]=fac[i-1]*i%md;
    for(int i=0;i<505050;i++)
    {
        ctl[i]=fac[i*2]*pw(fac[i]*fac[i+1]%md,md-2)%md;
    }
    ll t;cin>>t;
    while(t--)
    {
        ll n;cin>>n;
        vector<ll>L(n*2,nil),R(n*2,nil),P(n*2,nil),S(n*2);
        auto update=[&](ll x)
        {
            S[x]=1;
            if(L[x]!=nil)S[x]+=S[L[x]];
            if(R[x]!=nil)S[x]+=S[R[x]];
        };
        auto rotate=[&](ll x)
        {
            ll dummy;
            ll p=P[x];
            ll b=nil;
            if(p==nil)return;
            if(x==L[p])
            {
                L[p]=b=R[x];
                R[x]=p;
            }
            else
            {
                R[p]=b=L[x];
                L[x]=p;
            }
            P[x]=P[p];P[p]=x;
            if(b!=nil)P[b]=p;
            (P[x]!=nil?p==L[P[x]]?L[P[x]]:R[P[x]]:dummy)=x;
            update(p);update(x);
        };
        auto splay=[&](ll x)
        {
            while(P[x]!=nil)
            {
                ll p=P[x];
                ll g=P[p];
                if(g!=nil)
                {
                    if((x==L[p])==(p==L[g]))rotate(p);
                    else rotate(x);
                }
                rotate(x);
            }
        };
        update(0);
        for(int i=1;i<n*2;i++)
        {
            L[i]=i-1;
            P[i-1]=i;
            update(i);
        }
        splay(0);
        ll ans=ctl[n];
        cout<<ans<<" ";
        for(int i=0;i<n;i++)
        {
            ll li,ri;cin>>li>>ri;
            //li=(li+ans%(2*n))%(2*n);
            //ri=(ri+ans%(2*n))%(2*n);
            li--;ri--;
            splay(li);
            ans=ans*pw(ctl[S[li]/2],md-2)%md;
            ll lli=L[li];
            if(L[li]!=nil)P[L[li]]=nil;
            if(R[li]!=nil)P[R[li]]=nil;
            L[li]=nil;
            R[li]=nil;
            update(li);
            // now L[li] separated from tree
            // should not be affected in splay ri
            splay(ri);
            ll lri=L[ri];
            ll rri=R[ri];
            if(L[ri]!=nil)P[L[ri]]=nil;
            if(R[ri]!=nil)P[R[ri]]=nil;
            L[ri]=nil;
            R[ri]=nil;
            update(ri);
            if(lri!=nil)
            {
                splay(lri);
                ans=ans*ctl[S[lri]/2]%md;
            }
            if(lli!=nil&&rri!=nil)
            {
                while(L[rri]!=nil)rri=L[rri];
                splay(lli);
                splay(rri);
                P[lli]=rri;
                L[rri]=lli;
                update(rri);
                ans=ans*ctl[S[rri]/2]%md;
            }
            else if(lli!=nil||rri!=nil)
            {
                if(lli!=nil)
                {
                    splay(lli);
                    ans=ans*ctl[S[lli]/2]%md;
                }
                else
                {
                    splay(rri);
                    ans=ans*ctl[S[rri]/2]%md;
                }
            }
            L[ri]=li;
            P[li]=ri;
            update(ri);
            // make dummy tree (for invariant maintaining)
            cout<<ans<<" \n"[i+1==n];
        }
    }
}

Consider maintaining the MBSes directly, but instead of using a complex data structure, we will use a small-to-large trick with linked lists. Precisely, every time we have to split a linked list, we will identify the smaller section and split it out in $$$\mathcal{O}(|small|)$$$ time, and then the amortized time complexity will be $$$\mathcal{O}(n \log n)$$$. In this solution, we do not consider bracket pairs as MBSes, for a specific reason.

Given a linked list of indices and two nodes on it, we can identify the smaller section in $$$\mathcal{O}(|small|)$$$ by iterating over both lists at the same time, interlacing the operations. The list which hit the end earlier will be the smaller one, and then we immediately know the value of $$$|small|$$$.

The issue is that you cannot identify the size of both lists in $$$\mathcal{O}(|small|)$$$ time. This is hard to fix using only a linked list. Instead, we will also maintain the implicit rooted tree structure of the bracket sequence. The MBSes correspond to vertices, and the bracket pairs correspond to edges. Initially, the tree just consists of one vertex of $$$2n$$$ brackets.

Now, for each list node, we add a pointer to the corresponding tree vertex. Now we can know which tree vertex the list node corresponds to immediately, and if we bookkeep size informations in the tree vertices, we can also find the sum of two list sizes in $$$\mathcal{O}(1)$$$. Therefore we can now know the size of both lists in $$$\mathcal{O}(|small|)$$$ time.

The only issue is with how to maintain the pointers to the tree vertices. But no problem, you can just do the small-to-large for this also. After splitting the tree vertex into two vertices and one edge, redirect the smaller list to the new smaller vertex. Theoretically there are enough ways to do this, such as swapping vertex indices. Also it is notable that it is not necessary to maintain the whole tree in this process, it is quite sufficient to just maintain it implicitly by just maintaining a sequence of sizes.

The problem is solved online with $$$\mathcal{O}(n \log n)$$$ amortized time complexity.

#pragma GCC optimize("O3,unroll-loops")

#include <iostream>
#include <numeric>
#include <vector>

constexpr int MAX_N = 3e5;
constexpr long long MOD = 998244353;

struct _inv_small {
  long long data[MAX_N + 2] = {0};
  constexpr _inv_small() {
    data[1] = 1;
    for (int i = 2; i <= MAX_N; i += 2) {
      data[i] = MOD - (MOD / i) * data[MOD % i] % MOD;
      data[i + 1] = MOD - (MOD / (i + 1)) * data[MOD % (i + 1)] % MOD;
    }
  }
};

constexpr _inv_small __inv_small;
#define inv_small(x) __inv_small.data[x]

#define inv(x) (x < MAX_N ? inv_small(x) : data[(x) - MAX_N])
struct _inv {
  long long data[MAX_N + 3] = {0};
  constexpr _inv() {
    for (int i = 0; i <= MAX_N + 1; i += 2) {
      data[i] = MOD - (MOD / (i + MAX_N)) * inv(MOD % (i + MAX_N)) % MOD;
      data[i + 1] = MOD - (MOD / (i + MAX_N + 1)) * inv(MOD % (i + MAX_N + 1)) % MOD;
    }
  }
};
#undef inv

constexpr _inv __inv;
#define inv(x) (x < MAX_N ? inv_small(x) : __inv.data[(x) - MAX_N])

struct _catalan {
  long long data[MAX_N + 2] = {1};
  constexpr _catalan() {
    for (int i = 1; i <= MAX_N; i += 2) {
      data[i] = (4 * i - 2) * data[i - 1] % MOD * inv(i + 1) % MOD;
      data[i + 1] = (4 * i + 2) * data[i] % MOD * inv(i + 2) % MOD;
    }
  }
};

constexpr _catalan __catalan;
#define catalan(x) __catalan.data[x]

struct _catalan_inv {
  long long data[MAX_N + 2] = {1};
  constexpr _catalan_inv() {
    for (int i = 1; i <= MAX_N; i += 2) {
      data[i] = inv(2) * inv(2 * i - 1) % MOD * data[i - 1] % MOD * (i + 1) % MOD;
      data[i + 1] = inv(2) * inv(2 * i + 1) % MOD * data[i] % MOD * (i + 2) % MOD;
    }
  }
};

constexpr _catalan_inv __catalan_inv;
#define catalan_inv(x) __catalan_inv.data[x]

int main() {
  std::cin.tie(0)->sync_with_stdio(0);

  int t;
  std::cin >> t;

  for (int _ = 0; _ < t; ++_) {
    int n;
    std::cin >> n;

    std::vector<bool> used(2 * n + 2);

    std::vector<int> point(2 * n + 2);
    std::iota(point.begin(), point.end(), 1);

    std::vector<int> size(2 * n + 2);

    std::vector<int> parent = {0};
    std::vector<int> parent_idx(2 * n + 2);

    used[0] = true;
    point[0] = 2 * n + 2, point[2 * n + 1] = 2 * n + 1;
    size[0] = 2 * n;

    long long ans = catalan(n);

    std::cout << ans << " ";

    for (int i = 0, l, r; i < n; ++i) {
      std::cin >> l >> r;

      point[l] = r + 1, point[r] = r;
      used[l] = true;

      int p = parent[parent_idx[l]];

      int out_ptr = p + 1, ins_ptr = l + 1;
      int out_size = 0, ins_size = 0;

      while (point[out_ptr] != out_ptr && point[ins_ptr] != ins_ptr) {
        out_size += !used[out_ptr];
        ins_size += !used[ins_ptr];
        out_ptr = point[out_ptr];
        ins_ptr = point[ins_ptr];
      }

      ans = (ans * catalan_inv(size[p] / 2)) % MOD;

      int upd_ptr;
      if (point[out_ptr] == out_ptr) {
        upd_ptr = p + 1;
        parent.push_back(p);
        parent[parent_idx[l]] = l;

        ins_size = size[p] - 2 - out_size;
        size[p] = out_size, size[l] = ins_size;
      } else {
        upd_ptr = l + 1;
        parent.push_back(l);

        out_size = size[p] - 2 - ins_size;
        size[p] = out_size, size[l] = ins_size;
      }

      ans = (ans * catalan(size[p] / 2)) % MOD * catalan(size[l] / 2) % MOD;

      while (point[upd_ptr] != upd_ptr) {
        parent_idx[upd_ptr] = parent.size() - 1;
        upd_ptr = point[upd_ptr];
      }

      std::cout << ans << " ";
    }

    std::cout << '\n';
  }
}

Simulate until you feel confident, e.g. until $$$n=10$$$. What do you see? I think the result should give you confidence.

Let us think step by step starting from $$$n=1$$$.

• If $$$n=1$$$, $$$n=l$$$ is true, therefore no swap will happen.
• If $$$n=2$$$, $$$n=l$$$ is true, therefore no swap will happen.
• If $$$n=3$$$, $$$l=1$$$, so $$$B_1$$$ and $$$B_3$$$ are swapped. Now $$$1$$$ is on index $$$3$$$.
• If $$$n \gt 3$$$, $$$l$$$ is a power of $$$2$$$, and is therefore not $$$3$$$. The index of $$$1$$$ never changes afterwards.

Therefore, if $$$n\le 2$$$, the answer is $$$1$$$. Otherwise, the answer is $$$3$$$.

An upper bound is given on the examples.

You may simply implement what is written on the description. If we had to write the size of the $$$n$$$-th super prime with the Big-O notation, it would be $$$\mathcal{O}(n \log^2 n)$$$, but such a technical analysis was not required due to the fact that we know the largest answer is $$$318 \, 137$$$ thanks to the examples. The intended solution uses the sieve of eratosthenes, but a solution using $$$\mathcal{O}(\sqrt{x})$$$ primality tests may also pass if it has small enough constants.

Fix the root of Y. The cardinality of Y contributed by this specific root is now easy to see.

After fixing the root in the graph, it is not hard to see that the cardinality of Y is determined by the number of cases to choose the three leaves. When the degree of the root is $$$k$$$, the number of cases in choosing the three leaves is as follows.

Therefore, after we compute the degree sequence, the answer is as follows.

The task did not need an understanding of modular multiplicative inverses; the value of $$${10^5 \choose 3}$$$ simply fits in long long.

Try to implement what is explicitly written in the statements. It works surprisingly fast.

If we directly implement what is written in the description, the lawnmowing process will take $$$\mathcal{O}(n)$$$ or $$$\mathcal{O}(m)$$$ in the worst case. However, we can find out that the solution will pass even if we directly implement what is written in the description. In fact, if we implement the description itself, the time complexity is not $$$\mathcal{O}((n+m)Q)$$$, but in fact $$$\mathcal{O}(nm+Q)$$$. Why is it so?

Each time the lawn mower robot mows a cell of grass, $$$\mathcal{O}(1)$$$ time is used. Also, whenever the lawn mower robot terminates, $$$\mathcal{O}(1)$$$ time is wasted. Initially there are $$$nm$$$ cells with grass, therefore the time complexity from the former is $$$\mathcal{O}(nm)$$$. Each lawn mowing process finishes exactly once every query, so the time complexity from the latter is $$$\mathcal{O}(Q)$$$. In conclusion, the total time complexity is $$$\mathcal{O}(nm+Q)$$$. This method of time complexity analysis is called "amortized analysis".

Take some time thinking how the second condition affects the optimal solution.

If we only consider the first condition of the task, this is exactly the Traveling Salesman Problem (TSP) with Euclidean metric as edge lengths. How does the second condition affect the optimal solution?

In fact, the second condition does not affect the optimal solution at all. This is due to the fact that the optimal solution always satisfy the second condition. This can be proven by contradiction.

Let us assume that the optimal solution consists of some Hamiltonian circuit $$$A \to \cdots \to B \to C \to \cdots \to D \to A$$$, where $$$B \to C$$$ and $$$D \to A$$$ contains an intersection. Let us call this intersection $$$Q$$$. Then, $$$\overline{BD} \lt \overline{BQ}+\overline{DQ}$$$ and $$$\overline{AC} \lt \overline{AQ}+\overline{CQ}$$$ holds due to triangle inequality. Therefore, $$$\overline{BD}+\overline{AC} \lt \overline{BC}+\overline{AD}$$$ holds and $$$A \to \cdots \to B \to D \to \cdots \to C \to A$$$ has a smaller cost. This contradicts the assumption.

For the triangle inequality to not hold, either $$$\triangle BDQ$$$ or $$$\triangle ACQ$$$ must be degenerate (i.e. colinear) to change the inequality into an equality. However, by definition, $$$Q$$$ is both on $$$\overline{BC}$$$ and on $$$\overline{AD}$$$. Thus, if $$$\triangle BDQ$$$ is degenerate, three points $$$B$$$, $$$C$$$, $$$D$$$ are colinear, and if $$$\triangle ACQ$$$ is degenerate, three points $$$A$$$, $$$C$$$, $$$D$$$ are colinear. This contradicts the task's constraints.

Therefore, the optimal solution of TSP already satisfies the second condition. You may well ignore the second condition and compute the optimal solution of TSP.

We made the constraints very lenient, both $$$\mathcal{O}(n!)$$$ and $$$\mathcal{O}(n!\times n)$$$ should pass. Still, some solutions explicitly checking the line-line intersection (possibly, with some branch-and-bound in the backtracking) with time complexity $$$\mathcal{O}(n!\times n^2)$$$ can pass too.

Have you tried filling every second column? The intended solution doesn't deviate much from this.

The answer to existence of solution is always YES. There are multiple constructions that satisfy the conditions, and only one is explained here.

WLOG assume $$$n \ge m$$$. (Of course it does not hurt if we don't assume this, but we get a cleaner picture if we do.) Then, let us call the area of the first two columns as $$$A$$$, and the rest as $$$B$$$. From $$$A$$$, we will find a subset $$$A'$$$ whose size is exactly half of $$$A$$$. From $$$B$$$, we will find a subset $$$B'$$$ whose size is at most half of $$$B$$$, so that $$$|A' \cup B'| \le \frac{nm}{2}$$$.

This can be constructed as follows. $$$A'$$$ is the set of all vertices on the second row. $$$B'$$$ is the set of vertices in $$$B$$$ that are on even-indexed columns. It is not hard to prove that $$$|A'| = \frac{|A|}{2}$$$ and $$$|B'| \le \frac{|B|}{2}$$$ both hold. It is also not hard to prove that $$$A' \cup B'$$$ is a connected dominating set. Thus $$$A' \cup B'$$$ is a set satisfying the conditions of the task.

Can you guess the solution with minimum cardinality of the set $$$D$$$? In fact it was answered in 2021 by the paper "Connected domination in grid graphs". The task idea did come from the paper, but well, I couldn't have implemented what's in the paper, and I don't expect that anyone could have done it in less than three hours.

The usual binary search does not work. Think smarter.

The solution looks a little similar to a greedy algorithm that decomposes a number into sum of multiple square numbers.

As the function $$$\sqrt{x-a}-b$$$ increases monotonically, it should look like we can binary search the answer. However, binary search with only $$$b$$$ can (and very often does) lead to $$$\mathcal{O}(x)$$$ error. Binary search with $$$a$$$ is impossible due to the possibility that $$$x-a \lt 0$$$ may be true, and linear search with $$$a$$$ is definitely impossible.

Before explaining the solution, we will modify the formula a little. The inequality can be modified by the following method. As $$$x-a$$$ is always nonnegative, we do not need an absolute value sign even if we square both sides of $$$\sqrt{x-a} \lt b$$$. The inequality changes to the following.

Then, simply moving $$$b^2$$$ to the left hand side, the inequality changes to the following.

Using this, we can implement the comparison without any floating point operation. Now here is the solution.

Before and after the binary search, manage the interval $$$x$$$ can be in. Initially the interval is $$$[0,10^{18}]$$$. If the current size of the interval is $$$S$$$, we can find an interval of size no greater than $$$2\left\lfloor{\sqrt{S}}\right\rfloor$$$ using binary search. Set $$$a$$$ as the left end of this interval, and binary search again. Repeating this process, $$$S$$$ becomes $$$\mathcal{O}(1)$$$ in $$$\mathcal{O}(\log \log S)$$$ steps of binary search, and we can linear search after $$$S$$$ becomes $$$\mathcal{O}(1)$$$. How many questions will we use if we follow this method?

Each binary search uses $$$\left\lfloor{\log_2(\sqrt{S})}\right\rfloor=\left\lfloor{\log_2(S)/2}\right\rfloor$$$ questions, and after each binary search, the new value of $$$\log_2(S)$$$ becomes no greater than $$$1+\left\lfloor{\log_2(S)/2}\right\rfloor$$$. Of course, there are many values of $$$x$$$ where the value can be specified during the binary search, but the analysis becomes harder if we consider this, thus we will ignore this and assume $$$\log_2(S)$$$ always turns into $$$1+\left\lfloor{\log_2(S)/2}\right\rfloor$$$. Initially $$$0 \le x \le 10^{18}$$$, so let us set $$$\log_2(S)=60$$$. On the first step, $$$\left\lfloor{\log_2(S)/2}\right\rfloor=30$$$ questions are used, and $$$\log_2(S)$$$ changes to $$$31$$$. Repeating this, the number of questions until $$$S=2\left\lfloor{\sqrt{S}}\right\rfloor=4$$$ is $$$30+15+8+4+2+2=61$$$ in the worst case. If we linear search starting from this point, we can always solve the task with no greater than $$$70$$$ questions. The constraint is relaxed to $$$75$$$ questions maximum, to allow solutions which start the linear search early.

Of course, most $$$x$$$ are not the "worst case", and $$$10^{18}$$$ is a little far from $$$2^{60}$$$. Empirically we can find that this solution is hard to exceed $$$50$$$ questions, but I did not prove this formally.

A lot of solutions exist. Not all of them have elegant implementations.

Think in terms of how many times the value changes. If we can count this, the answer translates directly to the answer we want.

There are various solutions of time complexity $$$\mathcal{O}((n+q) \log{n})$$$. It is not hard to see that this task can be solved with GNU PBDS or many other methods. The issue is, the solution using GNU PBDS requires an excessive amount of implementation. Managing intervals with a data structure is not as easy as one may think, and the constants are quite large as well. Also there is a solution which uses Segment Trees with a tuple of $$$(\text{left val},\text{right val},\text{count})$$$, but the general technique is quite overkill for this single task. Therefore, this editorial suggests a way to solve this task using the usual range sum data structures.

Do not count the number of important continuous equal intervals, but instead see the task in terms of how many times the value changes. It can be shown that the former is exactly $$$1$$$ greater than the latter. Now, we only have to find how many times the values changed using a data structure, and as the change only happens between adjacent elements, we can simply maintain that information in a data structure.

Now, manage a range sum segment tree or fenwick tree. formally, set the element as $$$0$$$ if adjacent elements are equal, and $$$1$$$ if they are different. Queries of type $$$1$$$ turn into changing at most $$$2$$$ elements in the data structure, and queries of type $$$2$$$ simply turn into range sum. As the form is what the usual Segment Tree or Fenwick Tree supports, the implementation is not so hard.

Think of a necessary condition for the cactus to be foldable. You can use just use that to proof by AC...... except the time complexity, of course.

For a cactus graph, the following condition is both necessary and sufficient for the graph to be foldable into 1 dimension.

• For each cycle, if the sum of lengths is $$$S$$$, a subset of edges with length sum $$$S/2$$$ can be found.

For this task, we do not have to necessarily prove this condition, we can just use it for "proof by AC". A proof will be given on the editorial for the hard version.

Now we must solve the Subset Sum problem for each cycle. Time complexity is the issue. The basic dynamic programming solution takes $$$\mathcal{O}(m^2l)$$$ time, thus it is too slow. Assuming there are $$$k$$$ edges with length $$$l$$$, we can divide $$$k$$$ into $$$\mathcal{O}(\log k)$$$ different lengths. Formally, to do this, there are many ways, but subtracting $$$1,2,4,\dots,2^i$$$ until $$$k$$$ is smaller than $$$2^i$$$ (and do not forget to include the leftover part of $$$k$$$!) is a popular choice. Now the number of elements is $$$\mathcal{O}(l \log m)$$$, and the time complexity is $$$\mathcal{O}(ml^2 \log m)$$$. The solution can be optimized to $$$\mathcal{O}(\frac{ml^2\log m}{w})$$$ using bitsets. When using bitsets in this task, a dynamic bitset may be needed. For C++, you may use std::tr2::dynamic_bitset<> from GCC C++ or bitset<len> with $$$len=2^k$$$, and for other languages you may use arbitrary precision integers as dynamic bitsets.

Change the cost function into a piecewise linear function. Then, you can decompose the edges into multiple edges. The proof might interest you, I suggest you to read it.

The new graph probably has some unfriendly features, such as multiple edges and negative cycles. Beware of these while implementing.

The constraints of this task is designed to be only solved when you have an elaborate understanding of the traits of convex functions and the traits of the original MCMF problem. the function $$$f(x)=ax^2+bx$$$ is convex downwards due to $$$a \ge 0$$$, and this is very important. Not only is it important that the problem is NP-Hard and thus unsolvable when $$$a \lt 0$$$, but also this task can even be solved using an MCMF implementation as a blackbox, if you can manipulate the unique traits of convex functions.

First, we transform $$$f(x)=ax^2+bx$$$ into a function $$$g(x)$$$ where all (nondifferentiable) vertices are integer points. Precisely, $$$f(x)=g(x)$$$ holds when $$$x \in \mathbb{Z}$$$, and otherwise it is defined as $$$g(x)=f(\left\lfloor{x}\right\rfloor)+(f(\left\lceil{x}\right\rceil)-f(\left\lfloor{x}\right\rfloor))(x-\left\lfloor{x}\right\rfloor)$$$. The graph of the function $$$g(x)$$$ contains only integer points of $$$f(x)$$$ as its vertices, and the rest of the points are defined as a linear combination of the points before and after $$$x$$$. This is piecewise linear, and the gradient $$$f(x+1)-f(x)$$$ is $$$2ax+a+b$$$ which is weakly increasing. Therefore, the new function $$$g(x)$$$ is convex just like $$$f(x)$$$ is. For the task to be entirely solvable, we need one more observation.

The convexity of some function can be defined not only by their derivative, but also the fact that their epigraph (or hypograph) is a convex set. Also, for all convex sets $$$A$$$ and $$$B$$$, the Minkowski sum is also well defined, and the Minkowski sum is also a convex set. Conversely, we can decompose some convex set into the Minkowski sum of some two convex sets. This task is defined as finding two sets $$$A$$$ and $$$B$$$ where $$$P=A+B$$$ holds when a convex set $$$P$$$ is given.

Let us apply this observation to the new function $$$g(x)$$$. The convexity of the function $$$g(x)$$$ is defined by that the epigraph of $$$g(x)$$$ is a convex set. Now, in the modified problem, the set of interest, the intersection of the epigraph of $$$g(x)$$$ and $$$[0,c] \times \mathbb{R}$$$, is also convex because it is the intersection of two convex sets. Can this convex set be represented as the Minkowski sum of multiple simple convex sets? This is in fact possible. For each integer $$$x$$$ in the interval $$$[0,c)$$$, define a line segment $$$L_x$$$ connecting $$$(0,0)$$$ and $$$(1,f(x+1)-f(x))$$$. Then, define $$$S_x$$$ as the epigraph of the segment $$$L_x$$$. Then, $$$S_0+S_1+S_2+\cdots+S_{c-1}$$$ is equal to the set $$$C$$$.

Now we return to the original MCMF task. Some edge has cost $$$f(x)=ax^2+bx$$$, and the capacity is $$$c$$$ units. But then, the amount of flow is an integer, thus the cost can be represented as $$$g(x)$$$ also. When $$$a=0$$$, we leave the edge as is, and if $$$a \neq 0$$$, divide the edge to $$$c$$$ duplicate edges. For the divided edges $$$E_0,E_1,E_2, \cdots, E_{c-1}$$$, the cost of $$$E_x$$$ is $$$f(x+1)-f(x)$$$, and the capacity is all $$$1$$$. If we send $$$x$$$ units of resource through these $$$c$$$ edges, the minimum cost is $$$g(x)$$$. This can be proven by the observation above, or one may prove a greedy approach themselves.

As the flow integrality theorem holds for MCMF, there is an optimal solution where all variables are integers, and such an optimal solution satisfies the condition of this task. Therefore, if we run MCMF on the new modified graph stated above, the task will be solved. However, you must consider whether the MCMF implementation works on the modified graph also. Do note that the MCMF implementation must allow duplicate edges and negative cycles to solve this task.

Bonus: Still, I did not prove that this problem is in P. For this problem to be in P, there must be an algorithm with time complexity polynomial to the input size, but the input size of $$$c$$$ is $$$\mathcal{O}(\log c)$$$. However, the task's solution is polynomial in $$$c$$$ but exponential in $$$\log c$$$, thus it does not prove whether this problem is in P or not.

We gave you a condition in the editorial of the easy version. Prove it. Also go read the blog (link), it contains the algorithm you probably should be using in this task.

In the editorial of the easy version, we gave you this condition as a sufficient and necessary condition for the cactus being foldable.

• For each cycle, if the sum of lengths is $$$S$$$, a subset of edges with length sum $$$S/2$$$ can be found.

We will now prove it for a solution to the hard version.

First, we will prove that it is sufficient. For the edges in the set $$$A$$$ with sum $$$S/2$$$, assign $$$1$$$ to the edge. For the rest, assign $$$-1$$$ to the edge. Then, run a DFS starting from an arbitrary vertex. Let the coordinate of the current vertex be $$$x_v$$$. If we pass an edge with $$$1$$$ assigned, set $$$x_u=x_v+l$$$. Otherwise, set $$$x_u=x_v-l$$$. Then, $$$|x_u-x_v|=l$$$ will hold for every edge including back edges. This is because DFS will go around each cycle always in one direction, never the other direction.

To prove that this condition is necessary is not too hard. Just take one cycle, run DFS on that cycle, and include the set of edges that goes toward the negative direction in the set $$$A$$$. Now this is a solution to the partition problem itself.

Now the issue is, the $$$\mathcal{O}(\frac{ml^2\log m}{w})$$$ solution of the easy version is not quite scalable to larger values of $$$l$$$. Luckily, there is an $$$\mathcal{O}(nc)$$$ algorithm for Subset Sum in the paper "Linear Time Algorithms for Knapsack Problems with Bounded Weights", and you can track the solution as well using the algorithm. It uses a concept of "balancing", which is hard to explain, and I would rather suggest to read the blog linked on the hints. Using that algorithm, the time complexity lowers to $$$\mathcal{O}(ml)$$$.

Now, if you solved the Subset Sum problem for each cycle and tracked the solutions, adapt the sufficiency proof directly to a solution. Assign $$$\pm 1$$$ to each edge, and run DFS on it just as explained. Then a valid assignment of $$$x_i$$$ is found. If you start the DFS with $$$x_i=0$$$, the absolute values of $$$x_i$$$ will never exceed $$$m\max(l)$$$, which is $$$10^5 \times 500$$$. This is obviously smaller than $$$10^9$$$.

Only considering the farthest $$$k$$$ points makes the proof harder. Think more openly.

Instead of the sum of the maximum $$$k$$$ distances, can we express our objective as a maximum of sums?

Instead of considering the farthest $$$k$$$ points, let's consider all subsets of points with size $$$k$$$. Then we can express our objective function like this.

This is the maximum of all $$$\displaystyle{n \choose k}$$$ sums, and as the distance function is convex, the sum of convex functions is convex, and the intersection of convex functions is convex, this objective function is convex. Then, the maximum of all subset sums would be the sum of the largest $$$k$$$ distances, therefore this objective function is equivalent to the one to maximize in this task.

Think of the objective function as how high the balloon can go at a certain 2-dimensional coordinate $$$(x,y)$$$.

The sentence "The balloon is initially placed at (0, 0) on the ground." is meaningless. In convex optimization, we reach any local maximum (which is the global maximum in convex optimization) regardless of where we begin.

We can express our objective function like this.

Why $$$({l_i}^2-(x_i - x)^2-(y_i - y)^2)$$$ without the square root? If we use the square root here, negative values will cause errors, and we may have to cut it to $$$0$$$ when the value is negative (meaning that the balloon cannot fly upwards). But in that case, the function is no longer convex. So, we must not use the square root in our objective function. For the answer, it suffices to evaluate the value of the square root of the objective function in the end. Do note that even if the objective function is concave instead of convex, we can still treat it as a convex function by inverting the sign.

Think of the objective function as literally the distance to the closest line. (Treat the line segment as a straight line)

The objective function may seem convex already, but we need it concave if we would like to maximize it. However, if the distance function is convex, how do we make it concave?

Let's define $$$\mathbf{sdist}(L,p)$$$ as a "signed distance function" from a line to a point. Basically, one side of it has positive sign, the other side of it has negative sign. In this task, the sign will be positive if the point is towards the inside of the polygon, and negative if it is not. While $$$sdist(L,p)$$$ itself is not "strictly" concave, its intersection will be strictly concave if the half-plane intersection encloses a convex polygon. (We do not have to directly understand this in this task yet) Then our objective function will be like this.

Now, as our objective function is concave, we can just solve the task normally. (or you can just switch the sign and treat it as convex)

BONUS: Did you realize that this definition of $$$f(x,y)$$$ essentially includes the whole half-plane intersection implicitly? If you did, can you use this definition on some other half-plane intersection tasks?

gets.to_i.times do
    puts eval gets
end

Yes, it did not even take 45 seconds for me to type that.

Let's reinterpret the problem as a sorting problem. Why? The question is that we would like to find a sequence of "simple permutations" $$$q$$$, where the product of each permutation in order results in the permutation from the input. The thing is, though, that "simple permutation" is essentially just a permutation with cycles of length 2 at most. Therefore, if we have a "simple permutation" denoted as $$$q$$$, then effectively $$$q = q^{-1}$$$, and therefore $$$q \circ q = q \circ q^{-1} = I$$$. Therefore, if we have $$$k$$$ "simple permutations" denoted as $$$q_1 , \ldots , q_k$$$, and $$$p = q_1 \circ \ldots \circ q_k$$$, then $$$p \circ q_k \circ \ldots \circ q_1$$$, and therefore we can simply find a sequence of "simple permutations", that "sort" the provided permutation, and then just reverse the order.

Now, here's my approach of finding the sequence of "simple permutations" that "sort" the provided permutation. I will prove that we will only need $$$O(\log M)$$$ "simple permutations" to sort the provided permutation. ($$$M$$$ here denotes the length of the longest cycle in the permutation.) This can be done through constructive proof, by finding a way to reduce a cycle of length $$$M$$$ into one of length $$$\lceil {\frac{M}{2}} \rceil$$$.

I found that, to do this, we can construct a "simple permutation" that swaps the odd-index elements and the even-index elements in one cycle. If the cycle length is odd, we leave the one leftover element where it was. Here is an example, let's say we have a permutation of length 8, having a cycle length of 8. Initially, the permutation is as follows: $$$p=[8,1,2,3,4,5,6,7]$$$. Now, we make a "simple permutation" that swaps the odd-index elements and the even-length elements. This permutation will be: $$$[2,1,4,3,6,5,8,7]$$$. Now the product of $$$p$$$ and this new permutation would be $$$[1,8,3,2,5,4,7,6]$$$. We can see that the permutation after this step has four self-loops (1,3,5,7), and one cycle of length 4 (8,2,4,6). This method guarantees that the maximal cycle length will be reduced from $$$M$$$ to $$$\lceil {\frac{M}{2}} \rceil$$$ in one step.

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<functional>
using namespace std;
using ll=long long;

template<class T>
vector<vector<T>> decomp(vector<T>&vec)
{
	bool visit[size(vec)];
	for(bool&b:visit)b=0;
	function<void(vector<T>&,int)>
	dfs=[&](vector<T>&res,int idx)->void
	{
		if(visit[idx])return;
		res.push_back(vec[idx]);
		visit[idx]=1;
		dfs(res,vec[idx]);
	};
	
	for(T&i:vec)i--;
	
	vector<vector<T>> ans;
	for(int i=0;i<size(vec);i++)
	{
		vector<T>tmp;
		if(!visit[i])
		{
			dfs(tmp,i);
			for(int&i:tmp)i++;
			ans.push_back(tmp);
		}
	}
	return ans;
}

int main()
{
	cin.tie(0)->sync_with_stdio(0);
	int q;cin>>q;
	while(q--)
	{
		int n;cin>>n;
		vector<int>v(n);
		for(int&i:v)cin>>i;
		vector<vector<int>>ans;
		while(!is_sorted(begin(v),end(v)))
		{
			vector<int>conv(n),vcp=v;
			auto dc=decomp(v);
			for(auto&vv:dc)
			{
				int sz=size(vv);
				for(int i=0;i<sz-(sz&1);i++)
				{
					conv[vv[i]-1]=vv[i^1];
				}
				if(sz&1)conv[vv[sz-1]-1]=vv[sz-1];
			}
			for(int i=0;i<n;i++)
			v[i]=vcp[conv[i]-1];
			ans.emplace_back(conv);
		}
		
		reverse(begin(ans),end(ans));
		
		cout<<size(ans)<<"\n";
		for(auto&v:ans)
		{
			for(int&i:v)cout<<i<<" ";
			cout<<"\n";
		}
	}
}