Editorial for Programmers Army Monthly Contest - Nov - 2020

editorial
, , ,
1

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

NOTE:

  1. 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.
  2. 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

  1. Make an extra array called ​freq ​of size 10^5, to store the frequency of the elements
    present in the given array.
  2. 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
  3. If flag is false print “prekrasnyy” indicating it is a beautiful sequence else print “ne
    krasivo”.
  4. ​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

  1. 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,

  1. 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
  2. Firstly we will sort the given array of prices.
  3. Then, ​we will maintain 2 pointers,​ first one pointing to the start index and second
    pointing to the end index of array.
  4. Now, we will run a loop, till left and right pointers crosses each other (i.e. till ​left pointer <
    right pointer ​)
  5. 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.
  6. 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).
  7. 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).
  8. 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)

  1. Now to solve this problem efficiently we maintain a window of size k
  2. Calculate sum from 0 to kth element
  3. Now at each step take add the next (k+1)th value, and subtract the (k-1)th value and
    store the maximum sum.
  4. 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.​ ​C​ompartment 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:

  1. We will maintain a copy of our original array, and call it a different array.
  2. Now, we will build the difference array:
    a. Copy the first element
    b. For rest element do : ​diff[i] = arr[i] - arr[i-1];
  3. 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;
  4. 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)
  5. 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:
  6. 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
  7. 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 :slight_smile:

2

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;
}
3

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];

4

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

5

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

6

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

1 Like
7

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

1 Like
8

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.

9

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.

10

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