Dutch National Flag Partitioning

Dutch National Flag Partitioning

Problem Statement

Partitioning is a common process used in other algorithms such a quicksort. In this problem, we are given an Array A and an index i. We have to rearrange A such that , all elements less than A[i] appears first followed by all elements equal to A[i] followed by all elements greater than A[i]. 

Problem Solving

• Not lying but since I have done such a problem sometime in past, this has quickly led me to think of using iterators that spans 3 ranges of less than, equal to and greater than values. 
• However the first question is to where to position each initially. 
• First I thought of positioning them at begin and end -1 position, but just initializing them there because we do not have other option is breaking the invariant that at any time those iterator should point to correct values. 
• Also there can be a case where all values are same then there would be no point in doing anything. 
• This also means that we should skip the part that is correct and hence post skipping we could arrive at the correct iterator location. 
• So first iterate from both ends and get to a location for both iterators where they are in accordance with the arrangement that left iterator has values less than A[i] and the right one has values greater than A[i] 
• when this process ends we would reach the exact range we need to actually rearrange and bonus point if there is no range left to process. 
• Once we reach this range. We need to create another iterator that starts at begin + 1, to iterate till right iterator. 
• at every point we check if the iterator is less than A[i] then we swap it with left itr and increment left itr and similarly if it is greater than A[i] then we swap it with right itr.
• And yes that should do it. 
• It should also be able to handle cases where all values fall into one range, since that we would skip at the beginning only.
• I wrote it, it failed and corrected it and ran correctly then. 
• Find Code here.

Learning  

• Never doubt yourself In the first attempt the answer came out wrong and I immediately jumped to the conclusion that the comparison mechanism is incorrect since I have recalled it from past memory. 
• However it turns out that all that was missing was one more iteration that I did not perform. 
• This also makes me aware of the fact whenever we talk about iteration we need to be accurate about what are iteration limits. 
• The complexity for this solution straight forward is constant since we are only swapping elements by traversing the array once and no extra memory is required. 
• Also I learned the best way to swap elements of iterators are iter_swap a built in function in algorithms library. 
• Hmm.. simple one but panic caused a lot of time waste.   

Cops and the Thief Devu

Link here.

There are 100 houses located on a straight line. The first house is numbered 1 and the last one is numbered 100. Some M houses out of these 100 are occupied by cops.

Thief Devu has just stolen PeePee's bag and is looking for a house to hide in.

PeePee uses fast 4G Internet and sends the message to all the cops that a thief named Devu has just stolen her bag and ran into some house.

Devu knows that the cops run at a maximum speed of x houses per minute in a straight line and they will search for a maximum of y minutes. Devu wants to know how many houses are safe for him to escape from the cops. Help him in getting this information.

Input

First line contains T, the number of test cases to follow.

First line of each test case contains 3 space separated integers: M, x and y.

For each test case, the second line contains M space separated integers which represent the house numbers where the cops are residing.

Output

For each test case, output a single line containing the number of houses which are safe to hide from cops.

Constraints

• 1 ≤ T ≤ 10⁴
• 1 ≤ x, y, M ≤ 10

Example

Input:
3
4 7 8
12 52 56 8
2 10 2
21 75
2 5 8
10 51

Output:
0
18
9

Explanation

Example 1 : Cops in house 12 can cover houses 1 to 68, and cops in house 52 can cover the rest of the houses. So, there is no safe house.

Example 2 : Cops in house 21 can cover houses 1 to 41, and cops in house 75 can cover houses 55 to 95, leaving houses numbered 42 to 54, and 96 to 100 safe. So, in total 18 houses are safe.

Problem Solving

• First thing to notice is that it's a range problem. Given a range 1-100 we have to subtract ranges.
• Simple math tells us that for every Mi range for that cop is i +- x * y. Current position + (speed * time) (distance) the cop can cover.
• Now we have 1-100 range and have to subtract all Mi ranges and leftover will be our answer. 
• We need to calculate the total sum of ranges, excluding the overlaps and finally subtract the the total from 100, to get safe houses. 
• I mistakenly read the problem to output the indexes of houses, however now thinking about it that would have been a different problem.
• We can create a list of ranges and while adding a range to list merge the range if required to make a bigger range. Finally we can compute the total sum of the ranges in the list and subtract that from 100. 
• Here to make a list we can use std::vector, to represent a range we can use std::pair 
• Also while merging we need to search through all merges possible therefore if we can maintain a sorted list then the while merging we only have to check the last element. 
• Therefore we have to sort the houses list first and then give it to adding range. 
•  The submission went successful here.

Learning 

• I have a feeling that we can still improve this complexity of mlogm, if we would know how to store ranges properly. 
• May be in future we can study such  data structures. 
• We also used a built in sorting function which currently we have not implemented, so going forward we need to learn about sorting. 
• Since in the certification course all sample problems are done, I would pick up problems from "Elements of Programming Interview" to cover more array and vector problems. 

 

Chef and Rainbow Array

Link to problem here.

Chef likes all arrays equally. But he likes some arrays more equally than others. In particular, he loves Rainbow Arrays.

An array is Rainbow if it has the following structure:

• First a₁ elements equal 1.
• Next a₂ elements equal 2.
• Next a₃ elements equal 3.
• Next a₄ elements equal 4.
• Next a₅ elements equal 5.
• Next a₆ elements equal 6.
• Next a₇ elements equal 7.
• Next a₆ elements equal 6.
• Next a₅ elements equal 5.
• Next a₄ elements equal 4.
• Next a₃ elements equal 3.
• Next a₂ elements equal 2.
• Next a₁ elements equal 1.
• a_i can be any non-zero positive integer.
• There are no other elements in array.

Help Chef in finding out if the given array is a Rainbow Array or not.

Input

• The first line of the input contains an integer T denoting the number of test cases.
• The first line of each test case contains an integer N, denoting the number of elements in the given array.
• The second line contains N space-separated integers A₁, A₂, ..., A_N denoting the elements of array.

Output

• For each test case, output a line containing "yes" or "no" (without quotes) corresponding to the case if the array is rainbow array or not.

Constraints

• 1 ≤ T ≤ 100
• 7 ≤ N ≤ 100
• 1 ≤ A_i ≤ 10

Subtasks

• Subtask 1 (100 points) : Original constraints

Example

Input
3
19
1 2 3 4 4 5 6 6 6 7 6 6 6 5 4 4 3 2 1
14
1 2 3 4 5 6 7 6 5 4 3 2 1 1
13
1 2 3 4 5 6 8 6 5 4 3 2 1

Output
yes
no
no

Explanation

The first example satisfies all the conditions.

The second example has 1 element of value 1 at the beginning and 2 elements of value 1 at the end.

The third one has no elements with value 7 after elements with value 6.

Problem Solving 

• This seems to be a palindrome problem. 
• However this is incorrect, the input is mean to have increment by 1 at each step.
• Following from that one can clearly see that the N should be odd to satisfy these properties. 
• This gives us an early exit the range of values are small and we do not have to perform any operation other than comparison. So overflow is not possible.
• For space we need to store at least half of the array before we can start comparing the other half.
• A Stack looks to be more suitable for this problem. But we will implement an Stack later in syllabus under that section. 
• We can also carefully implement this recursively and use the native stack space instead of allocating memory ourselves. 
• One more issue here is that the size of the array should be decided at run time, which our array cannot do so we have to use a vector data structure, as discussed in previous post.
• Okay, So the submission went unsuccessful here. 
• It gives TLE, that means there is unseen problem that I have missed. 
• Okay so I found the glitch and solved it here, The problem was we were contructing the vector with N/2 capacity but then pushing back instead of using the allocated memory which for bigger inputs caused bad::alloc(). However it now says Wrong Answer. 
• Okay realized that we can ignore N < 3. checking for more ideas.
• Okay so misinterpreted the problem itself, the numbers appears to have meant that the numbers should grow up to 7 and come back to 1. In our case we just checked whether the numbers are increasing first and then decreasing to form a palindrome. 
• Okay so I submitted another solution which passed half of the task, one still remaining. I just capped my approach up to 7. Submission here. 
• Also that N < 3 should be changed to N < 13. Submission here
• After successive failures and beating up confidence to this "CAKEWALK" difficulty, I thought that I am just trying to fix my solution even after the original solution I wrote was thinking about misinterpreted problem. 
• So I wrote from scratch again, this time I created state machines, basically two functions one which validates increasing values till mid array and the other which validates decreasing through rest of the array. Through the traversal we keep the count of 1-7 numbers and while decreasing we keep decrement the count so that while changing the number or in the end the count should be 0. 
• Also learned, that std::array does not create zero initialized array - use array.fill to do that. here
• After few off by 1 errors and edge cases, this submission went through here. 
• Also learned that premature optimizations really bite in the ass if you are actively modifying the code. 
• This problem was easy to think, difficult to code and hard to interpret correctly. 
• In the end, this problem was easily solved by arrays only no vector required.

Vectors

Vectors

Just like arrays, vectors use contiguous storage locations for their elements, which means that their elements can also be accessed using offsets on regular pointers to its elements, and just as efficiently as in arrays. But unlike arrays, their size can change dynamically, with their storage being handled automatically by the container.

Usage 

• Store any type of data 
• Insert in amortized O(1)
• Remove in O(1) 
• Access in O(1)
• Size not known at compile time

Note

• Since vectors are more suitable to situations instead of arrays they are extensively used in all applications. 
• Vectors in java implements List interface and are synchronized.
• Vectors in C++ are sequence container. 

Vector Implementation

• The following implementation let's us create a vector with any int size.
• Default constructor creates a vector of size 2. 
• The container provides options to access and iterator to traverse the vector. 
• The container also provides push_back to add elements at the end of current last element. 
• The container also provide direct access to front and back elements 
• On Push back of the last element the container resizes to twice the capacity. It allocates new memory then copies original content swap unique pointers and reset the raw pointers. The local unique pointer variable goes out of scope and hence deletes the previous allocated memory. 
• The container also shrinks when the usage drops below half the current capacity.
• Since the vector internally allocates C array the memory allocated is contiguous.

Learning 

• C++ Vectors also have emplace_back function which leverages rvalue references to forward parameters to the container instead of creating temporaries like push_back. Read here
• Vector<bool> is a specialized version of vector and is not recommended to be used in Google Style guide. Read here
• std::swap is specialized for unique_ptr Read here. 
• std::vector also have overloaded operators  like equality and comparison. Read here
• One important question to answer is what's the complexity of inserting in a vector. 

Insert Complexity

• Now vectors have 2 main insert operations an inexpensive one and an expensive one. 
• If we always consider the worst case scenario as in terms of Big O, the expensive operation have order O(n) complexity and since we insert n5 elements the overall worst case analysis shows that complexity will be O (n^2). 
• However this is not true as the number of expensive operations does cannot occur on every insert. 
• Since the number of inexpensive operation increases and are often more than the number of expensive operation , we need to analyze this differently. 
• Amortized analysis is complexity analysis over a range of operations rather a single operation. 
• In this scenario, an amortized analysis means than while inserting n elements what is the overall cost of single insert operation. 
• Now if we see, there are two operations one inexpensive i.e O(1) when we  do not expand the vector, the other is expensive one where we allocate new memory and the copy the original elements to new memory taking O(2 ^ k) operations, where k is an intermediate value < n. 
• For reason that expand only happens on 2^k + 1 elements, 
• Therefore total number of operations = num of inexpensive operations * cost of light operations + num of expensive operations * cost of expensive operations. 
• Number of expensive operations = (2 + 4 + 8 + 16 ... + 2 ^ l) where l is the largest integer such that 2^l + 1 < n. 
• if we look at it the other way say n is the final size of the vector, therefore this expensive operations will occur n/2 + n /4 + n/ 8 + n/16 + ... + 1 which is almost equal to twice 2n. here
• Therefore the total operations will be somewhere n + 2n = 3n. 
• Dividing this by total number of inserts gives us a constant 3 .
• Therefore the amortized complexity  of inserting in a vector is O(1) .