Codeforces Beta Round #14

Hi All.. :)

It’s time to blog again.. Now i will post some small-writeup about the problems were used at this contest..

Well.., about today small-writeup, i will not post my source code anymore. Because
in practice we are sure that reading the source code at first sight will make us
bored and no creativity to implement our own solution..

Here is me at standing page :
Standing Page

Okay then, i will only put my ideas in this writeup. So, enjoy it.. ;)

Problem A : Letter (Accepted 1st try)
It is a very nice problem at the beginning. We are given rectangular board, we should take some rectangular board (possibly smaller) that cover all the shaded square. My idea is to make 4 lines, and take their intersection to be the left topmost and the right bottom, so we can make a rectangle with that. After that, print the solution. It can be done in O(n * m) time. Since the n and m is small, the algorithm above will be run in-time.

Problem B : Young Photographer (Accepted 1st try)
This problem is about “array differencing” problem. But since the constraints were small enough, i decided to code it in the worst complexity (maybe). My idea is just make an array of positions, then increment it one-by-one if there are sports-man at that position. The complexity of this solution is O(n ^ 2) i think. The solution of this problem is to compare each position that contain n sports-man at there and the initial position of the photographer, take the minimum.

Problem C : Four Segments (Accepted 3rd try)
This is a simple geometry problem. What did i do is to generate permutation of the segments, and decide if the rectangle is exist there. The complexity is O(4!), since there are 4 segments given. I did Wrong Answer 2 times because a silly mistakes. And it is time-consuming problem.

Problem D : Two Paths (Wrong Answer)
I can’t solve this problem yet. But actually my idea is to select some vertex and make it a “divider”. But i think that’s the wrong idea, so never mind.. :) Maybe anyone can help me to solve this? :D I am very sure that i have no idea how to solve it because of there are some algorithms that i never learn before.

Problem E : Camels (Accepted 1st try)
Well, this is my favorite problem in this contest. The combination about geometry stuffs and dynamic programming. I used 5-dimensions table of DP to solve it. Maybe anyone have a better complexity or memory? :D I spent many times to write the code, because the implementation was quite time-consuming.

Yeah, that’s all.. :)
Feedbacks are welcome then.. Please comment if you like this post or
want to give some tips, etc? :)

Best Regards,
Wilbert Liu

Advertisement

6 thoughts on “Codeforces Beta Round #14

    • Hahaha, ndak ada coding oq di atas.. :D
      Ak paling mau ambil TOEFL dll dulu sampe nanti
      setengah tahun ke depan.. :) hehehe..

      Gimana bro, ga resign? wakakakaka..

  1. There’s an O(N) solution to problem B. Each sportsman has a segment, find the intersection of all of those segments, L and R. If there is no intersection, then the answer is -1. If x0 is within the segment, the answer is 0. If x0 is greater than R, then the answer is x0-R. If x0 is less than L, the answer is L-x0.

  2. Hi LeppyR64,

    Yes, nice catch.. :)
    I understand your idea perfectly but i can’t come up
    with such idea at contest.., very bad..

    Thank you for pointing that out anyway.. :)

  3. *Aw, this was a really nice post. In idea I would like to put in writing like this additionally – taking time and actual effort to make a very good article… but what can I say… I procrastinate alot and by no means seem to get something done.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Connecting to %s