CHEFSPICE - Editorial

PROBLEM LINK:

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

Author: Varun Vaddiraju
Testers: Hriday, Utkarsh Gupta
Editorialist: Nishank Suresh

DIFFICULTY:

2613

PREREQUISITES:

None

PROBLEM:

You have a N\times M grid, initially with all its cells white.
In one move, you can paint all the cells in one row or one column black.

Is it possible to have exactly K black cells after some sequence of moves?

EXPLANATION:

Notice that neither the order of moves nor which rows and columns were chosen matters at all: the only thing that matters is how many rows and how many columns were chosen.

So, suppose we chose x rows and y columns.
Then, the number of cells colored black is exactly xM + yN - xy.
We’d like to check if some choice of x and y allows for this to equal K.

Suppose we fix x.
Then,

xM + yN - xy = K \implies y(N-x) = K-xM

That is, y is uniquely fixed to be \frac{K-xM}{N-x} once x is fixed.
Similarly, fixing y allows us to uniquely compute x.

However, x is the number of rows chosen, so it can be anything from 0 to N. Checking all of these would be too slow since N can be as large as 10^9.

To optimize this, we can make one simple observation: if we choose x rows and y columns, then we always color at least xy squares black.
This means that any valid solution must have \min(x, y) \leq \sqrt{K}.

Now we can simply loop over x and y to check if a valid solution exists! That is,

  • For each x from 0 to \sqrt{K}, check if a valid y exists
  • For each y from 0 to \sqrt{K}, check if a valid x exists

Note that when validating a pair (x, y) you must ensure that:

  • x and y are integers
  • xM + yN - xy = K
  • 0 \leq x \leq N and 0 \leq y \leq M

All of this can be done in \mathcal{O}(1) for a given x and y, giving us a solution in \mathcal{O}(\sqrt{K}) overall.

TIME COMPLEXITY

\mathcal{O}(\sqrt{K}) per test case.

CODE:

Setter's code (C++)
#include <bits/stdc++.h>

using namespace std;

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

    while (t--)
    {
        long long n, m, k, x, y;
        int v = 0;

        cin >> n >> m >> k;

        for (x = 0; x*x <= k && x < n; x++)
        {
            if ((k-m*x)%(n-x) == 0)
            {
                y = (k-m*x)/(n-x);
                if (y >= 0 && y < m && m*x + n*y - x*y == k)
                {
                    v = 1;
                }
            }
        }

        for (y = 0; y*y <= k && y < m; y++)
        {
            if ((k-n*y)%(m-y) == 0)
            {
                x = (k-n*y)/(m-y);
                if (x >= 0 && x < n && m*x + n*y - x*y == k)
                {
                    v = 1;
                }
            }
        }
        
        if (n*m == k)
        {
            v = 1;
        }

        if (v == 1)
        {
            cout << "Yes\n";
        }
        else
        {
            cout << "No\n";
        }
    }
}
Tester's code (C++)
/**
 * the_hyp0cr1t3
 * 22.11.2022 20:41:56
**/
#ifdef W
    #include <k_II.h>
#else
    #include <bits/stdc++.h>
    using namespace std;
#endif

// -------------------- 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() {
#if __cplusplus > 201703L
    namespace R = ranges;
#endif
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int64_t sum_k = 0, sum_sqrtk = 0, sum_min_nm = 0;

    int tests = readIntLn(1, 2000);
    while(tests--) [&] {
        int n = readIntSp(3, 1'000'000'000);
        int m = readIntSp(3, 1'000'000'000);
        int k = readIntLn(0, 1'000'000'000);
        sum_min_nm += min(n, m);
        sum_k += k;

        bool can = false;
        can |= k % m == 0 and k / m <= n;
        can |= k % n == 0 and k / n <= m;

        if(n > m) {
            for(int a = 1; !can and a < m and k >= a * n; a++)
                can = (k - a * n) % (m - a) == 0
                        and (k - a * n) / (m - a) <= n;
        } else {
            for(int b = 1; !can and b < n and k >= b * m; b++)
                can = (k - b * m) % (n - b) == 0
                    and (k - b * m) / (n - b) <= m;
        }

        cout << (can ? "yEs" : "nO") << '\n';
    }();

    cerr << "sum k = " << sum_k << '\n';
    cerr << "sum sqrt k = " << sum_sqrtk << '\n';
    cerr << "sum min(n, m) = " << sum_min_nm << '\n';

#ifndef W
    readEOF();
#endif

} // ~W
Editorialist's code (Python)
def check(n, m, k):
	x = 0
	while x <= n and x*x <= k:
		rem = k - x*m
		if rem < 0: break
		if x == n:
			if rem == 0: return True
		else:
			y = rem // (n - x)
			if y <= m and y*(n - x) == rem: return True
		x += 1
	return False

for _ in range(int(input())):
	n, m, k = map(int, input().split())
	print('Yes' if check(n, m, k) or check(m, n, k) else 'No')
1 Like

Will be (slightly) easier if we focus on achieve the desired number of white boxes (vs. black ones).

In order words, can you find K’ = n * m - K and K’ = xy (where x <= n and y <= m).

why i am not getting TLE here ??
https://www.codechef.com/viewsolution/80969243