As per [user:Cristofor,2024-02-06]'s request I am making an editorial on the problems I solved:↵
↵
<b>Room Temperature:</b>↵
↵
<spoiler summary = "Hint 1">↵
Does the exact temperature to each officer matter??↵
</spoiler>↵
↵
↵
<spoiler summary = "Hint 2">↵
What if every officer wore an infinite amount of jackets??↵
</spoiler>↵
↵
↵
<spoiler summary = "Hint 3">↵
In that case only the Mod matters.↵
</spoiler>↵
↵
↵
<spoiler summary = "Solution">↵
We first initialize the answer we are going to print to infinity (1e18), ↵
then we make an Array $B$, containing the set of $A_i mod T$ and then we itterate over every $B_i$ and set the answer to $min(ans, max(a[i - 1] - a[i] + k, a[n - 1] - a[i]))$, we add that $T$ as if (s)he took a jacket off. Time complexity: $O(N).$↵
</spoiler>↵
↵
<b>Construction Project:</b>↵
↵
<spoiler summary = "Hint 1">↵
Think of 2 dijkstras.↵
</spoiler>↵
↵
↵
<spoiler summary = "Solution">↵
We first assign two arrays, $DistanceFromS$ and $DistanceFromT$, then we do two dijkstras filling the two arrays, then for every element in the $DistanceFromS$ we do binary search to find the lower bound of $K \geq DistanceFromS_i + L$ if there↵
exists one, that means we can make a road connecting the two points. Time complexity: $O(N*Log(N)).$↵
</spoiler>↵
↵
<b>Marathon Race:</b>↵
↵
<spoiler> didn't solve this lol </spoiler>↵
↵
↵
<spoiler summary = "wasa855's Solution">↵
For problem 3, first consider how to answer one question. Balls at the same position can be merged, then consider the entire process in reverse order, The last ball collected must be one of the balls on left or right side of the end point, and the last $K$ balls collected must form an interval. Enumerate the last ball collected(at most 2 different balls possible), the observation leads a DP that $fl,r$↵
indicates if we collect the balls between $l-th$ to the $r-th$ position at the end of entire process, what is the minimal time to collect them. It answers a question in $O(n^2)$time, where n is the different places that have balls. If we calculate all $n$ beginning position, we can answer a question in $O(Log(N))$ time.↵
↵
Another observation is that if we have n different positions that have balls, the minimal time is at least $N^2/2$, so we only need to solve the task for $N \leq 1000$, previous $O(N)$ solution works.↵
↵
<spoiler summary = "Proof by Dominater069">↵
Assume you pick up anything in the middle right now, but you will pass this point atleast once more (when you go from leftmost to rightmost or vice versa), its just optimal to pick it up then.↵
</spoiler>↵
↵
(DK How to link comments sorry), [user:wasa855,2024-02-06] [user:Dominater069,2024-02-06]↵
↵
</spoiler>↵
↵
<b>Gift Exchange:</b>↵
↵
<spoiler summary = "Grade"> This only gets you the first 4 subtasks (50 grades) </spoiler>↵
↵
↵
<spoiler summary = "Hint 1">↵
Brute force approach works.↵
</spoiler>↵
↵
↵
<spoiler summary = "Hint 2">↵
Think of sorting the arrays.↵
</spoiler>↵
↵
↵
<spoiler summary = "Solution">↵
We make another two arrays of pairs, to keep track of the element and it's index, and sort both of them. Now to building the last answer, we itterate through every element in the arrays and check if (after sorted) there exists someone giving a gift to himself, since that's not allowed we check if we can exchange gifts with someone 1 index lower or higher, if we can't then the answer is no, and if we can we swap them. After that we itterate in the final two arrays and check if $A_i \geq B_i$, if it isn't then answer is No otherwise we print Yes. Time complexity $O(N*Log(N)*Q), I think segment can get you a 100 But I haven't learned it.$↵
</spoiler>↵
↵
↵
<spoiler summary = "Implementation"> ↵
```cpp↵
int n, q, a[500010], b[500010];↵
↵
void solve() {↵
cin >> n;↵
for (int i = 0; i < n; i++) cin >> a[i];↵
for (int i = 0; i < n; i++) cin >> b[i];↵
cin >> q;↵
while (q--) {↵
vector<pair<int, int>> v, v2;↵
int l, r;↵
cin >> l >> r;↵
--l;↵
for (int i = l; i < r; ++i) v.pb({ b[i],i }), v2.pb({ a[i],i });↵
sort(all(v)); sort(all(v2));↵
bool flag = true;↵
for (int i = 0; i < v.size(); ++i) {↵
if (v[i].ss == v2[i].ss) {↵
if (i && v2[i - 1].ff >= v[i].ff) swap(v[i - 1], v[i]);↵
else if (i < v.size() - 1 && v2[i].ff >= v[i + 1].ff) swap(v[i], v[i + 1]);↵
else { flag = false; break; }↵
}↵
}↵
for (int i = 0;i < v.size();i++) {↵
if (v2[i].ff < v[i].ff) { flag = false; break; }↵
}↵
if (flag) cout << "Yes\n";↵
else cout << "No\n";↵
}↵
}↵
```↵
</spoiler>↵
↵
↵
<spoiler summary = "Hint for Subtask 5"> I think greedy approach works </spoiler>↵
↵
<b>For the last problem "Road Service" I didn't understand what was written so I couldn't solve it lol</b>
↵
<b>Room Temperature:</b>↵
↵
<spoiler summary = "Hint 1">↵
Does the exact temperature to each officer matter??↵
</spoiler>↵
↵
↵
<spoiler summary = "Hint 2">↵
What if every officer wore an infinite amount of jackets??↵
</spoiler>↵
↵
↵
<spoiler summary = "Hint 3">↵
In that case only the Mod matters.↵
</spoiler>↵
↵
↵
<spoiler summary = "Solution">↵
We first initialize the answer we are going to print to infinity (1e18), ↵
then we make an Array $B$, containing the set of $A_i mod T$ and then we itterate over every $B_i$ and set the answer to $min(ans, max(a[i - 1] - a[i] + k, a[n - 1] - a[i]))$, we add that $T$ as if (s)he took a jacket off. Time complexity: $O(N).$↵
</spoiler>↵
↵
<b>Construction Project:</b>↵
↵
<spoiler summary = "Hint 1">↵
Think of 2 dijkstras.↵
</spoiler>↵
↵
↵
<spoiler summary = "Solution">↵
We first assign two arrays, $DistanceFromS$ and $DistanceFromT$, then we do two dijkstras filling the two arrays, then for every element in the $DistanceFromS$ we do binary search to find the lower bound of $K \geq DistanceFromS_i + L$ if there↵
exists one, that means we can make a road connecting the two points. Time complexity: $O(N*Log(N)).$↵
</spoiler>↵
↵
<b>Marathon Race:</b>↵
↵
<spoiler> didn't solve this lol </spoiler>↵
↵
↵
<spoiler summary = "wasa855's Solution">↵
For problem 3, first consider how to answer one question. Balls at the same position can be merged, then consider the entire process in reverse order, The last ball collected must be one of the balls on left or right side of the end point, and the last $K$ balls collected must form an interval. Enumerate the last ball collected(at most 2 different balls possible), the observation leads a DP that $fl,r$↵
indicates if we collect the balls between $l-th$ to the $r-th$ position at the end of entire process, what is the minimal time to collect them. It answers a question in $O(n^2)$time, where n is the different places that have balls. If we calculate all $n$ beginning position, we can answer a question in $O(Log(N))$ time.↵
↵
Another observation is that if we have n different positions that have balls, the minimal time is at least $N^2/2$, so we only need to solve the task for $N \leq 1000$, previous $O(N)$ solution works.↵
↵
<spoiler summary = "Proof by Dominater069">↵
Assume you pick up anything in the middle right now, but you will pass this point atleast once more (when you go from leftmost to rightmost or vice versa), its just optimal to pick it up then.↵
</spoiler>↵
↵
(DK How to link comments sorry), [user:wasa855,2024-02-06] [user:Dominater069,2024-02-06]↵
↵
</spoiler>↵
↵
<b>Gift Exchange:</b>↵
↵
<spoiler summary = "Grade"> This only gets you the first 4 subtasks (50 grades) </spoiler>↵
↵
↵
<spoiler summary = "Hint 1">↵
Brute force approach works.↵
</spoiler>↵
↵
↵
<spoiler summary = "Hint 2">↵
Think of sorting the arrays.↵
</spoiler>↵
↵
↵
<spoiler summary = "Solution">↵
We make another two arrays of pairs, to keep track of the element and it's index, and sort both of them. Now to building the last answer, we itterate through every element in the arrays and check if (after sorted) there exists someone giving a gift to himself, since that's not allowed we check if we can exchange gifts with someone 1 index lower or higher, if we can't then the answer is no, and if we can we swap them. After that we itterate in the final two arrays and check if $A_i \geq B_i$, if it isn't then answer is No otherwise we print Yes. Time complexity $O(N*Log(N)*Q), I think segment can get you a 100 But I haven't learned it.$↵
</spoiler>↵
↵
↵
<spoiler summary = "Implementation"> ↵
```cpp↵
int n, q, a[500010], b[500010];↵
↵
void solve() {↵
cin >> n;↵
for (int i = 0; i < n; i++) cin >> a[i];↵
for (int i = 0; i < n; i++) cin >> b[i];↵
cin >> q;↵
while (q--) {↵
vector<pair<int, int>> v, v2;↵
int l, r;↵
cin >> l >> r;↵
--l;↵
for (int i = l; i < r; ++i) v.pb({ b[i],i }), v2.pb({ a[i],i });↵
sort(all(v)); sort(all(v2));↵
bool flag = true;↵
for (int i = 0; i < v.size(); ++i) {↵
if (v[i].ss == v2[i].ss) {↵
if (i && v2[i - 1].ff >= v[i].ff) swap(v[i - 1], v[i]);↵
else if (i < v.size() - 1 && v2[i].ff >= v[i + 1].ff) swap(v[i], v[i + 1]);↵
else { flag = false; break; }↵
}↵
}↵
for (int i = 0;i < v.size();i++) {↵
if (v2[i].ff < v[i].ff) { flag = false; break; }↵
}↵
if (flag) cout << "Yes\n";↵
else cout << "No\n";↵
}↵
}↵
```↵
</spoiler>↵
↵
↵
<spoiler summary = "Hint for Subtask 5"> I think greedy approach works </spoiler>↵
↵
<b>For the last problem "Road Service" I didn't understand what was written so I couldn't solve it lol</b>
