Wet Chairs problem from Australian Informatics Olympiad

Question

I'm trying to solve this problem from the Australian Informatics Olympiad here.

(These are past questions which I'm completing for the purpose of revision, if you are worried about the integrity of the competition, and unfortunately the organisation doesn't provide answers).

Basically, when given an input with: a list of "wet" or "dry" chairs, the number of people needed to be seated, and the number of people who will ONLY sit on dry chairs, you must determine the shortest possible distance between the two people on the ends (the shortest possible distance in total taken up by the group from first person to last).

The solution I found looped through each of the chairs, and for each wet chair allocated someone who was not picky, unless there were no more of those - in which case I simply skipped the chair. For each dry chair I allocated one picky person, or a non-picky person. There's quite a lot of looping - I've tried to refuse to the size of the data with certain conditional statements - however my solution still timed-out on many of the larger inputs (the max time allowed is 1 second for you code to complete), despite getting the correct outputs.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;

public class Solution {

    public static void main(String[] args){
        try {
            BufferedReader bufferedReader = new BufferedReader(new FileReader("chairsin.txt"));
            String[] lineOne = bufferedReader.readLine().split(" ");
            int numberOfChairs = Integer.parseInt(lineOne[0]);
            int totalFriends = Integer.parseInt(lineOne[1]);
            int niceFriends = Integer.parseInt(lineOne[2]);
            int pickyFriends = totalFriends - niceFriends;
            String[] chairs = bufferedReader.readLine().split("");
            int shortestLength = numberOfChairs;

            for(int x = 0; x < (chairs.length - totalFriends); x++){
                int easyFriends = niceFriends;
                int hardFriends = pickyFriends;
                for(int y = x; y < chairs.length; y++){
                    if ((y - x + 1) > shortestLength){
                        break;
                    }
                    if(chairs[y].equalsIgnoreCase("w")){
                        if(easyFriends>0){
                            easyFriends--;
                        }
                        else
                            continue;
                    }
                    else{
                        if(hardFriends>0){
                            hardFriends--;
                        }
                        else if(easyFriends>0){
                            easyFriends--;
                            continue;
                        }
                    }
                    if(hardFriends == 0 && easyFriends == 0){
                        shortestLength = y - x + 1;
                        break;
                    }
                }
            }

            PrintWriter printWriter = new PrintWriter(new BufferedWriter(new FileWriter("chairsout.txt")));
            printWriter.print(shortestLength);

            bufferedReader.close();
            printWriter.close();

        } 
        catch (IOException exception) {
            exception.printStackTrace();
        }
    }
}

Overall, I'm just looking for ways to improve my solution - be it by optimization, or using a completely different method/algorithm to solve this problem.

Answer 1

A O(N) algorithm would be the sliding window method. Sliding Window means that you keep track of 2 indexes, the front and the back of the "window".

Let every dry chair be a 1 and every wet chair be a 0. At first, let front = 1 and back = 0.

While front is not out of bound (i.e. not more than C, 1-indexed), check if the number of dry chairs in the window is equal to N-K. If so, update the minimum length of the window if needed and increment the back by one. Subtract 1 to the running sum of dry chairs if the chair "removed" is a dry chair.

If not, then increment front by one. Add 1 to the running sum of dry chairs if the chair "added" is a dry chair

A pseudo-code is shown below

while front <= C 
if dry == N-K                                  //If there are enough dry chairs
    if front - back < min                      //Update minimum if necessary
        min = front - back
    back = back + 1                            //Decrease size of "window"
    dry = dry - chairs[back]                   //Update number of dry chairs 

else                                           //If there are not enough dry chairs
    if (front == C) break
    front = front + 1                          //Increase the size of the window (Make sure that front does not go out of bounds!)
    dry = dry + chairs[front]                  //Update number of dry chairs

Why is it O(N)? Because front is incremented exactly N times by the time the loop ends and back is incremented at most N times. You might want to check this link for another similar explanation

What is Sliding Window Algorithm? Examples?