Hey Drew. I am a SPOJ user too. Although, I don't use it much nowadays. I am more into other stuff (like doing the Iranian Olympiad, and the Bulgarian one for fun
)Computer Science Canada any SPOJ users? |
| Author: | saltpro15 [ Wed May 27, 2009 11:48 am ] |
| Post subject: | any SPOJ users? |
Hey guys, I'm going to hope this thread is in the right forum. Anyone here do the SPOJ's? I know Hanson's on there but he's not on this forum. I forgot my account/password a while ago, so my new ID is dr3w. I find the difficulty of them to be rather high, and some of the questions are translated from other languages to English, making them a little odd to understand. |
|
| Author: | bbi5291 [ Wed May 27, 2009 12:30 pm ] |
| Post subject: | Re: any SPOJ users? |
Sure, I have almost as many problems solved as Hanson, although he solves much harder problems than I (accounting for the discrepancy in score). One of the nice things about SPOJ is that you can look at the solved problems lists of other users. So pick a user such that you know you're better than him (her), and solve all the problems on their solved problem list. (I did this A LOT in my earlier days in SPOJ.) Also, you can sort the problem list by number of users who have solved it. If you need help, post on the SPOJ forum: http://spoj.pl/forum . Note on I/O: eschew cin >> and cout << , they're SLOW. Actually, more specifically: * If you're not going to R/W more than around 10KB-100KB of data, they are acceptable (but I can assure you that you'll get in the habit of not using them). However, TLE often occurs when you try to read 1MB of data or that sort of thing. * You can use cin.sync_with_stdio(false) if you are going to use only cin functions and not touch stdin (even indirectly through calls such as scanf, which have an implied stdin). The same applies for cout/stdout. This seems to be anywhere from 1.5 to 2 times slower than scanf/printf themselves currently. (In the newest version of g++ this is faster, which it should be, since cin/cout use overloaded operator selection at compile time and scanf/printf determine types at runtime - but SPOJ doesn't have this version yet.) As you might guess by the name sync_with_stdio, if you use stdio functions when this is false, you'll get strange results, as cin/cout and stdin/stdout won't be synchronized. * getline has acceptable speed. (cin.getline does too, but it writes to a C string, and if that's what you want, why not just use gets?) * cin.read() and cout.write() are fast but offer no distinct advantage over their corresponding stdio functions fread and fwrite. (Also, you almost never want to use those functions except when trying to get the best runtime on the ranklist.) |
|
| Author: | saltpro15 [ Wed May 27, 2009 12:35 pm ] |
| Post subject: | RE:any SPOJ users? |
ah, I see. Thanks Brian. Can you recommend any problems for a beginner to SPOJ? |
|
| Author: | A.J [ Wed May 27, 2009 12:36 pm ] |
| Post subject: | RE:any SPOJ users? |
Hey Drew. I am a SPOJ user too. Although, I don't use it much nowadays. I am more into other stuff (like doing the Iranian Olympiad, and the Bulgarian one for fun ) |
|
| Author: | saltpro15 [ Wed May 27, 2009 12:54 pm ] |
| Post subject: | RE:any SPOJ users? |
cool A.J. I like SPOJ for the fact that I can test my code at anytime, and there's a helpful forum. But the questions are in random order, and it's hard to find one's that aren't very difficult... care to recommend any? |
|
| Author: | Analysis Mode [ Wed May 27, 2009 2:19 pm ] |
| Post subject: | Re: any SPOJ users? |
yes, I use SPOJ too. you can find me here on the Canadian rankings page. Note: this list is bbi5291's. For easy to code and easy to solve problems, ADDREV ARITH ARMY CANDY CANDY3 CPRMT CUBES DIVSUM FASHION FAVDICE GNY07A GNY07B HANGOVER KROW NSTEPS OFFSIDE PERMUT2 POKER PQUEUE STPAR TOANDFRO TOE1 TOE2 TWOSQRS WSCIPHER for easy to code, but perhaps more mathematically challenging ARCTAN ARRANGE BAISED BINSTIRL BMJ CANTON CATM DRINK EASYPROB EIGHTS EQBOX FAVDICE FCTRL HUBULLU ICODER LEONARDO MINCOUNT NGM POLYGAME QUADAREA STONE TCOUNT2 TCOUNT3 TRICOUNT TRICENTR as for harder problems, I highly recommend this link |
|
| Author: | bbi5291 [ Wed May 27, 2009 2:28 pm ] |
| Post subject: | Re: any SPOJ users? |
Also, here's a list of SPOJ problems that involve DP. Analysis Mode may be able to provide more, as he's been keeping up with new problems better than I have. Warning: Several of these problems are non-trivial. LEXBRAC, for example, requires a great deal of thought (you can find hints on my blog for this problem if you get really stuck.) For the most part though, hard DP problems are hard to come by, and on a difficult archive such as SPOJ, they are comparatively rare. Most SPOJ problems are fairly ad hoc, if truth be told. ACODE AIBOHP BYTESM2 CHOCOLA GNY07H INUMBER LEXBRAC (requires bignums) LSORT MBEEWALK MINUS MIXTURES MTILE MUSKET ROCK SQRBR SUMITR (warning source code limit, requires hax) THREECOL TRT TWENDS There are also harder ones that I have not solved, such as AEROLITE. |
|
| Author: | saltpro15 [ Wed May 27, 2009 3:14 pm ] |
| Post subject: | RE:any SPOJ users? |
have any of you done fctrl2? I can't think of any way to represent 100! in C++. Would python be more suitable? |
|
| Author: | DemonWasp [ Wed May 27, 2009 3:53 pm ] |
| Post subject: | RE:any SPOJ users? |
You can't think of any way to represent 100 factorial in C++? How about your own custom integer type? You'd just have to define arithmetic operations on it. |
|
| Author: | Analysis Mode [ Wed May 27, 2009 7:36 pm ] |
| Post subject: | Re: any SPOJ users? |
You have to code your own bignum multiplication, using strings. edit: don't bother learning some python just to do this problem. coding up bignums yourself will be helpful in the future, and in more complex problems for which you don't want to use python. |
|
| Author: | bbi5291 [ Wed May 27, 2009 8:35 pm ] |
| Post subject: | Re: any SPOJ users? |
Analysis Mode hasn't actually solved this problem, I notice. Advice: When you're coding up your bignums, create a class so you can re-use this code for future SPOJ problems. Also, don't store the bignums as strings. Why? Well, storing as strings sure makes it easy to read them in and print them out. However, if you do this, you're effectively treating each number as a sequence of individual digits. Let's say you want to add two 1000-digit bignums together, then 1000 operations are required. On the other hand, if you store them in a vector or list with, say, 4 digits per element, you only need to do 250 operations. With the naive method of multiplying numbers, time taken is O(N^2). So in this case your multiplication would become 16 times faster! Also, notice that in this problem you'll never multiply by anything greater than 100. Using the multiple-digits-per-record representation simplifies this greatly, because you can simply start at the end and multiply, then shift one record left, carry, and multiply again, and so on, rather than having to iterate through the two digits as well if you mutiply by a two-digit number. |
|
| Author: | saltpro15 [ Thu May 28, 2009 5:57 pm ] |
| Post subject: | RE:any SPOJ users? |
I'm a little confused as to how the scores work... I've solved 3 classical and 3 challenge problems, yet they aren't showing up, and my score hasn't changed. Anyone know why? |
|
| Author: | bbi5291 [ Thu May 28, 2009 6:27 pm ] |
| Post subject: | Re: any SPOJ users? |
The scoring works as follows: For solving a classical problem you earn 80/(40+N) points, where N is the number of users (including yourself) that have solved it. So if a lot of people have solved a particular problem, you won't get a lot of points for it. The top scorer in a challenge problem earns 3 points. If higher scores are better, your score will be 3 * (your score) / (high score). If lower scores are better, your score will be 3 * (high score) / (your score). Also, challenge problems don't show up on your solved problem list. Tutorial problems don't contribute to your score or show up on your solved list - they are exactly that, tutorials. And partial problems don't count for points either, although that may change, who knows. In the classical problemset listing hover your mouse over the link in the Users column and alt-text should appear telling you how many points you would get for solving that particular problem. Problem ranklists: * Classical and tutorial problems - you appear in the ranklist as long as you got an Accepted status. Entries are sorted first in increasing order of time and then in increasing order of date. * Challenge problems - you appear in the ranklist as long as you didn't get an error, such as Wrong Answer, Time Limit Exceeded, or Runtime Error. The list is sorted first by score and then by date (and not by time). The same goes for partial score problems. You don't get any points for having a solution faster than somebody else's - you just get glory. |
|
| Author: | saltpro15 [ Sat May 30, 2009 8:56 pm ] |
| Post subject: | RE:any SPOJ users? |
I see, thanks Brian. edit : woo! 87th:D hopefully be top 70 after this summer |
|
| Author: | Analysis Mode [ Sun May 31, 2009 8:14 pm ] |
| Post subject: | Re: any SPOJ users? |
@bbi5291: It's M3TILE, not MTILE Other DP problems, off the top of my head and searching dynamic programming on the forums. DTT JEDNAKOS PIGBNK ININT SEQPAR PERMUT1 |
|
| Author: | saltpro15 [ Wed Jul 08, 2009 9:54 pm ] |
| Post subject: | RE:any SPOJ users? |
I'm working on MARBLES now, is this supposed to be done dynamically? I'm coding it recursively and getting SIGSEV, am I not allowed to have an array of long longs? |
|
| Author: | aramadia [ Wed Jul 08, 2009 10:27 pm ] |
| Post subject: | Re: any SPOJ users? |
I'm pretty sure this is straight forward combinatorics. Think factorial. |
|
| Author: | bbi5291 [ Thu Jul 09, 2009 11:32 am ] |
| Post subject: | Re: any SPOJ users? |
Of course you can have an array of long longs. If that was not allowed, you'd have a compile error, not a runtime error. I am pretty sure that you can have an array of any type, built-in or defined, except void, but that's pretty obvious since you can't actually declare a scalar of type void anyway. Of course, if you declare an array of size 1000000x1000000, you will get a runtime error. Not sure if it's SIGSEGV though, I thought it was "runtime error (other)" on SPOJ. Examine the number 475020 given in the sample output. Notice anything special about it? |
|
| Author: | saltpro15 [ Thu Jul 09, 2009 11:34 am ] |
| Post subject: | RE:any SPOJ users? |
hehe... well I found it that it requires a very large amount of memory to run, far more than the 200 odd MB given on SPOJ. I'm not sure what you mean about special... |
|
| Author: | bbi5291 [ Thu Jul 09, 2009 7:44 pm ] |
| Post subject: | Re: any SPOJ users? |
OK, I forgot that arrays of references are illegal... although, I've never had to explicitly declare a reference before, I only use them for passing-by-reference... By "special", I mean that if you knew what set it apart from, say, 475021, you'd be able to solve the problem with comparative ease  |
|
| Author: | saltpro15 [ Mon Jul 27, 2009 10:56 am ] |
| Post subject: | RE:any SPOJ users? |
Woo, I'm up to 27th! Analysis Mode, I'm coming for you |
|
| Author: | Analysis Mode [ Mon Jul 27, 2009 2:36 pm ] |
| Post subject: | Re: any SPOJ users? |
Are you declaring war on me? I haven't been coding for almost three months now. Your challenge just might be the impetus for me to start coding again. Yeah, good job, if you can get to where I am in two months, then we'll talk. If you'll take a look at my submissions page, March 1, 2009 is when I kicked my ass into gear. May 7, 2009 is when I took it down a notch. |
|
| Author: | saltpro15 [ Mon Jul 27, 2009 2:38 pm ] |
| Post subject: | RE:any SPOJ users? |
lol it was a joke. I'm taking a break from SPOJ as soon as I finish 3 more anyways. edit: I noticed you've solved BYTESM2, did you did it with graph theory or dynamically? |
|
| Author: | saltpro15 [ Mon Aug 10, 2009 9:02 pm ] |
| Post subject: | RE:any SPOJ users? |
alright Analysis, I don't think I'm going to catch up to you for a while... You said 2 months right? Well, I'm at a month and 3 weeks now. I'll settle for catching this Jacob Plachta guy 
SPOJ is somewhat frustrating after being spoiled by DWITE with it's hundred-points-a-question system 
edit : I've noticed CCC stage 1 problem S5 Wireless is on SPOJ now, I'm surprised only 8 people have solved it... |
|
| Author: | Analysis Mode [ Mon Aug 10, 2009 11:45 pm ] |
| Post subject: | Re: any SPOJ users? |
lol, interesting comparison, spoj vs. dwite? p.s. jacob also went to Stage 2, he's from woburn too. BYTESM2 is a classic DP problem, so yes, i did use DP. Specifically, if you were to graph out the grid (i.e. assign a number to every point and draw out the graph), you'd find it to be a directed acrylic graph, in which there are no cycles. This situtation applies to all DP problems, as it ensures that the answer you've found so far is optimal (As you can't go backwardS). |
|
| Author: | saltpro15 [ Tue Aug 11, 2009 9:35 am ] |
| Post subject: | RE:any SPOJ users? |
why does it not surprise me that he's also from Woburn : P . I noticed Woburn CI has a higher school ranking than the University of Waterloo
TO-DO: FPOLICE (Dijkstra's with PQ) |
|
| Author: | Analysis Mode [ Tue Aug 11, 2009 11:26 am ] |
| Post subject: | Re: any SPOJ users? |
yeah, well if I was my own institution, i'd be above MIT. And before you do FPOLICE, code up straight Dijkstra's. Test your code with the spoj tutorial problem EZDIJKST. |
|
| Author: | saltpro15 [ Tue Aug 11, 2009 8:02 pm ] |
| Post subject: | RE:any SPOJ users? |
Thanks Analysis Mode. Do you know any other problems similar to BYTESM2 by chance? |
|
| Author: | Analysis Mode [ Tue Aug 11, 2009 9:49 pm ] |
| Post subject: | Re: any SPOJ users? |
I don't, actually. Oh, and stop looking for easy problems like this |
|
| Author: | saltpro15 [ Tue Aug 11, 2009 9:51 pm ] |
| Post subject: | RE:any SPOJ users? |
alright, it was worth asking
never mind... |
|
| Author: | bbi5291 [ Thu Aug 13, 2009 2:50 pm ] |
| Post subject: | Re: any SPOJ users? |
Analysis Mode @ Tue Aug 11, 2009 11:26 am wrote: yeah, well if I was my own institution, i'd be above MIT.
Actually this is not true. MIT has a total of 23.51 (I don't know why it's so low, anyway) and you have 20.5 points. Before talking about how good you are, make sure you at least know what you're talking about... Also, Guru should've listed his institution as Waterloo, but never did. With him, they'd be above Woburn. And Hanson is going to Waterloo, so... Anyway, KRUSKAL isn't really bad. Although, not easy on beginners, that I will admit. Also, look at the problems on my easy problem list! They should all be within your reach. |
|
| Author: | Analysis Mode [ Thu Aug 13, 2009 2:55 pm ] |
| Post subject: | Re: any SPOJ users? |
Actually, there's one called "Massachusetts Institute of Technology" Rank 233. I was looking at that one. |
|
| Author: | Analysis Mode [ Thu Aug 13, 2009 2:56 pm ] |
| Post subject: | Re: any SPOJ users? |
And how'd IOI go for the CAnadian team? |
|
| Author: | bbi5291 [ Thu Aug 13, 2009 3:36 pm ] |
| Post subject: | Re: any SPOJ users? |
Partial results. Notes: * hpmv is Robin and Foundation is Peter. * Henadzi Karatkevich is Gennady Korotkevitch * Kazuhiro Hosaka was very close to pulling off an IMO/IOI double first (a.k.a. a "Reid Barton") * The results of the Polish team are not known at the time of this posting (but of course we should expect them to be good). * Hanson is most likely getting gold, Robin and I silver, Peter bronze * Goran Zuzic (also known as Zuza) is not getting a gold :O |
|
| Author: | A.J [ Thu Aug 13, 2009 4:54 pm ] |
| Post subject: | RE:any SPOJ users? |
wow, I am gone for 2 months, and a lot of you have already started SPOJ and have done quite a few problems! (I am referring to SaltPro15 =) ) good job I'll probably not do SPOJ for a while, as I am training for CMO (well, I have an IMO compendium that I am practicing off of) so Il'l probably lay off the CS for a while good job Brian! I am proud and happy for all you guys =) keep up the good work (and I hope we meet sometime ) |
|
| Author: | saltpro15 [ Thu Aug 13, 2009 7:45 pm ] |
| Post subject: | RE:any SPOJ users? |
well I beat [PROTOTYPE] and there's no other good 360 games this summer... so CS became the plan . Congrats Brian and the rest of Canada's IOI Team |
|
| Author: | saltpro15 [ Fri Aug 21, 2009 3:42 pm ] |
| Post subject: | RE:any SPOJ users? |
alright Analysis Mode, I have a challenge for you. When I get up to 20.2 points (same as you) want to see who can amass the most points before November 1st? I'll wait until the first day of school to get to 20.2 points though... edit : and what the hell is your optimization for FCANDY? I've been at this for 2 hours and I've TLE'd 4 times   |
|
| Author: | Analysis Mode [ Fri Aug 21, 2009 8:12 pm ] |
| Post subject: | RE:any SPOJ users? |
Not bad, you've done quite a bit in a short while. As for your challenge, it might be kind of difficult. I'll be simultaneously juggling my SAT's, US university apps as well as my other academic interests (biology, computer science, math) and some squash. CS might very well take a backseat role in my schedule until January 2010. |
|
| Author: | saltpro15 [ Fri Aug 21, 2009 8:16 pm ] |
| Post subject: | RE:any SPOJ users? |
well, any time between now and June of 2011 works for me
edit : is there something wrong with the test data for KRUSKAL? I've tried a few approaches then given up and submitted the sample solution and even THAT still gives Time Limit Exceeded... edit edit : and what for god's sake is this optimization for FCANDY?! I'm going insane here |
|
| Author: | Analysis Mode [ Fri Aug 21, 2009 8:18 pm ] |
| Post subject: | Re: any SPOJ users? |
For FCANDY, your code's O(N*S). Not sufficient to pass the time limit and at the CCC, the time limit was 6 seconds max for each case. You'd receive 19/25 with your solution (provided you coded the DP correctly). Here's the hint: You're performing a lot of unnecessary sweeping through your DP array. |
|
| Author: | saltpro15 [ Fri Aug 21, 2009 8:26 pm ] |
| Post subject: | RE:any SPOJ users? |
ok, thanks. I'll see what I can do. On an unrelated topic... my goal this year is to make the Stage 2 cut off. Anyone care to recommend algo's/techniques to learn? So far I can handle Basic DP and 2D DP Dijkstra's with or without a PQ Floyd Warshall DFS Combinatorics |
|
| Author: | bbi5291 [ Fri Aug 21, 2009 9:11 pm ] |
| Post subject: | Re: any SPOJ users? |
@Analysis Mode: I do not believe that your SATs can be that difficult. How much is there to study, anyway? I am merely going to brush up a bit on physics (it's one year only) and practice writing the essay, that should prepare me for SAT 1 and the math II, physics, and chem subject tests. You surely can't be far behind. There's nothing wrong with the input for KRUSKAL, but it is a rather finicky problem. I had to submit it 25 times to get AC, I think. The method I used to check for primes was to precompute primes up to 2^16 and then do trial division using these primes. After that the general case is similar to Nim, but watch out! There are lots of corner cases! Be prepared to spend easily an hour debugging! (Hint: the test data is available online.) |
|
| Author: | saltpro15 [ Fri Aug 21, 2009 9:17 pm ] |
| Post subject: | RE:any SPOJ users? |
well, FCANDY has priority right now, but thanks for the tips Brian! Analysis Mode, I will assume you're in gr11 or higher then? Since you're preparing for SAT's and such. Don't think of me as a creep, I just want to know who's competition for CCC 2011
edit : why does everything sound sarcastic when written online? |
|
| Author: | bbi5291 [ Fri Aug 21, 2009 9:23 pm ] |
| Post subject: | Re: any SPOJ users? |
He and I are in the same grade. That is, our grade 12 year is upcoming. I suggest the USACO training webpages. If you can finish the first two chapters, you should be pretty ready for stage 1. Although, I don't think that could've prepared anyone for Wireless, just judging based on how few people actually solved it. That brings up an interesting point: make sure that if you can't solve a problem completely, that you submit a dumb solution and get partial marks for it. USACO does not encourage this, because you have to solve a problem completely in order to move on - but it is very important in CCC and IOI. On an unrelated note, your post count has reached 666 |
|
| Author: | saltpro15 [ Fri Aug 21, 2009 9:28 pm ] |
| Post subject: | RE:any SPOJ users? |
so it has, so it has
I've started USACO this past month, and I'm currently on chapter 1.3 problem Mixing Milk. These are a LOT harder than SPOJ, holy $#!T... I think it's worth learning bit XOR'ing too, I'm looking into it |
|
| Author: | Analysis Mode [ Sat Aug 22, 2009 7:55 pm ] |
| Post subject: | Re: any SPOJ users? |
bbi5291 @ Fri Aug 21, 2009 9:11 pm wrote: @Analysis Mode: I do not believe that your SATs can be that difficult. How much is there to study, anyway?
I am merely going to brush up a bit on physics (it's one year only) and practice writing the essay, that should prepare me for SAT 1 and the math II, physics, and chem subject tests. You surely can't be far behind. When I say, prepare for SAT, I do mean, 2370+. That means at most 2 or 3 mistakes as possible. And trust me, after about a month of study (every other day, 1-2 hours per day), I still need a bit more time before I can do that. Not to mention there's a serious time crunch on all the sections. Mathwise, it's softings. As for the other stuff: most of the time, using your ear for the language helps, but in some cases, it helps to know specific grammar rules. Knowing those rules, of course, helps you write more gramatically perfect essays in English class.
When the school year comes around, I'll show you my SAT book. Would you like to bet (for fun) that you won't get higher than 2250 (which is still Ivy League competitive, I think) on the SAT without preparing for anything other than the essay? However, I haven't starting writing those application essays yet, which is unfortunate as I intended to finish both this summer (and further refine them until I send in my application). |
|
| Author: | bbi5291 [ Sun Aug 23, 2009 10:11 am ] |
| Post subject: | Re: any SPOJ users? |
Actually, at 2-3 mistakes per section, you'd get 2400. I'm pretty sure. The same applies for the subject tests - just 2 or 3 mistakes should be 800. Too bad we don't have anything meaningful to bet. But anyway - are you saying that the SATs are not as easy as I think they are, or are you saying I'm not as good as I think I am? I will openly admit that I am nowhere near world-class in either math or physics -- but then again, this is not the IPhO we're talking about here. |
|
| Author: | Analysis Mode [ Sun Aug 23, 2009 11:33 am ] |
| Post subject: | RE:any SPOJ users? |
No, I'm pretty sure one mistake on the SAT will cost at least 10 points. Grading for the SAT II depends upon the performance of others, but the SAT doesn't. |
|
| Author: | bbi5291 [ Sun Aug 23, 2009 1:21 pm ] |
| Post subject: | Re: any SPOJ users? |
hmm OK, I see... but how are the raw scores converted into scaled scores for SAT I? I can't seem to find the algorithm online... doesn't it vary between sessions? If so, are you sure they don't take into account the overall score distributions? |
|
| Author: | Cyril [ Sun Aug 23, 2009 1:50 pm ] |
| Post subject: | RE:any SPOJ users? |
I've heard that making 5 mistakes on Math II or 8 mistakes on the physics one would still yield a perfect 800. |
|
| Author: | Analysis Mode [ Sun Aug 23, 2009 6:12 pm ] |
| Post subject: | Re: RE:any SPOJ users? |
Cyril @ Sun Aug 23, 2009 1:50 pm wrote: I've heard that making 5 mistakes on Math II or 8 mistakes on the physics one would still yield a perfect 800.
Something like that. However, you should rephrase "would still yield" to "could still yield". According to the 06-07 Physics prep book by Kaplan, it said that on a recent administration of the exam, getting 12 wrong was still enough to yield 800. |
|
| Author: | saltpro15 [ Tue Aug 25, 2009 9:50 pm ] |
| Post subject: | RE:any SPOJ users? |
alright, I've read this problem several times now, and I'm not sure what it's asking. Poor translations are annoying... Seems like graph theory to me. Construct a graph of the boys and girls and check for vertex connectivity. Could possibly be done with DP too. Opinions? edit : Just because I'm posting online, doesn't mean I have to throw punctuation out the window. My English teacher would come at me with a katana if he read half of my posts... |
|
| Author: | Analysis Mode [ Tue Aug 25, 2009 10:36 pm ] |
| Post subject: | RE:any SPOJ users? |
My first thought was max flow. |
|
| Author: | saltpro15 [ Wed Aug 26, 2009 9:15 am ] |
| Post subject: | RE:any SPOJ users? |
I've heard of that, I haven't really learned how to code it yet edit : Oh, so it seems only 9 people in the world have solved this. Forget it then... |
|
| Author: | bbi5291 [ Wed Aug 26, 2009 10:13 am ] |
| Post subject: | Re: any SPOJ users? |
It's minimum edge cover in a sparse graph. Each girl is a vertex, each boy is an edge connecting the vertices of the two girls to which he is willing to give presents. We want to select some subset of the edges of minimal size such that each vertex is incident upon at least one of the edges in the set (that is, we want to select as few boys as possible so that each girl gets at least one present). This may be solved in O(E * sqrt(V)) time by finding a maximum matching with Edmonds' algorithm (btw: Jack Edmonds was at UW from 1969 to 1999, except from 1991-1993) and then adding one edge for each vertex left out of the matching. Edit: The publication outlining the O(E * sqrt(V)) method requires a subscription to view. (This is really annoying.) I guess you can find the algorithm at http://www.eecs.berkeley.edu/~karp/greatalgo/lecture05.pdf and http://www.eecs.berkeley.edu/~karp/greatalgo/lecture06.pdf - but I'm not sure how easy it is to understand (let alone to code) |
|
| Author: | A.J [ Wed Aug 26, 2009 6:38 pm ] |
| Post subject: | RE:any SPOJ users? |
hmm...well done brian I wasn't aware that this algorithm had been credited to Edmonds, as I hav seen this problem before. |
|
| Author: | bbi5291 [ Wed Aug 26, 2009 7:16 pm ] |
| Post subject: | Re: any SPOJ users? |
Are you serious? You actually knew that algorithm? I had to look it up! I'm scared now  |
|
| Author: | A.J [ Wed Aug 26, 2009 9:28 pm ] |
| Post subject: | RE:any SPOJ users? |
Well, I had initially looked it up too. |
|
| Author: | saltpro15 [ Wed Aug 26, 2009 9:31 pm ] |
| Post subject: | RE:any SPOJ users? |
umm, don't all algorithms have to be looked up? Or does stuff like Dijkstra's just pop into code gurus heads? |
|
| Author: | Analysis Mode [ Wed Aug 26, 2009 9:42 pm ] |
| Post subject: | RE:any SPOJ users? |
Oh, from a layman's point of view, Dijkstra's algorithm makes sense. It is a greedy algorithm and if you told random passersby on the street to figure out a method of finding shortest distance between two points, the greedy way would be what they'd come up with. Better question, A.J. and Brian: any of you coded it before? |
|
| Author: | bbi5291 [ Wed Aug 26, 2009 9:46 pm ] |
| Post subject: | Re: RE:any SPOJ users? |
saltpro15 @ Wed Aug 26, 2009 9:31 pm wrote: umm, don't all algorithms have to be looked up? Or does stuff like Dijkstra's just pop into code gurus heads?
Touche. What I meant is that I was impressed that he knew this algorithm before having read this problem (that is, he looked it up before.) @ Analysis Mode: You overestimate random passersby
And no, I have never coded this algorithm, and it's really too difficult even for IOI level so it'll be a while before I get around to coding it. I mean, it's not in the Algorithms text by Sedgewick, even. (Edit: this forum doesn't accept e with an acute accent on it >.<) |
|
| Author: | saltpro15 [ Wed Aug 26, 2009 9:49 pm ] |
| Post subject: | RE:any SPOJ users? |
ah I see. btw has anyone taken a look at that new SPOJ problem about determining points in a triangle? |
|
| Author: | bbi5291 [ Thu Aug 27, 2009 8:15 am ] |
| Post subject: | Re: any SPOJ users? |
It would be quite trivial if the third vertex of the triangle was guaranteed to be on a lattice point (Pick's theorem), but as it isn't, things get a bit more complicated. I'll work on it... |
|
| Author: | A.J [ Thu Aug 27, 2009 8:50 am ] |
| Post subject: | RE:any SPOJ users? |
@Brian - Alas, this algorithm floats above the realm of my capability...but one day I intend on using it. @saltpro15 - what is the problem code? |
|
| Author: | bbi5291 [ Thu Aug 27, 2009 9:54 am ] |
| Post subject: | Re: any SPOJ users? |
http://www.spoj.pl/submit/GPINTRI |
|
| Author: | Cyril [ Thu Aug 27, 2009 10:16 am ] |
| Post subject: | RE:any SPOJ users? |
I've got an okay heuristic solution for that GPINTRI problem- I don't know if it'll handle T = 100000. But, first, Mr. Mode, I don't see enough of a problem with my wording to be singled out. At least floor(b/a) x increments are needed for one y increment, so a straightforward walk along the line, sort of like the circle-walking in Project Euler 210, should suffice. That's the somewhat obvious algorithm for this, but here's a heuristic. Let N = the point (n, an/b), which is the third vertex of the triangle. Let O = the origin. Find the point L = the last lattice point on y = ax/b that before N. Drop a perpendicular to the x-axis: call this L'. Find the point P = the first lattice point on y = ax/b after N. Likewise, P'. Decide on whether L or P is closer to N. If L is closer, use Pick's theorem to find the number of points in OLL'. If P is closer, same thing for OPP'. In either case, you're left with a quadrilateral composed of a rectangle and a right triangle. After chopping away that rectangle, run the incremental walking thing on that annoying remaining non-lattice point triangle. I'll do it later- I'm hungry. |
|
| Author: | A.J [ Thu Aug 27, 2009 4:12 pm ] |
| Post subject: | RE:any SPOJ users? |
hey Cyril, the PE problem comes out tomorrow morning at 8 AM (our time). Are you going to attempt it then? |
|
| Author: | bbi5291 [ Thu Aug 27, 2009 4:33 pm ] |
| Post subject: | Re: any SPOJ users? |
You guys are in a different time zone? |
|
| Author: | A.J [ Thu Aug 27, 2009 5:34 pm ] |
| Post subject: | RE:any SPOJ users? |
No, but I just wanted to say that it is 8 AM EDT, and not GMT. |
|
| Author: | Analysis Mode [ Thu Aug 27, 2009 5:37 pm ] |
| Post subject: | Re: RE:any SPOJ users? |
Cyril @ Thu Aug 27, 2009 10:16 am wrote: But, first, Mr. Mode, I don't see enough of a problem with my wording to be singled out.
What are you talking about? |
|
| Author: | saltpro15 [ Thu Aug 27, 2009 8:28 pm ] |
| Post subject: | RE:any SPOJ users? |
For you math people, I've found another interesting problem |
|
| Author: | A.J [ Thu Aug 27, 2009 11:03 pm ] |
| Post subject: | RE:any SPOJ users? |
I believe all we need for this problem is P.I.E (in more ways than one) |
|
| Author: | Analysis Mode [ Thu Aug 27, 2009 11:26 pm ] |
| Post subject: | Re: RE:any SPOJ users? |
saltpro15 @ Thu Aug 27, 2009 8:28 pm wrote: For you math people, I've found another interesting problem
Uh no, it's not a math problem. I seem to recall someone (I think it was Hanson or bbi5291) mentioning that voronoi diagrams are needed. Not at all trivial to code. |
|
| Author: | A.J [ Thu Aug 27, 2009 11:34 pm ] |
| Post subject: | RE:any SPOJ users? |
hmm... Voronoi diagrams are useful when finding the largest circle in a set of points (or a polygon), but I think that might be jumping the gun here. I believe that PIE is too inefficient for this problem, though I believe there are other ways to go about this problem apart from using voronoi diagrams. |
|
| Author: | bbi5291 [ Fri Aug 28, 2009 10:41 am ] |
| Post subject: | Re: any SPOJ users? |
I think PIE would have a worst-case time complexity close to O(2^n). That being said, I think a more sophisticated approach would be in order. I posted a problem on the PEG Judge which required you to compute the perimeter of a union of circles. First we consider that problem. We can find the perimeter of the entire union by determining what amount of perimeter is contributed by each circle. To this end, we consider each circle in turn, and use line sweep. The details are left to you, of course. (If you want to code it, feel free to request an account on the PEG judge; the problem is called "detectors".) It turns out we can do the same with area. Consider the general case of two intersecting circles (that is, they are not tangent). If we draw a line through the two points of intersection, this divides the union of the two circles into two segments! Each segment "belongs" to one of the circles. If we add up the areas of the two segments, we get the area of the whole union! In general what you can do is, for each circle, consider all possible lines drawn through two intersection points of this circle with another circle (it has to be the same circle for both points, if that wasn't clear). These lines fence off a "cell" which is "owned" by that circle. By adding the areas owned by each circle, you obtain the area of the circle union. As n = 50 at worst, there is room for some slack. The reason I mentioned the Laguerre Voronoi diagram (also called a power diagram, although the latter may be more general) is because computing it solves this problem (almost, you still have to find the area of the intersection of each circle with its cell). Define the Laguerre distance of point P from circle C with center O and radius r to be sqrt(d^2 - r^2) where d is the Euclidean distance from P to O. (When P is outside C, this is the length of the tangent from P to C; this is trivial to prove with that well-known theorem whose name seems to be a subject of disagreement.) Now the Laguerre Voronoi diagram is constructed similarly to the Voronoi diagram, except that now the distance metric used is the Laguerre one. Incredibly, Laguerre cells are still convex polygons (or polyhedra, in the more general case of higher dimensions) and, for a given pair of intersecting circles, there is a line (or line segment, or ray) in the Laguerre Voronoi diagram that passes through their points of intersection; if they are disjoint, the corresponding line is outside both circles. The proof is left as an exercise for the reader. |
|
| Author: | A.J [ Fri Aug 28, 2009 1:18 pm ] |
| Post subject: | RE:any SPOJ users? |
I was considering a variant on Fortune's algorithm as a possible building block to the overall structure that is this problem. Although, the maintaining of a sweep line and a beach line seem redundant (and maybe a bit meaningless). Thanks for that bit of insight, Brian. |
|