Computer Science Canada DWITE Round #1 Solutions/Analyses

Author:  A.J [ Fri Oct 28, 2011 11:23 pm ]
Post subject:  DWITE Round #1 Solutions/Analyses

 code: Welcome back to DWITE everyone. First of all, I would like to welcome Cyril onto our DWITE dev team (thanks for helping us out. Hopefully you don't get too bored :P). This round went fairly well. There was a small issue regarding #5 we forgot to clarify that words like 'Tat' aren't palindromes due to 'T' not being equal to 't'. Also, as always, feel free to comment on the difficulty/style/etc... of the contest, and to talk about your own solutions as well. Analyses: #1) This was a fairly straight forward question involving reversing a string. One should be careful of cases where digits are concatenated to other letters (like '123cba'), as here the digits do get reversed as they are part of a word and don't represent a number. #2) Since we are given that it is always possible to divide the N stacks into stacks of equal sizes, first determine what the final number of each stack will be. Let c_1, c_2, ..., c_N denote the number of coins in the N stacks, and let f denote the number of coins in a stack after all the moves have been made. Then f = (c_1 + c_2 + ... + c_N) / N, and this is always a whole number. Finally, we then count how many coins should be moved to, or from, each stack to get f coins eventually: abs(f - c_1) + abs(f - c_2) + ... + abs(f - c_N). However, this double counts the number of moves being made, as each coin that is being moved is accounted for once for the pile its been moved from and once for the pile its been moved to. Thus, we divide the value by 2 to get our required number of moves: [ abs(f - c_1) + abs(f - c_2) + ... + abs(f - c_N) ] / 2 #3) Hopefully you guys had as much fun with this problem as I did writing it up. Consider the following sub-problem: Given a line segment AB, with A(ax, ay) and B(bx, by), and a point C(cx, cy), what is the shortest distance from C to AB? If you can answer this, then all you have to do is go through the path Billy takes a line segment at a time, storing the minimum distance from the candystore to each of the segments as you go. Consider the following:                                l1       l2                           |   |        |                        (1) C |   |        | (2) C                          \|   | (3) C  |    /                           \   |        |   /                           |\  |        |  /                           | \ |        | /                           |  \|        |/         ----------------------A--------B-------                           |                           |                           |                           |                           |                           | There are 3 cases (as shown above): 1) angle CAB is obtuse (i.e. > 90 degrees) in which case CA is the shortest distance from C to AB 2) angle CBA is obtuse (i.e. > 90 degrees) in which case CB is the shortest distance from C to AB 3) C is between the two lines drawn perpendicular to AB and through A and B respectively (i.e. l1 and l2). This case is the one that requires a bit of math. Consider the following diagram of case 3:                                                                   |                                        |                                      |        C        C'                           |       /--------/                           |      /        /                           |     /        /                           |    /        /         ----------------------A--------B-------                           |                           |                           |                           |                           |                           | Create a parallelogram through A, B and C, with base AB, by drawing a line through C that's parallel to AB (let's call the 4th corner C'). Then notice that the shortest distance from C to AB is the height of the parallelogram ABCC'. Since we know that the area of a parallelogram is base*height, thus we get that:    (Shortest distance from C to AB) * (Base of ABCC') = Area of ABCC' <=> Shortest distance from C to AB = (Area of ABCC')/AB (since AB is the base of ABCC') The area of ABCC' can be computed by taking the cross product of the vectors CA and AB, or in other words: Area ABCC' = |(bx - ax)*(ay - cy) - (ax - cx)*(by - ay)| Thus for case 3), the shortest distance from C to AB is: |(bx - ax)*(ay - cy) - (ax - cx)*(by - ay)|       |(bx - ax)*(ay - cy) - (ax - cx)*(by - ay)| -------------------------------------------   =   -------------------------------------------                    AB                                    sqrt((by - ay)^2 + (bx - ax)^2) #4) I would like to apologize to the teams who were seeking for a 'non-bruteforce' solution and didn't end up solving it. I realized that the testcases were so small that bruteforce would have worked, so I apologize for that (this question was intended to be a lot harder than that). So I'll illustrate the non-bruteforce solution here. Let n_{d}, n_{d-1}, ..., n_0 be the decimal digits of the input n from left to right (that is n = n_{d}*10^d + ... + n_0 * 10^0). The general idea is that we are going to count the number of times each of these digits were a 0 when counting from 0 to n. Let z(x) denote the number of times the xth digit was a 0 when counting from 0 to n. If the n_{x} (i.e. the xth digit of n) is not a 0, then z(x) = 10^x*a, where a is the number formed by taking the digits from n_{d}, n_{d-1}, ..., n_{x+1} (i.e. the number formed by removing the last x digits of n). And if n_{x} = 0, then z(x) = 10^x*(a-1) + b + 1, where a is as defined before, and b is the number formed by taking only the last x digits of n. You then add up all these counts, and then add 1 to account for the number 0, to get the total number of times your digits turned to a 0 when counting from 0 to n: z(0) + z(1) + ... + z(d) + 1. I know that this is confusing, so here's an example to illustrate this idea: Lets take n = 2034. We know count how many times each of the digits was a 0 when counting from 0 to n: z(0) (or unit's digit): The number of times the unit's digit was 0 is 10^0 * 203 = 203. The unit's digit is a 0 at 10, 20, 30, 40, ..., 2020, 2030 (so you notice that this is like counting from 1 to 203 ignoring the unit's digit). z(1) (or ten's digit): The number of times the ten's digit was 0 is 10^1 * 20 = 200. The ten's digit is a 0 10 times (100, 200, 300, ..., 1900, 2000), and for each of these times, the unit's digit can be anything from 0 to 9 (that's where the 10^1 part of the equation comes from). z(2) (or hundred's digit): Now, since the hundred's digit is a 0, we get that it was 0 10^2*(2 - 1) + 34 + 1 = 135 times. First we count the number of times the hundred's digit was a 0 with a first digit of < 2 (and this is just 10^2 * (2 - 1) = 100, which are 1000, 1001, 1002, 1003, ..., 1099), and then we count the number of times the hundred's digit was a 0 with first digit 2 (this is only 34 + 1, the + 1 is to account for 2000, whereas the others are 2001, 2002, ..., 2034). z(3) (the thousand's digit): This is just 10^3*(0) = 0. This makes sense as the most significant digit could never have been a 0. Thus when counting from 0 to 2034, the number of 0's you encounter is = z(0) + z(1) + z(2) + z(3) = 203 + 200 + 135 + 0 + 1 = 538 + 1 = 539 This is runs pretty quickly, as its time complexity is O(n*d), where d is average number of digits of the numbers from 0 up to n. #5) There are two ways you can solve this question. One solution is to take the longest common subsequence (http://en.wikipedia.org/wiki/Longest_common_subsequence_problem) of the given word and its reverse. The other solution is to try answering a subproblem instead: What is the longest palindrome you can form by removing any number of letters from the word formed by taking everthing from the i th letter to the j th letter of the given word? Let longest[i][j] denote this value. We'll now break this up into cases: 1) i = j 2) i th letter of the given word = j th letter of the given word 3) i th letter of the given word  != j th letter of the given word Case #1: In this case we are dealing with a one lettered word, and clearly longest[i][j] = 1 (as any one lettered is a palindrome, we don't have to remove anything to form a palindrome). Case #2: If this is the case, then we know for certain that the longest palindrome starts with the i th letter and ends with the j th letter. Thus the problem boils down to finding the length of the longest palindrome you can form by removing any number of letters from the word formed by taking everthing from the (i+1) th letter to the (j-1) th letter of the given word (i.e. longest[i+1][j-1]). Thus in this case longest[i][j] = longest[i+1][j-1] + 2 (the '+ 2' is two account for the fact that the longest palindrome starts with the i th letter and ends with the j th letter, as they are equal) Case #3: If this is the case, then either the longest palindrome is formed by some letters from the (i+1) th letter to the j th letter, or by some letters from the i th letter to the (j-1) th letter. Since we want the longest palindrome, we'll take the maximum of these two values. Therefore, in this case longest[i][j] = max(longest[i+1][j], longest[i][j-1]) However, we aren't done yet. Adding all these recurrences together and creating a naive recursive function will time out (as each pair of starting and ending letters (i, j) is visited many times by the function). Thus a fix to this is storing the longest[i][j] in a 2D array and either working bottom up (i.e. dynamic programming), or creating a recursive function that makes sure not to visit a pair of starting and ending letters (i, j) more than once (i.e. recursion with memoization). The time complexity of this program is O(n^2), where n is the length of the given word. I would like to stress that these are few of the many possible solutions that would work for this problem set. Feel free to try coding up some of these problems, the testcases are available at dwite.org. I hoped you all enjoyed the contest.

 Author: Cyril [ Sat Oct 29, 2011 12:37 am ] Post subject: Re: DWITE Round #1 Solutions/Analyses #4 can be done in logarithmic time. Let f(n) be the total coolness of all integers between 1 and n inclusive. (Then, our answer is just f(n) + 1.) Let's answer this question: how do we express f(123405) in terms of f(12340)? We should try all possibilities for the last digit. Consider all numbers with last digit 0. There are 12340 of these numbers, so each contributes their last digit 0. How about the zeros from these numbers that occur in the middle? Notice that to complete the rest of the number, we can just count from 1 to 12340; we simply count the zeros in that range. So, this case contributes 12340 + f(12340) to our total. Now, consider all numbers with last digit from 1 to 5. We get a similar case, but this time there are no zeros at the end. For each of these cases, we add f(12340). Finally, consider all numbers with last digit from 6 to 9. This is not the same as the previous case, because we don't want to include numbers greater than 123405, like 123408. We can exclude these by using f(12339) instead of f(12340). So, in general: f(n) = (let n' = floor(n/10), d = n%10) sum i = 0 to 9 { n' + f(n'), if i = 0 f(n'), if 1 <= i <= d f(n' - 1), if i > d } Or, if you want to feel like a hacker: long long f(long long n){ return n<10 ? 0 : n/10 + (1+n%10)*f(n/10) + (9-n%10)*f(n/10 - 1); } So we really should have imposed the restriction n <= 10^10000!

 Author: d310 [ Sat Oct 29, 2011 10:40 am ] Post subject: Re: DWITE Round #1 Solutions/Analyses A.J @ Fri Oct 28, 2011 11:23 pm wrote: There are 3 cases (as shown above): 1) angle CAB is obtuse (i.e. > 90 degrees) in which case CA is the shortest distance from C to AB 2) angle CBA is obtuse (i.e. > 90 degrees) in which case CB is the shortest distance from C to AB 3) C is between the two lines drawn perpendicular to AB and through A and B respectively (i.e. l1 and l2). This case is the one that requires a bit of math. I think you mean: 1) angle CAB is obtuse (i.e. > 90 degrees) in which case CA is the shortest distance from C to A 2) angle CBA is obtuse (i.e. > 90 degrees) in which case CB is the shortest distance from C to B And don't forget that there may be only one point, so just calculate the distance from C to all points first when inputting the points. Then check for each pair of points if C can create a perpendicular bisector between AB. Still a great contest!

 Author: Yves [ Sat Oct 29, 2011 2:03 pm ] Post subject: Re: DWITE Round #1 Solutions/Analyses d310 @ Sat Oct 29, 2011 10:40 am wrote:A.J @ Fri Oct 28, 2011 11:23 pm wrote: There are 3 cases (as shown above): 1) angle CAB is obtuse (i.e. > 90 degrees) in which case CA is the shortest distance from C to AB 2) angle CBA is obtuse (i.e. > 90 degrees) in which case CB is the shortest distance from C to AB 3) C is between the two lines drawn perpendicular to AB and through A and B respectively (i.e. l1 and l2). This case is the one that requires a bit of math. I think you mean: 1) angle CAB is obtuse (i.e. > 90 degrees) in which case CA is the shortest distance from C to A 2) angle CBA is obtuse (i.e. > 90 degrees) in which case CB is the shortest distance from C to B No, C to AB is correct; the length of the line CA is the shortest distance from point C to line segment AB when CAB is obtuse.

 Author: A.J [ Sun Oct 30, 2011 12:09 am ] Post subject: RE:DWITE Round #1 Solutions/Analyses Wow, I didn't see the logarithmic solution for #4. Well done Cyril!

 Author: ihsh [ Tue Nov 01, 2011 9:25 pm ] Post subject: RE:DWITE Round #1 Solutions/Analyses Hmm, I have a question about #3: how would you see if angles CAB or CBA are obtuse? Right now, the only way I can think of is to compute the three side lengths of triangle ABC, square them, and see if the squares of AC or BC are larger than the sum of the remaining two squares in each case (in other words, cosine law). However, that doesn't seem as simple as it could be...

 Author: crossley7 [ Tue Nov 01, 2011 9:29 pm ] Post subject: RE:DWITE Round #1 Solutions/Analyses you would have to use trig likely since lines won't necessarily be horizontal or vertical. So yeah, that is what you have to do. Although there is likely some way to solve it using just Pythagorean Theorem (I haven't bothered fixing my solution so I'm not sure)

 Author: A.J [ Wed Nov 02, 2011 3:50 pm ] Post subject: RE:DWITE Round #1 Solutions/Analyses You could use the Law of Cosines to help you out: AB^2 + BC ^2 - 2 * AB * BC * cos(angle ABC) = AC^2. This is basically a generalization of the Pythagorean Theorem.

 Author: hahd [ Thu Nov 03, 2011 12:28 am ] Post subject: Re: DWITE Round #1 Solutions/Analyses i still dont understand cyril's solution......sorry not a very strong math/compsci student can sm1 break it up further....

 Author: shaun [ Fri May 25, 2012 5:55 pm ] Post subject: Re: DWITE Round #1 Solutions/Analyses Cyril @ Sat Oct 29, 2011 12:37 am wrote:#4 can be done in logarithmic time. long long f(long long n){ return n<10 ? 0 : n/10 + (1+n%10)*f(n/10) + (9-n%10)*f(n/10 - 1); } Shouldn't this run in T(n) = 2T(n/10) + O(1) = O(n^0.31) time, not O(lg n) time?

 :