## Search found 519 matches

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...
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 ...
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.
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.
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.
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...
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
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.
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.
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.
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.
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.
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.
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.
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
``````