×

# RAINBOWA - 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.

cakewalk

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

This question is marked "community wiki".

118822
accept rate: 0%

19.0k348495531

 0 What Will be Answer for 17 1 2 3 4 5 6 6 7 6 7 6 6 5 4 3 2 1 ?? answered 20 Aug '17, 19:41 153●8 accept rate: 4% Not a rainbow array. "767" not allowed. (20 Aug '17, 19:50) it would be "no" (20 Aug '17, 19:51) Exactly !! Here is Link to my AC solution Which gives Yes for above testcase. https://www.codechef.com/viewsolution/14868106 (20 Aug '17, 19:53) Were test cases for RAINBOWA Weak? (20 Aug '17, 19:55)
 0 Update : Link is updated https://www.codechef.com/viewsolution/15060694 Can someone point out the mistake? Code commented. Shameful cant do cakewalk Logic : 1)Store half array 2)Subtract the incoming elements accordingly, so the resulting array should be consisting of all zeroes 3)Plus other conditions checked 4)still wa :( answered 21 Aug '17, 09:30 2★ab9999 1●1 accept rate: 0% Access denied! You don't have permissions for this page. (21 Aug '17, 20:52) eugalt4★
 0 https://www.codechef.com/viewsolution/15176625 this is my link can anyone point out which test case is not working Logic: 1)half the array itterate by for loop check only the differnce 2)remaining half itterated by another for loop and continuing the array elements by there index can anyone explain this test case => 1 1 1 2 2 3 3 3 3 2 2 1 1 is this "yes" or "no" for this answered 31 Aug '17, 20:45 2★nishugu2 1●1 accept rate: 0% the above test case 1 1 1 2 2 3 3 3 3 2 2 1 1 is not a rainbow array because rainbow array should go until it hits 7 and it should have all 1 2 3 4 5 6 7 without a skip over value.(1 2 4 5 6 7 6 5 4 2 1)(this is not a rainbow array) (1 2 3 4 5 6 7 6 7 6 5 4 3 2 1 ) (this is also not a rainbow array either). (01 Sep '17, 02:14) kunnu1202★ thanks bro for giving me some good explaination of test cases can you plz tell me about this case 1 2 3 4 5 6 7 7 6 5 4 3 2 1 and its length is 14 is it "Yes" or "No" (01 Sep '17, 11:49) nishugu22★
 0 Can any one point out why my code is not working, I to my knowledge have covered every cases. link: https://www.codechef.com/viewsolution/15336244 which case i am missing? answered 08 Sep '17, 00:54 1 accept rate: 0%
 0 https://www.codechef.com/viewsolution/15440629 please tell me what is wrong in this code? answered 17 Sep '17, 12:34 1 accept rate: 0%
 0 The question is incomplete, at least frame it correctly.At the beginning, i thought only numbers from 1-7 are allowed, also even this that 7 cannot repeat more than once! The question should be unambiguous. :( wasted almost 2 hours. link This answer is marked "community wiki". answered 11 Oct '17, 16:14 14●4 accept rate: 0%
 0 https://www.codechef.com/viewsolution/15899730 .. this code gives correct answer for sample test cases. can someone point out what's wrong with my code? answered 20 Oct '17, 10:38 0★ankush24 1●1 accept rate: 0%
 0 Hi Please tell me which case am i missing? https://www.codechef.com/submit/complete/16027422 Thanks, Krupamay answered 01 Nov '17, 18:52 0★krupamay 1 accept rate: 0%
 0 Every rainbow array must be: 1. A palindrome 2. Its first half should be non-decreasing (hence, 2nd half will be non-increasing, as its a palindrome) 3. It contains every element 1,2,3,4,5,6,7 and nothing more, as a(i) is a "non-zero" positive integer. While taking inputs, you can see if you have anything which does not belong to {1, 2, ..., 7}. Also, maintain an array p[7] with every value zero, and as you encounter elements, update the corresponding array element to 1. By doing a linear search for zeroes in this array p, you can see if you have all elements from 1 to 7. Then run a for loop through the first half of the array to see if its a palindrome and non-decreasing. TADA! answered 05 Nov '17, 09:20 1★mr_nair 2●1 accept rate: 0%
 0 Can anyone please point out the mistake in my code, I am not able to find one. Thank you. Code has been provided in the link below link text answered 27 Dec '17, 17:54 0★vg_1996 1 accept rate: 0%
 0 19 1 2 3 4 4 5 6 7 7 6 7 7 6 5 4 4 3 2 1 should be "no" but my AC code says its "yes" https://www.codechef.com/viewsolution/16728131 I suggest that every upcoming number till the mid of the array should either be equal or greater than the previous number. answered 31 Dec '17, 23:03 2★xprilion 3 accept rate: 0%
 0 can anyone tell why i am getting NZEC? please check my code here https://www.codechef.com/viewsolution/16810625 i guess the error is in converting string to integer array.how to handle the NZEC? THANKS IN ADVANCE answered 06 Jan, 20:36 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×14,366
×1,410
×854
×504
×193
×34

question asked: 11 Aug '17, 13:32

question was seen: 5,058 times

last updated: 06 Jan, 20:36