A dp problem(I think)

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	160
5	djm03178	158
5	-is-this-fft-	158
7	adamant	155
8	Dominater069	154
9	awoo	152
10	luogu_official	150

The problem is basically monopoly but you don't need to roll dices or stuffs, we have $$$N$$$ $$$(1 \leq N \leq 10^5)$$$ positions each of which are all empty. We can play any number of rounds by each rounds we choose an index $$$i$$$, if it's empty, we'll build a house on that position which will cost us $$$A_i$$$, and gives us 1 points, but if it's a house already, we'll transform the house to a apartment, which will cost us $$$B_i$$$, and gives us 1 points, if it's already an apartment we'll do nothing, which gives us nothing and cost us nothing (so there's no reason to do this). We always want to maximize the amount of points. (We can make an apartment on the position $$$i$$$ if and only if the position $$$i$$$ is a already a house)

There will be $$$Q$$$ $$$(1 \leq Q \leq 10^5)$$$ queries, on the $$$ith$$$ query $$$(1 \leq i \leq Q)$$$ we have a budget of $$$X_i$$$, which means that the total sums of cost cannot exceed $$$X_i$$$. We want to know that, for each queries $$$i$$$ $$$(1 \leq i \leq Q)$$$ what is the maximum amount of points we can possibly get?

Constraints:

$$$1 \leq N,Q \leq 10^5$$$
$$$1 \leq A_i,B_i \leq 10^{9}$$$
$$$1 \leq X_i \leq 2 \cdot 10^{14}$$$

What I tried(Not the full solution)

Time complexity: $$$O(N^2+QlogN)$$$

I made a knapsack $$$ks$$$ as an array of size of $$$2 \cdot N$$$ , which $$$ks_i$$$ represent the minimum cost to get $$$i$$$ amount of points.(takes time of $$$O(N^2)$$$ of precomputing), then I received the queries and binary searched the maximum amount of points we can get and outputted it.(takes time of $$$O(QlogN)$$$) aaaand I'm stuck here. I don't know how to optimize this further...

/********************
 * what  the  sigma *
 ********************/
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
using namespace std;
#define lgm cin.tie(0)->sync_with_stdio(0);
#define be(x) x.begin(),x.end()
#define ve vector
#define ll long long
#define ld long double
#define db(x) cout << "Debug at " << x << endl;
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int, int>
#define tii tuple<int,int,int>
#define pll pair<ll,ll>
#define sz(x) (int)x.size()
#define pb push_back
const int mod = 1e9+7,maxn=200005;
ll ks[200001];
int main() {
    cin.tie(0)->sync_with_stdio(0);
    ll n,cnt=0,cnt2=0;
    cin >> n;
    ll a[n],b[n];
    vector<ll> v;
    for (ll i=0;i<n;i++) {
        cin >> a[i];
        v.push_back(a[i]);
    }
    for (ll i=0;i<n;i++) {
        cin >> b[i];
        v.push_back(b[i]);
        if (a[i] <= b[i]) {
            cnt++;
        } else if (a[i]>=b[i]) {
            cnt2++;
        }
    }
    ll q;
    cin >> q;
    ll m=100000;
    m=m*m*m;
    ll x;
    for (int i=1;i<=2*n;i++) {
        ks[i]=m;
    }
    for (int i=0;i<n;i++) {
        for (int j=2*(i+1);j>=2;j--) {
            ks[j]=min(ks[j],min(ks[j-1]+a[i],ks[j-2]+a[i]+b[i]));
        }
        ks[1]=min(a[i],ks[1]);
    }
    while (q--) {
        cin >> x;
        int l=upper_bound(ks,ks+2*n+1,x)-ks-1;
        cout << l<<'\n';
    }
}

I could not find a solution. But if anyone can, please comment what the solution to this problem could be(Other people would know too!), I would really appreciate it!

Thanks in advance!

Comments (9)

Write comment?

SkyMagic

4 weeks ago, # |

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

→ Reply

avnithv

You can calculate the minimum cost to obtain each number of points from $$$1$$$ to $$$2N$$$. If we know the optimal way to get $$$x$$$ points, we can find the optimal way to get $$$x+2$$$ points (take the minimum of the two smallest indexes to build once or the smallest index to build twice). So we can calculate this cost in increasing order for odd and even number of points separately. After that we answer queries in $$$O(\log N)$$$. I don't have a proof that this works, however.

akshit5638

I think this can be solved by greedy. Please correct if i am wrong

First lets solve it for a fix value of x[i] lets say x

make two set name house and apartments which store for every index cost of making house and apartment with their index. eg house will have {a[i],i} and apartment will have {a[i]+b[i],i} for every i

now while(x>0) compare the cost of making 2 smallest house (h) and a aprtment (a) from set as both of them will give you two points. if you can't even make smallest house with given x simply break.Otherwise If a<=h you add 2 to answer and erase first element from apartment and erase {a[i],i} from house where i is index of first element in apartment and decreament x by a[i]+b[i] otherwise erase first element from house and decreament x by a[i]. now since a house is formed we can consider making apartment at that index equivalent to house so just erase {a[i]+b[i],i} from aparment and insert {b[i],i} to house

now for query part store them in array and then sort them in increasing order and then keep doing this for x[i] in sorted order . initilize x=0 then for every i in query sorted array add x[i] to x and perform above operation.

since in every operation either nothing happen or one element is removed from set it will run at max 3*n times and log factor for set so it should pass

Muaath_5

At first you have $$$N$$$ options to choose from, all of them are the array $$$A$$$.

For every point, choose the one with minimal cost, remove it from the set, and insert $$$B_i$$$ instead.

When you get a query, binary search for the answer.

like this:

Code

// Build()
set<array<ll, 3>> s;
for (int i = 1; i <= n; i++)
    s.insert({a[i], i, 0});

vector<ll> costs = {0};
for (int i = 1; i <= 2*n; i++) {
    array<ll, 3> option = *s.begin();
    s.erase(s.begin());
    costs.push_back(costs.back() + option[0]);
    if (option[2] == 0)
        s.insert({b[options[1]], options[1], 1});
}

// Query(x)
int res = lower_bound(costs.begin(), costs.end(), x) - costs.begin();

justin_zed

4 weeks ago, # ^ |

Consider A = [5, 9] and B = [10, 1]. If X = 10 your greedy approach will get A1 when it's better to take A2 and B2

Oh yes, Then probably we need DP

An important observation is that among locations where Ai > Bi, we will never need to pick more than one where we only take Ai

Suppose we have A1 > B1 and A2 > B2 where we take the A's. Suppose we cannot replace A2 with B1, then A1 > B1 > A2 > B2 and we can replace A1 with B2

Given this knowledge, we can build a two-step greedy algorithm that supports fast addition/removal of an element and apply Mo's algorithm

Ah okay, thank you very much!

SkyMagic's blog