and like these problems

I thought this problem in this way: You have N numbers (a_i = {0,1}), find the maximum consecutive sum (only whit ones) if you can convert at most K zeros into ones. ?

It can be solved using two pointers. Now you can repeat this algorithm for each letter. I hope it helps you.. (Sorry for my poor english)

I'll explain C using the example: "abbaa" , k = 1

First, find out how many consecutive a's are possible in "abbaa" if we can swap no more than one 'b':

We're going to have "pointerLeft" and "pointerRight" describing the substring we're looking at during the execution. Both pointers start from -1.

pointerRight++ 
-> "a" possible
pointerRight++;
-> "ab" possible by swapping 1 b
pointerRight++;
-> "abb" not possible, we cant swap 2 b's
pointerLeft++;
-> "bb" not possible
pointerLeft++;
-> "b" possible by swapping 1 b
pointerRight++;
-> "ba" possible by swapping 1 b
pointerRight++;
-> "baa" possible by swapping 1b, also the longest possible substring so far

We have now looked into all relevant substrings of consecutive a's. Next we would do the same thing for consecutive b's.

Pick one of the alphabet (a or b in this problem) and do the following: - Consider every character other than the picked character as a bad character. You need to find the maximum subarray that contains at most k bad characters because we can replace them with the picked character. Finding Maximum subarray with at most k bad characters can be computed with two pointers

Check this submission

Me too, but I can give you alternative solution. Lets do binary search for answer — can we get "good" substring with such length. Left = 1, right = n + 1. In search we will look all substrings with middle = (left + right) / 2 length. At first we look at s[0:m — 1] and count "a" and "b" on it. Then we look at s[1:m] and so on, recounting "a" and "b". If we have min("a", "b") <= k at any moment, return true. Else return false. Answer is Left. O(n * log(n)). http://mirror.codeforces.com/contest/676/submission/18085847

algo:

1. record the positions of the characters in different vectors( resizeable array). suppose,vector A for char 'a' and vector B for char 'b'.

2. base case: if the size of A or B vector <= K then answer is n

3. i) loop with k' th index of array A till the end of A and question one thing, " what is the maximum size if we change the previous k 'a' characters?"

ii)then, " what is the maximum size if we change the last k 'a' characters?"

Do 3 for array B also.

Maximum size is the answer.

C++ solution:18097109

You've to change k no. of same characters to optimise the substring length. Now suppose I take an array and assign 1 to the indices where character a occurs in the string and 0 where b occurs. Here marking the index as 1 implies we've changed an 'a' to 'b' .Now take the prefix sum of an array(array is a[]) . Considering two indices i and j (j >= i) , (a[j] — a[i-1]) represents the no. of characters changed for a substring starting from i and ending at j. so for every index i from 0 to n-1 find the upper_bound j such that a[j]-a[i-1] = k and the length of the string becomes j-i+1. Do this for all the b's also and take the max at each step.

Hope it helps!

I like to think about two pointers this way:

Without the time limit, we could solve the problem by testing each of the n possible solutions, each one starting from each position of the string. This would give us O(n^2) complexity with the naive approach.

However, we can find the solution for a given position with the solution of the position before. How? Well, the first difference between the two solutions is the first characters. By removing it from the first solution it relaxes the constrictions of the second. It is obvious that every character of the first solution will also be present in the second. That means that, after removing the initial character, we just need keep inserting the following until it breaks the condition.

We can implement this solution with two pointers, one for the beginning and one for the end of the string. Note that each one of them will only increase, moving to next position, never regressing. This gives us O(n) complexity.

You can swap 1 and 3.

You have to check if f(k) = 0. First consider a0: it must be divisible by k otherwise f(k) != 0 because all the other terms are multiples of k. So you can add a0/k to a1. Now consider a1: it must be divisible by k otherwise f(k) != 0 because all other terms are multiples of k. So you can add a1/k to a2... and so on. Finally when only a_n is left, check that it is equal to 0.

Code: 18087228

Let the answer mod a large prime. If it is hacked, mod more primes.

I used integers in range [2e9, 2e9 + 200) as mod, and got accepted ;)

18092407

You have to check if f(k) = 0 as mentioned. However, f(k) may be very large and thus cannot be stored. I used a slightly different approach to calculating f(k).

ll done = a[n];
for(i = n - 1; i >= 0; i--) {
  if(abs(done) > 10000000000LL) {
    break;
  }
  done = a[i] + (k * done);
}

Finally, check if done is zero. The comparison with 10000000000LL works because of the following. When i = 0, abs(done) must be less than 10^4, since the problem specifies that abs(a[0]) < 10^4 and their sum must be zero. Now, when i = 1, abs(done) must be < 2 * 10^4, since abs(a[1]) < 10^4. Continuing so on, abs(a[n]) < 10^5 * 10^4 if n = 10^5.

One way to do it is the following: Notice that you can calculate the value of the polynomial as follows:

x_n = a_nk

x_n - 1 = (x_n + a_n - 1)k

...

x₁ = (x₂ + a₁)k

The value is then x₁ + a₀. Now notice that if any of the x_i is too big in absolute value, then x_i - 1 = (x_i + a_i - 1)k will also be too big and so on. Thus then k cannot be a root in this case. If none of the intermediate results are too big, all of them will fit in a 64-bit integer and we can just check whether we get zero in the end.

The precise condition for 'too big' can be found to be the following:

Note: here I've considered only the case when |k| ≥ 2. When |k| ≤ 1, things are trivial.

I replied to comment under, I explained "my" solution (actually I took idea, but I coded it later xD)..So if you are interested go and see..

I had problems with understanding it, but I solved it after looking some other codes.. Here is my solution; Make array 10 x 10 and let array[0][0] be the top Glass. Give it value 2048 * (t -1) Now you ask: Why the hell 2048 * (t-1)?! Because you dont want to play with doubles,to every "child glass" you will add half of vine from its parents, so when you do operation /2, you dont want to lose precision, thats why you put 2048 ( 2048 = 2 ^ 10, you will always get integer). Then, array[1][0] is child with only one parent, array[0][0], so you set array[1][0] = array[0][0] /2 -2048 ( you substract 2048 because you save values which will be added to childs). Also, array[1][1] has same one parent so you will do same.. So you just go through matrix and fill needed cells by adding half of parents values to childs! If child is array[x][y] then there are two cases; 1. It can have only one parent ( if x == 0 or y == x, or by words if it is most left or most right glass in row) 2. It can have two parents — all other cells.. Also, if you get negative value in child, that means it wont be filled, so when you go through matrix you just ++counter when cell is >=0..

I hope I explained well, But I dont think so xD

Here is a way to solve it. It doesn't involve doubles.

Let's say our current glass is located at row i and col j.

Obviously if a glass ever gets full then it will add water to the two corresponding glasses below it:

glasses located at (i+1,j) and (i+1,j+1)

Now for each time we water a glass, we can simulate the process by watering to the top glass, and then the ones below it and so on.

However, there is a problem, we need to know when a glass is full, so we can push water to the level below it. ( It can easily be done by a recursive code).

If you trace it with the pen and paper for few samples, you can find that a glass is full when it is watered ( 2^(lvl) ) times. (The lvl is zero based ).

So basically you need to maintain a 2D array, where arr[i][j] corresponds to how many times the cell located at arr[i][j] was watered.

Set counter to 0.

When you are watering a cell, if after watering it becomes full, increment the counter.

If it doesn't get full, do nothing.

If it is full before you water it, then water glasses below it. (i+1,j+1) and (i+1,j).

Again, the formula of 2^lvl gets very clear why it works if you trace it with a pen and paper.

Sample Code : http://mirror.codeforces.com/contest/676/submission/18082377

Monotonicity, i.e., right pointer increment increases the function value and left pointer increment decreases the function value.

You can easily prove the two pointer technique in monotonic function works with contradiction.

• • oh, problem solved, I've forgot the coff can be real...

I think use queue to simulate the pouring operation is a good way. to avoid floating number, I use the 2^10 as the whole glass. My Submission

One for each rotation

Each rotation is new level-every element changes(except '+' and '*'). So you need to make 3d array: matr[k][i][j], where k is current level(0<=k<=3)- there are 4 levels.And then you need to fill all array levels with changed elements('>' --> 'v', for example). Finally, just use bfs, where you can go to upper level or to closest neighbour cell(check if you can go there)

At a glance, try if changing variable types of stx,sty,edy,edx to int works.

you can solve it using Dijkstra on a 3D distance array this is my solution :

https://mirror.codeforces.com/contest/676/submission/55204169

I think editorial's solution is not the only solution there. I just used brute force approach to solve it.

89604997