## Search found 114 matches

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

### 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...
Sat Aug 15, 2009 8:50 pm
Forum: Volume 107 (10700-10799)
Topic: 10714 - Ants
Replies: 20
Views: 12671

### 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.
Sat Mar 14, 2009 10:32 am
Forum: Volume 106 (10600-10699)
Topic: 10622 - Perfect P-th Powers
Replies: 47
Views: 23573

### 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...
Mon Jan 19, 2009 9:59 am
Forum: Volume 104 (10400-10499)
Topic: 10491 - Cows and Cars
Replies: 17
Views: 8200

### 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.
Fri Jan 16, 2009 10:12 am
Forum: Volume 104 (10400-10499)
Topic: 10482 - The Candyman Can
Replies: 10
Views: 5745

### 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 ...
Thu Jan 15, 2009 7:43 am
Forum: Volume 104 (10400-10499)
Topic: 10475 - Help the Leaders
Replies: 24
Views: 10494

### 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 the end of i...
Thu Jan 15, 2009 6:29 am
Forum: Volume 104 (10400-10499)
Topic: 10471 - Can't be too GREEDY
Replies: 0
Views: 1987

### 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.
Tue Jan 13, 2009 8:40 am
Forum: Volume 104 (10400-10499)
Topic: 10443 - Rock
Replies: 26
Views: 3666

### 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...
Tue Jan 13, 2009 8:07 am
Forum: Volume 104 (10400-10499)
Replies: 10
Views: 7163

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...
Sat Jan 10, 2009 10:14 am
Forum: Volume 104 (10400-10499)
Topic: 10422 - Knights in FEN
Replies: 49
Views: 16449

### 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...
Fri Jan 09, 2009 7:29 am
Forum: Volume 104 (10400-10499)
Topic: 10401 - Injured Queen Problem
Replies: 19
Views: 9495

### 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...
Wed Jan 07, 2009 8:25 am
Forum: Volume 103 (10300-10399)
Topic: 10392 - Factoring Large Numbers
Replies: 14
Views: 7671

### 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 program got ...
Wed Jan 07, 2009 7:01 am
Forum: Volume 103 (10300-10399)
Topic: 10375 - Choose and divide
Replies: 23
Views: 11353

### 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...
Sun Oct 26, 2008 5:54 am
Forum: Volume 103 (10300-10399)
Topic: 10307 - Killing Aliens in Borg Maze
Replies: 54
Views: 17351

### 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...
Fri Oct 24, 2008 8:27 am
Forum: Volume 102 (10200-10299)
Topic: 10286 - Trouble with a Pentagon
Replies: 7
Views: 4945

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