I used simple N^2 DP approach as we do in very basic DP problems…
In short, I took “minimum of all possible paths”.
Can anyone tell me what mistake i did?
while index < (n-k+1) {since, after that you can directly jump to n+1)
traverse backward from index+k to index+1, if you find any element having parity as p, break immediately and set index as break_element_index.
Look at my code, it will be clear.
In short, you are jumping to the last place having same parity in a group of range k.
This is almost same approach which i used…
The only difference is that i traversed in forward direction, and stored minimum for each position…
But i dont know where am i going wrong
Any advice?
Thanks in advance
First of all, your code does not fit the time limit.
Secondly, the line if(a[i]&1==a[j]&1) is not working, replace it with if((a[i]&1)==(a[j]&1)) [Just put it in bracket].
Test case :
1
5 2
948 28 1 238 94
After putting brackets, it shows correct output. You can verify.
vector<int> dp(n+1,INT_MAX); //it'll store the minimum values as you require
//thes two multisets will store the dp values of the range [i-k,i) according to there parity of values so that you can get the minimum in the range as per the parity of current i
multiset<int> evens,odds;
//just setting up the initial values where we can reach without considering parity and inserting them in multiset as per parity
for(int i=1;i<=k;i++){
dp[i]=1;
if(v[i]%2==0) evens.insert(dp[i]);
else odds.insert(dp[i]);
}
//now the final transitions begin we find the minimum in range [i-k,i) as per the parity in the multiset
for(int i=k+1;i<=n;i++){
//if v[i] is even well look in even multiset and after querying and doing necessary transition will add it to multiset
if(v[i]%2==0){
if(!evens.empty()) dp[i]=(*evens.begin()+1);
evens.insert(dp[i]);
}
//similarly for odd
else{
if(!odds.empty()) dp[i]=(*odds.begin()+1);
odds.insert(dp[i]);
}
//now the (i-k)th index won't be available for transition anymore so remove it from its respective set
if(v[i-k]%2==0){evens.erase(evens.find(dp[i-k]));}
else {odds.erase(odds.find(dp[i-k]));}
}
Some things to care during implementation
Remember it’ll have minimum moves for N and we need to find for N+1 to which we can make transition from any of the last k positions so query for the minimum is the last k dp values and return min+1 as ans.
(If min is greater than or equal to INT_MAX return -1
Actually during contest its more about getting it right so there are many conditions at the end of my code to this problem which might not be necessary as well but i didn’t want to miss out any of them so the code at end becomes confusing.Thus I added the main part with comments instead of complete code.
Hope its clear from the comments added, feel free to ask.
Its good to see juniors working hard and doing great in programming competitions.
Keep up the good work
There is an unnecessary cout<< statement in line 54
You are storing indices in the set and querying for upperbound of current index .I’m not sure if it is a correct way of transition.Do revisit your intution for using this.