@coderji I did the first two parts of the problem manually. Then found out a formula.
I don’t remember the formula exactly now though.
@coderji I did the first two parts of the problem manually. Then found out a formula.
I don’t remember the formula exactly now though.
whats the cut off?
For 1) The answers are definitely a) 75 b) 175 and c) 399
1 Like
Hey here are my answers:-
- 75 , 175 , 399
- 38 , didn’t solve , didn’t solve
- 71 , 461 , 3447
- 13 , 10, 12
Today’s paper was bad , kids from RDPS were cheating rampantly , some people around me were coding in Dev and getting the output, IIITD should’ve been the center , no invigilation whatsoever and paper should’ve been written.
Hey guys I’m in class 11. Please tell us your class too cause then we can make an approximation for the cut off as it varies class to class… Also I’m expecting 40/80 
@dmhero My bad, I double counted some case, the answer for first subproblem is 36.
Method: Combinatorics
For the first row you have 3 choices and for the following rows until the last you have 2 choices.
For the last row you have only 1 choice.(You pick red if the count for red is odd upto the last row and don’t pick red if count is odd)
So for the 2nd subproblem
3 * 2 * 2 * 2 * 2 * 1=48
For the 3rd subproblem
3 * 2 * 2 * 2 * 2 * 2 * 1=96
In the first problem the red on the last row is below the red on the previous row. So you have subtract some cases.
Hope this solution is correct.
Yep this seems to be correct I spent a lot of doing this problem manually but I miscounted and got 38 as the answer :’’(
im in class 10 n expecting 25
Q1. 1) 75 2)175 3)399 (i wrote 400 though)
Q2. 1) 36 not sure about any answer here would like some clarity
Q3. all wrong
Q4. !) 13 2) 10 3) 12
11th grade - expecting 30
PS. Could someone give a definitive answer for question 2 and a valid method (ideally not brute force)
Yes 36 seems to be correct I counted it manually as well however I wrote the answer as 38,I got for R = 0, 2 ways,for R = 2, 24 ways , R = 4, 10 ways. Total 2+10+24 = 36
Can we have these problem sets for practice please in practice section of codechef? Please provide the link for aforesaid.
15 class 10 I made 2 very silly mistakes in sub problems or else I could have got 30 so surely i am not qualifying
I don’t remember my solutions but here’s my algorithm for Problem 2,
Let n represent the number of columns.
Let f(i, 1) represent the number of paths ending at peg 1 of column i while red count is even. Similarly for f(i, 2) and f(i, 3).
Let g(i, 1) represent the number of paths ending at peg j of column i while red count is odd. Similarly for g(i, 2) and g(i, 3).
We want to find —> f(n, 1) + f(n, 2) + f(n, 3)
Here is the recursive function :
If peg at (i, 1) is red, then f(i, 1) = g(i-1, 2) + g(i-1, 3) and g(i, 1) = f(i-1, 2) + f(i-1, 3). Similarly for pegs (i, 2) and (i, 3).
else f(i, 1) = f(i-1, 2) + f(i-1, 3) and g(i, 1) = g(i-1, 2) + g(i-1, 3). Similarly for pegs (i, 2) and (i, 3).
Using this, we solve the problem bottom-up.
For instance(I just made this up to demonstrate how this works),
1 2 3
R B B
G R G
B R B
Base cases are
f(1, 1) = 0, g(1, 1) = 1
f(1, 2) = 1, g(1, 2) = 0
f(1,3) = 1, g(1, 3) = 0
Now, we look at the 2nd column.
f(2, 1) = 1 + 1 = 2, g(2, 1) = 0 + 0 = 0
f(2, 2) = 1 + 0 = 1, g(2, 2) = 0 + 1 = 1
f(2, 3) = 1 + 0 = 1, g(2, 3) = 0 + 1 = 1
Now we look at the 3rd column(note that we only need f(n, i) to compute the final answer and so, we don’t calculate g(n, i))
f(3, 1) = 1 + 1 = 2
f(3, 2) = 2 + 1 = 3
f(3, 3) = 1 + 2 = 3
Finally, our answer is 2 + 3 + 3 = 8.
It’s sad. I made a silly mistake in P3 by not looking at a case and so, all my answers to that question are off by a few numbers. My P4 is correct and same as you guys. Assuming I made no calculation errors in P2(which is possible), I’ll get a 40. And I’m in class 12th. I have very low chances of getting through.
Probably the cutoffs will be 5 points lower than last years’ - for each class.