Related questions

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:

    1. User on top position
    2. User on bottom position
    3. 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

  • How can I fix this quicksort partition in python? (dealing with Numpy arrays)

    I've been working on this quicksort partition for several days and still can't fix it. I've tried debugging it with prints to see how partitions evolve when called by the main quicksort but still can't figure out how to fix it. Showing the doctest to give context, apologies if it isn't relevant.

    It works on some examples but not in others and can't figure out why. Any insight and help much appreciated.

    def partition (s, cmp):
>>> import generate
>>> import numpy
>>> import element
>>> def cmp (x,y):
...    if x == y:
...       return 0
...    elif x < y:
...       return -1
...    else:
...       return 1
>>> t = numpy.array([element.Element(i) for i in [3, -8, 2 , -2, 3, 7, 9, 1, -1, 7]])
>>> p = {'left':0,'right':len(t)-1,'data':t}
>>> p1,p2 = partition(p,cmp)
>>> p1['data'][p1['left']:p1['right']+1]
array([-8, 2, -2, 3, -1, 1], dtype=object)
>>> p2['data'][p2['left']:p2['right']+1]
array([9, 7, 7], dtype=object)
"""
    a = s["data"]   #whole array
    lp = s["left"]+1  #left pointer
    rp = s["right"]    #right pointer
    pivot = a[lp-1]    #pivot is element of index lp=0 in slice
    while lp <= rp:
        if cmp(a[lp], pivot) <= 0:  #lp is already on the correct side since it's <= to pivot
            a[lp-1] = a[lp]
            lp += 1   #moving towards center
        else:
            a[lp], a[rp] = a[rp], a[lp] #taking advantage of python's easy swap
            rp -= 1     #moving towards center
    a[rp] = pivot   #replacing pivot in the end
    lslice = {"data" : a, "left" : s["left"], "right" : rp-1}   #<pivot
    rslice = {"data" : a, "left" : rp+1, "right" : s["right"]}  #>pivot
    return (lslice,rslice)
  • How can a maximum sub array problem fail when one omits one side or the other?

    If the right side is omitted, what can the left side have for it to fail? And vice versa. If the left is omitted, what can the right side be so that it fails?

  • Find the most "empty" place in an array

    Let's say that I've the following numpy array:

    foo = np.asarray([
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1],
    [1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1],
    [1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
    [1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1],
    [1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
])

    As you can see, it contains some 0 et 1. I'm searching for the most "empty" place in this array. I mean the place where you find the higher density of 0. I would like to do a function that return me the row and col index of the center of that place.

    For the moment what I tried to do is to cut that array in four parts of the same size with a function like this :

    def blockshaped(arr, nrows, ncols):
    """Return an array of shape (n, nrows, ncols)."""
    h, w = arr.shape
    arr = arr.reshape(h // nrows, nrows, -1, ncols)
    arr = arr.swapaxes(1, 2)
    arr = arr.reshape(-1, nrows, ncols)

    return (arr)

    Then I compute the sum of each part. Take the cut where the sum was the lowest and cut in again in 4, and so on... But I feel it's not the right things to...

  • Length of longest subarray having gcd greater than 1

    Assume an array of length n. We have to calculate the length of the longest subarray having the gcd greater than 1. How can I solve this with dynamic programming?

    for example : arr[]={2,4,6,12,15,21,27} length of longest subarray having gcd 3 in this case is 5.

  • Number of ways to buy candy given a money value and candy prices

    While trying to solve a problem at brilliant.org Dynamic Programming: Level 4 Challenges I tried a simple solution of just using an array (or list) and storing the number of ways each money value can be spent. This works until the money variable goes higher than 10. At 11 it has 1 more than it should, and I cannot find out why. I imagine it is counting the same value twice, but as there are too many posibilities at this point, it is infeasible to count one by one.

    I already looked at the solution, but I'd just like a hint on what I might be missing here.

    EDIT: All permutations of possible solutions should also be counted.

    money = 40
values = [1, 2, 5, 10]

def solver(money, values):
    mtx = [0 for _ in range(money+1)]

    mtx[0] = 1; mtx[1] = 1

        for i in range(2, money+1):
            for v in values:
            if i - v >= 0:
                mtx[i] += mtx[i-v]

    return mtx[-1]

    EDIT 2: This code, posted on the solutions section of the website, gives the correct answer. I think the line "res = 1 if n == 0 else 0", when it does an "else 0", is probably where the correcting from my solution is made, but I cannot be sure

    Candide_ = {}

def Candide(n, depth):
    "Candice's trip to the candy shop"
    if depth == 0:
        res = 1 if n == 0 else 0
    elif n == 0:
        res  = 1
    elif (n, depth) in Candide_:
       res  =  Candide_[(n, depth)]
    else:
        res = sum(Candide(m, depth - 1) for m in [n-1, n-2, n-5, n-10] if m >= 0)
        Candide_[(n, depth)] = res
    return res

print(Candide(40, 10))
  • Maximum sum from a 2D array-DP

    Given a 2D array with weights, find the maximum sum of the 2D array with the condition that we can select only one element from a row and the element under the selected element cannot be selected(this condition should hold true for all elements which are selected). Also we can see that sum will contain elements equal to the number of rows.

    If arr[i][j] is any selected element then I cannot select arr[i+1][j]. Also from each row only one element can be selected. Example if arr[i][1] is selected arr[i] [2 or 3 or..] cannot be selected

    Edit- I tried solving it using DP. Took a 2D array DP where DP[i][j]= max(arr[i+1][k] for k=1 to n and k!=j)+ arr[i][j] Then did this to build the DP matrix and finally looped to calculate the maximum. But I think complexity is very high when I approach like this. Please help!

    Input Matrix-

    1 2 3 4 
5 6 7 8 
9 1 4 2 
6 3 5 7

    Output- 27