3
\$\begingroup\$

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();
    }

}
\$\endgroup\$
  • \$\begingroup\$ Seems like this should work. I have a feeling that perhaps the time limit was exceeded due to slow I/O, since your input could have up to 300,000 lines. You can try taking the advice from this webpage to speed up Java I/O and see if it helps. \$\endgroup\$ – JS1 Mar 29 at 19:17
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Hi Mahdi, it is often more helpful to the OP if you can explain the parts in the original question that you liked or didn't like and what could be changed rather than just provide new code \$\endgroup\$ – Harald Scheirich Mar 29 at 12:28
  • \$\begingroup\$ Hi Harald, thank you for the comment, I am partially new to the Stack community. this is a problem solving issue, Prashin proposed a solution, which seems to cause a TimeLimitExceeded error on the platform he's working on using TreeSet as a main Data collection to solving this issue. I suggested another mechanism to solve the issue. \$\endgroup\$ – Mahdi Khardani Mar 29 at 13:23

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.