RBFLOWERS - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: Jeevan Jyot Singh
Testers: Tejas Pandey, Hriday
Editorialist: Nishank Suresh

DIFFICULTY:

TBD

PREREQUISITES:

Knapsack-style dynamic programming

PROBLEM:

You have two arrays R and B, both of length N. At each index, you can choose either R_i or B_i. Let X denote the sum of all chosen R_i and Y denote the sum of all chosen B_i. Maximize \min(X, Y).

EXPLANATION:

The limits on N and the values are small, so a natural knapsack-style dynamic programming solution should strike you, something along the following lines:

Let f(i, x, y) be a boolean function, where f(i, x, y) is true if and only if you can make choices among the first i elements such that the sum of reds is exactly x and the sum of blues is exactly y.
Transitions are extremely easy: f(i, x, y) = f(i-1, x - R_i, y) \vee f(i-1, x, y - B_i) (\vee denotes logical OR), and memoization naturally makes transitions \mathcal{O}(1).
The final answer is the maximum value of \min(x, y) across all (x, y) such that f(N, x, y) is true.

While this is correct, it is also too slow. x and y can be as large as 200\times N, so we have 200^2 \times N^3 states in our dp, which is way too much.

Note that the constraints do allow a solution in \mathcal{O}(200 \times N^2), i.e, kicking out one state of our dp.
We can achieve that by a relatively common trick: turn the removed state into the value of the dp!

Consider a function f(i, x) which denotes the maximum sum of blues from the first i elements, given that the sum of reds is x.
Transitions for this function are as follows:

  • If we choose R_i, the sum of blues is f(i-1, x - R_i)
  • Otherwise, the sum of blues is f(i-1, x) + B_i
  • So, f(i, x) = \max(f(i-1, x) + B_i, f(i-1, x-R_i))

Once again, by memoizing f(i, x) values, transitions are \mathcal{O}(1), so both our time and space complexity are fine.

The final answer is the maximum of \min(x, f(N, x)) across all 0 \leq x \leq 200\cdot N.

TIME COMPLEXITY

\mathcal{O}(N\cdot S) per test case, where S = 200\times N.

CODE:

Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
// -------------------- Input Checker Start --------------------

long long readInt(long long l, long long r, char endd)
{
    long long x = 0;
    int cnt = 0, fi = -1;
    bool is_neg = false;
    while(true)
    {
        char g = getchar();
        if(g == '-')
        {
            assert(fi == -1);
            is_neg = true;
            continue;
        }
        if('0' <= g && g <= '9')
        {
            x *= 10;
            x += g - '0';
            if(cnt == 0)
                fi = g - '0';
            cnt++;
            assert(fi != 0 || cnt == 1);
            assert(fi != 0 || is_neg == false);
            assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
        }
        else if(g == endd)
        {
            if(is_neg)
                x = -x;
            if(!(l <= x && x <= r))
            {
                cerr << "L: " << l << ", R: " << r << ", Value Found: " << x << '\n';
                assert(false);
            }
            return x;
        }
        else
        {
            assert(false);
        }
    }
}

string readString(int l, int r, char endd)
{
    string ret = "";
    int cnt = 0;
    while(true)
    {
        char g = getchar();
        assert(g != -1);
        if(g == endd)
            break;
        cnt++;
        ret += g;
    }
    assert(l <= cnt && cnt <= r);
    return ret;
}

long long readIntSp(long long l, long long r) { return readInt(l, r, ' '); }
long long readIntLn(long long l, long long r) { return readInt(l, r, '\n'); }
string readStringSp(int l, int r) { return readString(l, r, ' '); }
string readStringLn(int l, int r) { return readString(l, r, '\n'); }
void readEOF() { assert(getchar() == EOF); }

vector<int> readVectorInt(int n, long long l, long long r)
{
    vector<int> a(n);
    for(int i = 0; i < n - 1; i++)
        a[i] = readIntSp(l, r);
    a[n - 1] = readIntLn(l, r);
    return a;
}

// -------------------- Input Checker End --------------------

int main() {
	int t;
	t = readIntLn(1, 100);
	int smn = 0;
	while(t--) {
	    int n;
	    n = readIntLn(1, 100);
	    smn += n;
	    assert(smn <= 100);
	    int r[n], b[n];
	    for(int i = 0; i < n - 1; i++) r[i] = readIntSp(1, 200);
	    r[n - 1] = readIntLn(1, 200);
	    for(int i = 0; i < n - 1; i++) b[i] = readIntSp(1, 200);
	    b[n - 1] = readIntLn(1, 200);
	    int dp[n][n*200 + 1];
	    memset(dp, -1, sizeof(dp));
	    dp[0][0] = b[0];
	    dp[0][r[0]] = 0;
	    for(int i = 0; i < n - 1; i++) {
	        for(int j = 0; j <= n*200 - r[i + 1]; j++)
	            dp[i + 1][j + r[i + 1]] = dp[i][j];
	        for(int j = 0; j <= n*200; j++)
	        if(dp[i][j] > -1)
	            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + b[i + 1]);
	    }
	    int ans = 0;
	    for(int j = 0; j <= n*200; j++) ans = max(ans, min(j, dp[n - 1][j]));
	    cout << ans << "\n";
	}
	return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
	n = int(input())
	r = list(map(int, input().split()))
	b = list(map(int, input().split()))
	maxS = 20004
	dp = [-1]*maxS
	dp[0] = 0
	for i in range(n):
		R, B = r[i], b[i]
		for x in reversed(range(maxS)):
			val = -1
			if dp[x] != -1:
				val = dp[x] + B
			if x-R >= 0 and dp[x-R] != -1:
				val = max(val, dp[x-R])
			dp[x] = val
	ans = 0
	for i in range(maxS):
		if dp[i] == -1: continue
		ans = max(ans, min(i, dp[i]))
	print(ans)
4 Likes

To find the solution, it’s possible to do a binary search between 0 [minimum answer possible] and min(sum(R), sum(B)) [maximum answer possible].
At each step, perform a knapsack and adjust the interval accordingly.
This is what I submitted: https://www.codechef.com/viewsolution/77676358

3 Likes

Yes. I also did the same binary search approach.
https://www.codechef.com/viewsolution/77664583

Rust based solution here.

https://www.codechef.com/viewsolution/77776924

It’s 0.01s, 5.7M
It can be faster if it applies binary search approach.

The editorial is not very clear. It does not provide the intuition for the solution.

4 Likes

Can someone post top down code ?

2 Likes

Which part do you find unclear?

In my opinion, the only intuition needed for the problem is the very first step: noticing that it can be modeled as a knapsack-style dynamic programming. That, unfortunately, comes with experience and practice, and you’ll find that this is the case for most dp tasks.

Once you fit it into a knapsack the rest of the solution is fairly routine, only requiring one optimization where you turn a dp state into a value (which is itself a fairly common optimization trick).

The DP part is easy to understand. There is difficulty in understanding the part where we use only one parameter to optimize. It would have been easy to understand if the top-down approach was explained.

Please read the editorial again, it details a top-down solution by defining a recursive function that can be memoized. Only the code linked at the bottom is iterative.

Turning a dp state into a value is a very common optimization. There isn’t too much intuition there, because there’s a very limited set of things you can do at all, so you might as well try them all.

When you have too many states, there is no choice but to reduce them, otherwise your solution simply won’t run in time. When doing this, you don’t want to lose any information you have, so a lot of the time only one of three things will work:

  • Looking for some relation between the dp states, for example in this problem from a couple weeks ago.
  • Turning a state into a value, as explained above in the editorial.
  • Looking at the recursion and realizing that it isn’t possible to reach most of the states, so the naive dp is actually fast enough. One example is this problem.

In this task, if you try the first and third optimizations you’ll probably hit a dead end, while the second one does work.

2 Likes

Thanks for reply. Now I get it

This helped me understand the solution.

Thank you so much for also linking the problems related to other methods. Really helpful.

can u explain your possible() function