any SPOJ users?

Analysis Mode · **Posted:** Sat Aug 22, 2009 7:55 pm

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 Very Happy

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

bbi5291 · **Posted:** Sun Aug 23, 2009 10:11 am

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.

Analysis Mode · **Posted:** Sun Aug 23, 2009 11:33 am

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.

bbi5291 · **Posted:** Sun Aug 23, 2009 1:21 pm

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?

Cyril · **Posted:** Sun Aug 23, 2009 1:50 pm

I've heard that making 5 mistakes on Math II or 8 mistakes on the physics one would still yield a perfect 800.

Analysis Mode · **Posted:** Sun Aug 23, 2009 6:12 pm

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.

saltpro15 · **Posted:** Tue Aug 25, 2009 9:50 pm

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

Analysis Mode · **Posted:** Tue Aug 25, 2009 10:36 pm

My first thought was max flow.

saltpro15 · **Posted:** Wed Aug 26, 2009 9:15 am

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

bbi5291 · **Posted:** Wed Aug 26, 2009 10:13 am

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)

A.J · **Posted:** Wed Aug 26, 2009 6:38 pm

hmm...well done brian

I wasn't aware that this algorithm had been credited to Edmonds, as I hav seen this problem before.

bbi5291 · **Posted:** Wed Aug 26, 2009 7:16 pm

Are you serious? You actually knew that algorithm? I had to look it up! I'm scared now Confused

A.J · **Posted:** Wed Aug 26, 2009 9:28 pm

Well, I had initially looked it up too.

saltpro15 · **Posted:** Wed Aug 26, 2009 9:31 pm

umm, don't all algorithms have to be looked up? Or does stuff like Dijkstra's just pop into code gurus heads? Laughing

Analysis Mode · **Posted:** Wed Aug 26, 2009 9:42 pm

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?

	Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB Username: Password: Register
Wiki Blog Search Turing Chat Room Members