Can you explain me the dp stairs problems solution?
badly I have 2 of these in my set…salary one and the work life balance…I thought they put wrong value of K in work life so I take it as 100 only but got WA badly…
Moreover I don’t know how many partial test cases were passed by my solution on public test cases…Is that work for ranking??
This is different. Question said 3 can be used only once.
oh,is that so! Actually I didn’t get this problem,my friend got this. So I had ignored reading this one
Sure. as I mentioned the bottom up solution was a bit more tricky.
Note: I am assuming that 0 is the top and I have to get to N where N is the ground floor.
So, we have two dp arrays, or 1 dp matrix of Nx2 size. Let the first row’s column j denote the number of ways to get to j th step if we have not used the 3 step yet.
similarly, let the second row’s j th column denote the number of ways to get to j th step if we have used the 3 step.
Base cases
for both used and unused rows, dp[0] = 1, dp[1] = 1, d[2] = 2. Hope the base cases are clear or will be clear after reading the rest of the solution. If not then let me know.
Topological order
The order for the elements of first row is simple since only two possibilities are allowed in this (come here from step i-1 or i-2)
For the second row, it was the tricky part, the number of ways to get to i th step if we have used the 3 step ability is the number of ways to get to (i-1) and (i-2) if we have already used the 3 step ability before + the number of ways to get to (i-3) if we haven’t used the 3 step ability at (i-3) step (means that we use the 3 step ability to get to the i th step), which is the step (i-3) of first row.
Code
Using these we can write this
long long steps(int n){
dp[0] = 1; dp[1] = 1; dp[2] = 2;
dpused[0] = 1; dpused[1] = 1; dpused[2] = 2;
int i;
for(i=3; i<=n; i++){
dp[i] = (dp[i-1] + dp[i-2]) % PRIME;
dpused[i] = (dpused[i-1] + dpused[i-2] + dp[i-3]) % PRIME;
}
return dpused[n];
}
5 Likes
Great explanation! Thanks!
Got It!
1 Like
Ok, now that I think of it, there are some mistakes here. The answer would be correct but there are some conceptual mistakes in my solution.
One way to correct the concept is by saying that dp used is not just the number of ways to get to i’th step if we have used 3 step ability but it is the number of ways to get to i’th either if we have or haven’t used the 3 step ability.
Cause if i were to say what i said in my explanation then the base cases for dp used would be different
dpused[0] = dpused[1] = dpused[2] = 0
since there is no way to get to step 1 and 2 if i have used the step ability
And also in the end, I would have to return dp[n] + dpused[n] which means return the number of ways to get to n’th step if I haven’t used the 3 step ability + the number of ways to get to n’th step if I did use the 3 step ability.
2 Likes
could solve only two.
Question A was easy.
B Wrong Answer on hidden cases, couldn’t find the mistake it despite of trying for 3 hours.
C was easy.
D couldn’t understand question statement.
E TLE
F didn’t attempt.
If anyone needs now, here are the solutions to the four problems i solved.
Bit Score
Bottle Necks
Dole out cadbury
Pattern
Friend circle required very tedious recursive implementation and car optimization was 4 dimensional interval scheduling dp which i also didn’t solve.
If anyone has some easy (short) implementation of these two problems please share.
3 Likes
Bro what if the question is slightly changed to that we can use 3 steps almost k times. 
Then we will have to take k rows.
Row 1 will represent ways to get to i’th step by using 0 three steps
Row 2 will represent ways to get to i’th step by using either 0 or 1 three steps
Row 3 will represent ways to get to i’th step by using 0, 1 or 2 three steps
.
.
Row k will represent ways to get to i’th step by using 0, 1, 2. . . , k steps
The graph would look similar, just add more rows to it and each row will be connected to itself and the row above it like row 2 is connected to row 1 in the graph for k = 1
1 Like
Thats nice approach.
I was able to solve 3 problems 1 with presentation error however their compiler was somehow showing weird error which was little bit frustrating and time consuming
This might help.
Public Test Case Vs Private Test Case:
While submitting solutions on CodeVita site, On clicking on Compile and Run button, The program gets evaluated for public testcases only which are given in problem text. Getting Presentation Error or Accepted status here only means that your program is compiling and executing successfully against public testcases.
Simply executing Compile and Run is not enough . In order to run private testcases against programs one needs to Click on Go to Submit page button, then click on Submit button to evaluate program. This submission will be considered for Ranking. This can end up in any of the 8 statuses. Also, getting Accepted or Presentation Error while Compile and Run does not guarantee that the same status will appear after Submit functionality.
As described above, this is because Compile and Run is run against public testcases while Submit is run against private testcases. Public testcases are those testcases which are present in problem text whereas private testcases are hidden.
3 Likes
Solved 5/6 (6th one was too ambiguous to be given a thought). Codevita has improved a lot if I compare it to previous year. Yes they do miss constraints for a lot of questions! But yes we cannot expect much also! Overall they have improved in terms of quality of questions.
3 Likes
It was my first time where I participated in a competitive coding contest. The first question I had was of ‘Salary Paid’ and I spent my 5 hours on solving it. I have some doubts tho. It was given in the description that employee who paid 90,000 as tax was receiving 10,00,000 as salary.
Now excluding the rebate amount, the taxable component of his salary would be 9,00,000 which belongs to the slab of 6,00,000 - 9,00,000 thereby, 20% income tax should have been levied on the employee which is 20% of 9,00,000 = 1,80,000. Then how come he paid 90,000 only. Same with rest of the samples. Was your solution accepted?
Actually, that’s not how tax system works. if your salary is 9L and let’s say the slabs are as follows
<3L = 0%
3L-6L = 10%
6-9L = 20%
then for the first 3L you earn, you would have to give 0% tax.
Now the remaining salary is 6L.
From it, the next 3L you earn, you will have to give 10% tax = .1 x 3L = 30k
now the remaining salary is 3L
On it, the tax is 20% = .2 x 3L = 60k
so 0 + 30 + 60 = 90k
That’s why they wrote the hint in the end of the question telling to read abut tax system first if you don’t know about it 
1 Like
Yup…I was also fucked up my 1 hour to solve this problem but still TLE.
Anyone got “Accepted”??
I got run time error in the ODI scores problem, but all the private test cases were satisfied.I tried figuring out the i/o error but couldn’t figure it out.Will they consider it as a solution?