Problem 1
Given a binary string find no. of subsequence of length 3 such that no two adjacent characters are same(101, 010). N <= 1e5
Problem 2
Given an array we want to make it non-increasing by doing following operation one at a time :- - you can shift 1 from a[i] to a[i+1], after that a[i]->a[i]-1 and a[i+1]->a[i+1]+1 (if i+1<n) - you can shift 1 from a[i] to a[i-1], after that a[i]->a[i]-1 and a[i-1]->a[i-1]+1 (if i-1>=0) Calculate minimum moves required to make it non-decreasing. N <= 250. a[i] <= 1e9 Example: a[] = [5 3 2 3 3 3] -> [4 4 2 3 3 3] -> [4 3 3 3 3 3], output is 2
Problem 3
Given an array a[] find no. of array b, such that 1 <= b[i] <= a[i], and no two adjacent element of b are same(b[i] != b[i+1]). Print it modulo (1e9+7) since ans is large. N <= 1e5 a[i] <= 1e6 Example: a[] = [2 3] b[] = [1 2], [1 3], [2 1], [2 3], output is 4
I think there is issue in question 2 you write to make it non-decreasing but in example make it non-increasing.
Yeah you are right, i have updated it !
1,3 are pretty easy 1 is standard dp question and third one can be solved in 2 dp of size 2*n i can't think of second question for now but i feel it has same implementation as
https://mirror.codeforces.com/problemset/problem/2013/D
will update the comment if i got any soln for 2
1 can be done using prefix suffix counts as well right?
Yes, you are correct. Make s[i] the middle character and count possible subsequence.
thought of another dp solution
dp[index][last char 0/1][len], does it work? Although prefix and suffix would be easier and better and also this is a very standard problem.
yeah, i think it is correct
Can you provide soln for problem 3
At i'th position, if b[i-1] is greater than a[i], then we have exactly a[i] choices for b[i]. Otherwise, we must exclude b[i-1] because b[i]!=b[i-1], so we have a[i] — 1 choices in this case.
This is what came to my mind initially, but might have to improve the state a bit for efficient implementation.
what is your 3rd solution can u clarify
because the solution I am getting is if(ai>=ai-1) ans= prevsum*(ai — 1) else ans = ai*prev_sum — prev_sum(until ai) curr[x] = prev_sum — prev[x]
something like this relation which would take O(N*10^6); though I think some kind of range updates would work like in lazy segment tree converting prev[x] -> prev_sum — prev[x] which might then make it O(N*small const);
I dont think 3rd is easy , Here is the problem link
You can solve problem 3 using a Lazy Segment Tree. Let's define dp[i][j] as no of arrays you can form with first i elements, with j as the last element.
Now, dp[i][j] = (Σ(dp[i — 1][k])) — dp[i — 1][j], where 1 <= k <= a[i]. Here, you're basically calculating all such arrays that end with i — 1 elements, with the last element not being j.
Your segment tree should store dp[i][j]. At each transition, you take the range sum (let's call it VAL) for dp[i][k], 1<=k<=a[i], then negate each element in the range 1<=k<=a[i], then add VAL to each position in this range. you have your next transition.
NOT AN EASY PROBLEM AT ALL.
for 3rd can we do this D&C :
solving for i,j => find maxm elememt :
suppose it is at k
k == i => ans is (a[k]-1)*solve(i+1,j) k == j => ans is (a[k]-1)*solve(i,j-1)
else : (a[k]-2)*(ways to solve i,j neglecting element at k) + (a[k]-1)*(ways to solve i,j neglecting element at k , arg (max(a[i],a[j])) )
neglecting an element means forget it is there and element prev and next to it are assumed to be adjacent
my code got TLE'd anyone knows a good way to implement this?
or this brute force cant be optimised?