plz help me to solve this problem using bfs and graphs…provide explaination and code…
Hackerearth question paper
plz reply to this doubt…
There are N questions in the examination. You get +a for the correct answer and –b for the wrong answer. You have to print the number of different marks that can be achieved.
Start with 0 marks. Each time you have 3 options:
You get the correct answer.
You get a wrong answer.
You do not attempt the question.
So you can move to +a,-b or stay at 0.
These are your new states of the problem where you have (N-1) questions and you can start with 0,+a,-b.
This is similar to a bfs problem where at every step you have 3 choices. Just run a bfs starting with 0 till you reach down by N levels. The number of states that you visited will be the actual answer. Since there were negative states, it is advised to use map/unordered_map in C++ to store the new states. But this can be optimized further as the states can be stored in an array if we shift the origin.
Here is the code https://ide.codingblocks.com/s/240522
s=nb;
d=na+s;
why are these two lines in code…plz explain the reason
Okay this is just reference point. What if you don’t get any answer wrong it will start at nb and then reduce it upto 0, instead of encountering negative numbers. na+s is the max you can get.
Just consider nb as the reference point.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.
plz reply to other doubts of mine as well…
What is the time complexity of the solution code that you have provided?