Java Algorithms – How to Solve a Seating Problem

algorithmsjava

I was solving a seating problem whose solution seems trivial but I am not able to get it. The problem states in short that we have to seat n (even) students in n/2 rows where students are labelled from 1 to n and no two adjacent students should have consecutive labels like "1 2" or "5 4". Also every student is either in class L or R. No row should have a R students at the left position and L student in the right position simultaneously.

My approach was to first choose a student from a non-empty class and then iterate through all other left students so that whichever is feasible to be seated with him and make them sit and so on. In this process I choose first from L class and seat him on the left and if it is empty then from the R class.

Here:

        List<Integer> L = new ArrayList<>();
        List<Integer> R = new ArrayList<>();
        int n = in.nextInt();//number of students
        String s = in.nextLine();//It is a string like "RRLRLRLL" where i^th character is the class of i^th student
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == 'L')
                L.add(i + 1);
            else
                R.add(i + 1);
        }
        for (int i = 0; i < n / 2; i++) {
            int x = (L.size() > 0) ? L.remove(0) : R.remove(0);
            int y = 0;
            if (L.size() > 0) {
                y = findfrom(x, L, R);
            } else if (R.size() > 0) {
                y = findfrom(x, R, L);
            }
            out.println(x + " " + y);

private int findfrom(int x, List<Integer> L, List<Integer> R) {
    int y = -1;
    int j = 0;
    do {
        y = L.get(j);
        j++;
    } while (Math.abs(y - x) == 1 && j < L.size());
    if (Math.abs(y - x) != 1)
        L.remove(new Integer(y));
    else
        y = findfrom(x, R, L);
    return y;
}

But this would fail for the case where n=6 and L=[2,3,6] and R=[1,4,5] (RLLRRL).
Now we will choose 2 and 6. Then 3 and 1. Then left are 4 and 5, which is a problem.

I also thought of doing:
– DFS
– Random arrangement followed by swapping wrong student to another feasible position

What can I do, What am I not thinking?

See "Problem-234A : Codeforces" for more details.

Best Answer

The problem is inviting you to overthink it. You can solve it by making sure you don't give each rule more power over you than it deserves. This is a requirements gathering problem. Always boil a requirement down to the real needs. Don't let it create added assumptions about what it needs.

What you're missing is that the RL part of the problem (elbow bumping) is trivial to solve.

One of the example outputs looks like this:

1 4
2 5
6 3

That means 1 and 2 are not considered adjacent to each other. So being adjacent only happens horizontally, that is, at the same desk.

That makes the RL problem trivial because it doesn't matter what desk is next to what desk. You just need pairs whose numbers don't conflict. Once you have that you can fix RL by just swapping them because LR is just as legal as LL and RR.

I can even predict how they will always get their output. Their method of finding non conflicting pairs is to just cut the group in half to make two groups and pair lowest to highest.

It's obvious if you think of this:

6  
LLRLLL

as

L R  
===
1  
2  
  3  
---
4  
5  
6

Pairing from first to last gives the example output. Again:

1 4
2 5
6 3

The handedness looks like:

L L
L L
L R

You could have also made it

L L
L L
R L

with

1 4
2 5
3 6

But that causes the elbow bumping.

Pairing the first half with the second half in order wont pair conflicting numbers together unless n = 2. Which is fine because if n = 2 the problem isn't solvable anyway.

A pseudo code solution:

Students 1 to n/2, please sit at the desk that matches your student number. Of the two seats at that desk choose the one that keeps your elbow from poking your partner.

Students n/2+1 to n, please sit in the remaining chair at the desk that is n/2 less than your student number.

Done this way you don't even need to swap.

This solution didn't just come to me. At first I was thinking about backtracking, depth first searching, rule based reasoning. Then I thought, wait, start simple and make the problem prove that it's complicated. Lets see what it looks like if I just visualize the problem in text. I started typing numbers in different orders, row first, column first. I tried sliding the column around. I hit on the idea of showing the handedness of numbers by creating L and R columns so I didn't have to keep looking back at LLRLLL to see which was which. After that it all fell into place. A glance at the sample output told me exactly what they'd done. All because I'd created a useful way to express the input that simplified solving the problem.

Related Topic