Problem Description

You are tasked with finding the minimum number of bandages required to defeat a dragon using a sword. The sword deals:

• 1 damage if the i-th attack is not divisible by 3.
• 2 damage if the i-th attack is divisible by 3.

If your health becomes less than 0 at any point, you must use a bandage to restore it.

Solution Approach

You can solve this problem using a while loop to determine the minimum number of bandages required.

void solve(){
    int h,k,n;cin>>h>>k>>n;
    int ans = 0, l = k, r = 1;
    while(h > 1){
        r++;
        k -= n;
        if(k <= 0){
            k = l - n;
            ans++;
        }
        if(r % 3 == 0){
            h-=2;
        }else{
            h--;
        }
    }
    cout<<ans<<endl;
}

Good problem! :
Average problem :
Bad problem... :

Problem Statement

OwlBear is attacking a village. The village has n cannons, each dealing a_i damage. At the k-th second, the OwlBear is protected from the cannon at index (*k*-1) mod n. Given q queries, each with a damage threshold h, find the minimum number of seconds required to deal at least h damage.

Analysis

The key idea is to precompute the prefix sums of the damage dealt in each second, excluding the blocked cannon. Let sum be the total damage all cannons can deal in one second. Then, the damage dealt in the i-th second is sum - a[i % n]. We can create a prefix sum array p where p[i] stores the total damage dealt from second 1 to second i.

To answer a query with damage h, we can first calculate how many full cycles of n seconds are needed. This can be done by ans = h / p[n-1]. The remaining damage is h -= (ans * p[n-1]). Then, we multiply ans by n to get the number of seconds in full cycles. If there is still remaining damage (h > 0), we use binary search (specifically lower_bound) on the prefix sum array p to find the minimum number of additional seconds needed.

Solution

1. Read n and the damage array a.
2. Calculate the total damage sum and create the prefix sum array p where p[i] = sum - a[i] and accumulate the prefix sums.
3. For each query h:
   • Calculate the number of full cycles: ans = h / p[n-1].
   • Update the remaining damage: h -= (ans * p[n-1]).
   • Multiply ans by n.
   • If h > 0, use lower_bound on p to find the index of the first value greater than or equal to h. Add this index + 1 to ans to get the final answer.

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int tc;
    cin >> tc;
    while (tc--) {
        int n;
        cin >> n;
        vector<ll> a(n), p(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        ll sum = 0;
        for (int i = 0; i < n; i++) sum += a[i];
        for (int i = 0; i < n; i++) p[i] = sum - a[i];
        for (int i = 1; i < n; i++) p[i] += p[i - 1];
        int q;
        cin >> q;
        while (q--) {
            ll h;
            cin >> h;
            ll ans = h / p[n - 1];
            h -= (ans * p[n - 1]);
            ans *= n;
            if (h) ans += lower_bound(p.begin(), p.end(), h) - p.begin()+1;
            cout << ans << '\n';
        }
    }
}

Good problem! :
Average problem :
Bad problem... :

We can define a_i,j = a_j,i = i + j for i ≠ j. Then gcd(*a_i,j*, i + j) > 1, and the XOR of all elements is 0 for all i, j (*i ≠ j*).

For i = j, we have i + j = 2*i, which is even. We can set a_i,i = 2.

Now, if n is even, all conditions are met.

If n is odd, the XOR of all elements is 2. To balance out that 2, we can add 2 to any value where the 2 bit is not set.

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

int main(){

	ios_base::sync_with_stdio(false); cin.tie(NULL);

	int t;
	cin>>t;

	while(t--){

		int n;
		cin>>n;

		vector<vector<int>> a(n+1,vector<int>(n+1,0));

		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(i==j) a[i][j] = 2;
				else a[i][j] = i+j;
			}
		}

		if(n&1){
			a[3][1] = 6;
		}

		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++) cout << a[i][j] << ' ';
			cout << endl;
		}

	}
	
	return 0;
}

Good problem! :
Average problem :
Bad problem... :

There are only $$$n$$$ possible different shifts.Let's calculate cost for each of them in O(1).

Assume one-based indexing for array.
Let cost[i] represent the cost of the array after i shifts.

Initial cost:
cost[0] = 1*a1 + 2*a2 + ... + n*an

cost after first shift:

Rewriting cost[1] in terms of cost[0]

cost after second shift:

Rewriting cost[2] in terms of cost[1]

The generalized formula cost[i] from cost[i-1] terms :

Why the generalized formula is correct?

Using this formula, we can compute the cost for all shifts in O(1) per shift and take minimum among all, resulting in an overall complexity of O(n).

#include<bits/stdc++.h>
using namespace std;
 
int main(){
 
    long long t;
    cin>>t;
 
    while(t--)
    {
        long long n;
        cin>>n;
        long long a[n];
        long long sum=0;
        long long ans=0;
        for(long long i=0;i<n;i++)
        {
            cin>>a[i];
            sum+=a[i];
            ans+=((i+1)*a[i]);
        }
 
        long long cost=ans;
        for(long long i=0;i<n;i++) 
        {
            cost=cost-sum+n*a[i];
            ans=min(ans,cost);
        }
        cout<<ans<<"\n";
    }
 
    return 0;
}

Good problem! :
Average problem :
Bad problem... :

Good problem! :
Average problem :
Bad problem... :

Note that performing an operation is always optimal as it won't decrease the answer.

At first, lets find the number of good subarrays before applying the operation. For this, the condition is $$$a_l + a_{l+1} ... + a_r >= k*(r-l+1)$$$ which is $$$pre[r] - k*r >= pre[l-1] - k*(l-1)$$$. So we can make a new array $$$b$$$ where $$$b_i = pre[i] - k*i$$$ and the initial number of good subarrays is equal to the number of inversions in the array $$$b$$$.

Now, lets say we increment $$$a_i$$$ by $$$1$$$ for some $$$i$$$, then the additional good subarrays formed should have their left boundary to the left of $$$i$$$ or equal to $$$i$$$ and their right boundary to the right of $$$i$$$ or equal to $$$i$$$ $$$(i.e., l \le i \le r)$$$ and $$$b_r = b_{l-1} - 1$$$. If we have the number of additional good subarrays when the operation is performed at $$$i^{th}$$$ position, we can easily find the number of additional good subarrays when the operation is performed at $$$(i+1)^{th}$$$ position using a map.

Finally we take maximum over all positions and add it to the initial answer.

Good problem! :
Average problem :
Bad problem... :