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.
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.
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
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
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.
comment your guess after running your code or dry run
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?