----------------------------------- Aidin Kashigar Wed Apr 06, 2005 12:38 pm Congrats to Waterloo ACM team ----------------------------------- Congratulations to Waterloo's ACM team which ended up 4th in the ACM World Finals. If you're interested, the results are posted at http://icpc.baylor.edu/icpc/Finals/default.htm ----------------------------------- jamonathin Wed Apr 06, 2005 12:50 pm ----------------------------------- :clap: :dance: :clap: :dance: :clap: :dance: :clap: :dance: :clap: :dance: :clap: :dance: :clap: Props to Waterloo! ----------------------------------- Tony Wed Apr 06, 2005 1:29 pm ----------------------------------- Those crazy Russian took 1st and 2nd places. Now as a Russian kid attending Waterloo, I have lots and lots of potential :D but lucky for everybody else, I'm lazy :wink: ----------------------------------- Andy Wed Apr 06, 2005 5:43 pm ----------------------------------- :? :? :? err tony, china was number 1, russia was second and third ----------------------------------- thegoose Wed Apr 06, 2005 7:01 pm ----------------------------------- Cool...gj to the Waterloo team :D Chinese ownage again... Aidin...think you and Simon can match that next year? (I presume that you guys will do ACM after going to Waterloo) ----------------------------------- Tony Wed Apr 06, 2005 7:49 pm ----------------------------------- :? :? :? err tony, china was number 1, russia was second and third 1 Moscow State University 2 St Petersburg Institute of Fine Mechanics and Optics 3 University of Waterloo Since when is Moscow State University located in China? :think: ----------------------------------- jamonathin Wed Apr 06, 2005 8:25 pm ----------------------------------- They went there in Rush Hour 2, didn't you see them there tony?... :P ----------------------------------- [Gandalf] Thu Apr 07, 2005 1:49 am ----------------------------------- lol Russians and Chinese always own compsci :D always getting the highest marks... ----------------------------------- thegoose Thu Apr 07, 2005 6:15 am ----------------------------------- 1 Moscow State University 2 St Petersburg Institute of Fine Mechanics and Optics 3 University of Waterloo Since when is Moscow State University located in China? :think: http://icpc.baylor.edu/icpc/Finals/default.htm Rank Name Solved Time 1 Shanghai Jiaotong University 8 1517 2 Moscow State University 7 711 3 St Petersburg Institute of Fine Mechanics and Optics 7 888 4 University of Waterloo 7 1046 It also says on the site entrance that the winning team was Shanghai Jiaotong University. ----------------------------------- Andy Thu Apr 07, 2005 6:38 am ----------------------------------- tony... idunno what ur looking at, but thats not what i see when i go http://icpc.baylor.edu/icpc/Finals/Standings.html ----------------------------------- Tony Thu Apr 07, 2005 8:31 am ----------------------------------- ops, I was looking at a different page :? http://icpc.baylor.edu/icpc/Finals/Scoreboard/index.html ----------------------------------- Martin Thu Apr 07, 2005 11:24 am ----------------------------------- I'm trying to do problem A....damn that's hard... ----------------------------------- Aidin Kashigar Thu Apr 07, 2005 2:24 pm ----------------------------------- well, you're going at it the wrong way. None of the 80 teams successfully solved, or even submitted a solution, to problem A. You might have more luck on problem E or H. ----------------------------------- Martin Thu Apr 07, 2005 2:38 pm ----------------------------------- well, you're going at it the wrong way. None of the 80 teams successfully solved, or even submitted a solution, to problem A. You might have more luck on problem E or H. I found that out after I started. Ahh well, it doesn't seem too bad... For anyone interested, here're the problems. http://icpc.baylor.edu/icpc/Finals/2005FinalsProblemSet.pdf ----------------------------------- thegoose Thu Apr 07, 2005 3:36 pm ----------------------------------- well, you're going at it the wrong way. None of the 80 teams successfully solved, or even submitted a solution, to problem A. You might have more luck on problem E or H. I found that out after I started. Ahh well, it doesn't seem too bad... For anyone interested, here're the problems. http://icpc.baylor.edu/icpc/Finals/2005FinalsProblemSet.pdf The 'simple' solution is easier than you think. This might run into issues with float point but it should get MOST of the points (which is same as none for ACM). I'm not saying this is an easy problem since the ugly case work and the possible float point error. So here it is (please point out if I'm stupid) Several Cases (of the lines in the picture requiring mapping): 1. There are more than 2 horizontal and 1 vertical lines. Pick the lines which each of the 3 segments maps onto. This should determine the shift/magnification uniquely. The rest is trivial (cycle through, binary search). (N^2)M(N+M)log(N+M) calculations. Should run fast if pruned. 2. 1 horizontal and 1 vertical. Should be able to map onto any intersetion point if shrinked by a factor of infinity. 3. Everything is horizontal or everything is vertical Without loss of generality, assume they're vertical Pick the 2 lines and the lines they maps onto. This should give what lines each line map onto and their respective length. Then figure out the 'region' the first line can be in without causing an intersection a horizontal line in the region. If the region exist, a mapping would be possible. This is (N^2)(N+M)log(N+M) 4. All horizontal segment have the same x value and all vertical have the same y-value: There would be a 'focal point'. Map this to all such points on the 'big' picture (NM such points). Then for each segment, find the 'magnification' range for it to map to another segment (aka. check each pair). NMNM=(N^2)(M^2) operations. If at the end, the range exist, then it's doable. This might be a bit slow, but should work out. Overall, the solution works by the idea of 2 lines fixes the transformation ratio, 1 horizontal and 1 vertical fixes the location of the transfer. Time complexity is O((N^2)M(N+M)log(N+M)) with a fairly small factor due to pruning. ----------------------------------- Aidin Kashigar Thu Apr 07, 2005 5:40 pm ----------------------------------- I haven't taken a look at the problem yet so, no opinion as to whether you're right or not. ----------------------------------- bugzpodder Thu Apr 07, 2005 6:26 pm ----------------------------------- IOI ppl arent guarenteed a position on the ACM team just because they come to waterloo ;) if you want guarenteed position, goto Toronto or something ----------------------------------- thegoose Thu Apr 07, 2005 6:41 pm ----------------------------------- IOI ppl arent guarenteed a position on the ACM team just because they come to waterloo ;) if you want guarenteed position, goto Toronto or something I don't think that either me or Aidin ever posted on this forum saying that we're guaranteed a position on the Waterloo ACM team. Howerver, I do believe that we have a good chance of making it if we are to try for the team (Simon's performance on the Waterloo ACM contests is evidence) In many ways, IOI and ACM are different. ACM tends to emphasize more on correctness and speed. It also has more math (stuff like Polya and Burnside). IOI on the other hand requires deeper knowledge into algorithms/data structures and is generally harder (if you don't believe me, go look at IOI'02 Korea). Also, ACM is more team work while IOI requires individual working. ----------------------------------- bugzpodder Thu Apr 07, 2005 6:53 pm ----------------------------------- i never accused you or Aidin of saying anything. there are like 4-5 ppl in waterloo that rank at ~2000 or above on topcoder. I dont see how they wouldnt have a good chance of making the team next year. no need to be coky richard, we all know how good you are. come and join the fun here. ----------------------------------- Aidin Kashigar Fri Apr 08, 2005 8:16 pm ----------------------------------- there are like 4-5 ppl in waterloo that rank at ~2000 or above on topcoder. I dont see how they wouldnt have a good chance of making the team next year. no need to be coky richard, we all know how good you are. come and join the fun here. Initially I thought there were a bunch of people in the 2000+ region from waterloo that might be able to qualify for ACM next year. A quick search gave me 4 people: Adrian Keugel - can't qualify anymore kalmakka - don't know Ralph Furmaniak - can't qualify anymore tmyklebu - again, don't know So there are only 2 people in the 2000+ region from waterloo that might be capable of qualifying. Extending this to the 1700+ ranking, I get only 9 people, at least 3 of which cannot qualify. So, either all the waterloo professional programmers are shy in indicating the university they're studying at or .... I have a good chance of making it to at least the gold team next year based on my topcoder rating right now. Anyways, to make it more interesting, I suggest that bugz offers some amount of Bits (let's say 500 or something) to anyone from CompSci that enters the 2000+ region first (after today of couse, and for the first time) from CompSci and indicates this in this forum. I've been dying to use the shopping feature here but I don't have enough Bits to buy anything interesting, or anything for that matter. ----------------------------------- rizzix Sun Apr 10, 2005 11:54 am ----------------------------------- ehm mods can do that.. just PM one of us, if u have a suggstion.. preferably the Site Content Mods. ----------------------------------- bugzpodder Sun Apr 10, 2005 12:12 pm ----------------------------------- this is such a horrible idea that i didnt even bother answering right now only zylum and Aidin does TC regularly on this board thats fits Aidin's description(i made 2000+ before so i dont count in Aidin's criteria) and frankly, zylum is around 1100 so he'll take two years work at least to climb up to 2000. zylum is already better than almost every other person on compsci so Aidin is saying: I am better than anyone on this board at topcoder so I should get 500 bits from bugzpodder yah, whatever... this is so pointless... programming competitions is not your life you know... you probably wont make a living out of it... Aidin, if you want a *real* challenge, try to beat SnapDragon or tomek... after all, beating zylum or me or rest of compsci isnt too hard now is it? or if you want a more realistic goal, try HappyDude, he's first year from waterloo and he's not bad at all... he even got a higher max rating than me ----------------------------------- Aidin Kashigar Sun Apr 10, 2005 3:38 pm ----------------------------------- I started this topic to congratulate the ACM team on their recent achievement, becoming the North American champions and 4th place overall. Then, the topic was altered to the problems in ACM, which is logical. And then, you come along and change the topic to IOI and Topcoder (two competitions related to ACM) and me and richard (which is totally off subject). Me and Richard might have sounded a little "coky" as you'd like to put it, but that's because of your rather surprising initial post and the two not-so-positive followups. please do us a favour and stop posting negative things about people not having lives, people spending too much time on something, or people sounding arrogant in their posts. it pisses people off and causes a flame war to start. ----------------------------------- bugzpodder Sun Apr 10, 2005 8:48 pm ----------------------------------- whatever... a few things 1) not many cares about ACM here... in fact not many even know what the hell it is 2) I didnt change the topic, Richard did, sort of... Aidin...think you and Simon can match that next year? and I replied, largely as a joke IOI ppl arent guarenteed a position on the ACM team just because they come to waterloo ;) if you want guarenteed position, goto Toronto or something notice the nice ;) sign, indicating a joke, in case someone is slow but richard apparently took it as an insult to IOI ppl or something, I dont know. He dragged you into this. also, it should be common sense that team positions are not given to IOI ppl even in Toronto... you have to earn it So, either all the waterloo professional programmers are shy in indicating the university they're studying at or .... I have a good chance of making it to at least the gold team next year based on my topcoder rating right now. In all honesty, Aidin, I dont doubt your abilities... if you can make the team, great... if you cant, and somehow I made it, I'll consider giving you my position, because I dont really care about ACM, since its just a competition and i am in it for fun. please do us a favour and stop posting negative things about people not having lives, people spending too much time on something, or people sounding arrogant in their posts. it pisses people off and causes a flame war to start. i was going overboard with "getting a life" thing, so i will apologize for that. but being arrogant is not my problem since I am not the one doing it. as for pissing ppl off... its as if you or richard havent pissed me off before. But i dont want to get into this. I shrugged it off instead of taking it seriously and get pissed off whenever someone says or does something a little negative. deal it as you well. btw you are the one who is flaming me. one last thing, c.o.c.k.y is restricted word on compsci... well not really. c.o.c.k is... and c.o.c.k.y. is what you have being, in my opinion. tell me, what exactly did you want with the 500 bits contest?? who did you exactly plan to compete with? what exactly is the point of it? if you can answer that, then i'll retract my previous statements and give you an apology ----------------------------------- Aidin Kashigar Sun Apr 10, 2005 9:19 pm ----------------------------------- well, here are some answers to your many questions :wink: who did I exactly plan to compete with? - well, you. but I guess I screwed that up with the 1st time rule. and I assumed there were more topcoders in this community. what exactly is the point of it? - motivating more people to sign up to topcoder from CompSci and also, motivating myself to pass the 2000 rating finally. Actually, this might have forced Richard to finally compete in topcoder. Oh, wellz :P btw, when is your co-op term, bugz? ----------------------------------- bugzpodder Sun Apr 10, 2005 10:05 pm ----------------------------------- make it 2200 and you are on... 5000 bits. What if i win?? I work for SESI ----------------------------------- Aidin Kashigar Mon Apr 11, 2005 6:55 am ----------------------------------- 5000 bits, eh? Well, we have to get the mods in on this then. cause i'd need a few thousand posts to get that many Bits. ----------------------------------- bugzpodder Mon Apr 11, 2005 9:00 am ----------------------------------- neh... its not like we ever gonna make 2200 anytime soon anyways... not in 12 months i predict. ----------------------------------- Martin Mon Apr 11, 2005 3:01 pm ----------------------------------- Alright, Iet me in on this too. Right now my rating on TopCoder is slightly less than one fifth of four. I can provide the bits. Also, if it follows bugz's 12 month prediction, bits should be actually useful by then. ;) ----------------------------------- MysticVegeta Tue Jul 12, 2005 10:15 am ----------------------------------- You guys ever considered the geniuses from KCI? So many, Simon, Bill, etc. Simon is in top 3 in Canada for the CCC contests, also he has a place in the top 50 math rankings across Canada. By the ways, what happened to Vassili? ----------------------------------- thegoose Mon Aug 22, 2005 9:02 am ----------------------------------- You guys ever considered the geniuses from KCI? So many, Simon, Bill, etc. Simon is in top 3 in Canada for the CCC contests, also he has a place in the top 50 math rankings across Canada. By the ways, what happened to Vassili? Simon doesn't do topcoder, but he was first on CCC for the past 2 years. Vassili graduated last year.