The problem Hills states that we have to build k houses where each house must be strictly greater than its neighbours.

Here is one accepted solution.

I am not able to get transitions. if dp[x][y][z] denotes minimum cost to build y houses upto index x, and z tells whether we are going to build house on index x or not.

Now if z == 0, it means we are not gonna build house at current index x.

	if (z==0)
	{
		int cost=0;
		if (a[x-1]>=a[x]) cost+=(a[x-1]-a[x]+1);
		if (a[x+1]>=a[x]) cost+=(a[x+1]-a[x]+1);
		dp[x][y][z]=min(caldp(x+1,y,0),caldp(x+2,y-1,1)+cost);
	}

Then according to above transition.My doubt is, why are we calculating caldp(x+2,y-1,1). since it means that we made a house at index x with some cost and can't build at index x+1 and recurring for x+2. But z = 0 means we are not building any house at index x.

&&&

	if(z!=0)
	{
		int cost=0;
		if (min(a[x-2]-1,a[x-1])>=a[x]) cost+=(min(a[x-2]-1,a[x-1])-a[x]+1);
		if (a[x+1]>=a[x]) cost+=(a[x+1]-a[x]+1);
		dp[x][y][z]=min(caldp(x+1,y,0),caldp(x+2,y-1,1)+cost);
	}
	

And if z != 0, it means we are gonna build house at index x, why the cost will not be only (a[x-1]-a[x]+1) + (a[x+1]-a[x]+1). Why in the above equation there is a comparision between min(a[x-2]-1,a[x-1] >= a[x]). again my doubt is if we build a house at index at then we have to lower hills of index x-1 and x+1, why we are taking index x-2 in consideration.

Please help. Stuck in this problem since 2 days, trying to understand, but not getting clear picture. Thanks.

What are some good problems involving xor techniques and concepts, on codeforces or any other site. difficulty range <=2300.

Thanks.

Is there a way to contribute to cp algorithms like add code, modify etc. , or are they reserved for their own authors.

How LGM like tourist, Um_Nik, Petr, dotorya, ACRUSH , rng58 etc. are able to come up with such complex ideas which are required to solve div 1 e or atcoder grand contest last 2 problems which are almost unsolvable. From where they learn these hard tricks,methods and maths(imo level). Like tourist submits first 3 problems of div1 within 10 minutes.

Moreover, if you see problems from google code jam finals, distributed code jam they required very deep observation and intution, How they reach the correct observation and solution everytime.

Given an array of size n consisting of n-1 distinct elements.In other words there is exactly one element that is repeated.It is given that the element that would repeat would be either the maximum element or the minimum element. Find the number of structurally different max heaps possible using all the n elements of the array that is max heap of size n.

Let us take an example with array array elements as

1 5 5

The possible max heaps using the given elements are:- First: 5 on the root. 1 as the left child of root and 5 as the right child of the root

5

/ \

1 5

Second: 5 on the root. 5 as the left child of root and 1 as the right child of the root.

5

/ \

5 1

second example : N = 6, 1 1 2 3 4 5 ans = 11.

N = 5 , 1 1 2 3 4 ans = 4 N can be upto 1000.

when integers are all different T[N] = (n-1)C(left) * T[L] *T[R] , but what will be the recusion in this case.

You are given a strings of 0 and 1's. Now the task is to make the string consisting of only 1's. But you are allowed to perform only the following operation:

Take exactly k consecutive elements of string and change 1 to 0 and 0 to 1. Each operation takes 1 unit time so you have to determine the minimum time required to make the string of 1's only. If not possible return -1.

2 ≤ length of S ≤ 1000

Examples

Input

S = 00010110 k = 3

Output

3

Explanation

You can get 1 by first changing the leftmost 3 elements, getting to 11110110, then the rightmost 3, getting to 11110001, and finally the 3 left out 0's to 11111111; In 3 unit time.

Any approaches for it.

Hello, can someone provide me good tutorials on 2d segment tree and 2d fenwick tree, from where he/she studied. Thanks !

Can anyone please give me some good tutorials on interval trees. I know ST and FW. At todays Kickstart round when i saw the problem analysis of 3 it mentioned interval trees. but i dont know IT. can any one please give the source from where he studied IT. Thanks.

Hello, my binary search approach for problem e is , suppose we had played x-1 round and currently at round x , we will check whether we can kill monter in that round x or not , if yes we shift high to curr round — 1 else low to curr round + 1 .

my low range query is = 2 , since i alredy checked for round 1 , trivially . and high range r = (h / abs(sum) ) +1. where sum is my vector sum .

But the approach is continuously giving WA at tc : 92 .

https://mirror.codeforces.com/contest/1141/submission/51547489

where my approach is wrong .

in the problem sugarel and love , how to choose two sons such that we can maximize

DP[i][1]={max(DP[j][0]+v[i][j]+DP[t][0]+v[i][t])∣ where j and t are sons of i}. For all other sons, we add max(DP[j][0],DP[j][1],DP[j][2]) as given in editorial

since there can be nC2 choices time complexity would be O(n2) , how to do it in O(n) time .

i think we cant choose first two sums which gives max(DP[j][0]+v[i][j]+DP[t][0]+v[i][t]) as it will not always optimal .

any idea.