HackerEarth Good strings problem solution

In this HackerEarth Good strings problem solution There is a string consisting of only three characters (, ) and #.

For Example:- s = ((#)(#))

index = 1234 56 7 8

Here, the bracket pairs are 1 -> 8, 2 -> 4, and 5 -> 7 and each bracket pair can have some non – negative value associated with it.

You can categorize the bracket pair and # into two categories alpha and beta. # are also associated with some non-negative values which will be provided in the input.

Now you have to assign the category to each of the characters (i.e. alpha or beta) and non-negative values to the bracket pair such that the given string is the good string.

The good string is the string if the gamma values for each of the bracket pair is equal to Vali (Vali is provided in the input).

Gamma value is the sum of all the values of the character contained in the bracket pair whose category is the same as the category of the current bracket pair.

HackerEarth Good strings problem solution.

#include <bits/stdc++.h>
using namespace std;
const int N = 5010;
string s;
int n;
int cntHsh,cntBrac;
map<int,int> hshCos,braCos,matBrac;
int dp[N];
void brute(int i,int j){
  vector<int> task;
  int res = 0;
  for(int k = i + 1;k < j;k++){
    if(s[k] == '#'){
      dp[k] = hshCos[k];
      if(hshCos[k] < dp[k] - hshCos[k]) res += hshCos[k];
      else res += dp[k] - hshCos[k];
      task.push_back(abs(2 * hshCos[k] - dp[k]));
      dp[i] += dp[k];
    }else{
      brute(k,matBrac[k]);
      if(braCos[k] < dp[k] - braCos[k]) res += braCos[k];
      else res += dp[k] - braCos[k];
      task.push_back(abs(2 * braCos[k] - dp[k]));
      dp[i] += dp[k];
      k = matBrac[k];
    }
  }
  bitset <N> check = 0;
  check[res] = 1;
  for (int x : task){
   check |= (check << x);
  }
  for (int k = braCos[i]; k >= 0; k--){
    if (check[k] == 1) {
      dp[i] += braCos[i] - k;
      return ;
    }
  }
  cout << "Non";
  exit(0);
}
signed main(){
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  cin >> n >> s;
  for(auto x : s){
    if(x == '#'){
      cntHsh++;
    }else if (x == '('){
      cntBrac++;
    }
  }
  for(int i = 0;i < cntHsh;i++){
    int indx,val;
    cin >> indx >> val;
    indx--;
    hshCos[indx] = val;
  }
  for(int j = 0;j < cntBrac;j++){
    int indx1,indx2,val;
    cin >> indx1 >> indx2 >> val;
    indx1--;
    indx2--;
    braCos[indx1] = val;
    matBrac[indx1] = indx2;
  }
  brute(0,n - 1);
  cout << "Yesn";
}

Second solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e3 + 14, maxv = 5e4 + 14;
int n, dp[maxn], dval[maxn], hval[maxn], fin[maxn];
string s;
bool dfs(int v){
    // cerr << v << endl;
    bitset<maxv> knapsack;
    knapsack[0] = true;
    int sum = 0;
    auto add = [&knapsack, &sum](int x){
        sum += x;
        return knapsack << x;
    };
    for(int i = v + 1; i < fin[v] - 1; )
        if(s[i] == '#')
            knapsack |= add(hval[i++]);
        else{
            if(!dfs(i))
                return false;
            knapsack = add(dp[i]) | add(dval[i]);
            i = fin[i];
        }
    if(v == 0)
        return true;
    int near = dval[v];
    while(near >= 0 && !knapsack[near])
        near--;
    // cerr << v << " = " << near << 'n';
    if(near == -1)
        return false;
    dp[v] = sum - near;
    return true;
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> s;
    for(auto c : s)
        if(c == '#'){
            int i;
            cin >> i;
            cin >> hval[i];
        }
    for(auto c : s)
        if(c == '('){
            int b;
            cin >> b;
            cin >> fin[b] >> dval[b];
            fin[b]++;
        }
    s = '(' + s + ')';
    fin[0] = s.size();
    cout << (dfs(0) ? "Yes" : "No") << 'n';
}

HackerEarth Good strings problem solution

HackerEarth Good strings problem solution.

Second solution

Leave a Reply

Pages

Practice