This isn't my solution but it's an intuitive solution without obvious math like Lagrange or Cauchy Schwarz.
link
Wednesday, October 2, 2019
Sunday, August 11, 2019
Codeforces 1200D - White Lines Solution
Tags: prefix sums
The first thing you should think when you see this problem is prefix sums because it looks like this problem can be done in O(n*n).
1. Count the number of white lines there already are (like in WWW there's already 1 white line)
2. Create 2 arrays, a 2D horizontal prefix sum array and a 2D vertical prefix sum array.
3. For each horizontal line from the left then, if it's at most K places away from becoming a line horizontally, mark that position as 1.
Example 1:
BBB
WBB
BBB
If K = 2, the horizontal sum array (before you spread the sums to be a prefix sum array) would be
0 0 0
0 1 0
0 0 0
If K = 3, the horizontal sum array would be
1 1 1
1 0 0
1 0 0
4. For each vertical line from the top, if it's at most K places away from becoming a line vertically, mark that position as 1.
Example 2:
If K = 1, the vertical sum array would be
0 0 0
0 1 0
0 0 0
If K = 2, the vertical sum array would be
0 1 0
0 1 0
0 0 0
5. Then, you spread the sums. For the horizontal sum array, you spread the sums vertically and for the vertical you spread them horizontally.
Like the K = 2 array from Example 1, when you spread it vertically, it looks like this:
0 0 0
0 1 0
0 1 0
And for the K = 1 array from Example 2, you spread it like this:
0 0 0
0 1 1
0 0 0
You find out why we do it this way in step 6.
6. Iterate through all the cells where you can put the eraser (i = 1, 2, 3... N-K, j = i, 2, 3... N-K). From the horizontal sum array, get the vertical sum of the column j. Then from the vertical sum array, get the horizontal sum of the row i. These sums add to the number of lines because they are the number of lines that need at most K more cells to form lines. I think it's easier to understand in an example.
From example 2, we have
BWB
BBB
BWB
Let's say K = 2.
The vertical sum array will be
0 1 0
0 1 0
0 0 0
The horizontal sum array will be
0 0 0
0 0 0
0 0 0
Then, after we spread the sums, the vertical sum array will be
0 1 1
0 1 1
0 0 0
Then, we check every cell. If we check cell (0, 1), the sum we get is 1.
0 1 0 (getting the sum of 0+1 from the prefix array above)
0 1 0
0 0 0
Which is 1, and we can get this from the prefix sum array (the one above this array) by doing arr[0][2]-arr[0][0].
Another example:
BWB
WBW
BWB
K = 1
The vertical array will be
0 0 0
0 1 0
0 0 0
The horizontal array will be
0 0 0
0 1 0
0 0 0
Spreading the sums, the vertical array will be
0 0 0
0 1 1
0 0 0
The horizontal array will be
0 0 0
0 1 0
0 1 0
When we try (1, 1), the sum we get is in the bolded parts above (we only go 1 far since K = 1).
My submission: https://codeforces.com/contest/1200/submission/58621782
The first thing you should think when you see this problem is prefix sums because it looks like this problem can be done in O(n*n).
1. Count the number of white lines there already are (like in WWW there's already 1 white line)
2. Create 2 arrays, a 2D horizontal prefix sum array and a 2D vertical prefix sum array.
3. For each horizontal line from the left then, if it's at most K places away from becoming a line horizontally, mark that position as 1.
Example 1:
BBB
WBB
BBB
If K = 2, the horizontal sum array (before you spread the sums to be a prefix sum array) would be
0 0 0
0 1 0
0 0 0
If K = 3, the horizontal sum array would be
1 1 1
1 0 0
1 0 0
4. For each vertical line from the top, if it's at most K places away from becoming a line vertically, mark that position as 1.
Example 2:
If K = 1, the vertical sum array would be
0 0 0
0 1 0
0 0 0
If K = 2, the vertical sum array would be
0 1 0
0 1 0
0 0 0
5. Then, you spread the sums. For the horizontal sum array, you spread the sums vertically and for the vertical you spread them horizontally.
Like the K = 2 array from Example 1, when you spread it vertically, it looks like this:
0 0 0
0 1 0
0 1 0
And for the K = 1 array from Example 2, you spread it like this:
0 0 0
0 1 1
0 0 0
You find out why we do it this way in step 6.
6. Iterate through all the cells where you can put the eraser (i = 1, 2, 3... N-K, j = i, 2, 3... N-K). From the horizontal sum array, get the vertical sum of the column j. Then from the vertical sum array, get the horizontal sum of the row i. These sums add to the number of lines because they are the number of lines that need at most K more cells to form lines. I think it's easier to understand in an example.
From example 2, we have
BWB
BBB
BWB
Let's say K = 2.
The vertical sum array will be
0 1 0
0 1 0
0 0 0
The horizontal sum array will be
0 0 0
0 0 0
0 0 0
Then, after we spread the sums, the vertical sum array will be
0 1 1
0 1 1
0 0 0
Then, we check every cell. If we check cell (0, 1), the sum we get is 1.
0 1 0 (getting the sum of 0+1 from the prefix array above)
0 1 0
0 0 0
Which is 1, and we can get this from the prefix sum array (the one above this array) by doing arr[0][2]-arr[0][0].
Another example:
BWB
WBW
BWB
K = 1
The vertical array will be
0 0 0
0 1 0
0 0 0
The horizontal array will be
0 0 0
0 1 0
0 0 0
Spreading the sums, the vertical array will be
0 0 0
0 1 1
0 0 0
The horizontal array will be
0 0 0
0 1 0
0 1 0
When we try (1, 1), the sum we get is in the bolded parts above (we only go 1 far since K = 1).
My submission: https://codeforces.com/contest/1200/submission/58621782
Thursday, August 8, 2019
Codeforces 1202B - You Are Given a Decimal String Solution
Tags: brute force
The realization to this problem to make is that even though there can be up to 2*10^6 characters in the string, the number of combinations of 2 adjacent characters is 10*10 (00, 01, 02... all combinations). So then, for each of these combinations, you calculate the frequencies of each combination and keep that in an array.
Then, you iterate over every counter (0-0, 0-1, 0-2...) let's call them i and j, and then for each counter, iterate over all combinations of possible adjacent characters (00, 01, 02...), let's call the first one a and second one b (like in 01, a is 0 and b is 1). Use a BFS (breadth first search) to find the shortest path from a to b using the i-j counter, and make sure that if a == b, then the BFS doesn't end when you put a into the queue (because the BFS checks if the current node is equal to b). If it's not possible for the i-j counter to reach b, then the answer for this counter is -1. Otherwise, the answer is (the frequency of a and b next to each other in the string)*((shortest distance from a to b using i-j counter)-1), and this is added to the sum for this counter. There's a -1 for the distance from a to b because the distance still counts b, which is already in the string.
Example:
08408
For the frequencies:
08: 2
84: 1
40: 1
Then iterate over each counter:
Let's say, i = 0 j = 1 (counter 0-1)
Then iterate over each adjacent number combinations:
Let's say, a = 0 b = 8
Starting from 0, the minimum distance from 0 to 8 using a 0-1 counter is 8. Since 08's frequency is 2, we add 2*(8-1) to the 0-1 counter's sum.
My submission (I'm using links w/ ads, tell me if it doesn't work for you): http://stfly.io/uhWA3r
The realization to this problem to make is that even though there can be up to 2*10^6 characters in the string, the number of combinations of 2 adjacent characters is 10*10 (00, 01, 02... all combinations). So then, for each of these combinations, you calculate the frequencies of each combination and keep that in an array.
Then, you iterate over every counter (0-0, 0-1, 0-2...) let's call them i and j, and then for each counter, iterate over all combinations of possible adjacent characters (00, 01, 02...), let's call the first one a and second one b (like in 01, a is 0 and b is 1). Use a BFS (breadth first search) to find the shortest path from a to b using the i-j counter, and make sure that if a == b, then the BFS doesn't end when you put a into the queue (because the BFS checks if the current node is equal to b). If it's not possible for the i-j counter to reach b, then the answer for this counter is -1. Otherwise, the answer is (the frequency of a and b next to each other in the string)*((shortest distance from a to b using i-j counter)-1), and this is added to the sum for this counter. There's a -1 for the distance from a to b because the distance still counts b, which is already in the string.
Example:
08408
For the frequencies:
08: 2
84: 1
40: 1
Then iterate over each counter:
Let's say, i = 0 j = 1 (counter 0-1)
Then iterate over each adjacent number combinations:
Let's say, a = 0 b = 8
Starting from 0, the minimum distance from 0 to 8 using a 0-1 counter is 8. Since 08's frequency is 2, we add 2*(8-1) to the 0-1 counter's sum.
My submission (I'm using links w/ ads, tell me if it doesn't work for you): http://stfly.io/uhWA3r
Tuesday, August 6, 2019
Nature Logic Problem
Sometimes you see a spider web that spans from one place to another far place. For example, there's 2 trees next to each other and there's a string of spider silk 4 feet long between them. Assuming the spider can't jump/crawl from one tree to another, how does it get it's silk string to go from one tree to the other tree? (Look it up to see the answer)
Sunday, August 4, 2019
UVa 793 - Network Connections Solution
http://clesolea.com/1FHN
Tags: union-find
It's a union problem to see which networks are in the same set or not. My algorithm for unions involves the ranks and finding the parents, like here (where it says "by rank"): http://clesolea.com/1FLE
My solution: http://clesolea.com/1FFg
Tags: union-find
It's a union problem to see which networks are in the same set or not. My algorithm for unions involves the ranks and finding the parents, like here (where it says "by rank"): http://clesolea.com/1FLE
My solution: http://clesolea.com/1FFg
Codeforces 1201B - Zero Array Solution
http://clesolea.com/1EY8
Tags: observations, invariant theory (see more about this here)
I struggled with this but got it in the last couple minutes of the contest. First, I wrote down the requirements, which were that the sum had to be even and the greatest element is less than or equal to the rest of the sum (think about if it was n=2, 2 4). I couldn't go any further with this though so I tried some incorrect greedy things and gave up and did C. My mistake was looking too far into it (for a B problem) and doing some cases I created incorrectly (I thought n=4, 2 2 2 4 was impossible). I realized the answer when I correctly did the case I just mentioned (the n=4 one).
The answer is just to make sure the sum is divisible by 2 and the greatest element is less or equal to the rest of the sum of the array. You can just assume that this always works after doing some samples, or you can try proving it by performing some operations and seeing if the requirement of the greatest element not being greater than the sum of the rest still holds (idea from here).
Tags: observations, invariant theory (see more about this here)
I struggled with this but got it in the last couple minutes of the contest. First, I wrote down the requirements, which were that the sum had to be even and the greatest element is less than or equal to the rest of the sum (think about if it was n=2, 2 4). I couldn't go any further with this though so I tried some incorrect greedy things and gave up and did C. My mistake was looking too far into it (for a B problem) and doing some cases I created incorrectly (I thought n=4, 2 2 2 4 was impossible). I realized the answer when I correctly did the case I just mentioned (the n=4 one).
The answer is just to make sure the sum is divisible by 2 and the greatest element is less or equal to the rest of the sum of the array. You can just assume that this always works after doing some samples, or you can try proving it by performing some operations and seeing if the requirement of the greatest element not being greater than the sum of the rest still holds (idea from here).
Atcoder Beginner Contest 136 (ABC 136) D - Gathering Children Solution
After simulating the sample cases, the observation to make is that if there's a R and a L next to each other, it creates an infinite back and forth exchange of children. For example if the blocks are RL and there's 2 children on R and 1 child on L, on the next cycle there's 1 child on R and 2 children on L, and the next there's 2 children on R and 1 child on L.
For each RL you find, find the number of R's behind the R and L's ahead of the L in a row. For example, for RLRRRL, for each RL, look at RLRRRL and find 1 R, and then look at RLRRRL and find 3 R's. For each of these R's, they will end up at either the R or the L depending on what second it comes to the R. For example, in RRRL (1 1 1 1), in the first cycle, it goes to (0, 1, 2, 1). The child at the 3rd R went to L and the child at the 2nd R went to the 3rd R. This child that is currently at the 3rd R will go to L, then R, then L over and over, but we only care about the even cycle since 10^100 is even. Because of this, on an even cycle, it will be at L. Then, the child on the 1st R will be on the 3rd R on an even cycle.
Example:
RRRRRRL
On an even cycle, the child at the 6th (final) R will be on the 6th R. The child at the 5th R will be on the L. The child at the 4th R will be on the 6th R. The child at the 3rd R will be on the L. The child at the 2nd R will be on the 6th R and so on. The same thing happens to the children on the L's too if there's a string of L's ahead of the L.
My solution: http://stfly.io/Bqmwg27T8
For each RL you find, find the number of R's behind the R and L's ahead of the L in a row. For example, for RLRRRL, for each RL, look at RLRRRL and find 1 R, and then look at RLRRRL and find 3 R's. For each of these R's, they will end up at either the R or the L depending on what second it comes to the R. For example, in RRRL (1 1 1 1), in the first cycle, it goes to (0, 1, 2, 1). The child at the 3rd R went to L and the child at the 2nd R went to the 3rd R. This child that is currently at the 3rd R will go to L, then R, then L over and over, but we only care about the even cycle since 10^100 is even. Because of this, on an even cycle, it will be at L. Then, the child on the 1st R will be on the 3rd R on an even cycle.
Example:
RRRRRRL
On an even cycle, the child at the 6th (final) R will be on the 6th R. The child at the 5th R will be on the L. The child at the 4th R will be on the 6th R. The child at the 3rd R will be on the L. The child at the 2nd R will be on the 6th R and so on. The same thing happens to the children on the L's too if there's a string of L's ahead of the L.
My solution: http://stfly.io/Bqmwg27T8
Atcoder Beginner Contest 136 (ABC 136) C - Building Stairs Solution
Tags: greedy
Iterate from the last element and look at the current element and the one ahead of it, let's call them a and b. If a <= b, keep them the same. Otherwise if a > b, if a is too big to subtract 1 from to make it less than or equal to b, the answer is no. Otherwise, subtract 1 from a and move on to the next element, which is, again, one element down the list because we start from the end.
I didn't try it but I think another solution is to start from the beginning and subtract 1 from an element when the element behind it is less than it, so it minimizes the chance that there is a small element ahead of a big element.
My code: http://stfly.io/ArP9EpG
Iterate from the last element and look at the current element and the one ahead of it, let's call them a and b. If a <= b, keep them the same. Otherwise if a > b, if a is too big to subtract 1 from to make it less than or equal to b, the answer is no. Otherwise, subtract 1 from a and move on to the next element, which is, again, one element down the list because we start from the end.
I didn't try it but I think another solution is to start from the beginning and subtract 1 from an element when the element behind it is less than it, so it minimizes the chance that there is a small element ahead of a big element.
My code: http://stfly.io/ArP9EpG
Saturday, August 3, 2019
Atcoder Median of Medians Solution
http://tonancos.com/3noa
Tags: Inversion counting, binary search, median, prefix sums
Let's say x is the answer to the problem, you want to know how many intervals have a median below or equal to x. If you find how many
intervals have a median less than or equal to x, even though we don't know if x is the median for sure, the binary search helps choose the
greatest possible x. In the binary search we go up if the result is under the median of the intervals (n*(n+1)/2 divided by 2) and down if it's over
it. The answer is the highest x that's over or equal to the median of the intervals (the n*(n+1)/4 thing above).
Then there's the part where you check each interval to see if the median is below or equal to x. Like in the editorial, put 1's for values greater
than x and -1's for values less than x. Then take the prefix sums of this. Then, when you get the sum of an interval, if it's greater or equal to the
interval's median, the median is over x, else it's under x. Then, instead of computing each interval with brute force, you use inversion counting (count the number of unsorted pairs of numbers). This is because when you get the value for the interval, you want to know if the median is over or equal to x, so you only want to know how many intervals have a negative value.
My solution: http://tonancos.com/3nuN
Tags: Inversion counting, binary search, median, prefix sums
Let's say x is the answer to the problem, you want to know how many intervals have a median below or equal to x. If you find how many
intervals have a median less than or equal to x, even though we don't know if x is the median for sure, the binary search helps choose the
greatest possible x. In the binary search we go up if the result is under the median of the intervals (n*(n+1)/2 divided by 2) and down if it's over
it. The answer is the highest x that's over or equal to the median of the intervals (the n*(n+1)/4 thing above).
Then there's the part where you check each interval to see if the median is below or equal to x. Like in the editorial, put 1's for values greater
than x and -1's for values less than x. Then take the prefix sums of this. Then, when you get the sum of an interval, if it's greater or equal to the
interval's median, the median is over x, else it's under x. Then, instead of computing each interval with brute force, you use inversion counting (count the number of unsorted pairs of numbers). This is because when you get the value for the interval, you want to know if the median is over or equal to x, so you only want to know how many intervals have a negative value.
My solution: http://tonancos.com/3nuN
UVa 11572 - Unique Snowflakes Solution
http://tonancos.com/3nM1
Tags: greedy
First, you make a set and start from the beginning of the array. As you move up the array making a segment, insert the numbers into the set. If you find that there's a duplicate element in the segment (using the set), from the bottom, delete the elements before the number from the set so that there's no more duplicates in the segment. From all the lengths you compute during this process, get the maximum.
Example 1:
6
1 2 2 3 2 1
(i is the current index we're on)
i = 0:
add 1 to the set
set = {1}
i = 1
add 2 to the set
set = {1, 2}
i = 2
you already have 2 in the set, so delete the numbers up until the earliest 2
set = {2} (deleted 1)
i = 3
set = {2, 3}
i = 4
you already have 2 again, so delete the elements before the earliest 2, which is just 2
i = 5
set = {2, 3, 1}
---------------------------------------
Example 2:
6
1 2 3 4 5 5
i = 0
add 1 to the set
set = {1}
i = 1
set = {1, 2}
i = 2
set = {1, 2, 3}
i = 3
set = {1, 2, 3, 4}
i = 4
set = {1, 2, 3, 4, 5}
i = 5
we already have 5, so we'll delete all elements before last 5
set = {5}
Tags: greedy
First, you make a set and start from the beginning of the array. As you move up the array making a segment, insert the numbers into the set. If you find that there's a duplicate element in the segment (using the set), from the bottom, delete the elements before the number from the set so that there's no more duplicates in the segment. From all the lengths you compute during this process, get the maximum.
Example 1:
6
1 2 2 3 2 1
(i is the current index we're on)
i = 0:
add 1 to the set
set = {1}
i = 1
add 2 to the set
set = {1, 2}
i = 2
you already have 2 in the set, so delete the numbers up until the earliest 2
set = {2} (deleted 1)
i = 3
set = {2, 3}
i = 4
you already have 2 again, so delete the elements before the earliest 2, which is just 2
i = 5
set = {2, 3, 1}
---------------------------------------
Example 2:
6
1 2 3 4 5 5
i = 0
add 1 to the set
set = {1}
i = 1
set = {1, 2}
i = 2
set = {1, 2, 3}
i = 3
set = {1, 2, 3, 4}
i = 4
set = {1, 2, 3, 4, 5}
i = 5
we already have 5, so we'll delete all elements before last 5
set = {5}
Tuesday, June 18, 2019
LA (Live Archive) 2949: Elevator Stopping Plan - Solution
http://tonancos.com/3nHS
Tags: binary search, greedy
Solution:
First, we binary search the time it's going to take the person who takes the most time to get to their floor. Inside the binary search, we choose which floor to put the stops on greedily. The greedy part is wanting to put the stop as far from the beginning as we can so that it still covers floors it would take too long to walk to. I'm not so sure on why because it could just be intuitive, or that the less stops we make the better, so putting it further down lowers the amount of stops we need to use.
Example:
Input = 3 3 5 6
The answer to this is 32 (it takes 32 minutes) 2 4 6 (put the stops on floors 4 and 6). To get this, let's say in our binary search mid is 32. First we check if we can walk to any of the floors during this time, but we can't (if there was 2 in the input, we could walk to 2 since 32 is over 20). Then, let's say start = 3, we iterate floors to put the next stop on (3 (start), 4 (start+1), 5 (start+2)...) until the floor we iterate over is too far away from 3 (start) to walk to. This floor in this example is 5, because if we stop at 5, it would take 4*4+20*2 minutes to get from 5 to 3. Since we know 5 is too big, 4 must be the floor to put the stop on. To get from 4 to 3, it takes 32 minutes. After we put the floor on 4, we go on to see which floors above floor 4 can be reached in at most 32 minutes. 5 can be reached from 4 in 32 minutes, so we skip over 5 and don't put a stop there. After we reach the point where a floor can't be reached by 4, we take that floor and assign start to it, and repeat the part before this. You can just put a stop at the last floor (in this case 6) because it doesn't affect the time.
My code: http://tonancos.com/3nIN
Tags: binary search, greedy
Solution:
First, we binary search the time it's going to take the person who takes the most time to get to their floor. Inside the binary search, we choose which floor to put the stops on greedily. The greedy part is wanting to put the stop as far from the beginning as we can so that it still covers floors it would take too long to walk to. I'm not so sure on why because it could just be intuitive, or that the less stops we make the better, so putting it further down lowers the amount of stops we need to use.
Example:
Input = 3 3 5 6
The answer to this is 32 (it takes 32 minutes) 2 4 6 (put the stops on floors 4 and 6). To get this, let's say in our binary search mid is 32. First we check if we can walk to any of the floors during this time, but we can't (if there was 2 in the input, we could walk to 2 since 32 is over 20). Then, let's say start = 3, we iterate floors to put the next stop on (3 (start), 4 (start+1), 5 (start+2)...) until the floor we iterate over is too far away from 3 (start) to walk to. This floor in this example is 5, because if we stop at 5, it would take 4*4+20*2 minutes to get from 5 to 3. Since we know 5 is too big, 4 must be the floor to put the stop on. To get from 4 to 3, it takes 32 minutes. After we put the floor on 4, we go on to see which floors above floor 4 can be reached in at most 32 minutes. 5 can be reached from 4 in 32 minutes, so we skip over 5 and don't put a stop there. After we reach the point where a floor can't be reached by 4, we take that floor and assign start to it, and repeat the part before this. You can just put a stop at the last floor (in this case 6) because it doesn't affect the time.
My code: http://tonancos.com/3nIN
Subscribe to:
Posts (Atom)