Open Cup 2017-18 Grand Prix of America wrapped up that week (results, top 5 on the left, parallel round results), with another two World Finals favorites in top 5: SPb ITMO 1 and Moscow SU Red Panda. The first place, however, went to team Past Glory — once again thanks to their incredible accuracy. Congratulations!
Problem K in this round was quite educational, if a bit professional. You are given n points p1, p2, ..., pn on the plane and q queries (n, q <= 100000). Each query is defined by two numbers a, b, and you need to print the size of the smallest square with sides parallel to coordinate axes that contains all points from a-th to b-th (from the list pa, pa+1, ..., pb) except maybe one. Can you dissect this problem into standard pieces?
In my previous summary, I have mentioned a Yandex.Algorithm problem: you are given a string s with 100000 characters, each a, b or c. You must swap exactly two distinct letters to obtain a new string t. How many ways are there to do that in such a way that the string t is good? In this problem we define a good string somewhat similarly to a valid parentheses sequence: empty string is good, if a string u is good then the strings aua, bub, cuc are good as well, and if two strings u and v are good, then their concatenation uv is also good.
The key insight in this problem is to learn to check if a string is good easily. Let's pick a group and 3 elements of order 2 in it: aa=1, bb=1, cc=1. We will then map each string to the product of the corresponding elements of the group. We can see that any good string will map to 1. Moreover, if our group is general enough, in other words does not have any other non-derived products that are equal to 1 (or if such products are simply unlikely to be equal to 1), then the opposite is also true: when a string maps to 1, it is good. As an example group that works in this problem we can use the group of movements of 3D space that keep the origin fixed, where a, b and c correspond to reflections through three random planes passing through origin. This way, we obtain a compressed representation for a string of any length as a single 3x3 matrix (modulo some prime number, to avoid dealing with floating point).
We can then use the divide-and-conquer approach: we start by splitting our string in two in the middle, and consider the case where the two positions being swapped are in different halves. If we also try all 6 possibilities for the letters being swapped, we have a sub-problem of the following kind: we have two strings, and need to replace a single a with b in the first string, and a single b with a in the second string, so that after doing those replacements and concatenating the strings we get a good one.
We can compute the compressed representation of each candidate for the first half using prefix and suffix products, then compute the compressed representation of each candidate for the second half in the same way, and then for each representation of first half find its inverse element in the second half, thus processing the case where the swapped elements are in different halves in O(n).
In order to handle the case where both swapped elements are in the same half, we follow the divide-and-conquer approach and recursively execute the same algorithm for each half, with the only difference that the target product in each half we want to get is not 1, but rather the inverse of the product of the other half. This allows to complete the solution of the entire problem in O(n*log(n)).
Thanks for reading, and check back soon!
Problem K in this round was quite educational, if a bit professional. You are given n points p1, p2, ..., pn on the plane and q queries (n, q <= 100000). Each query is defined by two numbers a, b, and you need to print the size of the smallest square with sides parallel to coordinate axes that contains all points from a-th to b-th (from the list pa, pa+1, ..., pb) except maybe one. Can you dissect this problem into standard pieces?
The key insight in this problem is to learn to check if a string is good easily. Let's pick a group and 3 elements of order 2 in it: aa=1, bb=1, cc=1. We will then map each string to the product of the corresponding elements of the group. We can see that any good string will map to 1. Moreover, if our group is general enough, in other words does not have any other non-derived products that are equal to 1 (or if such products are simply unlikely to be equal to 1), then the opposite is also true: when a string maps to 1, it is good. As an example group that works in this problem we can use the group of movements of 3D space that keep the origin fixed, where a, b and c correspond to reflections through three random planes passing through origin. This way, we obtain a compressed representation for a string of any length as a single 3x3 matrix (modulo some prime number, to avoid dealing with floating point).
We can then use the divide-and-conquer approach: we start by splitting our string in two in the middle, and consider the case where the two positions being swapped are in different halves. If we also try all 6 possibilities for the letters being swapped, we have a sub-problem of the following kind: we have two strings, and need to replace a single a with b in the first string, and a single b with a in the second string, so that after doing those replacements and concatenating the strings we get a good one.
We can compute the compressed representation of each candidate for the first half using prefix and suffix products, then compute the compressed representation of each candidate for the second half in the same way, and then for each representation of first half find its inverse element in the second half, thus processing the case where the swapped elements are in different halves in O(n).
In order to handle the case where both swapped elements are in the same half, we follow the divide-and-conquer approach and recursively execute the same algorithm for each half, with the only difference that the target product in each half we want to get is not 1, but rather the inverse of the product of the other half. This allows to complete the solution of the entire problem in O(n*log(n)).
Thanks for reading, and check back soon!
No comments:
Post a Comment