Hello, everyone! My name is Rujia Liu. I used to do a lot of problem solving and problemsetting, but after graduated from Tsinghua University, I'm spending more and more time on my company :( Anyway, here I come again, with my 3rd present for UVa OJ: A Data Structure contest.
Recently, Tsinghua students are busy with its 100-th anniversary. For example, as a (graduated!) member of Tsinghua Chorus, I've just attended a performance in the Concert Hall of National Grand Theatre (NCPA) on April 4th. When you're reading this text, I'm most probably on the luxury stage of the final anniversary show in the campus 8-)
(A photo of me, taken in the dressing room in NCPA)
But why bother data structures? Well, I love data structures. I've enjoyed working as the TA for two data structure courses - I'd like to express my thanks to the teachers: Prof Junhui Deng and Prof Hong Wang, and also the students. As a bonus for reading my story, the easiest problem is E, and K is a bit more difficult that it seems. Be careful!
The things you should know:
I know that data structures can be very difficult to debug, especially when you're using online judges and don't have access to the test data. Thus, I decided to provide quite a lot of additional test data (apart from the sample I/O in the problem description) as a gift, for your reference. You can download them here.
Note that the files are in DOS format. Sorry for *nix/MacOS users, but I'm pretty sure that you're good at converting between formats 8-) Anyway, please make sure you pass all these additional test data before submitting. Real data are a lot more difficult, so you're still facing great challenges!
I'd like to thank Yiming Li, Yeji Shen, Dun Liang and Yao Li for writing alternative solutions for some of the problems, Erjin Zhou for problem L, and Xinhao Yuan for problem J. And finally, thanks to Prof. Miguel (again)!
Some technical info: the timelimit for each problem is about 3 times the runtime of the fastest standard solution, unless we have special reasons to enlarge/shorten the timelimit. In most cases, you don't have to deliberately optimize your code if you're using an asymptotic "fast enough" algorithm, but it's not guaranteed. It depends on how fast your "natural code" is. Similarly, implementations of naive algorithms are not supposed to pass the judge data. If you got "Accepted" with a theoretically slow program, please let me know (after the contest), by sending your code to rujia.liu@gmail.com. Thanks!