LT15-Editorial

editorial
, ,
1

Problem Link

Loop Through

Author: isag2008

Difficulty

MEDIUM

Prerequisites

Dynamic Programming

Problem Statement

Henry and your friends (N in total including Henry) decide to go to an escape room called 'Trapped in the 80s'. One room requires them to "steal" some money from a fake bank vault, and they have exactly M minutes to do so before the guards get alerted and they lose the game.
The catch is that the vault has motion sensors that gets triggered if there are more than two people inside at a time.

To collect the money, the ith friend needs to be inside for exactly X[i] minutes (0 ≤ i ≤ N), in one continous stretch. Every friend should be able to take their money without getting caught in order to win the game. You have to find if there is any way that they can win.

If one person goes inside the vault at a time "A" and at the same time another person comes out, it's equivalent to saying they were never in the vault at the same time. Similarly, when the security gets inside vault at time M and a friend comes out exactly at time M, the guard will not be able to see the friend.

Approach

We have an array of size N, A[i] and an integer M. The friends can successfully execute the plan if, within a time period of M, each one of them is able to visit the vault for X[i] time and not more than two of them are present in the vault at any time.

Let us define sum(S) where S is a set as the sum of all elements in the S.
So, if we are able to divide the array X into two disjoint subsets set1 and set2 such that set1 union set2 = X and set1 intersection set2 = NULL, and sum(set1)<=M and sum(set2)<=M, it’s is possible to execute the plan.

Therefore, sum(set1) <= M
sum(set2) <= M
sum(set1) + sum(set2) = sum(X)

From above three equations, if there exists any set Z such that
(sum(X) – M) <= sum(Z) <= M (obviously (sum(X)-M)<=M holds)
then our solution is possible.

The above condition can be checked by using the classic Dynamic programming problem subset sum problem.

Solution

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

 int main()
 {
      int test;
      scanf("%d", &test);
      assert(test>=1 && test<=20);
      while(test-->0) {
           int N, G;
           cin >> N >> G;
           assert(N >= 1 && N <= 100);
           assert(G >= 0 && G <= 1e6);
           vector <int> tm(N);
           int sum = 0;
           for(int i = 0; i < (int)N; ++i) {
                cin >> tm[i];
                assert(tm[i] >= 0 && tm[i] <= 100);
                sum += tm[i];
           }
           vector <bool> sumPossible((int)1e4+1, false);
           sumPossible[0] = true;

          for(auto it = (tm).begin(); it != (tm).end(); ++it) {
                for(int t = (int)1e4; t >= (int)0; --t) {
                       if(t - *it >= 0 && sumPossible[t - *it] == true) {
                            sumPossible[t] = true;
                      }
               }
          }
          bool flag = false;
          for(int i = 0; i <= (int)sum; ++i) {
                if(sumPossible[i] && i <= G && sum - i <= G) {
                      flag = true;
               }
          }
          cout << (flag ? "YES" : "NO") << "\n";
      }

      return 0;
}