hadi's blog

By hadi, 9 years ago, In English,
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.
  • Vote: I like it  
  • +13
  • Vote: I do not like it  

9 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Thanks! :)
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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.
  • 9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I'm sorry, Alias has kindly pointed out,
     ... ,which are all lowercase Latin letters.
    just as you say, "Read problem statement more carefully."
  • 9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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.
    • 9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Thank you, Alias and hadi. Now I understand why "straightforward implementation" works.
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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.
  • 9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
      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.
    • 9 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      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.
  • 9 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it
    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.
    • 9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Dear Hadi

      1) According to Helen (you should remember Helen): And now you know!
      Clues were all for you to "and then you know"!
      Fair! No of course it is not. But let's start thinking about some other unfair things in the world around us.

      And let us say some words to you (to be not as unfair as mentioned):
      Do you remember the day Mr. P1 asked you "How much time can you dedicate to our team?" and do you remember what was your answer. Do you remember the day you accidently forgot to go to Tabesh's office and prosecute the sponsorship.Do you remember the day you insisted to bring your wife to a travel which in no ways whould relate to her. Do you remember the day we asked you to set NEERC contest for us and you suddenly fall asleep. Do you remember the days which you wasn't there to bring your online judge up again. Do you remember the day which keeping track a small balloon wasn't much of a concern to you. Do you remember world finals contest day when you even wasn't there. And do you remember ... . (Hope you remember at least half of them).

      All of the above seems to be started since your marriage. What a bad happening was losing a friend such as you, but now you belong to your wife (and we really hope you the best, no matter you believe it or not). But being active again in programming contest, spending time for blog post (specially for such trivial tasks), doubles our pains.

      Hope you know, Greatest ever AUT ACMER
      PMP (P1&M1&P2)
      • 9 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
         Thanks for your comment. Although it's not enough, but I already felt guilty after what happened. Of course, I'll contact you and talk with you as soon as possible.
         I hope you don't hate me.
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Very good