Problem A: Honest or Dishonest

Two characters (a) and (b) are given, each either H (honest) or D (dishonest). Person A always tells the truth if (a = H), otherwise always lies. A states that B is honest if (b = H), or that B is dishonest if (b = D). Determine whether B is actually honest.

Solution

If A is dishonest ((a = D)), the statement is false, so we invert (b). Otherwise, output (b) directly.

char a, b; std::cin >> a >> b;
std::map<char, int> mp{{'H', 0}, {'D', 1}};
std::map<int, char> invmp{{0, 'H'}, {1, 'D'}};
std::cout << (a == 'H' ? b : invmp[mp[b] ^ 1]) << "\n";

Problem B: Rectangles Intersection

Two rectangles of size (W \times 1) are placed on a plane. The first has its lower-left corner at ((a, 1)), the second at ((b, 2)). Find the minimum distance they must move along x-axis to touch each other.

Solution

Project both intevrals onto x-axis: ([a, a+W]) and ([b, b+W]). If they intersect, output 0. Otherwise, the distance is the minimum gap between endpoints: (\min(|b - (a+W)|, |a - (b+W)|)).

int W, a, b; std::cin >> W >> a >> b;
int l1 = a, r1 = a + W;
int l2 = b, r2 = b + W;
if (std::max(l1, l2) <= std::min(r1, r2)) {
    std::cout << 0 << "\n";
} else {
    std::cout << std::min(abs(l1 - r2), abs(l2 - r1)) << "\n";
}

Problem C: Kangaroo Jump

A kangaroo starts at position 0 on an infinite line at time 0. In each second (i), it can stay, jump left by (i) units, or jump right by (i) units. Find the earliest time to reach position (X).

Solution

An optimal strategy is to jump right until the cumulative sum (\frac{t(t+1)}{2}) first meets or exceeds (X), then cancel the excess by replacing one jump with a stay. The minimal time is the smallest (t) such that (\frac{t(t+1)}{2} \ge X).

int X; std::cin >> X;
int t = 0;
while (t * (t + 1) / 2 < X) t++;
std::cout << t << "\n";

Problem D: Unnecessary Cards

We have (N) cards with values (a_i). A subset is good if its sum is at least (K). A card (i) is unnecessary if every good subset containing (i) remains good after removing (i). Count unnecessary cards.

Solution 1: Binary Search with DP

Sort (a) ascending. If a card is necessary, all larger cards are also necessary. We can binary search for the first necesary card. To check if a card at position (p) is necessary, remove it and run DP to see if any subset of the remaining cards has sum in ([K - a_p, K-1]). Complexity (O(NK \log N)).

int N, K; std::cin >> N >> K;
std::vector<int> a(N + 1);
for (int i = 1; i <= N; i++) std::cin >> a[i];
std::sort(a.begin() + 1, a.end());

int lo = 0, hi = N + 1;
while (hi - lo > 1) {
    int mid = (hi + lo) / 2;
    auto check = [&](int idx) -> bool {
        std::vector<int> b = a;
        b.erase(b.begin() + idx);
        std::vector<int> dp(K + 1, 0);
        dp[0] = 1;
        for (int i = 1; i < N; i++) {
            for (int j = K; j >= b[i]; j--) {
                dp[j] |= dp[j - b[i]];
            }
        }
        for (int j = std::max(K - a[idx], 0); j < K; j++) {
            if (dp[j]) return true;
        }
        return false;
    };
    if (check(mid)) lo = mid;
    else hi = mid;
}
std::cout << lo << "\n";

Solution 2: Linear DP with Reverse Order

Sort (a) increasingly. Process cards from largest to smallest. Maintain DP over sums up to (2K). A card is necesssary if there exists (j) with (K \le j \le K + a_i - 1) such that both (dp[j]) and (dp[j - a_i]) are true. Mark necessary cards. Count prefix before the first necessary card.

int N, K; std::cin >> N >> K;
std::vector<int> a(N + 1);
for (int i = 1; i <= N; i++) std::cin >> a[i];
std::sort(a.begin() + 1, a.end());

std::vector<int> good(N + 1, 0), dp(K * 2 + 1, 0);
dp[0] = 1;
for (int i = N; i >= 1; i--) {
    if (a[i] >= K) good[i] = 1;
    for (int j = K * 2; j >= a[i]; j--) {
        dp[j] |= dp[j - a[i]];
        if (dp[j] && dp[j - a[i]] && K <= j && j <= K + a[i] - 1) {
            good[i] = 1;
        }
    }
}
int ans = 0;
for (int i = 1; i <= N && !good[i]; i++) ans++;
std::cout << ans << "\n";

Extensions

• Multiple copies per value: Treat as bounded knapSack, but monotonicity may fail.
• Variable thresholds: Problem becomes more complex; alternative methods like item removal DP are needed.