Hello guys,
Hope you guys had a great time thinking about the problems (Yeah, in competitive programming we “enjoy” solving problems 
). Here, you can avail the official solutions to each of the problems. If you still have any doubt after this, you can surely comment down below and one of the members will reply in an hour or two. If you have lost the question paper,
here
it is!
Before that, I would address the people who were a bit skeptical about not having an exam that doesn’t require any programming knowledge. Thing is, if you once start competitive programming, you will notice the similarity between the problems that are here and in an actual contest or the olympiads. It’s more about problem-solving than knowing how a language works, or the syntax. Anyone can learn a syntax of any language once he knows at least one. If you know JAVA, learning C++ is a breeze, same for python or any other language. You must enjoy solving problems to be a good competitive programmer. It is a sport and you can only succeed in it if you enjoy it like any other sport.
I would now like to start the solutions.
Q1. Author: Istasis Mishra(@ista2000)
Resources: CMI entrance exam for CS dept.
Related topic: Counting
Solution: As you might see, just case-working and seeing which follows the condition and count it. I will provide a nice combinatorial solution anyway. First trivial observation is of course that B is below everyone, so just fix B in the end. Then you see that A and E are independent of each other but C>D, so, the possible combinations if you keep A and E indistinguishable are ^4C_2, because you have 4 vacant places and you have to choose 2 places to put C and D. But A and E are distinguishable and we see that in each configuration we can just swap their positions, so we just multiply the result by 2, so we arrive at the solution 2\times^4C_2.
Q2. Author: Istasis Mishra(@ista2000)
Resources: CMI entrance exam for CS dept.
Related Topic: Basic logic
Solution: |A \cap B|= 80 After that, A has 10 left and B has 10 left, put each of C there and you then have got 40 left which will have to overlap with the intersection of both. This |A \cap B \cap C| = 40
Q3. Author: Istasis Mishra(@ista2000)
Resources: Original
Related Topic: Logic
Solution:
- I did not violate any terms in the statement; I got the tickets and went to England, thus in this case, P is true.
- I said if I win, I will go the England; but I didn’t. I violated the statement, thus in this case, the P is false.
- This was a tricky one, but if you observe, I said if I win, I will go to England; but I did not say anything about if I don’t. I did not say “I will go to England IF AND ONLY IF I win the tickets”. So, there might be other reasons for me to go to England. So even here P holds true as I did not violate it.
- Obviously, no violation and thus, P holds true.
- It cannot be determined unless we can time travel somehow
Q4. Author: Akash Agrawal(@akash9702)
Resources: CMI entrance exam for CS dept.
Related Topic: Basic counting
Solution:
Let there be n people in the business before Mr. L came. So everyone shook hands with each other once.
Allow me to digress. If there are three people (A, B, and C) who want to shake each others’ hands once. A shakes hands with B and C. B can’t shake hands with A (they can only shake hands once), so she shakes hands with C. Now, everyone has shook everyone else’s hands.
Similarly, when we have n people (named 1, 2, 3, ...). 1 shakes hands with 2, 3, 4, …, n, 2 shakes hands with 3, 4, …, n, ……, n-1 shakes hands with n. So 1 shakes hands with n - 1 people, 2 shakes hands with n - 2 people……n-1 shakes hands with 1 person. Therefore, total handshakes = (n - 1) + (n - 2) + …. + (1) = \dfrac{(n - 1)(n - 1 + 1)}{2} = \dfrac{n(n - 1)}{2}.
Now, some people have left the meeting. Let the number of people remaining when Mr. L comes be x. So Mr. L shakes hands with the remaining x people. Now, total number of handshakes = \dfrac{n(n - 1)}{2} + x = 100 => n^2 - n + 2x = 200, x \leq n. Now, let’s put some probable values for n. We find that 14^2 - 14 = 182. At n = 14, n^2 - n + 2x = 182 + 2x = 200 => 2x = 18 => x = 9. This is the only possible case (you can check others around it). So, 14-9=5 people left the meeting before Mr. L arrived.
Q5. Author: Istasis Mishra(@ista2000)
Resource: FIITJEE maths teacher ( 
)
Related topic: Thinking about a problem in a different way
Solution:If you just try to open up the cube, like…think of it like a box and try to open it up, you will get something similar to the image below
The red line connects the initial and the final positions that were given in the original problem statement. The red line also represents the shortest path that one will need, this is because a straight line is always a shortest path between two points. If you think of the red line as a paint, it will be intact if you close up the cube, now if the ant just follows the red path, she will be on the shortest possible path to her desired position. Thus, the answer is
.
Q6. Author: Akash Agrawal(@akash9702)
Resources: MIT OCW
Related topic:Pigeonhole principle(Even though this is a specific topic, this is very basic and so, we decided not to ask people to prepare for it specifically)
Solution:
There are 85 members, whose IDs are 9 digit numbers. E.g., 012345678 and 123456789. Thus, the general ID is d_1, d_2, d_3, d_4, d_5, d_6, d_7, d_8, d_9 where, for 1 \leq i \leq 9, 0 \leq d_i \leq 9.The sum of the digits of an ID is d_1 + d_2 + d_3 + d_4 + d_5 + d_6 + d_7 + d_8 + d_9.The value of this sum will be minimum when every digit is equal 0. This minimum value itself is equal to 0. The value of this sum will be maximum when every digit is equal to 9. The maximum value is 81.
So, any ID will have its sum between 0 and 81 (inclusive).That’s why there are only 82 valid possibilities for the sum of the digits, any ID it may be. With there being 82 possible sums and 85 members, something interesting happens.
Imagine there are 82 labelled buckets, with numbers 0 to 81. Let each member get a sheet of paper where s/he will write the sum of the digits of his/her ID.Now, make each member put their sheets in the buckets labelled with their respective sums.As there are 82 buckets and 85 sheets, there has to be at least one bucket where there are two sheets of paper, because even if the first 82 sheets go into different buckets, the next will go into a bucket already occupied by a sheet.
Q7. Author: Akash Agrawal(@akash9702)
Resource: Link shared as solution
Related topic: Thinking about a problem in a different way(again)
Solution:
There are an infinite number of points on the earth where you can be. Solution here
Author: Istasis Mishra(@ista2000)
Resource: Original
Related topic:Recurrent relations
Solution: Even though this is based on recurrent relations, one might not even solve it even if he is well versed with them, as this problem requires ingenious use of them. This can even be solved in a different not-so-elegant way but I will not discuss about it here as it is very tedious. Lets try to build up a solution now. For the first ball, there are K different choices of colours, for the second ball, which is adjacent to the first ball, there are K-1 different choices as one of them have already been used in the first one. In the third one, we can choose from K-1 different colours, as the first and third balls can have the same colour but not the second and third one.
We can keep doing this until we only have one uncoloured ball left. Then we have two cases, if the first and then second last ball are of the same colour, we have K-1 choices for the last one, else K-2. This is where the problem arises, you cannot get around it using basic counting techniques like P and C. But think about it a little. Suppose, keep our choices as K-1 colours only. Now, we need to subtract the number of ways to colour the given arrangements such that the first and the last balls have the same colour. We might notice that this is the same the number of ways to colour N-1 balls such that no two adjacent balls have the same colour. But we also know this is just F(N-1, K). So, we now have our solution, it is just
Author: Istasis Mishra(@ista2000)
Resource: Original
Related topic:Catalan Numbers, Logic
Solution: We are already acquainted to changing path to a string of ‘E’, ‘W’, ‘N’, and ‘S’. We just now have to find the number of ways to arrange a string of these characters such that it forms a valid path, i.e, follows all the conditions given. How to translate the conditions to the string? “Coming back to home” can be translated as having the same number of ‘E’ as that of ‘W’ and ‘N’ as that of ‘S’. Staying in the first quadrant always translates to having |’E’|>|’W’| and |’N’|>|’S’| at each point of time.
We explained catalan number as “Number of valid bracket sequences”. But what makes a bracket sequence valid? A bracket sequence can be valid only when |(| = |)| overall and |(|>|)| in each moment of time.
Notice the similarity? Now, we can see that ‘E’ and ‘W’ should form a valid bracket sequence and so do ‘N’ and ‘S’.
We are not finished yet even though we are done with most of our work. Now we have to find the number ways actually. What we can do to construct the solution. For each i, from 0 to N, let’s set \dfrac{i}{2} characters in the string as ‘E’, \dfrac{i}{2} characters ‘W’, \dfrac{N-i}{2} characters as ‘N’ and \dfrac{N-i}{2} characters as ‘S’, we have \binom{N}{i} ways to select the vacant places for ‘E’ and ‘W’ and the rest are ‘N’ and ‘S’. And for each arrangement we have Cat(\dfrac{i}{2}) ways to arrange the ‘E’ and ‘W’, and Cat(\dfrac{N-i}{2}) ways to arrange ‘N’ and ‘S’. So, we have our answer as
Q10.Author: Istasis Mishra(@ista2000)
Resource: Original
Related topic: Logic, optimization, binary search(Don’t worry, it’s quite easy), bits
Solution: This is going to be a long one. But the solution is very elegant. Take a read and you will surely learn something new and interesting.
So, I will slowly build up the solution from the least optimal to the most optimal one. As some of you have taken the hints, you know what the most optimal solution is, but here I would explain in depth how I come to that.
Least optimal: The most naive solution is to take a 1000 servants and then giving each of them a drink each and the one that dies next day, we know that the poison is in the drink that he drunk.
1st optimization: A pretty straightforward optimization would be to use 999 servants and give them a drink each, if no one dies we know the drink that was not given to anyone is poisoned.
2nd optimization: This is going to be an elegant optimization. We all know what “Binary Search” is, right? Just in case we don’t, I would explain it in short.
So, suppose we have an array of length 8 having elements in increasing order and we want to find an element. How do we do it? We can simply use a loop and match each element with the given one and check if its equal. But for this will take 8 steps for you to do so. What optimization can we make here? We can use the fact that the elements are increasing. We check the middle element, if that is greater than the given number then if it’s present the element to be searched should be in the lower half. For example A = [1, 3, 5, 8, 10, 12, 15, 19], if we want search 3, we would first check the middle element(8) and see that 8>3 and thus 3 must be in the lower half, if we search 12, 8<12 and thus 12 must be in the upper half, we can do this each time and the size of the array we are searching in becomes half each time. Here, we can do it in 3 steps, in first step, the size becomes 4, in second step, it becomes 2 and in last step it’s 1. The formal proof is given below, you can skip it if you want to but it is recommended you understand. We refer to the length of the array in which we are search as “Search domain”.
$
\text{Let the size of the array be N and the number of steps be T}\
\text{In step 1, Size of the search domain} = \dfrac{N}{2} \
\text{In step 2, Size of the search domain} = \dfrac{\dfrac{N}{2}}{2} = \dfrac{N}{4} \
\text{In step 3, Size of the search domain} = \dfrac{\dfrac{N}{4}}{2} = \dfrac{N}{8} \
\text{In general, in step R, Size of search domain} = \dfrac{N}{2^R} \
\text{But we know that in the last step, the size of search domain must be 1}
\therefore \dfrac{N}{2^T} = 1\
\implies N = 2^T \
\implies T = log_2(N) \
\text{Since, T must be a whole number we can either take the ceil or the floor of it.} \
\text{We would take the ceil because less steps than the desired amount will cause} \
\text{the search domain in the end to be >1 while more steps than the desired will} \
\text{cause the search domain to be \leq 1} \
\therefore T = \lceil log_2(N) \rceil
$
Now that we know about binary search, let’s see some of it’s real world applications. We use it in daily lives without even thinking about it. We use it to find words in dictionary and names in a call log(It’s obsolete now :3).
Here we will use binary search in a very clever way. In this example, there are 1000 glasses. We can take some from each glass from the first 500 glasses, mix them in a new glass and give it to a servant to drink. If he dies, we know that poison is in one of the first 500 glasses, if he doesn’t die then, the poison is in the last 500 glasses. We can then again divide 500 into two parts of 250 glasses each.
\text{Number of people we need} = \lceil log_2(1000) \rceil = 10 (\because 2^{10} = 1024)
Wow! Wasn’t that elegant? We would need 10 people and it will take 10 days!(Because we can only decide which part to search in after a day)
The final optimization: The last optimization was to just give a feeling of what binary search is like. But this optimization is even more elegant! For this solution, I will assume you know about the binary number system. If you do not know you can learn about it from here.
Okay, so, here what we can do is, label each glass with a number, say 0 to N-1. For each number, we can convert the label to binary and depending on whether a bit is 1 or 0, we decide whether to give that person the drink or not respectively. The next day, some set of servants will die and from that we can infer which glass was poisoned, since each glass will have a unique binary, for each glass a unique set of people will die.
Let’s take an example:-
Suppose we have 8 glasses, we could do it in 3 people and 1 day.
0 \to 000 \\ 1 \to 001 \\ 2 \to 010 \\ 3 \to 011 \\ 4 \to 100 \\ 5 \to 101 \\ 6 \to 110 \\ 7 \to 111 \\
These are the corresponding binary representations of the numbers from 0 to 7. Let’s name the servants A, B and C. We give the drink to C if the leftmost bit is 1, we give it to B if middle bit is 1 and we give it to A if the rightmost bit is 1. For example, we won’t give glass 0 to anyone, we will give glass 1 to A only, we will give glass 2 to B only, we will give glass 3 to both A and B and so on.
Now, if only A dies, we know glass 1 is poisoned. If A and C die, then glass 5 is poisoned. I hope I could give you the feel.
We know that with B number of bits we can represent numbers upto 2^B. If we have 9 bits we can represent numbers upto 511 and if we have 10 bits then we can represent numbers upto 1023(One less because 0 is also included). Since, we have 1000 glasses, we will need 10 bits to represent the labels on the glasses and thus, we would need 10 people. Also, we get the results in the next day only.
Thus, this last optimization gives us the result with 10 people in 1 day.
I hope you guys liked the problems and enjoyed solving them. Again, in case of any doubts, you can surely ask one of us for clarification.
Also, it took a lot of time and dedication from us to prepare the problems and write the solutions. As you can see, some of the problems here are original, i.e, you won’t find the solutions if you google them. We will sincerely appreciate any feedback that you guys have.
Also, I would like to thank Akash Agrawal(@akash9702) for contributing a lot for this test, both setting problems and writing the solutions.
Lastly, I would like to apologize to you because maybe the test was “too hard” but don’t worry, we will most probably bring down the cutoff and will sincerely try to prepare you to solve problems like these in the future.
Regards
Competitive Programming Department Head
Istasis Mishra(@ista2000)
