APIO was coming up in a few days, so I decided to practice. I suck at programming, so it took a while, but I finally managed to solve all 3 problems in the 2010 set.
Commando
When given a sequence and coefficients $a$, $b$, and $c$, you must calculate the maximum possible effectiveness you can achieve by splitting the original sequence into some number of subsequences. The effectiveness is calculated as followed.
- Lets say the subsequence consists of elements $x_i, x_{i+1}, \cdots , x_{i+k}$
- When $x = x_i + x_{i+1} + \cdots + x_{i+k}$, the effectiveness is calculated as $ax^2 + bx + c$
Lets define $DP_i$ as the maximum possible effectiveness possible when using up to the $i$’th number. Then, we can calculate $DP_i$ using the following equation($E_{j+1,i}$ denotes the effectiveness of soldiers $j+1$ to $i$).
\[DP_i = min_{j < i}(DP_j + E_{j+1,i})\]Using the equation above, it is possible to solve the proble in $O(N^2)$ time as it takes $O(N)$ time to calculate one $DP$ value. Lets improve this.
We can precalculate the prfix sum of the sequence, which would allow us to calculate $E$ in $O(1)$ time. Lets define $s_i$ as the prefix sum up to $i$. The $E_{j+1,i}$ can be calculated as $s_i - s_j$. Then, the above equation can be written as the following.
\[DP_i = min_{j < i}(DP_j + a(s_i - s_j)^2 + b(s_i - s_j) + c)\]The equation within $min$ can be further organized into the following.
\[-2as_js_i + as_j^2 + as_i^2 + bs_i + c\]Since the back part that only contains $s_i$ does not have anything to do with $j$, it can be calculated in $O(1)$ time. As for the other part($-2as_js_i + DP_j + as_j^2$) we can think of this as a line with slope $-2as_j$ and the y-intercept as $DP_j + as_j^2$. This is a trick known as the Convex Hull Trick(CHT). Using this trick it is possible to solve the problem in $O(N)$(as both $-2as_j$ and $DP_j + as_j^2$ are monotone).
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[1000001],la[1000001],lb[1000001];
ll a,b,c,n,p,sz;
ll x[1000001],s[1000001],k[1000001],m[1000001];
double cross(ll x, ll y){
return (double)(lb[y]-lb[x])/(la[x]-la[y]);
}
void insert(ll p, ll q){
la[sz] = p;
lb[sz] = q;
while(sz>1&&cross(sz-1,sz-2)>cross(sz-1,sz)){
la[sz-1] = la[sz];
lb[sz-1] = lb[sz];
sz--;
}
sz++;
}
ll query(ll x){
while(p+1<sz&&cross(p,p+1)<=x) p++;
return lb[p]+la[p]*x;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n;
cin >> a >> b >> c;
for(int i=1;i<=n;i++) cin >> x[i];
for(int i=1;i<=n;i++) s[i] = x[i] + s[i-1];
for(int i=1;i<=n;i++) k[i] = -2*a*s[i];
insert(k[0],m[0]);
for(int i=1;i<=n;i++){
dp[i] = query(s[i])+a*s[i]*s[i]+b*s[i]+c;
m[i] = dp[i]-b*s[i]+a*s[i]*s[i];
insert(k[i],m[i]);
}
cout << dp[n];
}
Patrol
In this problem you are given a tree with $N$ , and you must add $K$ edges to the tree($1 \leq K \leq 2$). Then, a person has to traverse the tree starting from node 1, return to node 1, and must pass through every edge(including the added ones). The problem is to find the minimum number of edges the person must pass through by adding the new edges.
Lets begin by thinking what happens if we dont add any edges. As said in the problem, if no edges are added the minimum number of edges the person must pass will be $2(N-1)$, two times the number of edges.
Now lets solve the problem when $K = 1$. By adding an edge, we are basically creating a cycle. Using the cycle, we can traverse the edges in that cycle once without haveing to revisit them. Therefore, if we create a cycle containing $L$ edges in the tree, the minimum number of edges to pass will be $2(N-1) - L + 1$(the +1 is because we have to go through the new edge).
To maximize $L$, we have to find the longest path possible in the tree. This is known as the trees diameter. Hence, when $K = 1$, we just have to calulate the length of the trees diameter, and plug it in the equation to solve the problem.
Now we must solve the problem when $K = 2$. Similarly to when $K = 1$, we are creating 2 cycles in the tree. If some edge of the tree is contained in both cycles, the minimum number of edges needed to pass becomes difficult to calculate.
However, it is possible to prove that the minimum number of edges can be achieved by creating 2 cyces that don’t overlap each other. Therefore, the above situation is not a problem.
Lets call the length of the two cycles $L_1$ and $L_2$. Then, the minimum number of edges needed will be $2(N-1) - L_1 - L_2 + 2$. Hence, we must calulate the maximum possible sum of the lengths of two disjoint paths in the tree. This can be achieved with the use of dynamic programming on trees, and a bit of case work.
Lets start by defining a few things.
- Denote $DP_i$ as the maximum length of two disjoint paths in the subtree with root $i$
- Denote $DP2_i$ as the maximum length of two disjoint paths in the subtree with root $i$, where one of the paths end at $i$
- Denote $DP3_i$ as the maximum length of a path in the subtree with root $i$
- Denote $Dep_i$ as the maximum length of a path starting from $i$ in the subtree with root $i$
$DP3$ and $Dep$ are the easiest of the bunch to fill. They can be filled as the following. $j$ denotes a child of $i$, and $Dep_x$ and $Dep_y$ are the two maximum values of $Dep$ of the childs of $i$.
\[Dep_i = max(Dep_j + 1)\] \[DP3_i = max(DP3_j, Dep_x + Dep_y + 2)\]Now lets find $DP2$. There are a total of 3 different cases.
- Both paths pass $i$
- Both paths lies entirely inside the same subtree(excluding the edge connecting $i$)
- One path lies entirely inside a subtree, while the other is in a different subtree
Each case can be solved in $O(ch_i)$ time, where $ch_i$ is the number of child nodes node $i$ has. Case 1. can be solved by simple adding the length to the 3 deepest leaf nodes. Case 2. can be solved by taking the maximum of $DP2_j + 1$ for every child node. For case 3. we can take the maximum of $DP3_j + Dep_x + 1$, where $x$ is a child node that is not $j$. By reordering all $Dep$ values in increasing order, this can also be calculated in $O(ch_i)$ time.
Finally, lets find $DP$. There are a total of 4 different cases.
- Both paths pass $i$
- No path pass $i$
- One path passes $i$ and the other lies in a subtree of $i$
- One path passes $i$ and the other lies in the subtree of a child of $i$
Each case can be solved similar to the cases of $DP2$. For case 1. add the the length to the 4 deepest leaf nodes. For case 2. add the 2 maximum values of $DP3_j$ or the maximum value of $DP_j$. For case 3. add $DP3_j$ and the lengths to the 2 deepest leaf nodes(excluding ones in the subtree of $j$). For the last case, add $DP2_j + 1$ and the length to the deepest leaf node(exluding the one in the subtree of $j$). All of these can be solved in $O(ch_i)$ time.
Implementation can be done using a single dfs function using recursion.
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
#define fastio cin.tie(0)->sync_with_stdio(0); cout.tie(0);
#define all(x) x.begin(),x.end()
#define compress(x) x.erase(unique(all(x)),x.end())
#define ff first
#define ss second
#define INF 987654321
#define MAX 500010
#define SIZE 100010
ll n,k,dis,ed;
ll dp[100010],dp2[100010],dp3[100010],dep[100010];
vector<ll> g[100010];
void k1dfs(ll x, ll d = 0, ll p = -1){
if(d>dis){
dis = d;
ed = x;
}
for(auto i:g[x]){
if(i==p) continue;
k1dfs(i,d+1,x);
}
}
void dfs(ll x, ll p = -1, ll d = 0){
ll d1=0,d2=0,d3=0;
vector<pll> vd,v3,v2;
for(int i=0;i<4;i++) vd.push_back({0,0});
for(auto i:g[x]){
if(i==p) continue;
dfs(i,x,d+1);
dep[x] = max(dep[x],dep[i]+1);
vd.push_back({dep[i]+1,i});
v3.push_back({dp3[i],i});
v2.push_back({dp2[i],i});
d2 = max(d2,dp2[i]+1);
d3 = max(d3,dp3[i]);
d1 = max(d1,dp[i]);
}
sort(all(vd),greater<pll>());
sort(all(v3),greater<pll>());
sort(all(v2),greater<pll>());
d2 = max(d2,vd[0].ff+vd[1].ff+vd[2].ff);
d3 = max(d3,vd[0].ff+vd[1].ff);
d1 = max(d1,vd[0].ff+vd[1].ff+vd[2].ff+vd[3].ff);
if(v3.size()>=2) d1 = max(d1,v3[0].ff+v3[1].ff);
for(auto i:g[x]){
if(i==p) continue;
if(i==vd[0].ss){
d2 = max(d2,dp3[i]+vd[1].ff);
}
else{
d2 = max(d2,dp3[i]+vd[0].ff);
}
if(i==vd[0].ss){
d1 = max(d1,dp3[i]+vd[1].ff+vd[2].ff);
}
else if(i==vd[1].ss){
d1 = max(d1,dp3[i]+vd[0].ff+vd[2].ff);
}
else{
d1 = max(d1,dp3[i]+vd[1].ff+vd[0].ff);
}
if(i==vd[0].ss){
d1 = max(d1,dp2[i]+vd[1].ff+1);
}
else{
d1 = max(d1,dp2[i]+vd[0].ff+1);
}
}
dp[x] = d1;
dp2[x] = d2;
dp3[x] = d3;
}
int main(){
fastio;
cin >> n >> k;
for(int i=1;i<n;i++){
ll x,y; cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
if(k==1){
k1dfs(1);
dis = 0;
k1dfs(ed);
cout << 2*(n-1)-dis+1 << "\n";
}
else{
dfs(1);
//for(int i=1;i<=n;i++) cout << dp[i] << "\n";
cout << 2*(n-1)-dp[1]+2 << "\n";
}
}
Signaling
In this problem, you have to count how many points are contained(including the ones on the boundary of) in every circle that passes three points. No three points lie on the same line, and no four points lie on the same circle.
One observation you can make is that in the case of 4 points, 2 points are contained inside a circle if the quad is convex, and only one if the quad is concave. Therefore, the number of points contained inside the circle is $2A + B$, where $A$ is the number of convex quads, and $B$ is the number of concave quads. This fact can be proven, although I won’t explain it in this blog.
Then how do we count $2A + B$? There are many ways. The way I used was by calulating $2A + 3B$, then subtracting that from $4A + 4B$. $A + B$ is just the number of quads, which is $_nC_4$. To count $2A + 3B$, I used a rotating sweep line technique. By choosing to points to be the diagonal line, one convex quad will be counted twice, while a concave quad is counted 3 times. Look at the code to see how it works.
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio cin.tie(0)->sync_with_stdio(0); cout.tie(0);
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
struct Point{
ll x,y;
bool operator < (const Point&O) const {
if(x==O.x) return y<O.y;
return x<O.x;
}
};
struct Line{
ll i,j,dx,dy;
Line(ll i, ll j, const Point&pi, const Point&pj):
i(i), j(j), dx(pj.x-pi.x), dy(pj.y-pi.y) {}
bool operator < (const Line&O) const {
return dy*O.dx < dx*O.dy;
}
};
ll n,idx[2000];
Point a[2000];
vector<Line> v;
int main(){
cin >> n;
for(int i=1;i<=n;i++) cin >> a[i].x >> a[i].y;
sort(a+1,a+1+n);
for(int i=1;i<=n;i++) idx[i] = i;
for(int i=1;i<=n;i++) for(int j=1;j<i;j++){
v.push_back(Line(i,j,a[i],a[j]));
}
sort(all(v));
ll dig = 0;
for(auto i:v){
ll u = i.i, t = i.j;
swap(idx[u],idx[t]);
swap(a[idx[u]],a[idx[t]]);
if(idx[u]>idx[t]) swap(u,t);
u = idx[u]; t = idx[t];
dig += (u-1)*(n-t);
}
dig = n*(n-1)*(n-2)*(n-3)/6-dig;
cout.precision(10);
cout << fixed << 1.0*dig/(n*(n-1)*(n-2)/6)+3 << "\n";
}