A The Fair Nut and the Best Path
Description
The Fair Nut is going to travel to the Tree Country, in which there are $n$ cities. Most of the land of this country is covered by forest. Furthermore, the local road system forms a tree (connected graph without cycles). Nut wants to rent a car in the city $u$ and go by a simple path to city $v$. He hasn’t determined the path, so it’s time to do it. Note that chosen path can consist of only one vertex.
A filling station is located in every city. Because of strange law, Nut can buy only $w_i$ liters of gasoline in the $i-th$ city. We can assume, that he has infinite money. Each road has a length, and as soon as Nut drives through this road, the amount of gasoline decreases by length. Of course, Nut can’t choose a path, which consists of roads, where he runs out of gasoline. He can buy gasoline in every visited city, even in the first and the last.
He also wants to find the maximum amount of gasoline that he can have at the end of the path. Help him: count it.
Idea
I guess you have noticed that the asked number is quite similar to the diameter of a tree.
How to find it? Let $f_i$ be the maximal sum on vertical way, which starts at vertex $i$, ends at somewhere in the sub-tree rooted at $i$, and $g_i$ be the second maximal sum. It is not difficult to calculate them, just using the values from the children of vertex $i$. As we know, every path can be divided to two vertical paths, so we can calculate answer in each sub-tree $i$ by simply adding $f_i$ and $g_i$ together.
Code
#include <bits/stdc++.h>
#define ll long long
#define maxn 300100
#define inf 0x3f3f3f3f3f
using namespace std;
struct Edge{
int to,next,val;
Edge(int a=0,int b=0,int c=0){
to=a,next=b,val=c;
}
}l[maxn<<1];
int head[maxn],w[maxn],n,cnt,tp;
ll f[maxn],g[maxn],d[maxn],ans;
void Add(int a,int b,int c){
l[++cnt]=Edge(b,head[a],c);head[a]=cnt;
l[++cnt]=Edge(a,head[b],c);head[b]=cnt;
}
void Dfs(int u,int fa){
int son=0;
for (register int i=head[u];i;i=l[i].next){
int v=l[i].to;if (v==fa) continue;
Dfs(v,u);son++;
ll t=f[v]>l[i].val?f[v]-l[i].val+w[u]:w[u];
ll p=g[v]>l[i].val?g[v]-l[i].val+w[u]:-inf;
if (t>f[u]) g[u]=f[u],f[u]=t;
else g[u]=max(g[u],t);
}
if (!son) f[u]=w[u],g[u]=-inf;
else if (son==1) ans=max(ans,f[u]);
else ans=max(ans,f[u]-w[u]+g[u]);
}
int main(){
scanf("%d",&n);
for (register int i=1;i<=n;++i)
scanf("%d",w+i),ans=max(ans,(ll)w[i]);
for (register int i=2,a,b,c;i<=n;++i)
scanf("%d%d%d",&a,&b,&c),Add(a,b,c);
Dfs(1,0);
printf("%I64d",ans);
}B The Fair Nut and Strings
Description
Recently, the Fair Nut has written $k$ strings of length $n$, consisting of letters “a” and “b”. He calculated $c$ — the number of strings that are prefixes of at least one of the written strings. Every string was counted only one time.
Then, he lost his sheet with strings. He remembers that all written strings were lexicographic ally not smaller than string $s$ and not bigger than string $t$. He is interested: what is the maximum value of cc that he could get.
A string aa is lexicographically smaller than a string bb if and only if one of the following holds:
- $a$ is a prefix of $b$, but $a≠b$;
- in the first position where $a$ and $b$ differ, the string $a$ has a letter that appears earlier in the alphabet than the corresponding letter in $b$.
Idea
It is not a hardcore problem. Starting from the beginning of these two given strings, you could just add characters to the prefix one-by-one, calculate the answer at each possible length. We could use a binary number to present the current prefix string, and the difference between the maximal possible number and the minimum possible number is part of the answer at this length. Keep the process going until the number is bigger than $k$, and the rest of answer is $\text{length-left}\times k$.
Code
#include <bits/stdc++.h>
#define ll long long
#define maxn 500100
int n,k,s[maxn],t[maxn];
char x[maxn];
ll ans,cur,a,b;
int main(){
scanf("%d%d",&n,&k);
scanf("%s",x+1);
for (register int i=1;i<=n;++i)
s[i]=x[i]-'a';
scanf("%s",x+1);
for (register int i=1;i<=n;++i)
t[i]=x[i]-'a';
for (register int i=1;i<=n;++i){
a<<=1,b<<=1;
a+=s[i],b+=t[i];
cur=b-a+1>k?k:b-a+1;
ans+=cur;
if (cur==k){
ans+=1ll*(n-i)*k;
break;
}
}
printf("%I64d",ans);
}E The Fair Nut and Rectangles
Description
The Fair Nut got stacked in planar world. He should solve this task to get out.
You are given nn rectangles with vertexes in $(0,0)$, $(x_i,0)$, $(x_i,y_i)$, $(0,y_i)$. For each rectangle, you are also given a number $a_i$. Choose some of them that the area of union minus sum of $a_i$ of the chosen ones is maximum.
It is guaranteed that there are no nested rectangles.
Nut has no idea how to find the answer, so he asked for your help.
Idea
Let’s order rectangles by $x_i$, so $x_1,\cdots,x_n$ will be increasing. If the $x_1,\cdots,x_n$ is increasing, $y_1,\cdots,y_n$ is decreasing, because there are no nested rectangles. Then lets define $dp_i$ as the maximum value, which can be achieved by choosing some subset of first $i$ rectangles which contains the $i$-th rectangle. It can be calculated by $dp_i = \max\limits_{1 \leq j < i} dp_j + x_i \cdot y_i – x_j \cdot y_i$, where $j$ is the previous chosen rectangle (we subtract $x_j⋅y_i$ because it is common square of the subset for $dp_j$ and $i$-th rectangle). This formula can be optimized using convex hull trick and calculated in $\Theta(n\log n)$ or in $\Theta(n)$ if rectangles are already sorted.
Code
#include <bits/stdc++.h>
#define maxn 1000100
#define max(a,b) (a>b?a:b)
#define ll long long
struct mart{
ll x,y,v;
mart(ll a=0,ll b=0,ll c=0){
x=a,y=b,v=c;
}
bool operator < (const mart &c) const{
return x<c.x;
}
}a[maxn];
int q[maxn],h,t,n;
ll ans,f[maxn],x,y,z;
ll bt1(int i,int j){
return f[i]+(a[j].x-a[i].x)*a[j].y-a[j].v;
}
double bt2(int i,int j){
return (double)1.0*(f[i]-f[j])/(a[i].x-a[j].x);
}
int main(){
scanf("%d",&n);
for (register int i=1;i<=n;++i)
scanf("%lld%lld%lld",&x,&y,&z),a[i]=mart(x,y,z);
std::sort(a+1,a+1+n);
for (register int i=1;i<=n;++i){
while(h<t&&bt1(q[h],i)<bt1(q[h+1],i)) h++;
f[i]=bt1(q[h],i),ans=max(ans,f[i]);
while(h<t&&bt2(q[t],q[t-1])<bt2(i,q[t])) t--;
q[++t]=i;
}
printf("%lld\n",ans);
return 0;
}