MathAndMusic's blog

By MathAndMusic, history, 10 months ago, In English,

Hello. I am trying to attempt the following problem

https://www.spoj.com/problems/HELPR2D2/

After trying for a while, I figured the lowest index of each ship with capacity more than C can be picked by just binary searching all the ships(lower_bound) and subtract the respective volume. However, after a few WA attempts, I googled if I can find a solution.

There is no explanation though, but I can see only segtree implementation and I can't get my head around why its a segtree problem(or rather, why not just bsearch). Can anybody help me point out the flaw in binary search approach. It looks so obvious to me that it is binary search(but it isn't). Thanks in advance for any help. Here's my bsearch WA attempt:

int main()
{
  int t;
  cin >> t;

  while(t--)
  {
    vector<ll> a;
    int k, n;
    cin >> k >> n;
    set<ll> s;

    a.assign(100005, k);
    char c;
    int r, v;
    ll used = 0, usedvol = 0;
    char lead[16];
    
    forn(i, n)
    {
      scanf("%s", lead);
      if(lead[0] != 'b')
      {
        r = 1;
        v = atoi(lead);
      }
      else
      {
        cin >> r >> v;
        n-=r-1;
      }

        forn(i, r)
        {
          int lowidx = std::lower_bound(a.begin(), a.end(), v) - a.begin();
          a[lowidx]-=v;
          if(s.find(lowidx) == s.end())
          {
            used++;
            usedvol += v;
            s.insert(lowidx);
          }
          else
          {
            usedvol += v;
          }
        }
      }
     cout << used << " " << used * k - usedvol << endl;
    }
}
 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

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

We have to take the lowest index where we can add the incoming value without overflow. e.g. if in an array, we have 86 85 100 as filled, then when 10 comes, it should go into the first index making the array 96 85 100. But in your case, set shuffles the values in increasing order and thus, you end up giving 10 to the 2nd index (with value 85, instead).

Try your code on the input -

1
100
7
50
70
25
10
16
5
15

The correct output utilises all 3 starships.