Can someone explain how do we get this formula
a1+a2+a3+a4+a5+a6=M/2=K is C(K-1, 5).
Can someone explain how do we get this formula
a1+a2+a3+a4+a5+a6=M/2=K is C(K-1, 5).
O(1) solution also exist for this problem.
what is “first 6 columns of the Pascal triangle” ? please explain.
The problem statement is unclear, ambiguous!
how to find combination formula using pascal? can u clear
Although i got your solution that you have brute force the value of a7. But, does it really required here is my solution to this problem .
I thought
if n is even then first n/2 will be exactly same as next n/2 integers but in opposite order.
else first (n)/2 will be same as next n/2 but n/2+1 being equal to 7.
so , what do we need to find is how many ways are there such that we can distribute (n+1)/2 elements in 7 boxes such that each box contains at least one element.
consider M=n/2+1
and the formulla M-7+6 C 6.
M-1 C 6.
A much simpler solution in terms of big notation. This way this problem can be solved for the higher constraints too.
Hope all of you get the idea. if anything is not understandable do comment here.
import sys
f=sys.stdin
mod=1000000007
n=int(f.readline())
if n<13:
print 0
else :
n+=1
n/=2
n-=1
ans=n*(n-1)*(n-2)*(n-3)*(n-4)*(n-5)
ans/=720
ans%=mod
print ans
</a
here is my python code for this problem . hope you like this.
Can anyone let me know why pascals triangle is required? PLease.
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.
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.
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.
/*
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 ?
Can you explain it?
I’ve tried my best to explain it.
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).
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…
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)
explanation to the solution is provided below
C(M,6) where M=(n-1)/2
C(M,6) where M=(n-1)/2
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)?