Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int t;
cin >> t;
while (t--) {
int n, x;
cin >> n >> x;
int prev = 0, ans = 0;
for (int i = 0; i < n; ++i) {
int a; cin >> a;
ans = max(ans, a - prev);
prev = a;
}
ans = max(ans, 2 * (x - prev));
cout << ans << '\n';
}
}
Idea: Roms
Tutorial
Tutorial is loading...
Solution (Roms)
#include <bits/stdc++.h>
using namespace std;
const int N = 200'000;
int t;
int main() {
cin >> t;
for (int tc = 0; tc < t; ++tc) {
int n;
cin >> n;
vector <int> cnt(n);
long long res = 0;
int cur = 0;
for (int i = 0; i < n; ++i) {
cin >> cnt[i];
if (cnt[i] > cur)
res += cnt[i] - cur;
cur = cnt[i];
}
cout << res - 1 << endl;
}
return 0;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
x, y = min(a), max(a)
res = []
while x != y:
res.append(x % 2)
x = (x + res[-1]) // 2
y = (y + res[-1]) // 2
print(len(res))
if len(res) <= n:
print(*res)
1901D - Yet Another Monster Fight
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (vovuh)
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n;
cin >> n;
vector<int> a(n);
for (auto &it : a) cin >> it;
vector<int> pref(n), suf(n);
for (int i = 0; i < n; ++i) {
pref[i] = a[i] + (n - i - 1);
suf[i] = a[i] + i;
}
for (int i = 1; i < n; ++i) {
pref[i] = max(pref[i], pref[i - 1]);
}
for (int i = n - 2; i >= 0; --i) {
suf[i] = max(suf[i], suf[i + 1]);
}
int ans = 2e9;
for (int i = 0; i < n; ++i) {
int cur = a[i];
if (i > 0) cur = max(cur, pref[i - 1]);
if (i + 1 < n) cur = max(cur, suf[i + 1]);
ans = min(ans, cur);
}
cout << ans << endl;
return 0;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
using li = long long;
const li INF = 1e18;
const int N = 555555;
int n;
int a[N];
vector<int> g[N];
li dp[N];
li ans;
void calc(int v, int p) {
vector<li> sum(4, -INF);
sum[0] = 0;
for (int u : g[v]) if (u != p) {
calc(u, v);
for (int i = 3; i >= 0; --i) {
sum[min(i + 1, 3)] = max(sum[min(i + 1, 3)], sum[i] + dp[u]);
}
}
dp[v] = -INF;
for (int j = 0; j < 4; ++j) {
dp[v] = max(dp[v], sum[j] + (j == 1 ? 0 : a[v]));
ans = max(ans, sum[j] + (j == 2 ? 0 : a[v]));
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int t;
cin >> t;
while (t--) {
cin >> n;
for (int i = 0; i < n; ++i) cin >> a[i];
for (int i = 0; i < n; ++i) g[i].clear();
for (int i = 0; i < n - 1; ++i) {
int x, y;
cin >> x >> y;
--x; --y;
g[x].push_back(y);
g[y].push_back(x);
}
ans = 0;
calc(0, -1);
cout << ans << '\n';
}
}
Idea: adedalic
Tutorial
Tutorial is loading...
Solution (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define x first
#define y second
typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
fore(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
pt operator+ (const pt &a, const pt &b) {
return {a.x + b.x, a.y + b.y};
}
pt operator- (const pt &a, const pt &b) {
return {a.x - b.x, a.y - b.y};
}
li operator *(const pt &a, const pt &b) {
return a.x * 1ll * b.x + a.y * 1ll * b.y;
}
li operator %(const pt &a, const pt &b) {
return a.x * 1ll * b.y - a.y * 1ll * b.x;
}
const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;
int n;
vector<pt> old, nw;
inline bool read() {
if(!(cin >> n))
return false;
old.resize(n);
nw.resize(n);
fore (i, 0, n) {
old[i].x = i;
cin >> old[i].y;
}
fore (i, 0, n) {
nw[i].x = i;
cin >> nw[i].y;
}
return true;
}
inline ld getTr(const pt &a, const pt &b) {
pt tmp = b - a;
pt v = {-tmp.y, tmp.x};
ld c = v * a;
ld y0 = (c - v.x * 0) / v.y;
ld y1 = (c - v.x * li(n - 1)) / v.y;
return (y0 + y1);
}
vector<pt> hull(const vector<pt> &ps, int l, int r) {
vector<pt> h;
fore (i, l, r) {
while (sz(h) > 1 && (h[sz(h) - 1] - h[sz(h) - 2]) % (ps[i] - h[sz(h) - 1]) >= 0)
h.pop_back();
h.push_back(ps[i]);
}
return h;
}
inline void solve() {
vector<ld> maxTr(n - 1, 0);
fore (t, 0, 2) {
auto h = hull(old, n / 2, n);
auto best = [&](const pt &p) {
int l = -1, r = sz(h) - 1;
while (r - l > 1) {
int mid = (l + r) >> 1;
if ((h[mid] - p) % (h[mid + 1] - h[mid]) >= 0)
l = mid;
else
r = mid;
}
return h[r].x;
};
vector<ld> bs(n / 2 + 1, 0);
for (int i = n / 2 - 1; i >= 0; i--) {
int j = best(old[i]);
bs[i] = getTr(old[i], old[j]);
bs[i] = max(bs[i], bs[i + 1]);
}
ld lans = 0;
fore (i, 0, n / 2) {
int j = best(nw[i]);
lans = max(lans, getTr(nw[i], old[j]));
maxTr[i] = max({maxTr[i], lans, bs[i + 1]});
}
reverse(all(old));
reverse(all(nw));
swap(old, nw);
fore (i, 0, n)
old[i].x = nw[i].x = i;
reverse(all(maxTr));
}
maxTr.push_back(maxTr.back());
cout << maxTr << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(12);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
In problem D, I am struggling to understand the statement. According to my perception, the answer to the first test case should be 7. I will choose i = 4. The chain of the indices to strike will be like 4->3->5->6->2->1. Please someone correct me.
The spell's power must cover the worst-case scenario, given the chosen location.
Ohh! That last line. Thanks a lot.
Worst case I don't get it. First Index will chosen same for best case and worst case ?
then if we consider i=1 as a case that x must be atleast 9 right?
you can actually choose the value of i, so despite x have to be 9 when i=1, you can choose other i instead of 1
Reached Specialist, in this round.
Congrats!
Thanks
problem E is a art.
It takes a lot of effort to achieve perfection in whatever any direction.
for C, if we have min = 2 & max = 11. since min is even then x=0 & min = 1, max = 5 now if I go according to the editorial. it would take a total of 4 steps (1,3 -> 1,2 -> 1,1). but when min = 1 & max =5, I can take x =0 and reduce in 1 step less (1,2 -> 1,1) total of 3.
am I missing something here?
Of course. When min=1 and you don't add 1 then 1/2 = 0
It's easier to think about it another way: if max is odd then by adding anything will not gain any steps reduction.
yeah this makes more sense.
Problem D: If it's necessary to check all indices as a first target point (according to tutorial), then why problem statement says that "Vasya chooses the first target optimally"?
How would you figure out the optimal first target without checking all indices as first target point?
Oh yeah.. I got it. We need to take the minimum of these max values for an optimal first target (if I'm not wrong).
Thanks...
Can't he choose the max element as the 1st target?
That's not always optimal.
If we start at monster $$$2$$$ with health $$$5$$$, the attack might take the path $$$2\rightarrow 3\rightarrow 4\rightarrow 1$$$ and we need to start with $$$x = 7$$$. If instead we start at monster $$$1$$$ with health $$$4$$$, we can start with $$$x = 6$$$.
Thanks man
Thanks buddy , i got the intuition .
[Problem C] Can someone help me understand why choosing $$$x$$$ as the average between $$$max$$$ and $$$min$$$ (or $$$a$$$ and $$$b$$$) doesn't work?
I guess it has somethings to do with parities and rounding down, but I honestly cannot figure it out myself.
In addressing the question of why choosing $$$x$$$ as the average between the maximum ($$$b$$$) and minimum ($$$a$$$) values doesn't always yield the optimal result in problem C, it is essential to understand how the parity effects the calculations.
We categorize the scenarios based on the parity of $$$a$$$, $$$b$$$, and $$$x$$$. By brute force, we identify eight possible parity combinations, but let's consider two illustrative examples:
When $$$a=2i$$$, $$$b=2j+1$$$ and $$$x=2k+1$$$, the difference is $$$\left\lfloor (b + x)/2\right\rfloor - \left\lfloor(a+x)/2\right\rfloor = j - i + 1$$$.
When $$$a=2i+1$$$, $$$b=2j$$$ and $$$x=2k+1$$$, the difference is $$$\left\lfloor (b + x)/2\right\rfloor - \left\lfloor(a+x)/2\right\rfloor = j - i - 1$$$.
In the remaining six cases, the difference is $$$\left\lfloor (b + x)/2\right\rfloor - \left\lfloor(a+x)/2\right\rfloor = j - i$$$.
The optimal strategy emerges from these calculations. Matching the parity of $$$x$$$ with $$$a$$$ tends to minimize the difference. This is because the difference doesn't depend on $$$k$$$ and different parity can lead to a larger difference when $$$a$$$ is even.
Now, regarding your specific question, if $$$a=4i+1$$$ and $$$b=4j$$$, then choosing $$$x$$$ as the average, $$$x = \left\lfloor (a+b)/2\right\rfloor = 2(i + j) = 2k$$$, does not align with the optimal strategy. In this case, $$$x$$$ is even while $$$a$$$ is odd, and as we've established, matching their parities is crucial for optimality.
Can we also say as long as parity of a and x matches it doesn't matter whatever x is since difference is independent of k ?
Please take a look at my submission, I used the midpoint of the min and the max rounded up.
Submission Number: 259266474
Take a look at Ticket 17162 from CF Stress for a counter example.
If you apply this strategy, the choice of $$$x$$$ at each step would be:
However, it's possible to achieve this in 2 steps instead:
Question no. C, what does the line " You can consider all cases of parities of a and b to discover that it's always possible to divide the difference by 2, rounding down, and it's never possible to make it less than that. ".
I am struggling to understand the solution. Please help me understanding the solution.
Why there's a tag of binary seach in problem D: although it seems at first glance that we can go for a approach like BS. But then realised there's nothing to do with BS.
i have solved using Binary search, my solution
Didn't mean to say but you are increasing time complexity with binary search
Thanks for the fast editorial !
I've added hints and thought process for problems:
on CF Step
For problem D, my after-contest solution only involved checking the first location, the last location, and the location with the monster that needs the most spell power to kill.
Submission: https://codeforces.net/contest/1901/submission/234308715
Is the test data weak, or is the strategy described above valid? Thanks.
In problem D, according to my understanding the worst case for 2 1 5 6 4 3 should be 2->1->5->6->4->3 and that would not be possible with 8 damage ?
We are optimally selecting the start point, then we have to consider worst case after selecting start point
nvm I set my dp = -1 if it's not visited but I forget that the dp might be negative
i got accepted on F (237389815) by computing the overall hull in each step of the transition from old points to new points (the hardest part is to update the segment L = PQ that goes from a point P of the prefix hull to a point Q of the suffix hull).
we have to keep the prefix hull, the suffix hull and L = PQ updated. for each point y of the suffix hull, consider the segments that goes from y to each point x of the prefix hull. if we fix y, we can binary search for the first x which cross product changes sign in relation to the point x-1. with this we can find the point x_best of the prefix hull such that the line that contains the segment (x_best, y) necessarily covers all points of the prefix hull. we now need only to verify if this line also covers the suffix hull, which can be done with a cross product in relation to y+1. the first point of the suffix hull that this happens is the point Q.
in each step we should update the point Q based on the removals and insertions of new points of the current prefix and suffix hull. in order to keep it correct, we can do the following steps:
1) update the suffix hull by removing its current leftmost point and undoing the points that have been removed by it (inserting them back). for each of these added points, we must verify wether or not its line covers the prefix hull. this can be done in O(log n) for each point with binary searching in the prefix hull + some cross products for verification, as explained. doing this we are locating the new position of point Q.
2) update the prefix hull and change the suffix hull point Q status accordingly. since the added point covers all the prefix hull removed points (afterall, it defines the new prefix hull), we only verify if the point added changes the status of Q, with a binary search on the suffix hull, and update the point Q (basically, it can only make the point Q go more to the right).
3) now we have an updated point Q, and can binary search again the prefix hull to find the other point P that makes segment L.
There is a small error in the editorial for problem D. The minimum spell power needed is $$$\displaystyle \min (\max_{j = 1} ^{i - 1} a_j +(n - j), a_i, \max_{j = i + 1} ^ {n} a_j + (j - 1))$$$ instead of the original $$$\displaystyle \max (\max_{j = 1} ^{i - 1} a_j +(n - j), a_i, \max_{j = i + 1} ^ {n} a_j + (j - 1))$$$. Guess it's just a typo.
In Problem C, I was thinking in terms of binary representation. Taking x as the most appropriate number to shift the prefix of same bits to the right considering left as the largest similar bit (with all before it as same) but didn't went very far with it. Any suggestion with approach?
For problen D, for this case
6
1 6 1 1 6 1 , the accepted ans is 10, but shouldn't it be 9?
1 6 1 1 6 1
5 6 7 8 9 4. <--- Like this?