Recent Forum Posts
From categories:
page 1 of 212next »
KennethTsuiKennethTsui 25 Aug 2010 01:41
in discussion Hidden / Per page discussions » 928 Eternal Truths

In general 800 lines of code is a lot for an ACM problem.

This problem can be solved with < 200 lines of code.

My suggestion is rather than destroying the maze, create three 2D vectors to store the visited property for step sizes of 1, 2 and 3.

The rest of your statements are perfect :D

by KennethTsuiKennethTsui, 25 Aug 2010 01:41

This is a BFS shortest path problem with move restrictions. In a standard BFS problem, visiting the same square more than once is avoided, but the same square can be visited more than once, so long as it is visited in a new state. I am not sure if any of the test data features a case where the same square must be visited 3 times, or if this is even necessary.
How I approached this problem:
Since only the shortest distance is required, not the actual path, the maze that is input can be destroyed (within reason). It might be easier to store as much information as possible on the grid than make the queue bigger. How can we identify which square we are in and what state it is in? Remember, don't run over or into walls.
I solved this in .200s with 800+ lines of code.

BFS Shortest Path by Evan ConwayEvan Conway, 15 Aug 2010 06:01

Programming Challenges by Skiena & Revilla classifies this problem under backtracking and says only this about it: "Does it pay to try to position the largest squares first?"
I am guessing yes, but the question remains on exactly how to position each square

Backtracking by Evan ConwayEvan Conway, 15 Aug 2010 05:48
KennethTsuiKennethTsui 08 Jun 2010 05:32
in discussion Hidden / Per page discussions » 481 What Goes Up

You need the O(n log n) version of this algorithm, not the O(n^2), otherwise you will get TLE

by KennethTsuiKennethTsui, 08 Jun 2010 05:32

you are doing it wrong! use the force!

you are doing it wrong! by d1bd1b, 01 Jun 2010 15:40

Some big hints for this problem, since the deadline is past. I didn't actually implement this correctly, but the theory is sound. I apologise in advance if I'm giving away too much. But I worked so hard on the problem, I figured someone else may benefit if I post….

Here is the math behind what I did:
[http://i97.photobucket.com/albums/l237/stales2/acm/luke-ewok-1.png]
lx,ly is luke. ex,ey are the ewoks, cx,cy is a tree on their path.
d(lx,ly,cx,cy) is the distance from luke to the centre of the tree, calculated by distance formula.
r is the radius of the tree
ro can be calculated from the radius, the distance and pythagorus.
ro is the longest straight line from luke to the edge of the tree, and is the shortest path that he can follow to get around the tree (my drawing is not to scale and looks misleading)

[http://i97.photobucket.com/albums/l237/stales2/acm/luke-ewok-2.png]

Now with ro, we can draw a circle from luke's position, with radius ro. This circle will intersect the edge of the tree exactly twice. Each of these points needs to be calculated. (in my first diagram, the path below is shorter than the path above)

To find the exact locations of these points is done by a bit of algebra, I've got the working there (although the diagram is dodgy)

[http://i97.photobucket.com/albums/l237/stales2/acm/luke-ewok-3.png]

Now, what this gives you is the shortest path from luke to the edge of the circle, and from the edge of the circle to the finish. All that's left is to compute the distance around the circle. Finding the circumference of a circle is easy, 2piR. Finding an arc of that circle is fraction of this. The exact fraction can be calculated over the angle between these two points (for example, 1/2*2*pi*r = 180/360*pi*r). To find the angle, consider the two points as an isosceles triangle, with two sides length r (radius), the base of this tirangle is the distance between the two points . The isosceles triangle can be broken into two right-angle triangles. From that, trig gives the angle.

From that you have all the info to find the shortest route from start to finish.

But!

That's not all the work. This is the simple case of 1 triangle. You need to take care with more. I did this recursively, dividing the problem with every circle that intersected, find the new shortest path to the finish and the end. But I had some precision errors.

The last thing is calculating if a circle intersects a line. Two ways this can be done:
-point-to-line distance formula
-find the height of the triangle made by lx,ly:ex,ey:cx,cy. compare the height to the radius (I did it this way)

by StepehenPearsonStepehenPearson, 01 Jun 2010 10:09

Umm, so?

I thought it would be useful to have some resources. If you think not having resources is somehow beneficial, that's fine….

Re: Good books? by StepehenPearsonStepehenPearson, 01 Jun 2010 08:54

I think that recognising the algorithm based on a book is only so good.
If you look at the google code jam first round problems for this year. You will notice that
the first problem is just binary addition. You have to be able to make decisions based upon what you know outside of algorithms.

Try to understand what the 'problem' and write addition test cases first.

Re: Good books? by d1bd1b, 31 May 2010 09:19

Sample data

7 0.0 0.0 100.0 0.0
2 0 2
4 -1 1.8
4 1 1.8
8 -1 4
8 4 5
50 -10 50
96 0 5

sample output

1895.44

sample data

7 0.0 0.0 0.0 100.0
0 2 2
-1 4 1.8
1 4 1.8
-1 8 4
4 8 5
-10 50 50
0 96 5

sample output

1895.44

by KennethTsuiKennethTsui, 28 May 2010 03:58

Stephen, to print out as 2 decimal points, try something like printf("%.2f", time) or something like that - can't be sure of the syntax on top of my head

by KennethTsuiKennethTsui, 27 May 2010 10:08
cool
d1bd1b 25 May 2010 12:37
in discussion Hidden / Per page discussions » 10224-Return of the Jedi

yes. I was thinking you would have to do something like that - I really was only after the
dist/(200/3600) part btw ^^.

Try 2 DP - it might work for that. (um ceiling not floor perhaps ?)

cool by d1bd1b, 25 May 2010 12:37

well then here is what I did:
You have to get the shortest path between two points, that's easy, it's a straight line distance calculation. Then have to find any circles (trees) that lie on that line, again easy. Point-to-a-line formula will tell you how far the centre of a circle is to a line, if it's less than the radius of that circle, it intersects. For simple cases, find a line that goes from the start point, to the edge of the circle, then from the edge of the circle to the finish point. Recursively checking and adjusting for additional circles that cross any new lines. For more complex cases, you need to find the longest straight line that will attach to a circle, then from the apex of the circle to the finish. It takes in an arc of the total circumference of the circle (imagine if the start and end points lie on opposite sides of a circle, the shortest distance would be half the circumference).

Finally, calculate all these distances and use the formula dist/(200/3600) to get the final answer.

I used this to get *fairly* good results, but for the life of me I can't work out the precision. On the given input I get an answer of 181.1206395, which does not round to 181.13

by StepehenPearsonStepehenPearson, 25 May 2010 12:02

woo don't take it that seriously …. i already had posted 'test cases' when i found stupid problems in my code that meant it failed for the other 2. imho these are weekly things that don't even count for anything. Also, in the competition you work in teams.

I would rather put information here that gets some gets some one to finish it than sit on the information.

Feature: finish a task
As a mq acm competitor
I want to complete UVA example problems
So that I can be better prepared for the ACM

http://cukes.info/

well, there are a large number of factors to consider. I don't know if I should be discussing it before the contest is over, because I may give out some hints that others haven't thought of (or in reverse, someone might give me hints I haven't thought of).

I'm treating this as ACM training (I can't ask for simple terms on the day =P), so all I'll say for now, is all the numbers you need are in the question. But it's a nightmare to properly implement them (unless i'm overcomplicating it)

by StepehenPearsonStepehenPearson, 24 May 2010 09:17

There's the specialised ACM book: http://www.comp.nus.edu.sg/~stevenha/programming/acmoj.html

Probably the best one, and his website is full of hints as well. I'm so jealous of that guy, he teaches a subject called Competitive Programming. Imagine that!

I like Carrano's (your 225 textbook) as well, but you're probably beyond it now. Anyway, my opinion is that one book is more than enough, if you can devour it in its entirety, you'd be godly.

Re: Good books? by DanielSutantyoDanielSutantyo, 24 May 2010 07:11
d1bd1b 23 May 2010 15:25
in discussion Hidden / Per page discussions » 10224-Return of the Jedi

/d / ___\
/ s|t
d = s * t

200 m/h
with trees to avoid, but otherwise as the crow fly's ?
I am not sure on how the units work out for this question. Can anyone explain this one in simple terms?

LUKE   -------------------------->    DST
0,0      ---------------------->  10,0

also fail at wikidot markup

by d1bd1b, 23 May 2010 15:25

wow, compared to the last two, this problem is insane! I hate floating point….

by StepehenPearsonStepehenPearson, 23 May 2010 00:51

Anyone know of any good books for ACM-like problems. One good one I've been looking at is "Introduction to Algorithms" (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein)

I flicked through it today, and I noticed a lot of the algorithms outlined in the book appear time and time again in ACM questions. Especially the parts about dynamic programming.

I'm sure people have recommended other books, but I always forget what their names are!

Good books? by StepehenPearsonStepehenPearson, 22 May 2010 04:09
d1bd1b 21 May 2010 03:04
in discussion Hidden / Per page discussions » 489 - Hangman Judge
"""
cat example
1
cheese
chese
2
cheese
abcdefg
3
cheese
abcdefgij
4
cheese
cjeesehabcdefgij
5
cheese
eBFDAIOPXAWeeecjeesehabcdefgij
-1
"""
 
"""
./a.out < example
Round 1
You win.
Round 2
You chickened out.
Round 3
You lose.
Round 4
You win.
Round 5
You lose.
"""
by d1bd1b, 21 May 2010 03:04

Just out put as you go apparently
and don't put a \n at the finish. - that got me.

by d1bd1b, 20 May 2010 13:17
page 1 of 212next »
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License