4
\$\begingroup\$

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.

\$\endgroup\$

migrated from stackoverflow.com Sep 12 '16 at 18:39

This question came from our site for professional and enthusiast programmers.

  • \$\begingroup\$ A quick thought: You only need to focus on sitting all of the "picky" friends as close together als possible because when you have done that you can just fill the spaces between and on the sides with the other friends. So you only need to focus on the dry chairs and their distances. \$\endgroup\$ – Florian Link Aug 29 '16 at 12:12
  • 1
    \$\begingroup\$ Hint: If you know a shortest-length solution that starts with someone sitting at position i, can you quickly adapt that into a shortest-length solution that starts with someone sitting at position i+1? The easy case is when seat i is wet: then you know that whoever was sitting there will be happy to sit anywhere. \$\endgroup\$ – j_random_hacker Aug 29 '16 at 12:34
  • 1
    \$\begingroup\$ Another hint (not sure if this is necessary for a quick solution, but it could help): Let nWetUpTo[i] be the number of wet seats up to and including position i. You can calculate this array quickly, and you can use it to tell you the number of wet seats between any two positions in just O(1) time :) \$\endgroup\$ – j_random_hacker Aug 29 '16 at 12:38
2
\$\begingroup\$

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?

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy