Editorial for Programmers Army Monthly Contest - Nov - 2020

pro_army · November 23, 2020, 12:37pm

Editorial for Programmers Army Monthly Contest held
on CodeChef dated 23rd Nov 2020

NOTE:

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 :

https://www.codechef.com/ARYS2020

**

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
krasivo”.
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 :

https://programmersarmy.com/algorithms/two-pointer.html

Solution coded in C++: 1s5tvk - Online C++0x Compiler & Debugging Tool - Ideone.com

4. Championship:

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
sum)

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
https://programmersarmy.com/algorithms/sliding-window.html

**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 !!

Happy Coding
Programmers Army

anon16027809 · March 29, 2021, 6:38am

Why is this code giving Runtime Error(SIGSEGV)? TIA!

#include <iostream>
using namespace std;

long long int goldCoins(int n, int a[], int q1, int q2){
    long long int coins = 0;
    for(int i=q1-1; i<q2; i++){
        coins += a[i];
    }
    return coins;
}

int main() {
	int t,n,q,q1,q2;
	int a[n];
	cin>>t;
	
	while(t--){
	    cin>>n;
	    for(int i=0;i<n;i++){
	        cin>>a[i];
	    }
	    cin>>q;
	    for(int i=0;i<q;i++){
	        cin>>q1>>q2;
	        cout<<goldCoins(n,a,q1,q2)<<endl;
	    }
	}
	return 0;
}

rathore_007 · June 14, 2021, 5:13pm

Hii @anon16027809 , you are getting this Error(SIGSEGV) ,because in the second line of the main function ,at the time of declaring the array of size n i.e a[n], the value of n is not assigned or set by you yet , you have assigned it in the later part inside the while loop.
So First assign the value of n , and then declare the array of size n.
cin >> n;
int a[n];

rathore_007 · June 14, 2021, 5:32pm

Hii everyone , I am getting Time Limit Exceeded Error in the problem GOLD COLLECTION , Can any one please let me know the reason for it.
Link to my code
https://www.codechef.com/viewsolution/47841511

rathore_007 · June 15, 2021, 8:06am

Can anyone please let me know why iam gettting wrong answer in the PROBLEM FREQUENCY ARRAY using the sorting approach and using set approach.
LINK to Sorting approach.
https://www.codechef.com/viewsolution/47849453
Link to SET approach.
https://www.codechef.com/viewsolution/47849783

rushi2001 · June 15, 2021, 8:36am

Your approach is correct but there are some methods in your program which are time consuming

I just added fast input output method and changed endl to “\n” and it got accepted .
https://www.codechef.com/viewsolution/47851199

rushi2001 · June 15, 2021, 8:43am

In set approach if let say testcase
2
5
1 2 3 1 4
3
1 2 3

Expected OP -
ne krasivo
prekrasnyy

Your Op -
ne krasivo
ne krasivo

as your program will take it as
2
5
1 2 3 1
4
3 1 2 3

In this in first testcase you will break at index four ie at element 1 as condition is getting wrong and hence entire input for this testcases will be not taken and this will act as next testcase so don’t break the loop

Here is your solution with set in which i just removed break statement and got ac .
https://www.codechef.com/viewsolution/47851388

rathore_007 · June 16, 2021, 1:39am

Thank you , now this is something new which I learned for first time in CP .
Nice to see how this additional line of code (breaking the synchronization b/w c++ standard stream and c standard stream , also switching from endl to \n which avoid flushing ) can make our code time more efficient.
So thank u again.

rathore_007 · June 16, 2021, 2:09am

Thanks for great explanation in SET Approach.
Can you explain me what would be the issue in SORTING approach. Incase u have figured it out.

rathore_007 · June 16, 2021, 2:50am

No need to explain anymore regarding SORTING approach . I got the mistake , I just miss the endl in my output.