Comprehensive Guide to Codechef Starter 194: Mastering 'Mark All

In Codechef Round 194 Div 4, there was one particular question that completely shattered my confidence. After failing to solve it during the contest, my brain froze — and I couldn’t think clearly for the remaining problems.

But after calming myself down, revisiting the problem, and going through some discussions and notes, I finally cracked it. This post is a documentation of everything I learned — written from my raw notes, code attempts, and insights.

---

🧩 Problem Breakdown

Difficulty: 1386
Platform: Codechef (Round 194 Div 4)

You are given:

• An array A[1...N], where A[i] is the cost of the i-th operation.

Each operation can be used once and in one of the two ways:

• Prefix Type: Marks all numbers in the range [1, i]

• Suffix Type: Marks all numbers in the range [i, N]

---

🎯 Goal

Use any one or two operations such that their combined effect marks the entire range [1...N], and the total cost is minimized.

---

📌 Constraints

• 2 ≤ N ≤ 5 × 10^5

• 1 ≤ A[i] ≤ 10^9

• 1 ≤ T ≤ 10^4 (number of test cases)

• Sum of N over all test cases ≤ 2 × 10^5

⏱ Time complexity required per test case: O(N)
❌ Brute force O(N²) will not work.

---

💭 What I Did During the Contest

Here’s the approach I took during the contest, which unfortunately didn’t work:

int cost = INT_MAX;
for (int i = 1; i <= n; i++) {
    int newCost = 0;
    if (i == 1) {
        newCost = suffix[i];
    } else if (i == n) {
        newCost = prefix[i];
    } else {
        newCost = min((prefix[i] + suffix[i+1]), (suffix[i] + prefix[i-1]));
    }

    cost = min(cost, newCost);
}

I tried combining prefix and suffix values for each i, thinking it would work. But I missed an important detail:
→ I didn't correctly handle i < j conditions, where one operation could mark the prefix and another the suffix, overlapping or intersecting to cover the entire array.

---

🧠 Better Insight (From Notes & Discussions)

🔁 Initial Brute Force Idea:

Try every pair (i, j) where you apply:

• A prefix operation at i

• A suffix operation at j
  Check if their union covers the array and compute A[i] + A[j].

This is O(N²) — too slow.

---

✨ Optimized Observation

If operations i and j intersect, they still cover the array!

That means we don’t need to worry about choosing a non-overlapping pair. We can:

1. Find the two smallest values in the array A — call them min1 and min2

2. Also consider the edge operations:

   • A[0] (prefix from start)

   • A[N-1] (suffix to end)

✅ Final answer:

min(min1 + min2, min(A[0], A[N-1]))

---

✅ Final Working Code

#include <bits/stdc++.h>
using namespace std;

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

    while (t--) {
        int n;
        cin >> n;
        vector<int> A(n);
        for (int i = 0; i < n; i++) {
            cin >> A[i];
        }

        int start = A[0], end = A[n - 1];

        int mn1 = INT_MAX, mn2 = INT_MAX;
        for (int x : A) {
            if (x < mn1) {
                mn2 = mn1;
                mn1 = x;
            } else if (x < mn2) {
                mn2 = x;
            }
        }

        cout << min(mn1 + mn2, min(start, end)) << endl;
    }

    return 0;
}

---

🔍 What I Learned

• ✅ Brute-force isn’t scalable. Don’t force nested loops in high constraint problems.

• ✅ Intersections can be powerful — overlapping operations still count.

• ✅ Sometimes problems reduce to something simpler like “find 2 smallest values”.

• ✅ Prefix + suffix can be thought of as left and right covers — if they intersect, that’s fine.

• ✅ Even if a problem breaks your flow in-contest, it's not a measure of your capability.

---

🧠 Bonus Example (From My Notes)

Array: [3, 2, 1, 4, 3]

• Two smallest: 1 + 2 = 3

• Start = 3, End = 3

• Final answer: min(3, 3) = 3

---

✨ Final Reflection

This problem hurt my performance in the contest — but solving it later taught me something far more important:

It’s okay to freeze during a contest.
What matters is how you bounce back and learn after.

This post is not just a solution — it’s a proof of growth. And next time, I won’t let one tricky problem break my confidence.

---

📈 Small Win, Big Step

Despite that tough moment, my rating went up from 1355 to 1372 in this contest.
That’s all the proof I needed that:

Growth happens exactly when you feel uncomfortable.

I’ll keep pushing. And so should you. 💪