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.
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.
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
I guess you need to update the line
ReplyDelete>> In this case we can't place 5 in anyway so output 5.
to
>> In this case we can't place 5 in anyway so output -1.
Yes thanks for pointing out , updated.
DeleteExtremely well explained
ReplyDeleteThanks
Deletecool solution. thank you
ReplyDeletemost welcome
DeleteThis comment has been removed by a blog administrator.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteThis comment has been removed by the author.
DeleteAs we place previous blocks on consecutive blocks they all will have unique colors each of type from 1 to m - 1. now if we move block of length 5 behind it will remove one of the color which is wrong.And we have to keep length of 5 inside all the given blocks , so there is no way to place it , hence the answer is -1
ReplyDeletevector ans(m);
ReplyDeletefor(int i = 1;i <= m; ++i){
ans[i - 1] = i;
if((i + a[i - 1] - 1)> n){
cout << -1;
return 0;
}
}
I don"t understand this part of block. Please explain
There is one thing i don't understand how do we know that every i will be within the range [1,n-l[i]+1]; cause you have chosen consecutive blocks that can only happen when this condition holds true. so, please tell how do we ensure this
ReplyDeletenice explanation
ReplyDelete