Can someone please provide the easy and expressive editorial of Road question?
You can solve this by dp. See a_i<=50. And one important observation is suppose you are at index i and you have a_j=a_k=x and k>j>i. So you can move to either j or k but its always optimal to move to j as in this case you can cover more nodes. So keep track of nearest index to right having distinct a_i for for every index i and then do a dp. F(N,K)=max(F(next[i],K-i)+1) for i=0 to 50.
I said “**easy and expressive **” editorial. This type of explanation is already given in question’s editorial section.
BTW Thanks for your explanation.
what do u mean by easy and expressive? Tell me what problem you are having i will do my best to help you
I mean the way you explained is out of my mind. Please try to use Latex for Maths and elaborate your approach with example.
Okay let me try explaining a bit more. See what you need is count of maximum number of nodes you can visit. Now see that max value a[i] can take is 50. And n is quite high so its obvious most values of a[i] will be repeated. Now from an index you can move to 1 or more indices having same a[i]. But you can see that best choice is always to move to nearest node to right with that a[i]. WHY? Because see suppose you are at index i and you see that a[j]=a[k]. and k>j. Now you can obviously try moving to both. But its better to move to j as had you moved to k all the indices between [j,k) would be ignored/never visited. Now you might claim ,let the optimal path be from i to k to p to … But see had you visited j, optimal path length would increase by 1 as cost to move from j to k is 0 and then follow your optimal path. So how to do this.? Keep an array next[N][51]. run a loop backwards and keep a temp[51] array. Each time copy next[i]=temp. and then update temp[a[i]]=i. So this ensures that next[i][j] is the next index to right of i having a[idx]=j. So now the states of dp are simple. From each index you can choose to go to any nearest index with some value of a[i]. You already have the nearest indices stored in next[] array. So F(N,K)=max number of nodes you can visit from N with weight K remaining. Now run a loop j= 0 to 50 and visit the nearest node with a[i]=j. So F(N,K)=max(F(next[i][j],K-j)+1) for j=0 to 50.
2 Likes
@soham1234 can u tell me simple definition of state in dp …
and how to attack a dp question when it comes …
There is small bug in your code… Other wise your code is perfect
if(curr==N)
return 0;
This must be replace with N-1, i.e,
if(curr==N-1)
return 0;
Well If you see the official editorial then, author used the Bottom-Up approach which I suppose is faster than your’s one. So can you explain that approach?