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
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