By hadi, 10 years ago, ,
Today I participated in my first codeforces contest. The problem-set was quite easy.

Here are how I solved the problems:

Problem A: The answer is "NO" if and only if n is either odd or equal to 2, otherwise you can decompose it as (2, n-2).

Problem B: The answer is "Yes" if and only if sum(minTime) <= sumTime <= sum(maxTime). You can construct a list in this case easily using a greedy method.

Problem C: Straightforward implementation. I used C++'s std::map to implement this problem.

Problem D: O(N^2) dynamic programming. DP state is index of last chosen envelope, and loop over for the next envelope.

I didn't do bad (I became 15th), but I expected better. In fact I could be 3rd if I was a bit careful and read the problem-statement of the last problem more carefully and got it in my first submission at 0:26. I missed that envelope size must be strictly larger than the card, and thought equal is also okay. I got the submission result about 25 minutes later, and lost lots of penalty time.

The lessons to learn are:
1. Read problem statement more carefully,
2. It's okay to waste another minute to check everything once more before submission,
3. Don't just wait for submission result, re-read the problem statement and your code once more.

I hope to do better in next contests, which I expect to have more difficult problem-sets.

By the way, congratulations to the winner of the contest, Xazker, who is also red at topcoder.

• +13

 10 years ago, # |   0 Thanks! :)
•  4 years ago, # ^ |   0 thank's for you
 10 years ago, # |   0 Excuse me, may I ask you describe your straightforward algorithm? I thought a straightforward implementation will be O(n^2) and won't be in time.
•  10 years ago, # ^ |   0 I'm sorry, Alias has kindly pointed out,  ... ,which are all lowercase Latin letters. just as you say, "Read problem statement more carefully."
•  10 years ago, # ^ |   0 By "straightforward implementation" I meant that I implemented exactly what problem statement said. I thought std::map is more natural as a database than an array or a std::vector, so what I meant by straightforward implementation takes O(n log n) time, not O(n^2). I did almost the same as Alias described.
•  10 years ago, # ^ |   0 Thank you, Alias and hadi. Now I understand why "straightforward implementation" works.
 10 years ago, # |   0 Are you a red? oh so TC has a bad rating system. it seems that these problems should be very easy for a red. I think that TC need to revise the rating system and you must be a blue at most.
•  10 years ago, # ^ |   +1   I am not sure to whom you are referring to, to Xazker or to me? Anyway we're both reds, and I don't see anything wrong by our being red there. I think the problem-set were easy for both of us, and we, along with many other red topcoders whom you may recognize, solved all problems.  I am not sure who you are, but it seems that you just registered to insult and stay anonymous.
•  10 years ago, # ^ |   +1 When I first saw that comment, it had a +6 rating, surprisingly high for a reply that is controversial at best.Doesn't seem like there are any moderation policies here, yet. But it's still beta; maybe that's a thing to change.
•  10 years ago, # ^ |   +2 Dear "acmer",  Maybe I don't deserve to be a topcoder red, but after some inspection, I found some convincing clues about who you *really* are. Although, I guess you are not a single person, and a group of probably [2 .. 4] people. And probably you deserve to become a topcoder target, but you were unsuccessful in hiding yourself and leaving no clues. Some clues are:    1. You posted this comment just after you registered, so I think this is not your real handle and you tried to hide yourself, so I guess you are someone I know.    2. Registration of some person whom I know coincides with your registration off by some minutes (You can see the exact times in page sources of profile pages), let him call Mr. P1.    3. Mr P1, and his friend Mr. P2 visited codeforces almost the same time of this comment, probably to "plus" it. I saw this comment 2 hours after it was posted, and their last visited time in their profile were almost same as this comment's. Again, I used page sources to extract exact times.  Above clues, and some other clues lead me to guess who you really are. Furthermore, all of my posts were also minused just after your registration by at least two people, so I guess you and your friends might hate me. That's ok, but isn't more fair to talk with me directly instead of posting comments like this and minusing my post regardless of their content?  Anyway, I don't understand your motives. But honestly when I first saw this comment, I didn't guess it could be you. I considered some other people before you.