PROBLEM LINK:
Practice
Contest
Video Editorial
Author: Dmytro Berezin
Primary Tester Prateek Gupta
Editorialist: Hussain Kara Fallah
PROBLEM EXPLANATION
A rainbow array of n elements follows the form
{ 1 (repeated a1 times), 2 (a2 times), 3 (a3 times), 4 (a4 times), 5 (a5 times), 6 (a6 times), 7 (a7 times), 6 (a6 times), 5 (a5 times), 4 (a4 times), 3 (a3 times), 2 (a2 times), 1 (a1 times) }
2*(a_1+a_2+a_3+a_4+a_5+a_6)+a_7 = n
Given an array consisting of n elements, check if it’s a rainbow array or not.
DIFFICULTY:
cakewalk
PREREQUISITES:
None
EXPLANATION:
This problem is similar to checking if a given string is a palindrome or not. The simplest and most effective way to check if the array is rainbow, is by maintaining 2 pointers one iterating through elements starting from the beginning of our array, and the other one iterating through the elements in the reversed direction.
Both of the first and the last element of the array must be ones. In fact, there must be two blocks consisting of the same number of consecutive ones (1) one of them located at the beginning of the array, and the other one at the end.
Figuring out the number of consecutive ones at the beginning of our array can be done easily by moving our first pointer forward, and stopping when encountering a number not equal to 1 or reaching the end of our array. We can do the same on the other side by moving our second pointer backwards. After that, we should check that we had processed the same number of ones on both sides.
After processing elements equal to one, you can observe that we are still solving the same problem (in fact, it’s a subproblem now). Both of our pointers must be referring to elements equal to 2. Moving our pointers is equivalent to dropping elements, so if we consider that we have dropped processed ones, there must be two blocks consisting of the same number of consecutive twos (2) one of them located at the beginning of the array, and the other one at the end. Of course instead of using 2 pointers, maintaining a data structure which supports dropping elements from both ends of the array (Like C++ Deque) does the job perfectly.
After repeating the same procedure for {1,2,3,4,5,6} (considering that none of our conditions was violated, in case that happened we can report that our array is not rainbow and break) we would be finishing with a single block consisting only of elements equal to seven 7. Reaching this point confirms that our array is rainbow.
You can check my implementation for better understanding.
AUTHOR’S AND TESTER’S SOLUTIONS:
AUTHOR’s solution: Can be found here
TESTER’s solution: Can be found here
EDITORIALIST’s solution: Can be found here
wasted almost 2 hours.