Mar 042009
 

Feb 28 was the first day of our new training session, but the number of attendance was quite astonishing: one (marcadian). It was expected though considering the announcement was made only the day before. I can’t help but feel pathetic, why should I spend my beautiful weekend with a guy? Yet, I was lucky he’s not a gay… or not yet (someone please tell me)? There was another student came in the middle of the training hour (jeff), be he went home soon…

Warm-up problems:
PKU 2236 – Wireless Network
PKU 2761 – Feed the dogs
PKU 3419 – Difference Is Beautiful
PKU 3421 – X-factor Chains

Spoiler Ahead!

PKU 2236 – Wireless Network
This is an easy problem (compared to the others). Each time a computer is being repaired, merge this computer with any other computers within range that has been repaired. Repairing a computer twice won’t effect anything, so it will be usefull to remember which computer that has been repaired.

PKU 2761 – Feed the dogs
You can find the k-th element in a range with a proper tree data structure, but marcadian said that he got TLE with this approach. There is a simpler solution using a certain tree stucture to find k-th element in the whole range (timo used to call it “misof-tree”). Notice that there will be no interval that contain another interval completely, we can use this special constraint. Solve the queries based on start-interval in ascending order. By doing so, we can “maintain” our tree structure by window-sliding.

PKU 3419 – Difference Is Beautiful
Yes indeed, difference is beautiful, I like this problem :-). First, precompute A[1..N] where Ai contains the longest extension you can make from datai, you can do it in O(N). Next, observe the extension’s end that can be made by each datai. Let the extension of datai ends at endi and dataj ends at endj. If i < j then endi <= endj. Now consider an interval (L, R), the extension’s end of each starting point in those intervals will be separated into two types: those which end within the interval, and those which end outside the interval. So? binary search is our friend.

PKU 3421 – X-factor Chains
The time limit for this problem is tight!! A simple O(n.ln(n)) dp solution (precompute the table) will give you TLE. One approach (which I used) to optimize this dp solution is by pruning the search space using prime numbers. You should realize that the length of the longest chain that can be made is equal to the number of it’s prime factors. Another approach (a non dp solution) is by factoring the number and calculate how many different alignment can be made by those prime numbers. Marcadian used this second approach, and his code run faster than mine.

  2 Responses to “First Training Day”

  1. but you are a good coach. however i don’t have, and i always find the way to improve myself , but failed.i have read your blog about your acm/icpc experience and felt mine is same with you. though i solve 100+ problems, i can’t AC regional problems or understand. i think i just have mastered little algorithms, and do not apply them flexible flexiblely. pls give me some suggestion. thx. thx your share.

  2. @CodeChomper: You need more practice, 100++ problems is not enough. I don’t know about your coding experience, but I usually suggest any beginner who just learn how to code to write code as much as they can (easy/adhoc problems are okay). This practice is intended to improve our coding skill so we can write “easy” code (implementing what in our mind) easily and fast. This skill is needed to learn algorithm (by “learn” I mean to fully understand it).

    When we learn an algorithm, don’t learn only the “how-to” part. You need to grasp the idea/concept of the approach, understand why it works, calculate the time and space complexity, and maybe spend sometimes to think is there any other alternative algorithm exists (even a worse one). To be able to apply these algorithms in a contest or problem solving, you’ll need practice (a lot of practice, unless you’re “super-smart”). Or maybe you can create your own problem (what if the problem bla bla bla…) and try to solve it. Don’t hesitate to ask other people to help you with the problem (try topcoder), but becarefull, usually a decent coder won’t help you if you don’t show any effort first before asking about the problem (like copy-pasting a problem statement and throw a question about how to solve it without explaining what you don’t understand or what approach you have tried and failed).

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)