Transmission Of Messages

Question

I have an assignment to solve this problem.

Problem Description

Bob the Cat is building a new system, dubbed the Cats Transmission System (CTS). This horribly inefficient system utilises cats to help transfer information. In this system, there are N cats lined up in a line from cat 0 to cat N-1. If a message needs to be transferred from, say, cat 2 to cat 7, cat 2 will pass on the message to cat 3, to cat 4... and so on, until it reaches cat 7. Sounds simple, right?

However, there is a problem. As everyone knows, cats LOVE sleeping. Some of these cats tend to fall asleep on the job. Say, if cat 3 falls asleep, the message from cat 2 to cat 7 will not be able to be transmitted. As such, given a list of "SLEEP" and "WAKE" events, as well as "TRANSMIT" requests in between, Bob wants you to check if each of these "TRANSMIT" requests will pass. All cats start out awake.

There will be a total of Q events. The format of the events will be as follows:

Input The first line of input will contain two integers, N and Q. The next Q lines of input will each contain one event as stated above.

Output There should be one line of output for every "TRANSMIT" operation, either stating a "YES" or a "NO".

Limits

• 0<N≤2^31-1

• 0<Q≤300,000.

• All values of x and y are guaranteed to be between 0 and N-1.

Commands

WAKE [x]

Cat [x] wakes up

SLEEP [x]

Cat [x] falls sleep

TRANSMIT [x][y]

Attempt to transmit information from cat [x] to cat [y] ([x] ≤ [y]). If it is successful (all cats from [x] to [y] inclusive are awake), then output “YES”. Otherwise, output “NO”.

Sample input

8 8
TRANSMIT 2 7
SLEEP 6
TRANSMIT 1 7
TRANSMIT 1 5
SLEEP 4
TRANSMIT 1 3
WAKE 4
TRANSMIT 1 5

Sample output

YES
NO
YES
YES
YES

Explanation There is a total of 8 cats, labelled from 0 to 7, and 8 events that follows.

Initially, all the 8 cats are awake. Hence, the transmission request from cats 2 to 7 will succeed. Then, cat 6 falls asleep. Subsequently, the transmission request from cats 1 to 7 will fail as cat 5 cannot transfer the information to cat 6, which is sleeping.

However, the transmission request from cats 1 to 5 will still succeed as every cat in the range is still awake.

Then, cat 4 falls asleep. The next transmission request from cats 1 to 3 still succeeds as every cat in the range is still awake.

Cat 4 now wakes up. The transmission request from cats 1 to 5 will succeed as every cat in the range is now awake.

I have attempted this problem using a TreeSet(I chose it because it's something like a double ended priority queue, hence my solution would run in O(log n), however for some reason I can still get TimeLimitExceeded on the platform I'm testing on. Is there anything slow about the TreeSet that I'm unaware of, and what is the better solution here?

Attempt

import java.util.*;


public class Transmission {
    private void run() {
        Scanner sc = new Scanner(System.in);
        int endIdx = sc.nextInt()-1;
        int cmdCount = sc.nextInt();
        TreeSet<Integer> dEndQueue = new TreeSet<>();

        for (int i=0;i< cmdCount;i++) {
            String cmd = sc.next();

            if (cmd.equals("TRANSMIT")) {
                int start = sc.nextInt();
                int end = sc.nextInt();

                if (dEndQueue.isEmpty()) {
                    System.out.println("YES");
                    continue;
                }

                Integer firstHole = dEndQueue.ceiling(start);
                if (firstHole==null || firstHole>end) {
                    System.out.println("YES");
                } else {
                    System.out.println("NO");
                }
            } else if (cmd.equals("SLEEP")) {
                int entry = sc.nextInt();
                dEndQueue.add(entry);
            } else if (cmd.equals("WAKE")) {
                int entry = sc.nextInt();
                dEndQueue.remove(entry);
            }

        }
    }
    public static void main(String[] args) {
        Transmission newTransmission = new Transmission();
        newTransmission.run();
    }

}

Answer 1

I recommend you to use a Boolean array (states[n]) and set the value of the correspondent element to either true or false and iterate that array every time the TRANSMIT command is called:

private static String keyWord;
private static int source;
private static int destination;
private static boolean[] states;


public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int q = sc.nextInt();
    sc.nextLine();
    String [] commands = new String[q];
    states = new boolean[n];
    for(int i=0; i<n; i++) {
        states[i]  =true;
    }
    String output = "";
    for(int i=0; i<q; i++) {
        commands[i] = sc.nextLine();
        output+=readCommand(commands[i]).length()!=0?readCommand(commands[i])+"\n":"";
    }
    System.out.println(output);
}

private static String readCommand(String command) {
    String[] words = command.split(" ");
    keyWord = words[0];
    source = Integer.parseInt(words[1]);
    if(keyWord.equals("SLEEP")) {
        states[source] = false;
        return"";
    }
    if(keyWord.equals("WAKE")) {
        states[source] = true;
        return "";
    }
    if(keyWord.equals("TRANSMIT")) {
        destination = Integer.parseInt(words[2]);
        return isTransmitted(source, destination);
    }
    return"";
}

private static String isTransmitted(int from, int to) {
    for(int i = from; i<=to; i++) {
        if(!states[i]) {
            return "NO";
        }
    }
    return "YES";
}

I hope this would help you.