4 ms·
A) is completely possible in a few minutes if you have a prewritten permutation function. for C) I wrote about 30 lines in python - 20 of them file handling -
by johnfn 17y ago
A) is completely possible in a few minutes if you have a prewritten permutation function.
for C) I wrote about 30 lines in python - 20 of them file handling - to solve the problem (after a few hours of deliberation). What matters is your speed in figuring out how to write a proper algorithm. The codewriting will not take near as much time.
B) is the one where they surprised me the most. It took me about 150 lines to finish off that beast in about 3 hours, and there are definitely errors in the large output even still. I would love to see how they did it.
- Tichy 17y agoA) true I think I fell just for premature optimization and made my solution too complicated. I assumed that they would pose the problem in a such a way that the naive approach would be too slow. C) yeah that was the shortest - my first "naive" algorithm was not fast enough, though. I have now thought of a better one and can't wait to try it out, but it is too late for the competition. Still, that alone was worth participating to me - it is a kind of "revelation feeling". I love it when by improving an algorithm a problem becomes solvable. B) Was actually the easiest for me - the naive algorithm worked well enough. Took me a while to get the program bug free, though...
- alexkay 17y agoIt also took me awhile to code the correct algorithm for B. I ended up with 60 lines of Python code, and 2 hours :/ All in all, this year's qualification round is much easier than the last's. No real algorithmic challenges, just boring debugging.
- mbenjaminsmith 17y agoI got so upset after B) I skipped C), which I was confident I could tackle. My first version of A) worked without issue and I ended up timing out on A.2 because I had overlooked the fact that I couldn't cut and paste the whole result from my terminal. B) I could solve the sample and the B.1 test case 'looked' like they could have been right but I kept getting incorrect answer on it. It wasn't anything with the dimensions of the map (something I ran into and fixed) so I still can't imagine how you can solve the examples and not solve the test cases. Kinda fun though...
- mquander 17y agoRegarding: A) If you're in a language with a good regular expression library, there is a very fast cheesy way ;) B) I'm equally mystified, I'm satisfied that my solution was correct, but it took 80 lines and multiple passes through the array. I'm impressed that the top tier polished it off in around ten minutes. There must be a fairly simple way. C) I agree that this one just depends on how quickly you can figure out an algorithm. It's entirely plausible to me that someone with algorithm competition experience has almost literally seen this problem before.
- der_ketzer 17y agoI found this today, I think it's worth reading. It's regarding A) http://swtch.com/~rsc/regexp/regexp1.html http://swtch.com/~rsc/regexp/regexp1.html