2.5 years ago

Geetika Aggarwal • 20

More ones

class Solution{
public:
  // Function to count the number of substrings
  long long countSubstring(string S){
    int n=S.size();
    long long ans=0,zero=n,minus=0;
    int mp[2*n+5];
    memset(mp,0,sizeof(mp));
    int cur=zero;

    // Loop through the string to determine the number of zeros and minuses
    for(auto i:S){
      if(i=='0')
        cur--;
      else
        cur++;
      if(cur<=zero){
        minus++;
      }
      mp[cur]++;
    }
    
    // Loop through the string again to count the number of valid substrings
    for(int i=0;i<n;i++){
      ans+=(n-i-minus);
      if(S[i]=='1'){
        mp[zero+1]--;
        zero++;
        minus+=mp[zero];
      }
      else{
        mp[zero-1]--;
        zero--;
        minus--;
        minus-=mp[zero+1];
      }
    }
    return ans;
  }
};

2.5 years ago

JoJo • 10

Minimum Cost Path 

class Solution {
    public int minCostPath(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                max = Math.max(max, grid[i][j]);
                min = Math.min(min, grid[i][j]);
            }
        }

        int low = 0;
        int high = max - min;

        int ans = -1;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (isPossible(grid, mid)) {
                ans = mid;
                high = mid - 1;
            } else low = mid + 1;
        }

        return ans;
    }

    private boolean isPossible(int[][] grid, int mid) {
        Deque<Pair> queue = new ArrayDeque<>();
        for (int i = 0; i < grid.length; i++) {
            queue.add(new Pair(0, grid[i][0], grid[i][0]));
        }

        while (!queue.isEmpty()) {
            Pair pair = queue.poll();
            int j = pair.j;
            if (j == grid[0].length - 1) return true;

            int next = j + 1;

            for (int i = 0; i < grid.length; i++) {
                int val = grid[i][next];
                if (Math.abs(val - pair.max) <= mid && Math.abs(val - pair.min) <= mid) {
                    queue.add(new Pair(next, Math.max(val, pair.max), Math.min(val, pair.min)));
                }
            }
        }

        return false;
    }
}

class Pair {
    int j;
    int max;
    int min;
    Pair (int j, int m, int n) {
        this.j = j;
        this.max = m;
        this.min = n;
    }
}

18 months ago

Shivam Bhadani • 10

Bengaluru

Minimum Cost Path

/* जय श्री गणेश */

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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
#define all(x) x.begin(), x.end()
#define nline '\n'

void run_case()
{
	int n, m;
	cin >> n >> m;
	vector<vector<int>> a(n, vector<int>(m));
	for (auto& v : a) {
		for (auto& x : v) {
			cin >> x;
		}
	}
	vector<pair<int, int>> track;
	for (int j = 0; j < m; j++) {
		for (int i = 0; i < n; i++) {
			track.push_back({a[i][j], j});
		}
	}
	sort(all(track));
	map<int, int> mp;
	int ans = INT_MAX;
	int i = 0;
	for (int j = 0; j < n * m; j++) {
		++mp[track[j].second];
		if (mp.size() >= m) {
			while (mp[track[i].second] > 1) {
				--mp[track[i].second];
				++i;
			}
			ans = min(ans, track[j].first - track[i].first);
		}
	}
	cout << ans << nline;
}

int32_t main() {
	IOS
	int test_cases;
	cin >> test_cases;
	while (test_cases--)
	{
		run_case();
	}
	return 0;
}

6 months ago

Nihal Reddy • 0

Hyderabad

def merge_count_inversions(arr, temp, left, mid, right):
    i = left
    j = mid + 1
    k = left
    inv_count = 0
    
    while i <= mid and j <= right:
        if arr[i] <= arr[j]:
            temp[k] = arr[i]
            i += 1
        else:
            temp[k] = arr[j]
            inv_count += (mid - i + 1)
            j += 1
        k += 1
    
    while i <= mid:
        temp[k] = arr[i]
        i += 1
        k += 1
    
    while j <= right:
        temp[k] = arr[j]
        j += 1
        k += 1
    
    for i in range(left, right + 1):
        arr[i] = temp[i]
    
    return inv_count

def merge_sort_count(arr, temp, left, right):
    inv_count = 0
    if left < right:
        mid = (left + right) // 2
        inv_count += merge_sort_count(arr, temp, left, mid)
        inv_count += merge_sort_count(arr, temp, mid + 1, right)
        inv_count += merge_count_inversions(arr, temp, left, mid, right)
    return inv_count

def count_substrings_more_ones(s):
    n = len(s)
    
    
    nums = [1 if c == '1' else -1 for c in s]
    
   
    prefix = [0] * n
    prefix[0] = nums[0]
    for i in range(1, n):
        prefix[i] = prefix[i-1] + nums[i]
    
    
    count = sum(1 for p in prefix if p > 0)
    
    prefix.reverse()
    
   
    temp = [0] * n
    inversions = merge_sort_count(prefix, temp, 0, n - 1)
    
    return count + inversions


def solve():
    t = int(input())
    for _ in range(t):
        s = input().strip()
        print(count_substrings_more_ones(s))


if __name__ == "__main__":
    solve()

6 months ago

annu sevada • 0

Jaipur

def count_substrings_more_ones(s):
    n = len(s)
    nums = [1 if c == '1' else -1 for c in s]
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]
    count = 0
    for start in range(n):
        for end in range(start + 1, n + 1):
            if prefix[end] - prefix[start] > 0:
                count += 1
    return count

def solve():
    t = int(input())
    for _ in range(t):
        s = input().strip()
        print(count_substrings_more_ones(s))

if __name__ == "__main__":
    solve()