Which subsegments are relevant?

$$$a_n$$$ and $$$a_1$$$ can be taken up only by some combination of elements, not all.

Which cases of $$$n$$$ and $$$m$$$ are easy to come up with a solution? Which cases is it easy to show that no solution exist?

What happens when $$$n$$$ is even but $$$m$$$ is odd?

When can a connected component begin?

What when two '(' appear consecutively?

There are several ways to solve this problem (even bash-able with data structures like DSU and Segment Trees), but here is the one that is easiest to code.

what does $$$m \le n + 2$$$ mean?

What if we look at a spanning tree?

Does any arbitrary spanning tree work?

#include<bits/stdc++.h>
using namespace std;
using lol=long long int;
#define endl "\n"

void dfs(int u,const vector<vector<pair<int,int>>>& g,vector<bool>& vis,vector<int>& dep,vector<int>& par,string& s)
{
    vis[u]=true;
    for(auto [v,idx]:g[u])
    {
        if(vis[v])  continue;
        dep[v]=dep[u]+1;
        par[v]=u;
        s[idx]='1';
        dfs(v,g,vis,dep,par,s);
    }
}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int _=1;
cin>>_;
while(_--)
{
    int n,m;
    cin>>n>>m;
    vector<vector<pair<int,int>>> g(n+1);
    vector<pair<int,int>> edges(m);
    string s(m,'0');
    for(int i=0;i<m;i++)
    {
        int u,v;
        cin>>u>>v;
        edges[i]={u,v};
        g[u].push_back({v,i});
        g[v].push_back({u,i});
    }
    vector<bool> vis(n+1,false);
    vector<int> dep(n+1,0),par(n+1,-1);
    dfs(1,g,vis,dep,par,s);
    map<int,int> cnt;
    for(int i=0;i<m;i++)
    {
        if(s[i]=='0')
        {
            cnt[edges[i].first]++;
            cnt[edges[i].second]++;
        }
    }
    if(cnt.size()==3)
    {
        int mn=2*n+5,mx=0;
        for(auto [_,c]:cnt)
        {
            mn=min(mn,c);
            mx=max(mx,c);
        }
        if(mn==mx && mn==2)
        {
            vector<pair<int,int>> can;
            for(auto [v,_]:cnt) can.push_back({dep[v],v});
            sort(can.rbegin(),can.rend());
            int u=can[0].second;
            int i,j;    //replace edge i with edge j
            for(auto [v,idx]:g[u])
            {
                if(s[idx]=='0') i=idx;
                else if(v==par[u])    j=idx;
            }
            s[i]='1';
            s[j]='0';
        }
    }
    cout<<s<<endl;
}
return 0;
}

How will the permutation cycles look like ?

Can we fix the number of the largest sized permutation cycles and calculate the number of perfect permutations?

How do we handle the smaller permutation cycles?

Key fact: There are only $$$3$$$ kinds of cycles in almost perfect permutations: $$$(i)$$$, $$$(i, j)$$$ and $$$(i, j, i + 1, j + 1)$$$.

Proof:

• Cycle size cannot be $$$3$$$: Take $$$(a, b, c)$$$ as a cycle with $$$a < b < c$$$, then $$$p_b = a$$$, $$$p^{-1}_b = c$$$, but $$$a < b < c$$$ implies $$$\lvert a - c \rvert > 1$$$.
• Cycle size cannot be more than $$$4$$$: Let $$$(a_1, a_2, a_3, a_4, a_5, \ldots, a_k)$$$ be consecutive elements of a cycle with size $$$k$$$ ($$$k \geq 5$$$). This means $$$a_1 \ne a_5$$$, but $$$\lvert a_1 - a_3 \rvert = 1$$$ and $$$\lvert a_3 - a_5 \rvert = 1$$$. For now assume $$$a_1 - a_3 = 1$$$ (proof of $$$a_1 - a_3 = -1$$$ is very similar). This means $$$a_3 - a_5 = 1$$$ (as $$$a_1 \ne a_5$$$) and similarly $$$a_7 - a_5 = 1$$$ and so on (if $$$k \leq 6$$$, $$$a_7$$$ is basically $$$a_{7 \bmod k}$$$; i.e. it wraps around). Now, we observe that if $$$a_1 = x$$$, then $$$a_3 = x - 1$$$, $$$a_5 = x - 2$$$, $$$a_7 = x - 3$$$. Therefore $$$a_{k + 1} = x - (k + 1)$$$. But since that cycle is of size $$$k$$$, $$$a_{k + 1}$$$ = $$$a_j$$$, for some $$$j \leq k$$$. Therefore $$$(x - (k + 1)) = (x - j)$$$, for some $$$j \leq k$$$; which means $$$(k + 1) \leq k$$$ — A contradiction.
• works for any $$$2$$$ sized cycles $$$(i, j)$$$: Proof is trivial.
• works for any $$$4$$$ sized cycles $$$(i, j, i + 1, j + 1)$$$: Proof is trivial.
• works only for $$$4$$$ sized cycles $$$(i, j, i + 1, j + 1)$$$: Consider cycle $$$(a, b, c, d)$$$. $$$\lvert a - c \rvert = 1$$$, $$$\lvert b - d \rvert = 1$$$. WLOG assume $$$a < c$$$ (therefore $$$c = a + 1$$$).

1. Case I: $$$b < d$$$. therefore cycle is $$$(a, b, a + 1, b + 1)$$$ — of the given form.
2. Case II: $$$b > d$$$. therefore cycle is $$$(a, d + 1, a + 1, d)$$$, which is same as $$$(d, a, d + 1, a + 1)$$$ — also of the given form.

Special thanks to Um_nik for sharing this solution!

Let's call $$$(i)$$$ as type $$$1$$$ cycles, $$$(i,j)$$$ as type $$$2$$$ cycles and $$$(i,j,i+1,j+1)$$$ as type $$$3$$$ cycles.

What we will do, is we will fix the number of type $$$3$$$ and type $$$2$$$ cycles and come up with a formula.

Let's say there are $$$s$$$ type $$$3$$$ cycles. We need to pick $$$2s$$$ numbers from $$$[1,n-1]$$$ such that no two are adjacent. The number of ways to do this is $$$\binom{n-2s}{2s}$$$. Then we can permute these numbers in $$$(2s)!$$$ ways and group the numbers in pairs of two, but these $$$s$$$ pairs can be permuted to get something equivalent, so we need to divide by $$$s!$$$. Hence we get:

Now, for the remaining $$$(n - 4s)$$$ elements, we know that only cycles will be of length $$$2$$$ or $$$1$$$. Let $$$I_k$$$ denote the number of permutations with cycles only of length $$$2$$$ and $$$1$$$. Then the final answer would be

Now, we would be done if we found out $$$I_k$$$ for all $$$k \in {1, 2, ... n}$$$. Observe that $$$I_1 = 1$$$ and $$$I_2 = 2$$$. Further for $$$k > 2$$$, the $$$k$$$-th element can appear in a cycle of length $$$1$$$, where there are $$$I_{k - 1}$$$ ways to do it; and the $$$k$$$-th element can appear in a cycle of length two, which can be done in $$$(k - 1) \cdot I_{k - 2}$$$ ways. Therefore we finally have:

This completes the solution. Time complexity: $$$\mathcal{O}(n)$$$.

Using the observations in Solution 1 this can be reduced to a counting problem using generating functions. Details follow.

Now, from the remaining $$$n-4s$$$ numbers, let's pick $$$2k$$$ numbers to form $$$k$$$ type $$$2$$$ cycles. We can do this in $$$\binom{n-4s}{2k}$$$ ways. Like before, we can permute them in $$$(2k)!$$$ ways, but we can shuffle these $$$k$$$ pairs around so we have to divide by $$$k!$$$. Also, $$$(i,j)$$$ and $$$(j,i)$$$ are the same cycle, so we also need to divide by $$$2^k$$$ because we can flip the pairs and get the same thing.

Finally, we have the following formula:

We can simplify this to get,

Now, observe that the answer is in the form of two nested summations. Let us focus on precomputing the inner summation using generating functions. We define the following generating function:

We can compute the first few terms of $$$e^x = \sum_{i \ge 0}{\frac{x^{i}}{i!}}$$$ and $$$e^{\frac {x^2}{2}} = \sum_{j \ge 0}{ \frac{x^{2j}}{2^j j!}}$$$; and using FFT, we can multiply these (in $$$\mathcal O(n \log n)$$$ time) to get the first few terms of $$$P(x) = e^{x + \frac{x^2}{2}}$$$.

Finally, we can get the answer (in $$$\mathcal O(n)$$$ time) as,

where $$$[x^m]F(x)$$$ is the coefficient of $$$x^m$$$ in the Taylor expansion of $$$F(x)$$$.

Time complexity: $$$\mathcal{O}(\max{(t_i)}\log{\max{(t_i)}} + \sum{t_i})$$$, where $$$t_i$$$ is the value of $$$n$$$ in the $$$i$$$-th test case.

There are solutions to this problem using lazy segment trees, or say, sets and maps. I'll describe my own solution here, which converts the problem to a shortest paths problem.

First of all, the $$$d_i$$$ are irrelevant, since we can take partial sums and add them to $$$c_i$$$. In the final answer, just add the sum of all $$$d_i$$$.

Now, we can offset the green (or red) intervals by the modified $$$c_i$$$ to get new red and green intervals modulo $$$T$$$.

Imagine $$$n$$$ parallel lines of length $$$T$$$, with the corresponding intervals coloured red and green. Now, consider the intervals to be static. In this picture, the car can be visualised to be moving upwards along the line (looping back at $$$T$$$) when on red intervals and shooting to the right when it reaches a green interval. Notice that for a fixed starting time, it is always optimal to drive whenever you can. So essentially, fixing your start time also fixes your answer.

Now let's convert this to a graph. Notice that only the endpoints of green intervals matter, so overall, we'll have $$$2n$$$ nodes in our graph, plus a dummy node representing the start of the journey that connects to all endpoints that can be reached without being blocked by a red interval, and a dummy node representing the end of the journey that connects to all endpoints from which you can reach the end without being blocked by a red interval. So in total, $$$2n+2$$$ nodes.

We'll add an edge between two nodes with a weight equal to the amount of time we'll have to spend waiting for the red light to turn green. We can achieve this with a multiset storing all currently visible endpoints, and then doing a little casework to add edges from nodes blocked by the current red interval and then deleting them, and adding new ones. We'll do this only $$$\mathcal{O}(n)$$$ times. In the end, whatever is left in the multiset are all the visible endpoints and we can connect them to the dummy node for the end. We can repeat this in the backward direction to get the endpoints for the dummy node for the start, though in my code, I elected to do this with an interval union data structure.

Finally, just run Dijkstra's algorithm on this graph. The answer is the sum of all $$$d_i$$$ plus the shortest path between the dummy node for the start and the dummy node for the end.

Time complexity: $$$\mathcal{O}(n \log n)$$$

#include<bits/stdc++.h>
using namespace std;
using lol=long long int;
const lol inf=1e18+8;
 
struct IntervalUnion{
    set<int> lf,ri;
    map<int,int> lr,rl;
    void add(int l,int r)
    {
        if(!ri.empty())
        {
            auto it=ri.lower_bound(r);
            if(it!=ri.end() && rl[*it]<=l)  return;
        }
        while(!lf.empty())
        {
            auto it=lf.lower_bound(l);
            if(it==lf.end() || r<*it)    break;
            int nl=*it;
            r=max(r,lr[nl]);
            rl.erase(lr[nl]);
            ri.erase(lr[nl]);
            lr.erase(nl);
            lf.erase(nl);
        }
        while(!ri.empty())
        {
            auto it=ri.lower_bound(l);
            if(it==ri.end() || r<rl[*it])   break;
            int nl=rl[*it];
            l=min(l,nl);
            rl.erase(lr[nl]);
            ri.erase(lr[nl]);
            lr.erase(nl);
            lf.erase(nl);
        }
        lf.insert(l);
        ri.insert(r);
        lr[l]=r;
        rl[r]=l;
    }
    bool contains(int x)
    {
        auto it=ri.upper_bound(x);
        if(it==ri.end())    return false;
        return rl[*it]<=x;
    }
};
 
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,t;
cin>>n>>t;
vector<pair<int,int>> gc(n);
for(auto& [g,c]:gc) cin>>g>>c;
lol sum=0;
for(int i=1;i<n;i++)
{
    int d;
    cin>>d;
    sum+=d;
    gc[i].second=(gc[i].second+(sum%t))%t;
}
vector<vector<pair<int,int>>> gr(2*n+2);
multiset<pair<int,int>> ms;
IntervalUnion iu;
for(int i=0;i<n;i++)
{
    auto [g,c]=gc[i];
    int l=(g-c+t)%t,r=t-c;
    if(l<r)
    {
        while(!ms.empty())
        {
            auto it=ms.lower_bound({l,-1});
            if(it==ms.end() || it->first>=r)    break;
            gr[2*i].push_back({it->second,r-it->first});
            ms.erase(it);
        }
    }else
    {
        while(!ms.empty())
        {
            auto it=ms.lower_bound({l,-1});
            if(it==ms.end() || it->first>=t)    break;
            gr[2*i].push_back({it->second,r+t-it->first});
            ms.erase(it);
        }
        while(!ms.empty())
        {
            auto it=ms.lower_bound({0,-1});
            if(it==ms.end() || it->first>=r)    break;
            gr[2*i].push_back({it->second,r-it->first});
            ms.erase(it);
        }
    }
    ms.insert({r%t,2*i});
    ms.insert({(l-1+t)%t,2*i+1});
    if(!iu.contains(r%t)) gr[2*i].push_back({2*n+1,0});
    if(!iu.contains((l-1+t)%t)) gr[2*i+1].push_back({2*n+1,0});
    if(l<r) iu.add(l,r);
    else
    {
        iu.add(l,t);
        iu.add(0,r);
    }
}
while(!ms.empty())
{
    auto it=ms.begin();
    gr[2*n].push_back({it->second,0});
    ms.erase(it);
}
//do dijkstra on this graph
vector<lol> sp(2*n+2,inf);
priority_queue<pair<lol,int>,vector<pair<lol,int>>,greater<pair<lol,int>>> pq;
pq.push({0,2*n});
sp[2*n]=0;
while(!pq.empty())
{
    auto [dist,u]=pq.top();
    pq.pop();
    if(dist>sp[u])   continue;
    for(auto [v,w]:gr[u])
    {
        if(dist+w<sp[v])
        {
            sp[v]=dist+w;
            pq.push({sp[v],v});
        }
    }
}
cout<<sum+sp[2*n+1];
return 0;
}

#include<bits/stdc++.h>

#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first 
#define ss second
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define FOR(i,N) for(i=0;i<(N);++i)
#define FORe(i,N) for(i=1;i<=(N);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,N) for(i=(N);i>=0;--i)
#define F0R(i,N) for(int i=0;i<(N);++i)
#define F0Re(i,N) for(int i=1;i<=(N);++i)
#define F0Rr(i,a,b) for(ll i=(a);i<(b);++i)
#define F0Rrev(i,N) for(int i=(N);i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define dbgLine cerr<<" LINE : "<<__LINE__<<"\n"
#define ldd long double

using namespace std;

const int Alp = 26;
const int __PRECISION = 9;
const int inf = 1e9 + 8;

const ldd PI = acos(-1);
const ldd EPS = 1e-7;

const ll MOD = 998244353;
const ll MAXN = 260007;
const ll ROOTN = 320;
const ll LOGN = 18;
const ll INF = 1e18 + 1022;

int N;
int A[MAXN];
bool B[MAXN];
vi a[2];
pii people[MAXN];
ll fact[MAXN + 1], ifact[MAXN + 1];


ll fxp(ll a, ll n){
	if(n == 0) return 1;
	if(n % 2 == 1) return a * fxp(a, n - 1) % MOD;
	return fxp(a * a % MOD, n / 2);
}

ll inv(ll a){
	return fxp(a % MOD, MOD - 2);
}
void init(){
	fact[0] = ifact[0] = 1;
	F0Re(i, MAXN){
		fact[i] = fact[i - 1] * i % MOD;
		ifact[i] = inv(fact[i]);
	}
}

struct SegTree_sum{
	int st[4*MAXN];
	void upd(int node, int ss, int se, int i, int val){
		if(ss > i or se < i)	return;
		if(ss == se)	{st[node] += val; return;}
		int mid = (ss + se) / 2;
		upd(node*2+1, ss, mid, i, val);
		upd(node*2+2, mid+1, se, i, val);
		st[node] = st[node*2+1] + st[node*2+2];
	}
	int quer(int node,int ss, int se, int l, int r){
		if(ss > r or se < l)	return 0;
		if(ss >= l and se <= r)	return st[node];
		int mid = (ss + se)/2;
		return quer(node*2+1, ss, mid, l ,r) + quer(node*2+2, mid + 1, se, l,r);
	}
	SegTree_sum()	{F0R(i, MAXN*4) st[i] = 0;}
	inline void update(int i, int val) {upd(0, 0, 2 * MAXN, i, val);}
	inline int query(int l, int r) {return quer(0, 0, 2 * MAXN, l, r);}
}S_sum;

struct Segtree_max{
	int st[4 * MAXN], lz[4 * MAXN];
	inline void push(int node, int ss, int se){
		if(lz[node] == 0) return;
		st[node] += lz[node];
		if(ss != se) lz[node * 2 + 1] += lz[node], lz[node * 2 + 2] += lz[node];
		lz[node] = 0;
	}
	void upd(int node, int ss, int se, int l, int r, int val){
		push(node, ss, se);
		if(ss > r or se < l) return;
		if(ss >= l and se <= r) {lz[node] += val; push(node, ss, se); return;}
		int mid = (ss + se)/2;
		upd(node * 2 + 1, ss, mid, l, r, val);
		upd(node * 2 + 2, 1 + mid, se, l, r, val);
		st[node] = max(st[node * 2 + 1], st[node * 2 + 2]);
	}
	int quer(int node, int ss, int se, int tar){
		push(node, ss, se);
		if(st[node] < tar || st[node] > tar){
			return -1;
		}
		if(ss == se){
			return ss;
		}
		int mid = (ss + se) / 2;
		push(node * 2 + 1, ss, mid);
		push(node * 2 + 2, mid + 1, se);
		return (st[node * 2 + 2] < tar) ? quer(node * 2 + 1, ss, mid, tar) : quer(node * 2 + 2, mid + 1, se, tar);
	}
	Segtree_max() {F0R(i,MAXN * 4) st[i] = - 10 * MAXN, lz[i] = 0;}
	inline void update(int l, int r, ll val) {if(l <= r) upd(0, 0, 2 * MAXN, l, r, val);}
	inline ll query(int v) {return quer(0, 0, 2 * MAXN, v);}
}S_max;

signed main(){

	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	init();
	cin >> N;
	F0R(i, N){
		cin >> A[i];
	}
	F0R(i, N){
		cin >> B[i];
	}

	F0R(i, N){
		a[B[i]].pb(A[i]);
		people[i] = {A[i], B[i]};
		S_sum.update(A[i], 1);
	}

	sort(all(a[0]));
	sort(all(a[1]));
	sort(people, people + N);
	int m = people[0].ff;
	int M = people[N - 1].ff;
	int T = people[0].ff + N - 1;

	if(m == M){
		cout << fact[N] << '\n';
		return 0;
	}else if(people[0].ss == 0){
		cout << "0\n";
		return 0;
	}else if(M > T){
		cout << "0\n";
		return 0;
	}

	int T_cnt = 0;

	F0R(i, (int)a[1].size()){
		if(a[1][i] == T){
			++T_cnt;
		}else if(i + 1 < (int)a[1].size() && a[1][i] == a[1][i + 1]){
			cout << "0\n";
			return 0;
		}
	}

	ll ans = fact[N] * ifact[N - T_cnt] % MOD;
	int p = -1, t = 0;
	for(int x : a[0]){
		if(p != x){
			ans = ans * fact[t] % MOD;
			t = 0;
		}
		++t;
		p = x;
	}
	ans = ans * fact[t] % MOD;

	int ptr = 0;

	for(int x : a[1]){
		if(x == T){
			break;
		}
		int y = x + S_sum.query(x + 1, 2 * MAXN);
		S_max.update(x, x, y + 10 * MAXN);
	}

	vii sequence(T_cnt, mp(T, 1));

	F0R(i, N - T_cnt){
		int zero = T + 1, one = T + 1;
		if(ptr < (int)a[0].size() && S_sum.query(1, a[0][ptr] - 1) + a[0][ptr] == T){
			zero = a[0][ptr];
		}
		one = S_max.query(T);
		if(one == -1 && zero == T + 1){
			cout << "0\n";
			return 0;
		}
		if(zero == T + 1 || one >= zero){
			sequence.pb({one, 1});
			S_max.update(one, one, - 10 * N);
			S_max.update(one + 1, T - 1, 1);
			S_sum.update(one, -1);
			S_sum.update(T, 1);
		}else{
			sequence.pb({zero, 0});
			S_sum.update(zero, -1);
			S_sum.update(T, 1);
			S_max.update(zero, T - 1, 1);
			++ptr;
		}
	}
	cout << ans << '\n';
	
	return 0;
}

What role does the angles of the polygon play?

Is there some overlap in the area of two such regions? How do we account for that?

#include<bits/stdc++.h>
using namespace std;
using lol=long long int;
using ldd=long double;
#define endl "\n"
const ldd PI=acos(-1.0);
const int ITERATIONS = 60;
const int PRECISION = 11;

struct Point{
    lol x,y;
    Point& operator-=(const Point& rhs){
        x-=rhs.x,y-=rhs.y;
        return *this;
    }
    friend Point operator-(Point lhs,const Point& rhs){
        lhs -= rhs;
        return lhs;
    }
};
std::istream& operator>>(std::istream& is, Point& obj){
    is>>obj.x>>obj.y;
    return is;
}

ldd norm(Point p){
    return p.x*p.x+p.y*p.y;
}
ldd cross_product(Point a,Point b){
    return a.x*b.y-a.y*b.x;
}
ldd dot_product(Point a,Point b){
    return a.x*b.x+a.y*b.y;
}
ldd getalpha(Point a,Point b,Point c){
    return atan2l(cross_product(c-b,a-b),dot_product(c-b,a-b));
}
ldd getarea(Point a,Point b,Point c){
    Point l1=c-b,l2=a-b;
    return (dot_product(l1,l2)/cross_product(l1,l2)+atan2l(cross_product(l1,l2),-dot_product(l1,l2))*((norm(l1)*norm(l2))/(cross_product(l1,l2)*cross_product(l1,l2))+2.0))/16.0;
}

ldd f(ldd theta, ldd alpha){
	return -cos(theta)+(1.0/tan(alpha))*sin(theta) + (cos(theta)*(1.0/tan(alpha))+sin(theta)) * (sin(2*theta)/2.0);
}
ldd g(ldd theta, ldd alpha){
	return (cos(theta)*(1.0/tan(alpha))+sin(theta)) * (1.0 - cos(2*theta))/2.0;
}
ldd get_x(ldd y, ldd alpha, ldd & theta){
	ldd lo = alpha, hi = PI;
	for(int it = 0; it < ITERATIONS; ++it){
		theta = (lo + hi) / 2.0;
		ldd y_guess = g(theta, alpha);
		if(y > y_guess){
			hi = theta;
		}else{
			lo = theta;
		}
	}

	return f(theta, alpha);
}
ldd A(ldd theta, ldd alpha){
	return (sin(2 * (alpha - 3 * theta)) - sin(2 * (alpha - 2 * theta)) - 4 * sin(2 * (alpha - theta)) - sin(2 * (alpha + theta))
			- 4 * theta * cos(2 * alpha) + 8 * theta - 2 * sin(4 * theta)) / (64.0 * sin(alpha) * sin(alpha));
}
ldd find_overlap_area(ldd alpha_1, ldd alpha_2, ldd L){

	ldd lo = 0, hi = sin(max(alpha_1, alpha_2));
	ldd theta_1 = PI, theta_2 = PI;

	for(int it = 0; it < ITERATIONS; ++it){
		ldd mid_y = (lo + hi) / 2;
		ldd x1 = get_x(mid_y, alpha_1, theta_1);
		ldd x2 = L - get_x(mid_y, alpha_2, theta_2);
		if(x1 < x2){
			hi = mid_y;
		}else{
			lo = mid_y;
		}

	}

	return (A(PI, alpha_1) + A(PI, alpha_2)) - (A(theta_1, alpha_1) + A(theta_2, alpha_2));
}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin>>n;
vector<Point> v(n);
for(auto& p:v)  cin>>p;
if(n == 4){
    int MY = max({v[0].y, v[1].y, v[2].y, v[3].y});
    int my = min({v[0].y, v[1].y, v[2].y, v[3].y});
    int MX = max({v[0].x, v[1].x, v[2].x, v[3].x});
    int mx = min({v[0].x, v[1].x, v[2].x, v[3].x});
    if(MY - my == 1 || MX - mx == 1){
        cout << fixed << setprecision(PRECISION) << 1.0 * (MY - my) * (MX - mx) << endl;
        exit(0);
    }
}
double ans=0.0;
for(int i=0;i<n;i++){
    ans+=getarea(v[(i-1+n)%n],v[i],v[(i+1)%n]);
}
for(int i=0;i<n;i++){
    Point a=v[(i-1+n)%n],b=v[i],c=v[(i+1)%n],d=v[(i+2)%n];
    if(norm(c-b)<3){
        ans-=find_overlap_area(getalpha(a,b,c),getalpha(b,c,d),sqrt(norm(c-b)));
    }
}
cout<<fixed<<setprecision(PRECISION)<<ans;
return 0;
}

#include<bits/stdc++.h>
using namespace std;
using lol=long long int;
#define endl "\n"
 
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int _=1;
cin>>_;
while(_--)
{
    int n,r,b;
    cin>>n>>r>>b;
    int p=r/(b+1),q=r%(b+1);
    for(int i=0;i<q;i++)    cout<<string(p+1,'R')<<'B';
    for(int i=q;i<b;i++)    cout<<string(p,'R')<<'B';
    cout<<string(p,'R');
    cout<<endl;
}
return 0;
}

t = int(input())
for i in range(t):
    n, r, b = map(int, input().split())
    p = r % (b + 1)
    y = ""
    for j in range(int(r / (b + 1))):
        y = y + "R"
    ans = ""
    for i in range(b + 1):
        if i > 0:
            ans = ans + "B"
        ans = ans + y
        if p > 0:
            ans = ans + "R"
            p = p - 1
    print(ans)

• Good problem:
• Average problem:
• Bad problem:
• Did not solve:

#include<bits/stdc++.h>
using namespace std;
using lol=long long int;
#define endl "\n"
 
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int _=1;
cin>>_;
while(_--)
{
    int n,k;
    cin>>n>>k;
    string s;
    cin>>s;
    vector<int> f(n,0);
    int tmpk=k;
    for(int i=0;i<n && tmpk>0;i++)
    {
        if(k%2==s[i]-'0')
        {
            f[i]=1;
            tmpk--;
        }
    }
    f[n-1]+=tmpk;
    for(int i=0;i<n;i++)
    {
        if((k-f[i])%2==1)   s[i]='1'-(s[i]-'0');
    }
    cout<<s<<endl;
    for(auto& e:f)  cout<<e<<" ";
    cout<<endl;
}
return 0;
}

t = int(input())
for i in range(t):
    n, k = map(int, input().split())
    kc = k
    s = input()
    f = [0] * n
    ans = ""
    for i in range(n):
        if k == 0:
            break
        if kc % 2 == 1 and s[i] == '1':
            f[i] = f[i] + 1
            k = k - 1
        elif kc % 2 == 0 and s[i] == '0':
            f[i] = f[i] + 1
            k = k - 1
    f[n - 1] = f[n - 1] + k
    for i in range(n):
        flip = kc - f[i]
        if flip % 2 == 0:
            ans = ans + s[i]
        else:
            if s[i] == '1':
                ans = ans + '0'
            else:
                ans = ans + '1'
    print(ans)
    for i in range(n):
        print(f[i], end = ' ')
    print()

• Good problem:
• Average problem:
• Bad problem:
• Did not solve:

#include<bits/stdc++.h>
using namespace std;
using lol=long long int;
#define endl "\n"
const lol inf=1e18+8;
 
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int _=1;
cin>>_;
while(_--)
{
    int n;
    lol a,b;
    cin>>n>>a>>b;
    vector<lol> x(n+1),p(n+1);
    x[0]=0;
    for(int i=1;i<=n;i++)   cin>>x[i];
    partial_sum(x.begin(),x.end(),p.begin());
    lol ans=inf;
    for(int i=0;i<=n;i++)
    {
        ans=min(ans,(a+b)*(x[i]-x[0])+b*(p[n]-p[i]-(n-i)*x[i]));
    }
    cout<<ans<<endl;
}
return 0;
}

• Good problem:
• Average problem:
• Bad problem:
• Did not solve:

#include<bits/stdc++.h>
using namespace std;
using lol=long long int;
#define endl "\n"
 
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int _=1;
cin>>_;
while(_--)
{
    int n;
    cin>>n;
    vector<lol> v(n);
    for(auto& e:v)  cin>>e;
    int k=accumulate(v.begin(),v.end(),0ll)/n;
    vector<int> b(n),ans(n,0);
    int lf=n-k;
    for(int i=lf;i<n;i++)   b[i]=n-1;
    for(int i=n-1;i>=0 && lf<=i;i--)
    {
        int cur=v[i]-(b[i]-i);
        if(cur==i+1)    ans[i]=1;
        else if(cur==1)
        {
            ans[i]=0;
            lf--;
            b[lf]=i-1;
        }
    }
    for(auto& e:ans)    cout<<e<<" ";
    cout<<endl;
}
return 0;
}

• Good problem:
• Average problem:
• Bad problem:
• Did not solve:

Try to solve this problem if it is possible for invalid $$$C$$$ to be given as input. This was the original version of the problem, but testers struggled a lot with it. The solution to this is still used in the validator.

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/rope>
 
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define gcd __gcd
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define rep(i, n) for (int i=0; i<(n); i++)
#define rep1(i, n) for (int i=1; i<=(n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define endl "\n"
 
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned uint;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
template<typename T, typename cmp = less<T>>
using ordered_set=tree<T, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> pref_trie;
 
struct dsu {
    vi d;
    dsu(int n) : d(n, -1) {}
    int find(int x) {return d[x] < 0 ? x : d[x] = find(d[x]);}
    void join(int x, int y) {
        x = find(x), y = find(y);
        if(x == y) return;
        if(d[x] > d[y]) swap(x, y);
        d[x] += d[y]; d[y] = x;
    }
    bool is_joined(int x, int y) {
        return find(x) == find(y);
    }
};
 
int32_t main() {
    fastio;
    int n, m; cin >> n >> m;
    vector<tuple<int, int, int>> edges;
    rep(i, m) {
        int u, v, w; cin >> u >> v >> w;
        edges.eb(--u, --v, w);
    }
    vector<dsu> zero(30, n), one(30, n);
    rep(j, 30) {
        for(auto& [u, v, w]: edges) if(w >> j & 1) {
            zero[j].join(u, v);
        }
    }
    vb even(n);
    rep1(j, 29) {
        for(auto& [u, v, w]: edges) if((w >> j & 1)) {
            one[j].join(u, v);
        }
        vb vis(n);
        for(auto& [u, v, w]: edges) if(!(w & 1)) {
            vis[one[j].find(u)] = 1;
            vis[one[j].find(v)] = 1;
        }
        rep(i, n) if(vis[one[j].find(i)]) even[i] = 1;
    }
    auto check = [&](int u, int v) -> int {
        rep(j, 30) if(zero[j].is_joined(u, v)) return 0;
        if(even[u]) return 1;
        rep1(j, 29) if(one[j].is_joined(u, v)) return 1;
        return 2;
    };
    int q; cin >> q;
    while(q--) {
        int u, v; cin >> u >> v; --u, --v;
        cout << check(u, v) << endl;
    }
}

• Good problem:
• Average problem:
• Bad problem:
• Did not solve:

Try to solve this problem if the queries were for longest walk instead.

#include<bits/stdc++.h>
using namespace std;
using lol=long long int;
#define endl "\n"
 
pair<int,int> dfs(int u,const vector<vector<int>>& g,int p=-1) //returns {node with max dist,max dist}
{
    pair<int,int> res{u,0};
    int mx=0;
    for(auto v:g[u])
    {
        if(v==p)    continue;
        pair<int,int> cur=dfs(v,g,u);
        cur.second++;
        if(mx<cur.second)
        {
            res=cur;
            mx=cur.second;
        }
    }
    return res;
}
 
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int _=1;
cin>>_;
while(_--)
{
    int n,x;
    cin>>n>>x;
    vector<vector<int>> g(n+1);
    vector<int> p(n+1),deg(n+1,0);
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
        deg[u]++,deg[v]++;
    }
    for(int i=1;i<=n;i++)
    {
        cin>>p[i];
    }
    //find diameter of tree with 2 DFSes
    int diam=dfs(dfs(1,g).first,g).second;
    //if diam>=3, Alice always wins
    //if diam=1, n=2, have to check if p=[1,2]
    //otherwise we have a star graph and cases follow
    if(diam>=3) cout<<"Alice";
    else if(diam==1)    cout<<((p[1]==1)?"Alice":"Bob");
    else
    {
        //we need to check if we have already won or can win in the first move
        //this is possible if the permutation is already sorted
        //or if there are two marked elements and the chip is on neither of them
        vector<int> marked;
        for(int i=1;i<=n;i++)
        {
            if(p[i]!=i) marked.push_back(i);
        }
        if((int)marked.size()==0)
        {
            cout<<"Alice";
        }else if((int)marked.size()==2 && (x!=marked[0] && x!=marked[1]))
        {
            cout<<"Alice";
        }else
        {
            //we haven't won yet and it is not possible to win in one move
            //cases follow
            //first find center, it will have deg>1
            int center;
            for(int i=1;i<=n;i++)
            {
                if(deg[i]>1)
                {
                    center=i;
                    break;
                }
            }
            //is chip on center?
            bool chiponcenter=(x==center);
            //is center marked?
            bool centerismarked=(find(marked.begin(),marked.end(),x)!=marked.end());
            //list the cycles
            vector<int> vis(n+1,false);
            vector<vector<int> > cycles;
            for(int i=1;i<=n;i++)
            {
                if(vis[i])  continue;
                int j=i;
                cycles.push_back({j});
                vis[j]=true;
                while(!vis[p[j]])
                {
                    cycles.back().push_back(p[j]);
                    vis[p[j]]=true;
                    j=p[j];
                }
            }
            //min number of swaps
            int swapcnt=0;
            for(auto& cycle:cycles) swapcnt+=(int)cycle.size()-1;
            //parity
            int parity=(swapcnt+!chiponcenter)%2;
            //cases
            if(!centerismarked)    cout<<(parity?"Alice":"Bob");
            else if(chiponcenter && centerismarked)  cout<<"Bob";
            else    //chip not on center and center is marked
            {
                //need to check if we can unmark center on first move
                //it is impossible if x is on p[center] (since we need to move p[center] to get center
                //to the right place, but p[center] is blocked)
                bool cannotunmarkcenter=(p[center]==x);
                if(cannotunmarkcenter)  cout<<"Bob";
                else    cout<<(parity?"Alice":"Bob");
            }
        }
    }
    cout<<endl;
}
return 0;
}

• Good problem:
• Average problem:
• Bad problem:
• Did not solve:

Since the maximum possible number of pairings is $$$10395$$$, I could just check all possible pairings for a cycle. But I'm not sure how I would implement this.

I have no clue. I do not think a brute force would work here.

I can precalculate shortest paths between the pharmacies, fixing the starting and ending. Then for every other vertex, I could take the minimum over all choices of starting and ending pharmacies. Then I could take the overall minimum. It works, but I'm having trouble implementing so much neatly.