22 months ago

srijansriv • 20

Islāmpur

is it possible that the second question's example can be completed with the rest of the photos maybe?

6 months ago

Nihal Reddy • 0

Hyderabad

#Q1
def smallest_subarray_infinite(arr, k):
    n = len(arr)
    total = sum(arr)
    prefix = {0: -1}
    curr, min_len = 0, float('inf')
    
    for i in range(2 * n):
        curr += arr[i % n]
        if curr - k in prefix:
            min_len = min(min_len, i - prefix[curr - k])
        if curr not in prefix:
            prefix[curr] = i
            
    if total > 0 and k > total:
        cycles = k // total
        rem = k % total
        part = smallest_subarray_infinite(arr, rem) if rem else 0
        return cycles * n + part if part != -1 else -1

    return min_len if min_len != float('inf') else -1



#Q2
def max_distance(starts, d):
    starts.sort()
    
    def feasible(dist):
        last = starts[0]
        for x in starts[1:]:
            pick = max(x, last + dist)
            if pick > x + d:
                return False
            last = pick
        return True

    lo, hi, ans = 0, max(starts) + d, 0
    while lo <= hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            ans = mid
            lo = mid + 1
        else:
            hi = mid - 1
    return ans

#Q3
MOD = 10**9 + 7

def special_values_sum(arr, k):
    n = len(arr)
    dp = [0] * (k + 1)
    dp[0] = 1
    total = 0
    
    for val in arr:
        for j in range(k, val - 1, -1):
            dp[j] = (dp[j] + dp[j - val]) % MOD
        total = (total + dp[k]) % MOD
    
    return (dp[k] - 1 + MOD) % MOD

6 months ago

Nihal Reddy • 0

Hyderabad

Effective use

6 months ago

Reddiwary Dhrutvan Reddy • 0

Bengaluru

Q1)

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

int smallest_subarray_infinite(vector<int>& arr, int k) {
    int n = arr.size();
    int total = accumulate(arr.begin(), arr.end(), 0);

    unordered_map<int, int> prefix;
    prefix[0] = -1;
    int curr = 0, min_len = INT_MAX;

    for (int i = 0; i < 2 * n; ++i) {
        curr += arr[i % n];
        if (prefix.count(curr - k))
            min_len = min(min_len, i - prefix[curr - k]);
        if (!prefix.count(curr))
            prefix[curr] = i;
    }

    if (total > 0 && k > total) {
        int cycles = k / total;
        int rem = k % total;
        int part = rem ? smallest_subarray_infinite(arr, rem) : 0;
        return (part != -1) ? cycles * n + part : -1;
    }
    return (min_len == INT_MAX) ? -1 : min_len;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) cin >> arr[i];
    cout << smallest_subarray_infinite(arr, k) << endl;
    return 0;
}

Q2)

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

bool feasible(vector<int>& starts, int d, int dist) {
    int last = starts[0];
    for (int i = 1; i < starts.size(); ++i) {
        int pick = max(starts[i], last + dist);
        if (pick > starts[i] + d) return false;
        last = pick;
    }
    return true;
}

int max_distance(vector<int>& starts, int d) {
    sort(starts.begin(), starts.end());
    int lo = 0, hi = *max_element(starts.begin(), starts.end()) + d, ans = 0;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (feasible(starts, d, mid)) {
            ans = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return ans;
}

int main() {
    int n, d;
    cin >> n >> d;
    vector<int> starts(n);
    for (int i = 0; i < n; ++i) cin >> starts[i];
    cout << max_distance(starts, d) << endl;
    return 0;
}

Q3)

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;

int special_values_sum(vector<int>& arr, int k) {
    vector<int> dp(k + 1, 0);
    dp[0] = 1;
    for (int val : arr) {
        for (int j = k; j >= val; --j) {
            dp[j] = (dp[j] + dp[j - val]) % MOD;
        }
    }
    return (dp[k] - 1 + MOD) % MOD;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) cin >> arr[i];
    cout << special_values_sum(arr, k) << endl;
    return 0;
}