RAINBOWB - Editorial

editorial
, , , ,
11

My approach might be similar to what others have suggested, but I will mention it nonetheless in case someone hasn’t understood any of the above methods -

if N < 13, then it is impossible to form a Rainbow Array.

Now, for N >= 13, let us first “distribute” the first 13 elements to each of a1 (2 times), a2 (2 times), a3 (2 times)…,a6 (2 times) and a7 (1 time). This constitutes a minimal rainbow array.

Now we have N-13 elements remaining.

If N is odd: // Implies N-13 is even
    In reality, now we only need to distribute (N-13)/2 elements since if we allot one element to a1 before a7 then the other will go to the other a1 (after a7).
    To distribute (N-13)/2 elements among 7 "containers" (a1, a2, a3, a4, a5, a6, a7) in zero or more ways (since we already filled them once before), we have the combinatorial formula C(n+r-1, r-1), where n = (N-13)/2 and r = 7.

If N is even: // Implies N-13 is odd
    Then the number of ways will remain the same as above case since the odd one left will always be sent to a7 and will not contribute to the number of ways.
4 Likes
12

Hi guys, Maybe I am not getting the solution correctly but where are we checking if the number of a1’s, a2’s etc. are equal in the left and the right of the array.

13

Please Somebody Explain my How the Number of Vectors equals C(K-1,5).

“…the well-known fact that the number of integer vectors (a1, a2, a3, a4, a5, a6) such that a1+a2+a3+a4+a5+a6=M/2=K is C(K-1, 5)…”.

Seriously I don’t know how it came ? Can somebody Please explain me this… I was stuck in this position for a long time during the contest.

14

/*

  • To change this license header, choose License Headers in Project Properties.
  • To change this template file, choose Tools | Templates
  • and open the template in the editor.
    */
    package codechef;

import java.util.Scanner;
import java.io.*;

/**
*

  • @author admin
    */
    class Rainbow {
    public static void main(String args[])throws IOException

    {
    //Scanner in=new Scanner(System.in);
    BufferedReader br=new BufferedReader(new InputStreamReader (System.in));
    int n=Integer.parseInt(br.readLine());
    if(n>100 || n<1)
    {
    System.out.println(“no”);
    System.exit(0);
    }
    for(int k=1;k<=n;k++)
    {
    int l=Integer.parseInt(br.readLine());
    if(l<7 || l>100)
    {
    System.out.println(“no”);
    break;
    }
    int arr[]=new int[l];
    for(int i=0;i<l;i++)
    {
    arr[i]=Integer.parseInt(br.readLine());
    if(arr[i]>100 || arr[i]<1)
    {
    System.out.println(“no”);
    break;
    }
    }
    String r=IsRainbow(l,arr);
    System.out.println(r);
    }

    }

    static String IsRainbow(int l,int arr[])
    {
    int flag=0;
    int k=((l/2)+1);
    int j=k;
    if (l%2==0 || arr[k-1]!=7)
    flag=0;
    else
    {
    for(int i=k-2;i>=0;i–)
    {
    if(arr[i]!=arr[j])
    {
    flag=0;
    break;
    }
    else flag=1;
    j++;
    }
    }
    if(flag==0)
    return “no”;
    else
    return “yes”;

    }
    }

I know its not good method but I am amateur. I tried this even with scanner method but its coming runtime error. I have successfully compiled it in netbeans and got the result. But, the codechef compiler is constantly showing error. Can someone please tell me the error ?

15

Can you explain it?

16

I’ve tried my best to explain it.

17

We have to distribute K objects among 6 people. Suppose, all the K objects are lying in a row on the floor equally spaced. Now, if you put 5 bars, beetween any of the objects (gap b/w the objects), it will divide K objects into 6 parts and will be one possible solution of the equation above. So, all possible combinations can be given by (k-1)c(5) ( i.e. selecting 5 gaps among k-1 gaps).

6 Likes
18

yeah got it thanks…i was missing the point that we need an integer solution (a(i) > 0)…so i was effectively considering 6 bars…

19

yeah…thats what i did during contest…basically we need to find the total integer solutions to equation. a1 + a2 + … + a6 <= K…
it comes to combination(K,6)

2 Likes
20

explanation to the solution is provided below

21

C(M,6) where M=(n-1)/2

22

C(M,6) where M=(n-1)/2

23

Can you tell me where my reasoning is wrong? For K=7, there is 1 solution: 1…7. for K=8, you can choose any one of [1,7] to clone, so ans=7. *For K=9, you can again choose any one of [1,7] to clone, including one chosen before (for. eg. 1,2,2,2,3,4…), so ans = 7**7. Continuing this way, shouldn’t it be 7^(K-7)?

24

Could you explain your reasons for believing so?

25

Can anybody tell if the formula (k-1)C(5) is applicable for k<7 ,because in all these cases answer will come out to be 1.
for example: a1+a2+a3+a4+a5+a6=2 ,here k=2,by using above formula answer will be 1.but in actual it should be 21…please help,any kind of help will be appreciated

26

for nCr to work n must be greater than equal to r. In your case k-1=1 is less than 5 therefore answer is 0.

1 Like
27

Dude Awesome !!

28

why C(K-1,5) ?

It should be 6, right?

29

@amit001 i think you perhaps misunderstood the solution given in the editorial. As we are brute forcing all the values for 7 so we need to distribute the rest of the values in six containers. agree ??

30

@kodoos my bad. i was reading solutions in comments so thought 6 should be used but solution above brute force a7. now got it