### NewFlow's blog

By NewFlow, history, 3 months ago, ,

This problems is nice Binary Search problem, first I figured out solution by myself, then I get WA#19 and choose to watch tutorial, but it uses the same approach, after 5 more WAs at that same 19th test, I sadly watched author's shitty written solution, but as I compared it with mine, they don't differ at all, also the contest which contains that problem doesn't allow to watch people's solutions, I did substitute long long instead of int, please point me to where I'm doing something wrong.

Problem's statement
Author's solution
Tutorial, problem F
I'm very sorry, here's my code (submission):

#include <bits/stdc++.h>

#define FILE_NAME "BattleFury"

using namespace std;

typedef long long ll;

ll up(ll n, ll d) {
return (n + d - 1) / d;
}

signed main() {
#ifdef LOCAL
freopen(FILE_NAME".in", "r", stdin);
freopen(FILE_NAME".out", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n, damage, splash;
cin >> n >> damage >> splash;
vector<ll> creeps(n);
for (ll& hp : creeps)
cin >> hp;
auto okay = [&](ll hits) {
ll done = 0;
for (ll hp : creeps) {
ll left = max(0ll, hp - hits * splash);
if (damage == splash) {
if (left)
return false;
} else done += up(left, damage - splash);
}
return (done <= hits);
};

ll ans = -1;
for (ll l = 1, r = (ll) 1e16; l <= r;) {
ll hits = (l + r) / 2;
if (okay(hits)) {
ans = hits;
r = hits - 1;
} else l = hits + 1;
}
cout << ans;
return false;
}


•
• +2
•

 » 3 months ago, # |   0 Lol. Cannot view your solution.
•  » » 3 months ago, # ^ |   0 fixed now
 » 3 months ago, # |   0 Auto comment: topic has been updated by ROIgold (previous revision, new revision, compare).
 » 3 months ago, # | ← Rev. 3 →   0 Replace the pair of lines ll ans = -1; for (ll l = 1, r = (ll) 1e16; l <= r;) { with ll l = 1, r = 1e9, ans = r; while( l <= r ) { And check if this fixes the solution as your slightly updated code was accepted.
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 Wow, thank You a lot, yes it got accepted with while instead of for, but what's the difference? ll ans = -1; for (ll l = 1, r = (ll) 1e9; l <= r;) { ... }  ll l = 1; ll r = (ll) 1e9; ll ans = r; while (l <= r) { ... } don't they have same meaning? (initializing ans = -1 is not difference, I checked assert(ans != -1))
•  » » » 3 months ago, # ^ | ← Rev. 7 →   0 With pleasure. As pmin = qmin = 1, you may just initialize ans and r dynamically as follows. 44418996And another update to the solution with reduced execution time is as follows. 44424987And a slightly more compact solution based on sorting the array is as follows.44426419
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 Thank You a lot for your response.So, was the issue in NOT initializing ans as r at the start?
•  » » » » » 3 months ago, # ^ | ← Rev. 4 →   +1 With pleasure, again.Compare the following almost identical pair of submissions: 44430222 AC with int r = ans and ans = -1 44430307 WA on test 19 with ll r = 1e16 and ans = -1 It seems that the "real" issue is the very large initial value of r, and is not related to initializing ans to -1.
 » 3 months ago, # |   0 Auto comment: topic has been updated by ROIgold (previous revision, new revision, compare).
 » 3 months ago, # |   0 Auto comment: topic has been updated by ROIgold (previous revision, new revision, compare).