Number of ways to seat people given certain constraints

2018-11-08 06:33 tracer imported from Stackoverflow

I'm struggling with this problem so if anyone can help, that would be appreciated. The problem goes like this:

Calculate the number of ways that k people can sit in a 2 x n matrix (n and k are obtained from the user through standard input). The matrix is also given by the user and can contain the following characters: '.' - people can sit here, '#' - people can't sit here.

People in the matrix can't be adjacent (that is if one person is situated at (row, column), another person can't sit at (row-1, column) or at (row, column-1) - notice that they can sit on (row-1, column-1)).

For example, if n = 3, k = 2 and given the following matrix:

..#
...

the answer would be 5. All possible ways to seat 2 people in the matrix are (u means that a person is sitting on that field):

u.#   .u#   ..#   u.#   .u#
.u.   u..   u.u   ..u   ..u

1 answer

answered 2018-11-08 09:28 Kozyr

Let's go through 2 x N matrix from left to right. On each column we could have only 3 states:

User on top position
User on bottom position
No users

So, on each step we could move from previous states and all we need to keep number of ways for each state and each number of users:

State Top can move to states: Bottom or None
State Bottom can move to states: Top or None
State None can move to states: Top, Bottom or None

Answer is a sum of all states with K users.

Sample code:

#include <iostream>
#include <map>
#include <string>
using namespace std;

enum State: int
{
    Top,    // u
            // -

    Bottom, // -
            // u

    None,   // -
            // -
};

int main()
{
    int N, K; cin >> N >> K;
    string S[2]; cin >> S[0] >> S[1];

    map<State, map<int, int>> prev = { { None, {{0,1}} } };
    for (int i = 0; i < N; ++i) {
        map<State, map<int, int>> cur;

        if (S[0][i] == '.') {
            for (auto& w : prev[None])   cur[Top][w.first + 1] += w.second;
            for (auto& w : prev[Bottom]) cur[Top][w.first + 1] += w.second;
        }
        if (S[1][i] == '.') {
            for (auto& w : prev[None]) cur[Bottom][w.first + 1] += w.second;
            for (auto& w : prev[Top])  cur[Bottom][w.first + 1] += w.second;
        }
        for (auto& w : prev[None])   cur[None][w.first] += w.second;
        for (auto& w : prev[Top])    cur[None][w.first] += w.second;
        for (auto& w : prev[Bottom]) cur[None][w.first] += w.second;

        swap(cur, prev);
    }

    cout << (prev[Top][K] + prev[Bottom][K] + prev[None][K]) << endl;
    return 0;
}

See also questions close to this topic

What is the Big-O of the function n^2/log(n)?

the time complexity of an algorithm is given by n^2/log(n). what is that in big O notation? Just n^2 or we keep the log?
Handling difference in test data set and training data set
I have collected two separate datasets one for training machine learning algorithm and other to make predictions on the test data.

Training Dataset:
```
Type of train, Date of departure, Driving safety, Driver group
A, 2018-10-15, 5, B1
B, 2018-11-03, 2, B1
A, 2019-01-12, 6, A2
```
Test Dataset:
```
Type of train, Date of departure, Driving safety, Driver group
A, 2019-05-20,, 
B, 2018-05-21,, 
A, 2019-06-10,, 
C, 2019-06-14,,
```
I am trying to find which 'Driver group' could drive the train, also notice Driving safety is not available here. As you can see 'Date of departure', and 'Type of train' differs from training to test datasets. After I have generated ARFF file to test the test dataset on trained final model, I am having issue due to above differences, but I feel these are natural differences specially Date's would differ in both train and test datasets. I am seeing following error on the weka console:

Weka exception: training and test set are not compatible Attributes differ at position 5: Different number of labels: 89 != 250

Given the above scenario, any suggestions how can I resolve this? Is there something I should do while training my model to be liberal on certain data elements.

I have removed the 'Type of train' i.e., C unknown to the model. But Date of departure is something I cannot remove.

I expect machine learning algorithm to successfully make predictions on my test data, having the said differences.

Regards, Shravan

Minimum number of replace operations to make a string S1 palindrome by replacing it with any character such that it contains substring S2

We have 2 strings s1 and s2. Make string s1 palindrome such that it contains substring s2. and return the minimum number of operations.

Conditions: Only replace operation is allowed. (no adding or deleting is allowed) You can replace with any characters.

Ex: 1. Input:s1 = "ccccc" s2 = "zzz" output: 3

the final string is "czzzc" it requires only 3 replace operations.

Input: s1 = "cczcc" s2 = "zzz" output: 2 the final string is "czzzc" it requires only 2 replace operations.

Input: s1 = "abcde" s2 = "fg" output: 4 The final string is "afgfa" it requires only 3 replace operations.

Input: s1 = "bbb" s2 = "bab" output: 1

Input: s1 = "gambleinghuxy" s2 = "hunt" output: 8

Input: s1 = "gambleinghuxyz" s2 = "bab" output: 10

Input: s1 = "aa" s2 = "bab" output: -1

What I did is: insert the s2 at various positions into the s1 and then convert it to palindrome. Then taking the minimum replace operations.

#include<iostream>
using namespace std;

typedef struct{
int c;
string s;
}countNode;

countNode insertS2(string s1,string s2,int index){
countNode res;
res.c = 0;
for(int i = index,j=0;i < index + s2.length();){
    if(s1[i] != s2[j]){
        s1[i] = s2[j];
        j++;
        i++;
        res.c++;
    }else{
        i++;
        j = (j+1)%s2.length();
    }
}
res.s = s1;
return res;
}

int minPalinReplace(string s1,string s2,int count){
int l1 = s1.length();
int l2 = s2.length();


int n = (isEven(l1))?l1/2-1:l1/2;
for(int i=0;i<=n;i++){
    if(i == (l1-i-1))
        break;
    if( s1[i] == s1[l1 - i - 1] ){
        continue;
    }
    else{
        s1[l1-i-1] = s1[i];
        count++;
    }
}

if(s1.find(s2) == string::npos)
    return INT_MAX;

return count;
}

bool checkPalindrome(string s){
int l1 = s.length();
int n = (isEven(l1))?l1/2-1:l1/2;
for(int i=0;i<n;i++){
    if(s[i] != s[l1 - i - 1] ){
        return false;
    }
}
return true;
}

int main(){

string s1 = "gambleinghuxyz";
string s2 = "hunt";

int res = INT_MAX;
int l1 = s1.length();
int l2 = s2.length();

if( ( (l2 > l1/2 + 1) && !checkPalindrome(s2) ) || l1 < l2 )
    res = -1;
else if( ((l1 < l2) && s1.find(s2) == string::npos )){
    res = -1;
}
else if(s1.find(s2) != string::npos){
    res = minPalinReplace(s1,s2,0);
}
else{
    countNode node;
    for(int i=0;i<=l1-l2;i++){
        node = insertS2(s1,s2,i);
        res = min(res,minPalinReplace(node.s,s2,node.c));
    }
}

cout<<res<<endl;
return 0;
}

My code works for the above cases that I've figured it out. But when I submit the code it didn't work for some hidden test cases. Plz help me find the test cases for which my code doesn't work. Thanks.

This question was asked by Amazon on 10th May on-campus.

How to model partition problem as Dynamic Programming problem?
I am unable to understand how this partition problem can be thought of as a dynamic programming problem.

I have the following doubts:

1) It is not an optimization problem (or I am unable to see) then why are we applying DP approach to it?

2) DP problems satisfy 2 properties:
1. Overlapping Subproblems
2. Optimal Substructure
  
  But I am unable to see the problem satisfying the above properties.
Partition problem is to determine whether a given set can be partitioned into two subsets such that the sum of elements in both subsets is same.

arr[] = {1, 5, 11, 5}

Output: true

The array can be partitioned as {1, 5, 5} and {11}

arr[] = {1, 5, 3}

Output: false

The array cannot be partitioned into equal sum sets.
Can this problem be solved using knapsack problem-solving approach (varying-size knapsack?)
To comply with regulation a bank needs to make sure that at least 90% (or some other fixed proportion) of the money it holds is “clean”.

Money is considered clean if it is in a “clean” account. An account is considered “clean” if all the money in it comes from a verifiable source.

The bank can forcefully return money to the clients coming from a non-verifiable source in order to increment the proportion of "clean" money to comply with the regulation. The problem is to determine the minimum amount that the bank needs to return to comply with the regulation.
```
Account Verif   NonVerif    Divi    Clean   NotClean
1   889.77  157.01  5.67    0   1046.78
2   907.88  160.21  5.67    0   1068.09
3   1187.18 209.5   5.67    0   1396.68
4   918.12  162.02  5.67    0   1080.14
5   1721.88 303.86  5.67    0   2025.74
6   828.17  276.05  3.00    0   1104.22
7   1127.6  375.86  3.00    0   1503.46
8   1177.13 392.37  3.00    0   1569.5
9   801.81  267.27  3.00    0   1069.08
10  741.9   247.3   3.00    0   989.2
11  0   1468.11 0.00    0   1468.11
12  0   853.66  0.00    0   853.66
13  2354.81 0   -1.00   2354.81 0
14  2267.1  0   -1.00   2267.1  0
15  2238.3  0   -1.00   2238.3  0
16  2188.66 0   -1.00   2188.66 0
17  2167.85 0   -1.00   2167.85 0
18  2166.1  0   -1.00   2166.1  0
19  2165.59 0   -1.00   2165.59 0
20  2163.84 0   -1.00   2163.84 0
21  2145.43 0   -1.00   2145.43 0
22  2117.76 0   -1.00   2117.76 0
23  1320.26 0   -1.00   1320.26 0
24  1299.99 0   -1.00   1299.99 0
25  1241.02 0   -1.00   1241.02 0
26  1237.36 0   -1.00   1237.36 0
27  1208.74 0   -1.00   1208.74 0
28  1114.58 0   -1.00   1114.58 0
29  1048.63 0   -1.00   1048.63 0
30  1010.92 0   -1.00   1010.92 0
31  971.1   0   -1.00   971.1   0
32  874.95  0   -1.00   874.95  0
33  832.01  0   -1.00   832.01  0
34  825.72  0   -1.00   825.72  0
TOTAL   45262.16    4873.22     34960.72    15174.66
```
In the example above, total money held by the bank is 34960.72 + 15174.66 = 50135.38; without doing any cleansing, only the 69.7% (34960.72 / 50135.38 = 0.697...) can be considered clean so the bank needs to cleanse to comply with the regulation.

If the bank cleansed the first two accounts then the total money held by the bank would be 50135.38 - 157.01 - 160.21 = 49818.16 and clean money would be 34960.72 + 889.77 + 907.88 = 36758.37; the proportion of clean money would be 36758.37 / 49818.16 = 73.7%.

In the example above, Div=Verif/NonVerif (Verif would be value and NonVerif would be Weight, as to see the items that provide the best ratio to select those); the list in example is sorted by descending Div. Naive approach is to pick which accounts to cleanse in that order until the bank complies with the regulation.

I was thinking of using approach suggested by Avikalp Srivastava here: so Verif (value) would be treated as weight and NonVerif (cost) would be treated as value; the regular knapsack problem-solving approach would then be used to find the maximum cost that can be removed while Verif remains >= 90% * (total money held by the bank); the thing is the total money held by the bank decreases when you add not-clean items to the knapsack because the bank is returning that money to the customer (so the knapsack would become smaller as more items get added to it?). Brute force caused memory overflow for the data shown. I actually tried to solve this for hours without getting any closer to the answer. Maybe knapsack problem-solving is not the correct approach for this (?)

The naive approach will suffice for my purposes, but I still want to find out how to solve it properly.
WIN or LOSE coding contest: Codegladiators
A new fighting game has become popular. There are N number of villains with each having some strength. There are N players in the game with each having some energy. The energy is used to kill the villains. The villain can be killed only if the energy of the player is greater than the strength of the villain.

Maxi is playing the game and at a particular time wants to know if it is possible for him to win the game or not with the given set of energies and strengths of players and villains. Maxi wins the game if his players can kill all the villains with the allotted energy.

Input Format

The first line of input consist of number of test cases, T.

The first line of each test case consist of number of villains and player, N.

The second line of each test case consist of the N space separated strengths of Villains.

The third line of each test case consist of N space separated energy of players.

Constraints
- 1<= T <=10
- 1<= N <=1000
- 1<= strength , energy <=100000
Output Format

For each test case, Print WIN if all villains can be killed else print LOSE in separate lines.

Sample TestCase 1

Input

1

6

112 243 512 343 90 478

500 789 234 400 452 150

Output

WIN

Explanation

For the given test case, If we shuffle the players and villains, we can observe that all the villains can be killed by players.

Player Villain RESULT 500 478 WIN 789 512 WIN 234 112 WIN 400 243 WIN 452 343 WIN 150 90 WIN

As all the villains can be killed by the players, MAXI will WIN the game. Thus, the final output is WIN.

Sample TestCase 2

Input

2

6

10 20 50 100 500 400

30 20 60 70 90 490

5

10 20 30 40 50

40 50 60 70 80

Output

LOSE

WIN

so far i tried the , but i dont know how to do shuffling?

Part-2: Codegladiators-Neighbours and New Year Party

Related questions

Number of ways to seat people given certain constraints

1 answer

See also questions close to this topic

Training Dataset:

Test Dataset: