Search found 519 matches

by sclo
Sat Feb 18, 2006 2:56 am
Forum: Volume 6 (600-699)
Topic: 688 - Mobile Phone Coverage
Replies: 2
Views: 2481

There's at least 2 ways I can think of to solve it. The easy way is to normalize the coordinates and just count the sum of area of rectangles that has at least one square covering it. The other way, which works for input size at much as 500000 is to use the sweep line algorithm for finding area of u...
by sclo
Sat Feb 18, 2006 1:57 am
Forum: Volume 109 (10900-10999)
Topic: 10926 - How Many Dependencies?
Replies: 33
Views: 14357

Yes, this can be done with topological sorting. First run dfs to topological sort the vertices. assume now that the vertices are sorted in order such that vertex a can only depend on vertices a[j], where j<i. Now we count the number of dependencies for vertex a . Let C be that count: for i = 1 to n ...
by sclo
Sat Feb 18, 2006 1:21 am
Forum: Volume 104 (10400-10499)
Topic: 10493 - Cats, with or without Hats
Replies: 13
Views: 6916

The general formula is (mn-1)/(n-1), just worry about the special cases.
by sclo
Fri Feb 17, 2006 10:22 pm
Forum: Volume 101 (10100-10199)
Topic: 10171 - Meeting Prof. Miguel...
Replies: 68
Views: 24325

I used Floyd to solve this one and got WAs. The thing to watch out for is that the input contains self loops with positive costs. Just simply ignore then when computing shortest path costs.
by sclo
Fri Feb 17, 2006 9:08 am
Forum: Volume 7 (700-799)
Topic: 763 - Fibinary Numbers
Replies: 40
Views: 16050

It is interesting that this problem can be solved using ordinary big ints.
by sclo
Thu Feb 16, 2006 11:19 am
Forum: Volume 106 (10600-10699)
Topic: 10669 - Three powers
Replies: 14
Views: 5840

This are the correct output from my AC program: { } { 3, 9 } { 1, 9, 27 } { 3, 9, 27, 6561, 19683 } { 59049, 3486784401, 205891132094649, 717897987691852588770249 } { 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 10460353203, 31381...
by sclo
Thu Feb 16, 2006 11:12 am
Forum: Volume 106 (10600-10699)
Topic: 10669 - Three powers
Replies: 14
Views: 5840

Just think about binary expansion of n
by sclo
Wed Feb 15, 2006 10:14 am
Forum: Volume 3 (300-399)
Topic: 347 - Run
Replies: 20
Views: 6057

Easiest way is to precompute all runaround numbers, then binary search. If you want to have AC in 0.0 time, just precompute the numbers in a table.
by sclo
Wed Feb 15, 2006 3:33 am
Forum: Volume 5 (500-599)
Topic: 501 - Black Box
Replies: 35
Views: 16198

This problem is easy to do with stl sets. Much easier than implementing some tree datastructure ourselves. As Abenego says, just be careful with the iterators. We need to adjust the iterator if we insert an element before the position that the iterator points at.
by sclo
Mon Feb 13, 2006 10:47 pm
Forum: Volume 100 (10000-10099)
Topic: 10051 - Tower of Cubes
Replies: 19
Views: 8890

I'm sure that there are at most only 500 cubes, since that's how large my array was. I never cared about how many colors there are in my algorithm. Suppose there are N cubes, then there's a way to do it with a O(N^2) LIS algorithm on 6*N elements.
by sclo
Mon Feb 13, 2006 10:12 pm
Forum: Volume 109 (10900-10999)
Topic: 10991 - Region
Replies: 17
Views: 8716

I still think using cosine formula should be preferred, although sine formula with additional checking can be used. During actual contests, it's easy to forget checking the conditions for the sine formula.
by sclo
Mon Feb 13, 2006 9:41 pm
Forum: Volume 109 (10900-10999)
Topic: 10993 - Ignoring Digits
Replies: 19
Views: 9616

Now I got AC, turns out that my initialization was incorrect. Misof, thanks for your i/o.
by sclo
Mon Feb 13, 2006 10:58 am
Forum: Volume 1 (100-199)
Topic: 101 - The Blocks Problem
Replies: 635
Views: 40423

Your code is much longer than it need be. It's too much for me to debug, maybe try to rewrite the code, you might be able to get rid of the bug.
by sclo
Mon Feb 13, 2006 10:52 am
Forum: Volume 109 (10900-10999)
Topic: 10994 - Simple Addition
Replies: 41
Views: 15676

Remember, this is for Volume I, next time, post in Volume CIX plz.
by sclo
Mon Feb 13, 2006 10:49 am
Forum: Volume 6 (600-699)
Topic: 632 - Compression (II)
Replies: 13
Views: 5443

I'm too lazy to go through java codes.
Also your inputs are not valid since there must be a blank line between each case.
Anyway, here's the correct output.

Code: Select all

1
a

4
aaaaa

7
ccccaaaabbbb

16
99999000005111111222222333333444444555556666677777
88888

Go to advanced search