?

Log in

No account? Create an account
TopCoder.com
 
[Most Recent Entries] [Calendar View] [Friends]

Below are the 20 most recent journal entries recorded in TopCoder.com problem discussion's LiveJournal:

[ << Previous 20 ]
Thursday, May 10th, 2007
8:38 am
[dplass]
SRM 347
I was in div 2, but did really well (I think...)

Now, though, www.topcoder.com is dead (for over 2 hours) so I don't know if they did in fact re-run systests...
Thursday, November 2nd, 2006
8:33 pm
[larrytc]
Topcoder get-around
For some reason, Topcoder is 500 on us. I already registered, but for those of you who need register quick, thank Google Cache:

http://72.14.209.104/search?q=cache:d3mapg94BHgJ:www.topcoder.com/tc+site:www.topcoder.com+topcoder&hl=en&gl=us&ct=clnk&cd=2

Just click on that O(n) button on the upper left..
Wednesday, September 20th, 2006
10:22 pm
[kalmakka]
Talk like a pirate day
Last round of google code jam was on talk like a pirate day and Eryx got into the spirit.

Some sample lines from his code:
// Aye, as ye can see on th' logo o' this competition, Earrrth be not round, matey
FERRR(l,0,Size(s)){
aye;
returrrn dp[0] matey;


Funny guy :)
Wednesday, June 28th, 2006
1:51 pm
[larrytc]
SRM 309
Wow! What a hard 600 and 1000.. while mostly everybody got the 250. Which means it became a typing contest of sorts!

Unforunately, my 250 was resubmitted 3 times due to stupid mistakes along the way. Bummer. And I actually got lucky and pulled a Larry on the 1000 for ~750 points, but then made a stupid mistake (didn't minimize s and then t), and resubmitted for a respectable 570. But of course, I had another silly mistake that I realized in challenge phrase, and so down it goes.

Needed to rant - the 250 was just bruteforce, the 600 was some kind of DP I don't quite understand. The 1000 I literally guessed on, so don't expect me to explain it.. a very achievable 240 (with next_permutation) would've been good enough for top 20. It was that kind of match..

Current Mood: sad
Saturday, June 17th, 2006
3:21 pm
[dplass]
SRM 301
This whole SRM was just evil and I wish I would've stood in bed.
3:17 pm
[dplass]
SRM 305
It's been a long time. Why don't people bother posting here any more? Is the magic gone?

250
Took me a long time, but I finally got this one. The trick: for each array index, find the highest entry between there, and there+nswaps left. Then go to the next array index. I had to resubmit, for a measly 100 points, but I still went up 60 ratings points.

500
No clue. The robber's rate plus the train's rate, taking into account where hs is on the train, and he might have to wait between cars, etc.etc.etc., it seems like some kind of evil pre-calc problem from 11th grade. ("A man is filling a bathtub with two hoses. The first hose fills at a rate of 1 liter/hr, and the second one fills at a rate of 2 liters/hr. But, the drain is open, but not right away, only every 10 seconds for 1 second, draining at a rate of 0.5 liters/hr. Which comes first, the chicken or the egg?")

I think only 10 people got it right.

1000
I didn't even read the whole problem, but it sounds hard, and I think only 6 got it right.
Thursday, May 25th, 2006
10:07 pm
[dplass]
TopCoder Forums...
... are down! Oh noes! Looks like they're having database problems.
Tuesday, May 9th, 2006
2:16 pm
[dplass]
TCO Blog
X-posted to dplass

In case you couldn't find it,
this is where my TCO Blog went.

Note, it includes all 4 blogs intertwingled, which is stupid.

Also the "times" are completely artificial.
1:54 pm
[dplass]
SRM tonight
Yay, only 7 hrs until the next SRM. I can hardly remember the last one!

One would think that after last week I would be TopCoder'd out, but the obsession continues!
Monday, April 24th, 2006
12:41 am
[staticentropy]
The anthropology of TopCoder, my final project, and you
[If you saw this on the TC forums, this is almost exactly the same thing, since I am too lazy to write another version.]

This term, I am taking a class called "Anthropology of Computing", which is an exploration of the social, cultural and personal forces behind computation in all its forms -- automata, AI, cyberspace, and so on. I missed a session of class due to the ACM World Finals (and will miss another one for the TCO), and so my professor suggested that I take the opportunity to do a final paper on some aspect of programming competitions.

But, of course, this being an anthropology course, the paper is not meant to be a straight description of TopCoder, or the ICPC, or even a compare and contrast exercise; it should deal with the people behind it. This is where you (yes, you, the reader of this post) come in.

I'd like to interview people involved with TopCoder and with other programming competitions, to get some sort of insight as to how I want to structure this paper, and what sort of point I actually want to make :) But I don't want to be intrusive or anything, so if you're reading this and want to help me pass, you can opt in by e-mailing me at antimatter AT mit DOT edu (replacing the obvious bits). I'm afraid that I can't offer any sort of incentive to make this worth your time, but hopefully I can appeal to your sense of goodwill and charity.


Obligatory disclaimers:

  1. All interview text may be taken and quoted in my paper, which will, in all likelihood, only be read by me and my professor, where it will then get a barely-passing grade and then never be seen again. I'll try to keep from quoting people out of context. (Of course, if people want me to post the paper when I'm done, I'd probably be okay with that, too.)

  2. If too many people want to be interviewed (as unlikely as that sounds), then I probably won't have enough time to follow up with everyone. Preference will be given to:


    • TopCoder admins, since they're on the other side of things
    • TCO semifinalists, since I'll be able to interview them in person next week (if they'll let me)
    • ICPC finalists, because I'd like to be able to compare the ICPC and TopCoder somehow
    • Women, because they are such a minority in programming competitions in general
Thursday, March 16th, 2006
5:17 pm
[kalmakka]
TCO 06 Round 3
200
A very simple binary game problem. A position is a winning position (to be given) if it is possible to reach a loosing position from it. It is a loosing position if only winning positions can be reached from it.
I read the constraints a bit too fast, so my program only worked for n<200. I noticed this before submitting, but only changed it for my array size and not for how long my loop was too run. A resubmit brought me down to 176 pts.

500
While checking for loops to see if anybody had temself as an ancestor was simple, checking for genders properly was something that most people (including me) forgot, thus resulting in a LOT of challenges. For instance, if A and B have a child, and B and C have a child, then it is impossible for A and C to have a child.
To check wether a valid gender-assignment exists, make a graph where the nodes are the people and the edges are the people who have had a child. Color the nodes of people with known genders with your two favorite colours, and spread out with colours so that no edge connects to nodes with the same colour. If any nodes remain uncoloured, colour a random uncoloured node with your favorite colour and progress.

I never seem to solve these problems involving sexes :P

1000
My original solution for this was based on just finding the probability of being able to be at home at any time. After submitting, I realized that this wouldn't work. For instance, if one bus leaves every minute and takes 10 minute to get you home, and the other bus leaves every 7 minutes and takes 5 minutes to get you home, my program would think that you could always be home 10 minutes after start. However, waiting for the fast bus is always advantageous, so it might take up to 11 minutes to get home. I almost had a correct solution done when the timer ran out. Basicly, you need to DP and see if waiting 1 minute and hoping to catch a faster bus is better than taking a slow bus now.


My recursive solution was, after cleaning it up a bit,
     //bus contains <tripTime,waitTime> pairs sorted by ascending traveltime, kt is time after start
double dome(vector<pair<int,int> > &bus, int kt){ 
  if (kt==bus[0].second-1) return bus[0].first;
  double timeIfWait = 1+dome(bus,kt+1);
  double s=0.0;
  double pwait=1.0; //probability of waiting
  for (int i=0;i<bus.size();i++){
    double p = 1.0/max(bus[i].second-kt,1); //probability that bus i gets here now
    if (bus[i].first < timeIfWait){
      s+=bus[i].first*p*pwait;
	pwait*=(1-p);
    }
  }
  return s+pwait*timeIfWait;
}


Solving the 200 really really really fast was sufficient to advance. Or you could just do like futo or bugzpoddere and break a lot of solutions. Or, like I did, you can do something in between. I found a 200 solution in C++ where the DP array was of size exactly 100000. Knowing that 176pts wouldn't be enough to advance, I took a chance and challenged it.

Current Mood: content
Thursday, March 9th, 2006
9:13 am
[dplass]
SRM 292
Better late than never:?

250

This problem reminded me of the Quipu problem of SRM 155, except I was in div 2 at the time.

For this problem, find the last dash on each line, figure out how far from the right side it is, add and multiply by 10. Then do the opposite.

For some reason I felt that reconstructing it "backwards" (bottom-to-top and right-to-left) was easier, but somehow I passed all examples.

I got kicked off right after opening the problem so I lost a couple minutes, grr.

500
This problem made my head hurt. BOB. The write-up was pretty convincing, though. Any BOB that is a supervisor can be "The" BOB who supervises everyone. (Except, I suppose, another BOB, because, er, what if that BOB is a supervisor too. Hmm, this is why my head hurt.)

Needless to say, I didn't get it.

1000

I thought a few minutes about this one, and saw that it was too big for bruteforce. Thought that it might be a DP-ish problem, but it seemed too graphy for that. Ultimately I didn't get it, but the posted solutions look pretty straightforward and the writeup was crystal clear (except for the time bounds; F-W does seem too slow.)
1:21 pm
[kalmakka]
TCO Round 2
A rather more complicated set of problems this time.

250
A very easy problem. Taking integer powers of a number to a certain moduli is something most TopCoders should be able to do in logarithmic time, but due to constraints the standard linear time algorithm was more than sufficient. There was one somewhat elusive corner case that a lot of people failed on. Apparently 0 is a 1-digit number, and not a minus-infinity-digit number. In addition to that bug, I had a silly </<= bug in my exponentiation function, going something like
if (x>100000) overflow=1;
return x%100000;


550
Clearly a number theory problem. The final letter in the input tells you whether you'll end up with an odd (2k+1) or even (2k+0) number before you do the final operation. Then, working from right to left you can determine the form for each previous step.
'E': If division by 2 gives you a number on the form ak+b, your number must have been on the form (2a)k+(2b).
'O': 3x+1=ak+b <=> 3x = b-1 (mod a) <=> x=(b-1)/3 (mod a) <=> x=(b-1)*(1/3) (mod a)
Coding up something to quickly find inverses is a bit tedious, but since 3 is such a small number we can do it very easily. Either 1 (well, not very likely :P), 1+a or 1+2a is a multiple of 3, and dividing that number by 3 gives the inverse of 3. Multiply up and make sure you get it on the form you want.

General approach for finding inversesCollapse )

1000
Actually, this one was the most straight-forward of all the problems. Using a 20-bit bitmask to represent the different possible positions you can occupy and looking at how the four different moves you can make affect these positions you reduce it to a a nice shortest-path graph problem.

What I failed to realize (due to a state of tiredness and/or stupidity) was that a BFS generates not only the shortest path but also the lexicographically shortest path (where lexicographically is taken to mean the order in which you try out the different paths out from each node). So, essentially I had a complete solution, but I thought it would create the shortest path whose reverse string was lexicographically first (like one of my programs for the TCCC 04 did) so I didn't submit but instead tried to do some rather random hacking around but didn't end up with anything working. Lesson learned, I hope :)

A good score on the 250, or, more likely, a reasonable score on the 250 and a couple of easy challenges, was required to advance.
Saturday, March 4th, 2006
10:22 pm
[kalmakka]
TCO 2006 Round 1
First round had some nice problems, imo. Apparently there were some technical difficulties that I didn't really notice. Something about point values. Anybody want to explain?

350
Basic maximum matching on a graph with 18 vertices. Quite a lot times-out because of forgetting to use DP and just did a recursion. 18 vertices with lots of edges was a nasty input for that. Use a bitmask to represent the communicating vertices and try out any pair of available vertices with an edge in between and see how you can keep on matching.

500
I really didn't see how to do this. It turns out, it just require a bit of serious thinking before you get started.
Say you want to find a k-digit number whose first digit is a that has the desired property. Such a number is then a*10k+b for some b<10k, and the number you get by rotating it is 10*b+a. Setting this ratio equal to p/q and juggling around a bit, you get that b(10d-p)=pa10k-aq which gives you the unique choice for b, provided it exists.
The programming part was easy, as long as you added enough checks, you just had to do the math first. Very good problem.

900
Graph theory, number theory... hey, how 'bout some group theory for the last problem!

The order of an element can be determined by taking the least common multiple of all its cycle lengths. Take (1 2 3 4 5) -> (2 3 1 5 4). It contains a 3-cycle (1 2 3) and a 2-cycle (4 5), so it will have order 6. Notice that since you can always make 1-cycles, there is no point in having cycle lengths with two or more different prime factors, since you could get the same order by having several smaller cycles and some 1-cycles. So c(n,p), the number of orders obtainable using n elements and no prime divisors above p, is equal to c(n,q)+c(n-p,q)+c(n-p2,q)+c(n-p3,q)+... until n-pk < 0, where q is the greatest prime < p.


Congrats to all positive-score earners!
Tuesday, February 28th, 2006
1:03 pm
[larrytc]
Good luck on the TCO, everybody!
Thursday, February 9th, 2006
9:19 am
[dplass]
SRM 288
250

Didn't we just do a "maximum triangle area" problem?

Anyway, three nested loops, make sure they're either all the same, or all different, and then get the area.

What's that? How do you get the area in 3d? Aw crap.

Google points me to http://mathworld.wolfram.com/TriangleArea.html

So I calc the length of each side (in 3d), and screw it up, because I'm using an array instead of x,y,z. That'll teach me...

But I squeaked it out, in only 18 mins.

450

OEIS (http://www.research.att.com/~njas/sequences/index.html) gives me the formula right away but I didn't realize it was a "make change with fewest coins" problem for a little while.

I flailed SO much on this. I knew it was a DP - a really "easy" DP - but I just couldn't figure it out.

Google only pointed me at "simple" DP homework assignments, but no answers! :-(

Finally I found one, and pretty much pasted it into the arena.

Submitted, but then I notice the page I found insisted on having the coins go from largest to smallest, not the other way. I panic, reverse my loop, and resubmit, dang. Turns out I didn't have to.


1000
Yet another DP/probability problem. I assume this is similar to KiloXMan (or whatever it was called - staticentropy you were the writer), plus the twist of calculating the actual probabilities. This is probably just another "layer" of calculations on top of the "find the best order in which to kill all thse enemies". Oh, also there's a graphing component too - how do all these three things interact?
2:13 pm
[july17]
red & blue ?
Redundant Data Access 1 Pops 87.51 $800
Redundant Data Access 2 dfn 86.92 $400

Screening Score Reviewers

    Luca   TheCois  DanLazar
Pops  92.03 80.91 94.78 86.84
dfn 95.27 97.19 67.84 95.72 

TheCois is outstanding reviewer

41,42 КБ 

Thursday, January 19th, 2006
9:31 am
[larrytc]
SRM 283
300 - Sweepline algorithm of some sort. The tricky part is doing the diagonals, of course. I avoid that by rotating the board around the origin, but then I get doubles.

600 - This was an UVa problem. Except for the factorial twist, this is pretty straightforward (if you've done the UVa, I mean.. I didn't.) The thing is to note that a^b % m has a rho function-like kind of thing, so for that, you'll need to find out what b is.. which can be done recursively. The factorial twist doesn't add much to it, if you happen to notice that for any b >= m, b! % m = 0.

1000 - I have no idea how to do this. Looked like it could be done with some sort of inclusion-exclusion, but the intermediate values were way too huge. Also though of some sort of matrix multiplication thing, but couldn't quite come up with it.. ah well.

How did everyone else found the problems?
Wednesday, January 18th, 2006
10:41 pm
[dplass]
TCO
TCO '06 starts tomorrow. Are you ready?
Wednesday, January 11th, 2006
9:15 am
[dplass]
SRM 282
250

Count the # of half tiles, quarters and three-quarters.

Then you gotta guess, because some people thought you could use "leftover" quarters to cover the halves, but I myself did not.

450

This was a cute problem. Too bad the SRM was canclled, as it would've been the first medium I got since August.

Basically, it's fractions and recursion.

1050
I actually didn't read the whole problem; while I was reading it at about 10:08 (7 minutes before coding was to end), the "This SRM will not be rated" message popped up.

I think it would've been DP, being careful with the fractional probabilities.

Hmm, fractions again.
[ << Previous 20 ]
My Website   About LiveJournal.com