Paper generator

, , ,
1

Ravi needs to set Question papers fairly for his students for an exam. He has three categories of Questions i.e. Simple, Medium, Complex. Each Question paper has one or more simple, medium, complex questions.

For each paper, he needs to choose precisely s out of a set of x simple, precisely m out of a set of y medium and precisely c out of a set of z complex questions.

These questions are labelled A, B, C and so on, with the first x being simple, the next y being medium and the last z being hard.

Write a program that prints the number of possible combination of Question papers

Ravi decides to impose following constraints while selecting the question papers:

Two given questions can’t come together in any Question paper

One of the given Question can come in only one Question paper

Remaining Questions can come any number of Question papers

Find how many Question papers can be generated after imposing the constraints.

Constraints

s,m,c > = 1

x > = s, y > = m, z > = c

1 < (s + m + c) < =26

Input Format

The First line contains x, the number of simple questions.

The Second line contains s, the number of simple questions to choose from x.

The Third line contains y, the number of medium questions.

The Fourth line contains m, the number of medium questions to choose from y.

The Fifth line contains z, the number of complex questions.

The Sixth line contains c, the number of complex questions to choose from z.

The Seventh line contains the question pair that cannot be the part of the same Question paper, delimited by single space.

The Eighth line contains the Question that should be asked only in one of the Question Papers.

Output

The First line contains total number of Question papers possible without any constraints.

The Second line contains total number of Question papers after imposing all the constraints.

Test Case

Explanation

Example 1

Input

3

2

4

3

3

2

A D

G

Output

36

4

Explanation:

From the input we know that there are 3 simple, 4 medium and 3 complex questions.

First x as per the alphabetical order are simple questions, next y are medium questions and remaining z are complex questions. The total number of Question papers that can be generated without imposing constraints is 36.

As Questions A and D cannot be cannot be in the same Question Paper and Question G can exist only in one of the Question paper, the maximum number of Question papers that can be generated after imposing constraints is 4.

And one of the possible set of 4 question papers is:

ABEFGHI

BCDEFHI

BCDEFHJ

BCDEFIJ

// explain how to solve this

1 Like
2

someone please help me to try to solve this problem

3

I feel you should paste the link to the og question instead of pasting the entire text here, just so that we can be sure this is not from any ongoing contest :slight_smile:

1 Like
4

If I’m not wrong this question came in MockVita. Here is how I solved it: Competitive_Programming/main.cpp at master · NinjaGaurav/Competitive_Programming · GitHub

2 Likes
5

yess this is first question in MockVita . And thanks for your answer

6

Added few more comments, do let me know if you need a more detailed explanation

7

yes please explain your solution

8

ok i will paste in og question

9

for test case
2
1
5
3
4
3
A B C
your code is giving output 80 17
but i think it should be 80 33

10

this output is according to @kamalkarki03

1 Like
11

hey how many questions did you solve? :slight_smile:

12

Yes there was a bug in nCr calculation, it had to return 0 if r or n is negative(since 0 possible ways in that case) but it returned 1 hence output was less. Fixed it in github link.
Output for the test case you gave now is: 80 33

13

I solved 2 questions in 3 hrs, this and Bad Permutation.

14

@gogetassj4 can u explain ur logic

15

I use the property of Sets.

First I calculate all possible ways let this be S.

Then I calculate the no of ways in which the 2 questions (reverse of condition 1) are together let this be A

Then I calculate the no of ways in which the question which can come only once (reverse of condition 2) let this be B.

Then for the answer I do:
ANS = S - A - B + ( A intersection B)
( A intersection B) is added because the part that satisfied both reverse of condition 1 & reverse of condition 2 is subtracted twice. See this pic for visualisation:
https://dr282zn36sxxg.cloudfront.net/datastreams/f-d%3A53d1c8ea561f962b852b7b34cf5bdf8496bcff65a2e901977a67f213%2BIMAGE%2BIMAGE.1

We do this because we need the ways in which condition 1 and 2 are satisfied.

Also we need to add 1 to ANS because we could use the question in condition 2 once.

4 Likes
17

can you explain the logic of your bad permutation code to generate the count in list

18

#include
#include<bits/stdc++.h>
using namespace std;
int binomialCoeff(int n, int k)
{
// Base Cases
if (k==0 || k==n)
return 1;

// Recur
return binomialCoeff(n-1, k-1) + binomialCoeff(n-1, k);
}
int combi(int val,int x,int y,int z,int s,int m, int c)
{
int a=x,b=y,d=z;
if(val<=x&&x>s)
{
x=x-1;
}
else if(val>x&&val<=x+y&&y>m)
{
y=y-1;
}
else if(val>x+y&&val<=x+y+z&&z>c)
{
z=z-1;
}
if(a==x&&b==y&&d==z)
{
return 0;
}
else
{
return binomialCoeff(x,s)*binomialCoeff(y,m)*binomialCoeff(z,c);
}

}

int main()
{
int x,y,z,s,m,c;
char h[2],e;
cin>>x>>s>>y>>m>>z>>c;
for(int i=0;i<2;i++)
cin>>h[i];
cin>>e;
if(s+m+c<26||s+m+c<1||s<0||m<0||c<0||x<s||y<m||z<c)
{
return -1;
}
int n,t,val;
n=int(h[0])-64;
t=int(h[1])-64;
val=int(e)-64;
int op1=0;
op1=binomialCoeff(x,s)*binomialCoeff(y,m)*binomialCoeff(z,c);
cout<<op1<<endl;
if(val<=x&&x>s)
{
x=x-1;
}
else if(val>x&&val<=x+y&&y>m)
{
y=y-1;
}
else if(val>x+y&&val<=x+y+z&&z>c)
{
z=z-1;
}
int op2=0,nevertog1,nevertog2;
nevertog1=combi(n,x,y,z,s,m,c);
nevertog2=combi(t,x,y,z,s,m,c);
op2=nevertog1+nevertog2+1;
cout<<op2<<endl;
return 0;
}

please tell me where my code is wrong it’s not working for private test cases.