ROIgold's blog

By ROIgold, history, 5 weeks ago, In English,

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;
}
 
 
 
 
  • Vote: I like it  
  • +2
  • Vote: I do not like it  

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Lol. Cannot view your solution.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ROIgold (previous revision, new revision, compare).

»
5 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

44391497

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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))

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 7   Vote: I like it 0 Vote: I do not like it

      With pleasure.

      As pmin = qmin = 1, you may just initialize ans and r dynamically as follows.

      44418996

      And another update to the solution with reduced execution time is as follows.

      44424987

      And a slightly more compact solution based on sorting the array is as follows.

      44426419

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Thank You a lot for your response.
        So, was the issue in NOT initializing ans as r at the start?

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
          Rev. 4   Vote: I like it +1 Vote: I do not like it

          With pleasure, again.

          Compare the following almost identical pair of submissions:

          1. 44430222 AC with int r = ans and ans = -1

          2. 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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ROIgold (previous revision, new revision, compare).

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ROIgold (previous revision, new revision, compare).