Editorial for Programmers Army Monthly Contest + Hiring Contest - Dec - 2020

editorial
, ,
1

Editorial for ​Programmers Army​ Monthly Contest + hiring contest held on CodeChef dated 27th Dec 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.
  2. if you get stuck in coding then you can see solutions to that question. ​
  3. 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.
  4. This Contest was purely based on Strings and it’s algorithms.

Contest Link :​ Programmers Army Monthly Contest - Strings Coding Competition | CodeChef

1. ​ Unique Encryption​:​​

Approach / Explanation​: In this problem, you are given a string, and you have to do operations as written step-wise in question ( nothing special here).

Solution coded in C++​: ​ https://ideone.com/MbUfaP


2. ​ Remix of Songs:​

Approach / Explanation: ​In this problem, you are given a sentence and you need to find the first word which has a minimum length from the words of the entire sentence, and then you need to print that minimum word to start, end, and between every word of the sentence with whitespaces.

This can be done simply by traversing the given sentence and calculating the length of each word and taking out the word having a minimum length from it.

Solution coded in C++​:​ https://ideone.com/6xZIEg


3. ​ Total Cars ​:​

Approach / Explanation ​In this problem,

  1. Create a segment tree with each node consisting of a set which is formed by merging of the sets of its child nodes.
  2. Each set contains only even numbers.
  3. For each query, take an empty final set and for every node lying within the given range, push its set values into the final set.
  4. At the end print the size of this final set.

Solution coded in C++​: https://ideone.com/461E9M


4. ​ Smallest String​:

Approach / Explanation​: In this problem, you are given a string and you need to find the minimized string from the given string which can be any permutation of any length from the given string. also, you can re-arrange the minimized string in any way to form the original string.

Note: There can always, be a solution for any given string. beacause, the original string itself is an integer multiple of itself ( integer value = 1).

You were told to print “-1” if answer doesn’t exist, was just to trick your mind. ( It was intentional ).

Approach : Read code and comments, all things are explained

Solution coded in C++​:​ https://ideone.com/5joyUZ


5.​ ​ Palindromic Tree​:​

Approach / Explanation​: Basic concept, just go to every node and consider it as the middle of palindrome and also take two adjacent Node and Consider it as a middle of the palindrome.

Solution coded in Python​:​ https://ideone.com/5DG9eX

We hope you enjoyed this contest and learned something new from it, also we hope you will be more excited about such contests in the 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 :smile:

2

Can you elaborate your approach for 5th problem ?

3

What was the expected complexity in the 5th problem? O(N^2) was giving TLE and your code also looks O(N^2) only.

4

btw isn’t this almost the same problem : check this. Only thing is that nodes are substituted by edges

5

I tried various O(N^2) approaches in C++ but all TLE’d. First was Like doing dfs from every node and second was about using Manacher’s algorithm on paths from root to leaf nodes.

6

@cubefreak777 u can explan CodeChef: Practical coding for everyone the solution for me plz for car qn?

7

@samarth Can you please confirm the approach for 4th problem as it seems like their solution gives wrong answers for test-cases of this kind(where minimum number is not the gcd)

TEST_CASE 
1
10
aaaabbbbbb

My idea was about taking the gcds of all frequencies and then take the corresponding multiples for each character in the minimized string or my interpretation of the problem statement is wrong itself.

8

He is solving the problem via offline queries. After storing the queries in arrays l,r start iterating over every second character compute their corresponding prefix sums p. After that iterate over all the stored queries and check if there is least one occurrence of our current character (this can be done in O(1) by checking if p[r]-p[l-1] is zero or not) along with it keep on storing the result in sone res array as he did in the code.

9

On Palindromic Tree solution the time complexity should be N*P where P is the number of palindrome in side the tree. So yep worst case should be N^2 but avg case should be less that’s what required.

10

Are you guys sure about your approach for 4th problem ?

11

Their solution is wrong, your approach is correct, I also used the gcd approach only and got AC. @rishabh_singh0 , @pro_army use this test case:

1
10
aaaabbbbbb

Correct Output : aabbb
Your Output : aaaabbbbbb

12

Yes exactly, thanks for confirming :+1:

13

Seriously? Consider the test case with same character on each vertex. You get O(N^2) palindromes for each test case. And this test case should have been there.

14

I am not the author for any other questions, tag me only if problem in Palindromic Tree

15

Yes it’s there.

16

hey @cubefreak777 @samarth2017 yes the solution presented, in the Editorial will not work on the test cases like this, and Ig there was some problem during the contest on test cases of this question, and it may also be due to this reason ( which was later, fixed by our team )

We apologize, for this mistake and we’ll make sure that this won’t happen in our future contests.

And, Programmers Army team would like to appreciate your efforts, for making learners take the right stuff in there, and we expect this support from good coders like you in our future contests as well :innocent:

hoping to have a great journey with all of you ahead !!

Thanks & Regards
Team Programmers Army