This is the official editorial for AASF JPC-II.
Also, fill this feedback form form to let me know about your experience, at the end of this tutorial. I am eager to hear from you.
Problem Author and Editorialist: Ayush Sah
Problem Testers: Pranav Jarande, Aditya Bharadwaj
Quick shoutout to the unofficial testers:
NonTechNerd69, Sohail, Hippie for their valuable feedback! ❤️ Also, thanks Pratyush for editing the artwork in the first problem. ❤️1. Aparecium!
Tag(s)
String
String Matching
Hash Table
2 Pointers
Hint
Do what the problem says.
Tutorial
Iterate over the whole string and store the string of length 2 by concatenating the current and the next character in a hash set. For every
Time Complexity: O(N)
Problem Rating (Equivalent to Codeforces)
800
Tag(s)
Game
String
Greedy
Sorting
Hint
When does Kafka have advantage over Camus?
Tutorial
Let us assume that, the total number of common words known to both are
For this case, it is easy to observe that Kafka has an advantage over Camus when the count of common words is odd. This is because, for each common word that Kafka uses, Camus loses that word. Eventually, Kafka ending up using the last common word always. This would mean that Kafka would have effectively 1 more word than Camus and would thus win as
Time Complexity:
Problem Rating (Equivalent to Codeforces)
1000
Tag(s)
Search
Simulation
Sorting
Policy Based Data Structure
Hint
What if we maintained an array of unoccupied seats and simulated the whole process?
Tutorial #1
This is a straight forward problem of simulation. One such way to solve the problem is described here. Maintain an array of size n where each seat is initially unoccupied, denoted by -1. Iterate over this array and update the seat with the value 0 as they get occupied. Now, iterate over this updated array and from the very first seat which is unoccupied, increment the seat number starting from 1. Finally, do a linear search over this array to find the original seat number.
Since, the constraints aren't very strict, a solution till
Time Complexity:
Tutorial #2
This problem can be solved with the help of an ordered set from the policy based data structure class which gives all the basic operations that an STL ordered set gives, alongwith two extra functions find_by_order()
and order_of_key()
. Although, using this data structure here would result in a worse time complexity than author's solution, it is still a very powerful data structure to learn. It helps to solve offline query based problems for example, in a very elegant way. The solution code can be found in author's alternative solution.
Here is the extended version of the problem to try this method: https://www.thejoboverflow.com/problem/148/
Time Complexity:
Problem Rating (Equivalent to Codeforces)
1100
Tag(s)
Array Shifting
Derangement
Hint
This is a problem of derangement. How is the possibility of a possible derangement related to the count of each element?
Tutorial
Derangement can be defined as an arrangement in which no element is in its original position. Thus, it is easy to figure out that in this problem, if we can make a valid derangement of the given sequence, then Baldwin wins. But, doing it in a naive way would be computationally difficult. So, instead of embarking upon the journey to print this derangement let us first figure out if there is a way to determine whether Baldwin can even win or not. Upon inspection of few examples, we can make a key observation that if the count of any element in the sequence is more than
PROOF
STATEMENT: If an element occurs more than 'half the size' number of times in an array then the derangement of that array is not possible.
Let us say that it is possible to make a derangement even if an element's count is more than half of the total input size.
So, to generate the derangement we try to pick this number and at every occurrence of it, we fill the remaining numbers in.
But, eventually we run out of remaining numbers as there would always be atleast 1 empty position where nothing but this selected element could only go in.
This arrangement is not a valid derangement.
Hence, by contradiction we prove our statement.
Thus, Baldwin can only win if all elements occur not more than
Now, to generate a valid derangement we can take help of our result above. If we can have all the same coloured sheaths in a line, then we know that the colour appearing for the most number of times would also require most number of other remaining colours to fill their position. So, if we rotate this sorted sequence by an amount of
Time Complexity:
Problem Rating (Equivalent to Codeforces)
1400
Tag(s)
Coordinate Compression
Sorting
Difference Array
Sweep Line
Hint
You have to find out the total cost incurred on each day without YZY Deluxe and compare and find out the better one.
Tutorial
Since, the constraints over the number of days are very large, its not feasible to iterate over them and calculate the total sum. So, we instead use the coordinate compression technique since we only need the starting and ending days of each album.
Assume you have an ifinite time length spanning over
EXAMPLE
Say, the days are {1,5} and {4,10} for two albums. The finals time segments would be:
[1,3] [4,5] [6,10] [11, ∞) where [4,5] is the segment where both the albums are listened to.
These segments can also be viewed like this:
[1,4) [4,6) [6,11) [11, ∞)
So, now to represent these segments we only need to deal with the left end-points of each segment which are either
After we get the segments, we now need to calculate the cost for each segment, and compare it with K, the price of the subscription. Thus, for implementation we can use a map (since we need the time stamps in a sorted manner) to store the change that is happening to the total cost on each critical day, i.e., the left end-points of each and every segment. At the, end we get the final total answer.
Time Complexity:
Problem Rating (Equivalent to Codeforces)
1500
6. ICPC Team
Tag(s)
Binary Search
Bitmasking
DP
Hint
How can we represent a yes/no valued tuple in a quick way?
Tutorial
A naive brute force solution will give TLE as for the worst case, it will be in the order of
I won't be explaining the working of binary search as it would stretch the tutorial. You can find the dry run in an explained sample below.
The Yes/No question (the checker function) we have to get answer for, in our problem is- Is the parameter greater than or equal to x (the middle value of binary search)? If it is, we set that bit as 1, otherwise 0 (This is the step of bitmasking). In this way, we need to find the masks for all the
Here is an illustration of the sample testcase:
Time Complexity:
Problem Rating (Equivalent to Codeforces)
1700
Hope you enjoyed giving it and got something new to learn out of it.
If you wish, you can now go back to filling the feedback form.