PROBLEM LINKS:[Practice] [Contest]
PREREQUISITESBasic string reading, using array
PROBLEMThe problem essentially is to maintain binary (open(1) or close(0)) state of N tweets and simulate K actions on them. The two types of actions are (a) CLICK X , which toggles the state of Xth tweet and (b) CLOSEALL , which sets the state of all the N tweets to close(0). After each of the K actions given, we need to find the total number tweets in open(1) state.
EXPLANATIONIf you are beginner in programming contests, note that its common to assume that 108 basic arithmetic operations are performed in 1 second on modern computers. It may actually be faster than this (roughly 109 operations per second) on your computer. This is not always guaranteed as it may depend on several other factors. Some of them are handling heavy input/output, using modulo operator a lot, using long or double operands etc. So its always good to try a few practice problems in a site, for better estimation of actual run times.
For this problem, first lets look at a very naive approach, which is fast enough for the given constraints N ≤ 1000 and K ≤ 1000. We need to maintain the current state (isOpen) of N tweets, for which we can simply use an array of booleans (true/false) or integers (1/0). CLICK X toggles the state of Xth tweet, so if isOpen[X] == 1 then set isOpen[X] = 0, else if isOpen[X] == 0 then set isOpen[X] = 1. This can be done using a single statement isOpen[X] = 1 - isOpen[X] or using xor(^) operator, isOpen[X]^=1. CLOSEALL sets the state isOpen[X] = 0, for all the tweets X = 1 to N. To find the number of opened tweets at any time we can simply traverse the state array and count the number of opened tweets. This method requires O(N) memory, O(1) time for toggle, O(N) time for each CLOSEALL and O(N) time to find number of opened tweets. Overall for K operations it has worst case time of O(NK), which is fast enough for the given constraints.
SETTER'S SOLUTIONCan be found [here]
APPROACHThe problem setter used the above approach to solve the problem. For comparing two strings, the inbuilt function [strcmp] in string library is used.
TESTER'S SOLUTIONCan be found [here]
Note that we don’t need to run a O(N) loop each time we want the count of opened tweets. The number of opened tweets changes by only either +1 or -1 with each CLICK X. So if the state of Xth tweet changes from close to open, we add 1, else if it changes from open to close, we subtract 1. So we can have this count in O(1) time per CLICK. Note that CLOSEALL still requires to reset all the states to 0 and is O(N). The overall solution if still O(NK) worst case time. Refer tester’s solution for this approach.
- Can you solve this problem in O(K) time using O(N) memory ? meaning, constant time for each CLICK and each CLOSEALL. Think about it and write your ideas in comments below.