Search found 274 matches

by Cho
Wed Apr 05, 2006 9:13 am
Forum: Volume 108 (10800-10899)
Topic: 10808 - Rational Resistors
Replies: 19
Views: 9796

I've just got AC, but I still have a question about the problem. I use long long and can easily construct test case to make my AC-code fail: 1 6 15 0 1 1 0 2 2 1 2 9 0 3 3 1 3 1 2 3 4 0 4 9 1 4 5 2 4 1 3 4 6 0 5 9 1 5 7 2 5 1 3 5 8 4 5 9 15 0 1 0 2 1 2 0 3 1 3 2 3 0 4 1 4 2 4 3 4 0 5 1 5 2 5 3 5 4 5...
by Cho
Tue Apr 04, 2006 3:42 pm
Forum: Bugs and suggestions
Topic: The photo in the front page is TOO big
Replies: 2
Views: 2089

The photo in the front page is TOO big

For those who use Windows' Internet Explorer must agree that the photo of Mr. William Poucher and Prof. Miguel Revilla in the front page is too big. The original size image (2616x1864) dominates the whole screen. The image's html tag is as: <img src="images/billenlauva_19.jpg" width="95%" alt="Joe D...
by Cho
Tue Apr 04, 2006 11:46 am
Forum: Volume 107 (10700-10799)
Topic: 10762 - Treasure Castle
Replies: 12
Views: 8925

The reduced grid is no doubt one of the first approaches those came to my mind after I read the problem (almost 1.5 years ago?). But I missed the point that flood fill on this grid will work. Don't know what I was thinking all these months. Thanks for pointing that out, Krzysztof. (And the ':' chara...
by Cho
Mon Apr 03, 2006 6:12 am
Forum: Volume 110 (11000-11099)
Topic: 11025 - Mr. And Mrs. Hamilton
Replies: 21
Views: 8037

I made the same mistake... and now let's read the problem again...
... smallest expected amount of time that Mrs. Hamilton needs in order to find her husband and bring him home ...
:)
by Cho
Sun Mar 26, 2006 6:48 am
Forum: Volume 110 (11000-11099)
Topic: 11019 - Matrix Matcher
Replies: 43
Views: 18078

As far as I know good hash is the one which uses nice primes... 2^32 is not one of them as far as I know The hash value (for one dimensional string) introduced by some text book is: Summation over all k, c[k]*2^k mod p, where p is a prime. But mine is: Summation over all k, c[k]*p^k mod (2^32), whe...
by Cho
Fri Mar 24, 2006 7:43 am
Forum: Volume 110 (11000-11099)
Topic: 11019 - Matrix Matcher
Replies: 43
Views: 18078

You have very nice idea but I have some doubts that this will give TLE. After you find the same hash as the patern you will need to do the slow compare to see if the matching is valid. For the test case that krijger mentioned (a lot of 'A's) this will give TLE. Do you do something else which I miss...
by Cho
Fri Mar 24, 2006 4:54 am
Forum: Volume 110 (11000-11099)
Topic: 11014 - Make a Crystal
Replies: 16
Views: 6915

1. Run sieve so that factor[n] store the max prime factor of n 2. Compute all phi[n] by making use of factor[n], O(n) 3. Compute all A[n] by making use of factor[n], O(n) 4. Compute all sumphi[n] to be phi[1]+...+phi[n], O(n) 5. Compute all sumA[n] to be A[1]+...+A[n], O(n) 6. Finally, for each quer...
by Cho
Thu Mar 23, 2006 12:50 pm
Forum: Other words
Topic: topcoder releated question -- > cheating
Replies: 17
Views: 6695

You better send an email to them to ask why they think you was cheating.
Most brobably they think you collaborated with somebody else.
by Cho
Thu Mar 23, 2006 5:01 am
Forum: Volume 110 (11000-11099)
Topic: 11014 - Make a Crystal
Replies: 16
Views: 6915

The bottle neck of my algorithm is the sieve, afterwards, everything can be done in linear time. Since our approaches are different, it's not surprised that there is a constant factor difference in the running times.
by Cho
Thu Mar 23, 2006 4:24 am
Forum: Volume 110 (11000-11099)
Topic: 11019 - Matrix Matcher
Replies: 43
Views: 18078

Let c[j] be the character of the shorter string, I define its hash value as:
Summation over all valid i,j: c[j] * (3 ^ (i*100+j)) mod 2^32
(x^y denotes x to the power y instead of bitwise-XOR.)
by Cho
Wed Mar 22, 2006 3:11 pm
Forum: Volume 110 (11000-11099)
Topic: 11014 - Make a Crystal
Replies: 16
Views: 6915

(Assuming you know about Euler's Phi function .) My approach starts from thinking about a two dimensional version of Phi function. Let A(n) be | { (x,y) : 1<=x,y<=n and gcd(x,y,n)=1 } | What's A(n) when n is prime? power of prime? What's A(ab) if a and b are co-prime? Then the final solution could b...
by Cho
Wed Mar 22, 2006 2:50 pm
Forum: Volume 110 (11000-11099)
Topic: 11016 - Square Counting
Replies: 19
Views: 7358

"For each test case, output a line containing two space separated integers, the number of light and dark squares completely encompassed by the polygon in descending order ." Funny, I've missed that part too. I did the plane-sweep also and got accepted. THX A LOT... That's tricky! And I'm just toooo...
by Cho
Wed Mar 22, 2006 11:32 am
Forum: Volume 110 (11000-11099)
Topic: 11016 - Square Counting
Replies: 19
Views: 7358

Since the square in the first row and first column is dark (from the figure), I couldn't understand why the second sample output is "1 0".

Do I mis-understand something?

Btw, I think plane-sweep will do.
by Cho
Tue Mar 21, 2006 11:22 am
Forum: Volume 110 (11000-11099)
Topic: 11014 - Make a Crystal
Replies: 16
Views: 6915

Strange. Your output is correct.
by Cho
Tue Mar 21, 2006 6:05 am
Forum: Volume 110 (11000-11099)
Topic: 11019 - Matrix Matcher
Replies: 43
Views: 18078

I compute the hash value (long long multiplications involved) of the small pattern. Then preprocess the large text such that the hash value of each X by Y 2D-substring can be computed in constant time. I didn't optimize the code (and found no much room for optimization). It runs roughly 2.5 secs too.

Go to advanced search