Editorial for Programmers Army Monthly Contest held
on CodeChef dated 23rd Nov 2020
- It is highly recommended to first just read the explanation of questions that you were not
able to solve and then again try to solve that question without going through the solution and
after that, if you get stuck in coding then you can see solutions to that question. If you do not find a solution coded in your preferred language, it is always better to
understand core logic and code it out yourself.
- As this Contest was purely based on Arrays and it’s algorithms, so we hope that you solved
all of the questions using just arrays only.
**Contest Link :
1. Frequency Array:
Approach / Explanation: In this problem you are given an array of integers of size ‘n’ and
you have to tell whether the array contains any duplicates. ( hint: you can also use
brute-force to solve this question, as constraints are too small )
Below is the Logic for Optimal approach which works in O(n) time complexity
- Make an extra array called freq of size 10^5, to store the frequency of the elements
present in the given array.
- Now, Traverse the given array and increase the count of frequency of, current element by
1 and after that check if frequency of the current element exceeds 1, then mark flag to false
and break the loop
- If flag is false print “prekrasnyy” indicating it is a beautiful sequence else print “ne
- GK Facts: Just for your knowledge, “prekrasnyy” is a russian word meaning beautiful.
**Solution coded in C++: https://ideone.com/CVYuj1
2. Gold Collection :
Approach / Explanation In this problem you are given an array which indicates the
maximum number of coins, the traveller can get from respective islands. And in each query
you just have to take the sum form ‘l’ to ‘r’ and print it.
( hint: you can also use brute-force to solve this question, as constraints are too small )
Below is the Logic for Optimal approach which answers each query in O(1) time complexity
- Just make a prefix sum of the given array and for each query output the prefix sum from
‘l’ to ‘r’ (this can be done in O(1) ).
Solution coded in C++: https://ideone.com/XnZjwC
3. Birthday of Annabelle :
Approach / Explanation In this problem,
- In this Problem you are given an array of prices and you have to check whether there
exists two elements in that array, such that sum of that 2 elements is equal to 2000
- Firstly we will sort the given array of prices.
- Then, we will maintain 2 pointers, first one pointing to the start index and second
pointing to the end index of array.
- Now, we will run a loop, till left and right pointers crosses each other (i.e. till left pointer <
right pointer )
- In each iteration we will check if the sum of the elements pointed by both of them is equal
to 2000 or not, if it is then make flag to true and break the loop.
- If the sum is less than 2000, then we will increment the left pointer by one as we want our
sum to be increased hence moving the left pointer towards right is an optimal decision (
remember array is sorted).
- If the sum is greater than 2000, then we will decrement the right pointer by one as we
want our sum to be decreased hence moving the right pointer towards left is an optimal
decision ( remember array is sorted).
- Finally if the flag is true print Accepted else print Rejected.
Note: This algorithm is also known as 2-pointer Technique you can read about it here :
Solution coded in C++: 1s5tvk - Online C++0x Compiler & Debugging Tool - Ideone.com
Approach / Explanation: In this problem you are given an array and integer value ‘k’ and you
have to find ‘k’ consecutive list of elements which can give you maximum powers( or maximum
- Now to solve this problem efficiently we maintain a window of size k
- Calculate sum from 0 to kth element
- Now at each step take add the next (k+1)th value, and subtract the (k-1)th value and
store the maximum sum.
- The maximum sum is actually the sum or the maximum powers of our team, which is
going to win the sports championship, So output the same
Note: This algorithm is also known as Sliding-Window Technique you can read about it here
**Solution coded in C++: https://ideone.com/u1NTNn
5. Compartment Weights:
Approach / Explanation: In this question you are given an array which, and ‘q’ queries in
each query you have to update the array in the given range ( i.e. add the number to all elements
from ‘S’ to ‘E’ ). And finally output the sum of entire array.
There are majorly two ways to solve this problem:
A. Using Difference Array
B. Direct formula with some observations.
A. Using Difference Array:
- We will maintain a copy of our original array, and call it a different array.
- Now, we will build the difference array:
a. Copy the first element
b. For rest element do : diff[i] = arr[i] - arr[i-1];
- Now, read each query and update this difference array i.e. just add the given weight to
(S-1)th index and subtract it from (E)th index like below:
diff[S-1] += W;
diff[E] -= W;
- In the above step we are just updating the start and end point, for the range query this
helps us to optimize our approach to process each query in O(1)
- Finally, after doing step 3, for each query just take the prefix sum of the difference array
and print it, this is the actual weight of entire goods train after loading it.
Solution coded in C++: 5s19Ts - Online C++0x Compiler & Debugging Tool - Ideone.com
B. Direct formula with some observations:
- The formula is as follows: ( E - S + 1 ) * W
Where E - End number of compartment
S - Start number of compartment
W - Weight to be added in each compartment from range ‘S’ to ‘E
- For each query calculate the weight using the above formula and find sum for all queries,
and output it.
Solution coded in C++: https://ideone.com/uFOGd2
We hope you enjoyed this contest and learned something new from it, also we hope you will be more excited for such contests in future also.
Make sure to fill the feedback form, as this is the only way we can work upon our improvements
(if any needed) :
Programmers Army Monthly Contest - Arrays (Feedback) - Google Forms
See you at our next Monthly Contest !!