1
$\begingroup$

There is an exam and the marking pattern is -

0 marks - Unattempted 

4 marks - Correct Answer

-1 marks - Incorrect Answer

And total number of question is 30. Find the total marks ( in integer ) which are not possible to obtain in the exam. eg.,119 , 118 , 117 etc are the marks that I can think of. Is there any way to approach such question.

$\endgroup$
2
  • $\begingroup$ Since the answer is simple, I would like you to mention what approach you took to arrive at the examples: 119, 118, 117, etc., and why do think that is incorrect/inefficient? $\endgroup$ Jun 8, 2021 at 6:58
  • $\begingroup$ @InuyashaYagamiI just started with 1 then 2 ,....but these were possible.So I started from last. Hit and trial $\endgroup$ Jun 8, 2021 at 7:10

1 Answer 1

2
$\begingroup$

If you need a computational way, you can use dynamic programming.

Let $C(i, s)$ be an indicator whether you can achieve a mark $s$ by $i$ questions. This means $C(i, s) = 1$ if there is a way to achieve a mark $s$ by $i$ questions, and $0$ otherwise. Clearly for $i = 0$ we have $C(0, 0) = 1$ and $C(0, j) = 0$ for all $j \neq 0$. Now the recursive formula is given by $C(i, j) = \bigvee\limits_{k \in \{0, -1, 4\}} c(i-1, j-k)$.

Clearly, you can implement this by iterating over all $i \in [30]$ and for each $i$ over each value $s \in [-30, 120]$.

This is a pseudo-polynomial algorithm, which means it runs in polynomial time in the input itself and not its size. However, since you need to output these values, we can assume that the input is given in unary and hence the algorithm runs in polynomial time (else the output itself might have exponential size).

However, if you want a more straightforward (mathematical) way to know whether a given mark is achievable, I would suggest you look up the extended euclidean algorithm. Specifically, the part where they put an upper and lower bound on the coefficients. Note that the sum of the coefficients, in this case, is at most $30$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.