 Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki Blog Search Turing Chat Room Members
DWITE Round #1 Solutions/Analyses       Author Message
A.J  Posted: Fri Oct 28, 2011 11:23 pm   Post subject: DWITE Round #1 Solutions/Analyses    Cyril Posted: 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!  d310 Posted: 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! Yves Posted: 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. A.J  Posted: 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! ihsh Posted: 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... crossley7 Posted: 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) A.J  Posted: Wed Nov 02, 2011 3:50 pm   Post subject: RE:DWITE Round #1 Solutions/Analyses

AB^2 + BC ^2 - 2 * AB * BC * cos(angle ABC) = AC^2.

This is basically a generalization of the Pythagorean Theorem.    hahd Posted: 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.... shaun Posted: 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? Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First        Page 1 of 1  [ 10 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: