Codeforces Round #631 (Div. 2) - Problem C

Problem link : https://codeforces.com/contest/1330/problem/C

So this problem is quite easy once we figure out the greedy.

The statement was made quite hard by using all sorts of variables.

Ok so first observation : We can color any consecutive l[i] blocks in ith move. Why ?

because we can start with 1 and go till n - l[i] + 1. So if we are on n - l[i] + 1 we can go till
n - l[i] + 1 + l[i] - 1 which is n.

Second Observation : If the sum of lengths of all blocks are smaller than n we can never fill up n blocks. Why ? Because even if we put them in non intersecting blocks they will never fill all n blocks so answer in this case will be -1.

As we see in above image even in best case we can't fill last block

Getting the order of painting : Now here the greedy is we should start coloring from consecutive blocks. Why ? Because if we don't we fill up the blocks faster and then chances of overlapping later increases. So we assign consecutive blocks as start of the i'th operation.

Now here if we can't place some block answer will be -1.

In this case we can't place 5 in anyway so output -1.

After we have placed the elements we have to make sure all blocks are colored. Also as sum >= n so we are sure we can color all the blocks.

So just start from the last block and pull it towards the end till the last l[n - 1] blocks are not covered.
Then go the block n - l[n - 1] - 1 and do the same for the last blocks from there.

This way we make sure we have atleast one block of each color and no block is empty.

Solution Link : https://codeforces.com/contest/1330/submission/75429806

Codeforces Round #631 (Div. 2) - Problem B

Problem Link : https://codeforces.com/contest/1330/problem/B

The problem is very easy to solve if you make some basic observations.

The main observation to solve this problem is you cannot take a contiguous segment which has repeated elements as it violates the property of permutation.

In the above figure it's impossible to go after 4 so it's no use checking.

Using this observation we try to make a contiguous array as long as we don't find a duplicate, because if we don't find a duplicate the current element either belongs to the permutation on the left side or the permutation on the right side. So after you get 2 arrays left and right , sort them and check if they form a permutation and if yes this is a valid case.

Now there can be two solutions as can be seen from pretest

5
1 4 3 2 1

So in the case above we have 2 valid solutions .

In first case will start forming a non repeating contiguous array from left and get 1 3 4 2 as left and 1 as right. 

In second case we will get 1 as left and 1 2 3 4 as right array.

So check from both the directions if you get 2 valid permutations and then output the result.

Do check that a[0] == 1 after you sort left and right array , as you can get 2 3 4 and 3 4 5 as 2 arrays and it will be a wrong solution.

Solution : https://codeforces.com/contest/1330/submission/75395895

Codeforces Round #630 (Div. 2) Problem C

Problem link : https://codeforces.com/contest/1332/problem/C

So the problem is basically constructive and involves observation.

Here we have 2 restrictions

1) The string should be a palindrome

2) s[i] == s[i + k]

Let's make some observations using 2nd condition

as s[i] == s[i + k] , this basically means there will be same blocks of size k repeated n/k times.
Also n is divisible by k so there is no problem.

See this in the figure above.

But now see how we violate the first condition of palindrome.

s[i] should be equal to s[n - i].

If you think about it a bit you will find out that the small block k should itself be a palindrome !!

This is the main observation, after this it's easy to solve.

So basically the palindrome positions of the smaller block of size k = 3 should be fixed and rest of the blocks should also have same value.

So we are in a way restricted to keep values of i = j,j + k,j + 2*k, ... for all j = 0 to k -1 same and make the small block as palindrome.

So greedy intuition says don't replace the letter which has occurred most in some position and change others to this letter. So you accumulate all the letters into one block of size k and then accumulate for positions s[i] and s[k - 1 - i] in this block and then choose the letter which has occurred the most.

Submission Link : https://codeforces.com/contest/1332/submission/75153656

Codeforces Round #630 (Div. 2) Problem D

Link to the Problem : https://codeforces.com/contest/1332/problem/D

So basically it's a constructive problem.

First Step to realize is that how dp solution is not optimal.

Let's see using an example

I will be using 1 based indexing

In the figure above we see if we move from cell (1,1) to (2,2) then going from (1,1) -> (1,2) -> (2,2) is optimal according to the dp which results is (1 1 0) for block (2,2) . But for block (3,3) we will also use this path only according to dp because it was the optimal path before but that leads to wrong answer. Why? Because if we choose path from (1,1) -> (2,1) -> (2,2) -> (3,3) we will get better answer(1 0 1) than using the dp path(1 0 0).

So only time we want to drop some non optimal path that will be when non_optimal&optimal = non_optimal which basically means that non_optimal always have subset bits set compared to optimal and will never produce a better answer later on.

After this realization it's just implementation.

So we would like to choose a number which dosen't interfere with other bits in the answer and is also < 3 * 1e5 which is the constraint for any given cell . 2^17 seems to be a good number as it's less than 3* 1e5 and also more than 1e5 so it won't interfere with the k.

From the 2nd figure above we can see how arranging elements will produce an error of exactly k.
Answer according to the path of dp will be 0 and optimal path will give result k. So difference is exactly k.

Submission Link : https://codeforces.com/contest/1332/submission/75186543