Tutorialspoint.dev

Check if all people can vote on two machines

There are n people and two identical voting machines. We are also given an array a[] of size n such that a[i] stores time required by i-th person to go to any machine, mark his vote and come back. At one time instant, only one person can be there on each of the machines. Given a value x, defining the maximum allowable time for which machines are operational, check whether all persons can cast their vote or not.

Examples:

Input  : n = 3, x = 4
         a[] = {2, 4, 2}
Output: YES
There are  n = 3 persons say and maximum
allowed time is x = 4 units. Let the persons
be P0, P1, and P2 and two machines be M0 and M1.
At t0: P0 goes to M0
At t0: P2 goes to M1
At t2: M0 is free, p3 goes to M0
At t4: both M0 and M1 are free and all 3 have
        given their vote.

Let sum be the total time taken by all n people. If sum <=x, then answer will obviously be YES. Otherwise, we need to check whether the given array can be split into two parts such that the sum of the first part and sum of the second part are both less than or equal to x. The problem is similar to the knapsack problem. Imagine two knapsacks each with capacity x. Now find, maximum people who can vote on any one machine i.e. find maximum subset sum for a knapsack of capacity x. Let this sum be s1. Now if (sum-s1) <= x, then answer is YES else answer is NO.

C++

// C++ program to check if all people can
// vote using two machines within limited
// time
#include<bits/stdc++.h>
using namespace std;
  
// Returns true if n people can vote using
// two machines in x time.
bool canVote(int a[], int n, int x)
{
    // dp[i][j] stores maximum possible number
    // of people among arr[0..i-1] can vote
    // in j time.
    int dp[n+1][x+1];
    memset(dp, 0, sizeof(dp));
  
    // Find sum of all times
    int sum = 0;
    for (int i=0; i<=n; i++ )
        sum += a[i];
  
    // Fill dp[][] in bottom up manner (Similar
    // to knapsack).
    for (int i=1; i<=n; i++)
        for (int j=1; j<=x; j++)
            if (a[i] <= j)
                dp[i][j] = max(dp[i-1][j],
                        a[i] + dp[i-1][j-a[i]]);
            else
                dp[i][j] = dp[i-1][j];
  
    // If remaining people can go to other machine.
    return (sum - dp[n][x] <= x);
}
  
// Driver code
int main()
{
    int n = 3, x = 4;
    int a[] = {2, 4, 2};
    canVote(a, n, x)? cout << "YES " :
                      cout << "NO ";
    return 0;
}

Python3

# Python3 program to check if all people can
# vote using two machines within limited
# time
  
# Function returns true if n people can vote 
# using two machines in x time.
def canVote(a, n, x):
      
    # dp[i][j] stores maximum possible number
    # of people among arr[0..i-1] can vote
    # in j time.
    dp = [[0] * (x + 1) for _ in range(n + 1)]
    a = a[:]
    a.append(0)
  
    # Find sum of all times
    sm = 0
    for i in range(n + 1):
        sm += a[i]
  
    # Fill dp[][] in bottom up manner 
    # (Similar to knapsack).
    for i in range(1, n + 1):
        for j in range(1, x + 1):
            if a[i] <= j:
                dp[i][j] = max(dp[i - 1][j], a[i] + 
                               dp[i - 1][j - a[i]])
            else:
                dp[i][j] = dp[i - 1][j]
  
    # If remaining people can go to other machine.
    return (sm - dp[n][x]) <= x
  
# Driver Code
if __name__ == "__main__":
    n = 3
    x = 4
    a = [2, 4, 2]
    print("YES" if canVote(a, n, x) else "NO")
  
# This code is contributed 
# by vibhu4agarwal


Output:

YES

Time Complexity: O(x * n)
Auxiliary Space: O(x * n)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter