Search found 114 matches

by stcheung
Sun Aug 23, 2009 9:30 am
Forum: Volume 109 (10900-10999)
Topic: 10930 - A-Sequence
Replies: 102
Views: 36362

Re: 10930 - A-Sequence

Just got AC after almost 10 WA. Let me sum up the cases at this point: (1) If there's duplicate or if the input sequence is NOT in increasing order, then it's NOT an A-sequence. With that said, you do NOT have to sort the input. (2) Instead of setting the array size as 30000, setting it to 1000 is e...
by stcheung
Sat Aug 15, 2009 8:50 pm
Forum: Volume 107 (10700-10799)
Topic: 10714 - Ants
Replies: 20
Views: 13332

Re: 10714 - Ants

Here's some more hints for those who need it. Both the min & max time scenarios won't involve 2 ants touching each other, so you can safely ignore that piece of fact in the problem description. Furthermore, while sorting would help, it also isn't necessary to solve the problem.
by stcheung
Sat Mar 14, 2009 10:32 am
Forum: Volume 106 (10600-10699)
Topic: 10622 - Perfect P-th Powers
Replies: 47
Views: 25107

Re: 10622 - Perfect Pth Powers

I got over 10 WA and passed every single test case posted here. My algorithm is same as that mentioned in a previous post: (1) Get all primes < sqrt(MAX) (2) For each prime that divides the input, store the power in a hashmap (3) Iterate over the value of the hashmap to see if they all equal 1 value...
by stcheung
Mon Jan 19, 2009 9:59 am
Forum: Volume 104 (10400-10499)
Topic: 10491 - Cows and Cars
Replies: 17
Views: 8976

Re: 10491 - Cows and Cars

Consider these 2 scenarios:
(1) Cow was initially chosen, then a Car was chosen after doors are revealed
(2) Car was initially chosen, then a Car was chosen after doors are revealed

The result is the sum of their probabilities.
by stcheung
Fri Jan 16, 2009 10:12 am
Forum: Volume 104 (10400-10499)
Topic: 10482 - The Candyman Can
Replies: 10
Views: 6202

Re: 10482 - The Candyman Can

Yeah like one of the previous post says, simple BFS is more than enough to solve this. So do BFS to get all DISTINCT (a, b) pairs such that neither a or b is >= 250. To make sure they are distinct you want to maintain a double array [250][250] to keep track of all the ones you have seen already. At ...
by stcheung
Thu Jan 15, 2009 7:43 am
Forum: Volume 104 (10400-10499)
Topic: 10475 - Help the Leaders
Replies: 24
Views: 11279

Re: 10475 - Help the Leaders

As for me, I got my several WA because I didn't follow this: "Print a blank line after the output for each case." Frankly I consider the fact that each problem may have its own blank line policy to be quite annoying. ACM should probably standarize this. And might as well standardize how th...
by stcheung
Thu Jan 15, 2009 6:29 am
Forum: Volume 104 (10400-10499)
Topic: 10471 - Can't be too GREEDY
Replies: 0
Views: 2096

10471 - Can't be too GREEDY

I read the problem statement so many times but still couldn't understand what we need to do. It's not my English because this is the first time I can't understand a problem statement. Can somebody be kind enough to do some explaining? Thanks.
by stcheung
Tue Jan 13, 2009 8:40 am
Forum: Volume 104 (10400-10499)
Topic: 10443 - Rock
Replies: 26
Views: 4523

Re: 10443 - Rock, Scissors, Paper

This problem is one of the most straightforward ones I have seen, so if you are struggling then you are probably doing something wrong. In that case see if the following hints help: (1) As someone mentioned before, it's probably easier to figure out how a given cell will change based on its neighbor...
by stcheung
Tue Jan 13, 2009 8:07 am
Forum: Volume 104 (10400-10499)
Topic: 10440 - Ferry Loading II
Replies: 10
Views: 7784

Re: 10440 - Ferry Loading II

In case the hints aren't enough for the uninitiated. Basically you want to move the ferry when passenger #m (last passenger) has arrived, when passenger #(m-n) has arrived, when passenger #(m-2n) has arrived and so forth. But due to the roundtrip time, there will be some delay involved and so it boi...
by stcheung
Sat Jan 10, 2009 10:14 am
Forum: Volume 104 (10400-10499)
Topic: 10422 - Knights in FEN
Replies: 49
Views: 18868

Re: 10422 - Knights in FEN

If you are struggling to solve this problem with backtracking/dfs/2-way bfs then you might as well try the precalc idea that someone mentioned already. Since the board has 25 squares, and each square has only 3 different possibilities, you can use a 64-bit integer to uniquely represent each differen...
by stcheung
Fri Jan 09, 2009 7:29 am
Forum: Volume 104 (10400-10499)
Topic: 10401 - Injured Queen Problem
Replies: 19
Views: 10668

Re: 10401 - Injured Queen Problem

Took me a while to understand what the previous hints meant when they mentioned memoization and creating a dp table. Let me try elaborating on that. Assuming n is board size, let's start with the 2nd to last column. Let c denote this column. For each row r in column c, if you put a queen on (c, r) t...
by stcheung
Wed Jan 07, 2009 8:25 am
Forum: Volume 103 (10300-10399)
Topic: 10392 - Factoring Large Numbers
Replies: 14
Views: 8070

Re: 10392 - Factoring Large Numbers

Instead of outputting a blank line between test cases, you should output a blank line after each test case (including the last one). On the other hand, thanks for your program. I was implementing the same "naive" idea but got TLE, which I thought was reasonable at first. Then I saw your pr...
by stcheung
Wed Jan 07, 2009 7:01 am
Forum: Volume 103 (10300-10399)
Topic: 10375 - Choose and divide
Replies: 23
Views: 12247

Re: 10375 - Choose and Divide

If you are using Java and keep getting WA, you might want to try using C/C++. At first I converted the program in the 1st thread into a Java program. I also took the suggestion in the 2nd thread and converted the 6 loops into a single loop. However that got me WA whether I use Math.log10 or Math.log...
by stcheung
Sun Oct 26, 2008 5:54 am
Forum: Volume 103 (10300-10399)
Topic: 10307 - Killing Aliens in Borg Maze
Replies: 54
Views: 18978

Re: 10307 - Killing Aliens in Borg Maze

This problem is very lenient on the timing, so no need for any optimization at all. My Java solution did the most straightforward thing and still got AC in < 0.4 sec: (1) For each starting point/alien location, do simple bfs to find distance to other aliens. (2) Build mst using Prim's algorithm, sta...
by stcheung
Fri Oct 24, 2008 8:27 am
Forum: Volume 102 (10200-10299)
Topic: 10286 - Trouble with a Pentagon
Replies: 7
Views: 5249

Re: 10286 - Trouble with Pentagon

Isn't the answer of the form F * sin(a) / sin (b)?

I calculated values for a & b, but the result is different from output. I then used brute-force to come up with values for (a, b) that would yield sample output, but these all got me WA. Any idea? Can somone provide more output? Thanks.

Go to advanced search