ALCATRAZ2 - GO GOA GONE | SPOJ



So, it was winter and Me and 8 of my friends decided to plan a trip to GOA. Since the Bars and Clubs are too Expensive out there, we decided to pool money together for our whole trip expenses. Now since every group has some internal politics going on, the same applies to our group also :P . 2 Members that are having a cold war between them won't go to the trip if the other one is going. But Since we want to enjoy a lavish party, we want to maximize the pooled money. So, for this task, I've chosen my Marwari friend Mohit to solve this problem  ( He's good at money matters ). Your task is to help Mohit achieve the maximum pooled money.

Input

First Line will contain  8 space-separated integers denoting the money contributed by each member in order.
The next line will contain the total number of pairs having a cold war between them. Let us denote this by P.
The next P lines will contain 2 numbers separated by a space showing the members having a cold war. Numbers used to denote members will be ( 1-8 ) for each 8 members.
Constraints:
Everything is guarenteed to  easily fit in 32 bit integer type  .
Output description
Output will give the maximum amt of money that can be pooled.
Example
Input: 
3 14 5 2 3 4 1 9 
4
1 2
2 3
4 5
7 8
Output:

30


Solution (C++) :

#include <iostream>

#include <vector>

using namespace std;


int m;

int a[8];

int assignment[8];

int finalAns = 0;

vector <int> Adjlist[8];


void backtrack(int n) {

    for (int i = 0; i < 2; i++) {

        assignment[n] = i;

        if (n == 7) {

            bool satisfied = true;

            for (int j = 0; j < 8; j++)

                if (assignment[j] == 1) {

                    for (int zz = 0; zz < Adjlist[j].size(); zz++)

                        if (assignment[Adjlist[j][zz]] == 1)

                            satisfied = false;

                }

            if (satisfied) {

                int tmp = 0;

                for (int j = 0; j < 8; j++)

                    if (assignment[j] == 1) {

                        tmp += a[j];

                    }

                if (tmp > finalAns)

                    finalAns = tmp;

            }

        } else

            backtrack(n+1);

        assignment[n] = 0;

    }

}


int main() {

    int tmpA, tmpB;

    for (int i = 0; i < 8; i++) {

        cin >> a[i];

        assignment[i] = 0;

    }

    cin >> m;

    for (int i = 0; i < m; i++) {

        cin >> tmpA >> tmpB;

        Adjlist[tmpA-1].push_back(tmpB-1);

        Adjlist[tmpB-1].push_back(tmpA-1);

    }

    backtrack(0);

    cout << finalAns << "\n";

} 


Comments

Post a Comment

Popular posts from this blog

Boxes through a Tunnel | HackerRank

You are transporting some boxes through a tunnel, where each box is a  parallelepiped , and is characterized by its length, width and height. The height of the tunnel   feet and the width can be assumed to be infinite. A box can be carried through the tunnel only if its height is strictly less than the tunnel's height. Find the volume of each box that can be successfully transported to the other end of the tunnel. Note: Boxes cannot be rotated. Input Format The first line contains a single integer  , denoting the number of boxes.  lines follow with three integers on each separated by single spaces    ,   and   which are length, width and height in feet of the  -th box. Constraints Output Format For every box from the input which has a height lesser than   feet, print its volume in a separate line. Sample Input 0 4 5 5 5 1 2 40 10 5 41 7 2 42 Sample ...
Read more

Array Manipulation | HackerRank

Image
Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in your array. For example, the length of your array of zeros  . Your list of queries is as follows: a b k 1 5 3 4 8 7 6 9 1 Add the values of   between the indices   and   inclusive: index -> 1 2 3 4 5 6 7 8 9 10 [ 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ] [ 3 , 3 , 3 , 3 , 3 , 0 , 0 , 0 , 0 , 0 ] [ 3 , 3 , 3 , 10 , 10 , 7 , 7 , 7 , 0 , 0 ] [ 3 , 3 , 3 , 10 , 10 , 8 , 8 , 8 , 1 , 0 ] The largest value is   after all operations are performed. Function Description Complete the function  arrayManipulation  in the editor below. It must return an integer, the maximum value in the resulting array. arrayManipulation has the fo...
Read more

String Validators | HackerRank

Python has built-in string validation methods for basic data. It can check if a string is composed of alphabetical characters, alphanumeric characters, digits, etc. str.isalnum() This method checks if all the characters of a string are alphanumeric  (a-z, A-Z and 0-9) . >>> print 'ab123'.isalnum() True >>> print 'ab123#'.isalnum() False str.isalpha() This method checks if all the characters of a string are alphabetical  (a-z and A-Z) . >>> print 'abcD'.isalpha() True >>> print 'abcd1'.isalpha() False str.isdigit() This method checks if all the characters of a string are digits  (0-9) . >>> print '1234'.isdigit() True >>> print '123edsd'.isdigit() False str.islower() This method checks if all the characters of a string are lowercase characters  (a-z) . >>> print 'abcd123#'.islower() True >>> print 'Abcd123#'.islower() False str....
Read more