A Study in Combinatorics
All submissions for this problem are available.
Its the day of the final exam of the Combinatorics course.
The question paper consists of K sections and there are a total of N questions, with ith section consisting of Ni questions.
The students can attempt some(possibly all) questions in any order, but there is just one constraint that he/she cannot attempt two questions of same section consecutively, i.e. if suppose the student has attempted a question of section 1, then the next question he attempts cannot be of section 1, it has to be of a different section, after which he may choose to attempt a question of section 1. Note that it may not always be possible for a student to attempt all the questions. Also note that, a student can attempt a question atmost once.
Now the teacher has kept some buzzers (represented by integers), such that on going from one question to another, a buzzer has to be pressed. There may be multiple buzzers having the same number and each transition from a question to another is represented by exactly one buzzer. The numbers on the buzzers are in the range [1,M]. You can assume that the number of students is enough to encompass all possible combinations of question attempts, as allowed by the above constraint. In short, for every two question I and J, you are assured that all possible ways in which one can move from question I to question J is attempted by atleast one student.
Now after the exam is over, the performance of the teacher is evaluated. The teacher had to specify initially as to which buzzer should be pressed if the student wishes to go from one question to another, keeping in mind the constraint given above. He further had to ensure that given any two questions I and J (not necessarily of different sections), there must exist at least one student such that the buzzers he/she pressed in between completing question I and J had different numbers. For example, suppose a student attempts the questions in the order I, then X, then Y, then J, and the buzzers pressed in going from I to X, and X to Y and Y to J are all distinct from each other. The teacher has to ensure that there must exist atleast one such student for each pair of questions I and J.
To successfully pass the evaluation, the teacher should choose a value of M which is minimum for that particular question paper and satisfies the constraint as well.
Help in the teacher in finding such a value of M.
There are several test cases. Each test case consists of 2 lines.
Each test case begins with a single line contains two space-separated integers N and K.
Next line contains K space-separated integers representing the number of questions in each section.
The file ends with a single line N=K=0, which should not be processed.
Single line denoting the case number as "Case #i: " (without quotes) and value of M in the same line.
- TestCases ≤ 100
- 2 ≤ K ≤ 106
- 1 < N ≤ 109
- 1 ≤ N i < 109
1 1 3
Case #1: 2
The buzzers can be assigned in the following way :
Questions are denoted as Q(Section No.) . (Ques No.)
Q3.1 -> Q2.1 - Buzzer 1
Q3.2 -> Q2.1 - Buzzer 2
Q3.3 -> Q2.1 - Buzzer 1
Q3.1 -> Q1.1 - Buzzer 1
Q3.2 -> Q1.1 - Buzzer 1
Q3.3 -> Q1.1 - Buzzer 2
Q2.1 -> Q1.1 - Buzzer 1
For the above configuration, there will always be a student who has attempted two questions in such a way that all buzzers pressed in between attempting these two questions are distinct. The above solution may not be unique and there could exist another assignment of buzzers. However the number of buzzers used is the minimum possible.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, GO|
Fetching successful submissions
If you are still having problems, see a sample solution here.