Junior94's blog

Google Code Jam Round 1A
By Junior94, 10 years ago, In English

Code Jam Round 1A starts in a few hours.

GL & HF.

  • Vote: I like it
  • +36
  • Vote: I do not like it

Comments Comments (77)
| Write comment?
»
10 years ago, # |
← Rev. 2   Vote: I like it +20 Vote: I do not like it

Are you that only person from Mozambique? That's cool.

http://www.go-hero.net/jam/15/regions

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Yeah and you seem to be in the same situation :)

    → Reply
»
10 years ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve large input version of C (Logging)?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    For each point, you can sort all other points around it and look for a line that passes through that point (+- collinearities) and cuts off as few other points as possible. You can just use something like 2 pointers, rotate the line and recalculate the number of points on either side of it. It runs in .

    → Reply
»
10 years ago, # |
← Rev. 4   Vote: I like it +8 Vote: I do not like it

Task C — is my approach incorrect or I just couldn't find all the bugs in an hour?

To find an answer for a fixed point X: sort all vectors by polar angle from the basis in X, then considering every other point Y, count how many points there are strictly on the left side of X -> Y and on the right side. The minimum value for all Ys and all sides is the answer for the given X. If Y are considered in sorted order, this sides can be found by sliding window.

UPD: Yep, my solution is exactly the same as Xellos described and I have also finally found a bug (long long f(); int x = f();). Lesson learned and all the extra flags from this were added alongside -Wall.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    Sounds right, maybe you have an issue with corner case N = 1? That was my bug on which I spent almost the entire contest.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for suggestion, I had that covered, turns out it was a standard int overflow bug which I managed to avoid spotting because it was on a line with no arithmetic computations.

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +123 Vote: I do not like it

    You should have used Excel.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe it's easier if you coded a quick O(N3) solution and compare what's wrong from both output? At least you can get 18 points in like 10 mins.

    → Reply
»
10 years ago, # |
  Vote: I like it +64 Vote: I do not like it

I spent 10 minutes at start, 30 in the middle and 30 at the end of the contest to understand statement of the task A. But i didn't understand it yet. I just want to know, i alone with this problem?:)
Only thing that i understand it is how to get number 25.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Same here, I still have no idea what that problem asked me to do...

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I read the statement 3 to 4 times at the start and found it very, very ambiguous.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    Code Jam has done it again. I'm impressed at the ability of the problem setters to make such HORRIBLE contests. This one was even worse than the Qualification Round, and that's quite a feat.

    I read Problem A statement like 5 times at the beginning of the contest, and I didn't understand what the hell it was asking. I asked for clarification, and some asshole jury replied with "Please read more carefully". If the problem was just that I was reading hastily, I wouldn't have contacted you, you stupid moron!

    So I decided to move on to Problem B, and solved it in around 15 minutes for both small and large. Then moved on to A again, and after seeing that there was no way I could understand the hyeroglyph written there, I tried to solve (without success) Problem C.

    So, anyway, can anyone please explain what the hell was Problem A asking?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      It's quite dumb.

      Basically there's a person who's eating mushrooms. They give you the # of mushrooms at 10 second intervals, and, through a process of eating and gaining mushrooms, what is the least number of mushrooms the person could have eaten using the two methods (note, for the second method, rate can be non-integral).

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        You don't need rate per second, you only need rate per 10 seconds, which is always integral.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          And that confused me for quite long time I also asked the question about that during the contest and the reply was: "Please read the problem statement more carefully. Consider looking at the limits and the example cases if those might help."

          My question was: "Can the speed of eating be decimal number like 3 mashrooms in 2 seconds => 1.5 per second?"

          The answer didn't help me. Probably the description for first test case "We can determine that she must eat mushrooms at a rate of at least 1 piece per second." confused me, trying to calculate rate per second...

          → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it -16 Vote: I do not like it

          In what kind of multi-dimensional universe you can only eat integral number of mushrooms every 10 seconds however you can eat non-integral number of mushrooms per second???

          → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            Well, for example, 90 kilometers per hour is 1.5 kilometers per minute. That's in our universe, not sure about yours :)

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              10 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I know, I guess I got frustrated because like I said this ruined the contest for me. Of course it's partially my fault too. It would have been much clearer in my opinion if the interval was always 1 second.

              → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it +55 Vote: I do not like it

      I wholeheartedly agree that the task statement was exceedingly confusing. Hopefully this will clear it up:

      Every time the number of mushrooms on Kaylin’s plate decreases, it means she has eaten some of them. Bartholomew can add arbitrary mushrooms at Bartholomew times, so when the number increases, that’s his doing. What’s the smallest number of mushrooms Kaylin could’ve eaten? It doesn’t matter what the exact numbers are except that she can’t eat more than she has; what really matters is the difference between every two consecutive numbers. In particular, she doesn’t have to eat the mushrooms that are left on her plate at the end.

      The first example works like this:

      10 5 15 5

      • She had 10 mushrooms at time 0.
      • She had 5 mushrooms at time 10. This means she must’ve eaten 5.
      • She had 15 mushrooms at time 20. That’s fine, Bartholomew must’ve added some, but we don’t care.
      • She had 5 mushrooms at time 30. This means she must’ve eaten 10. She left the 5 mushrooms on her plate and walked away.

      That’s it, she has eaten 5 + 10 = 15.

      Now, if she eats at a constant rate (in the second case we’re interested in), that rate must be at least 5 per 10 seconds because she ate 5 between times 0 and 10, and it must be at least 10 per 10 seconds because she ate 10 between times 20 and 30. Overall, the rate is at least 10 per 10 seconds. With this, we get:

      • She had 10 mushrooms at time 0.
      • She had 5 mushrooms at time 10. We know from our minimum speed that she must’ve eaten at least 10. Hence these 5 mushrooms must’ve been newly added by Bartholomew.
      • She had 15 mushrooms at time 20. We know from our minimum speed that she must’ve eaten the 5 mushrooms she previously had. Bartholomew could’ve added some new mushrooms (at least 15) at any point between times 10 and 20. If he added them before time 20, then Kaylin would’ve already eaten some of them, but we want to minimize the amount she eats, so we can assume Bartholomew added exactly 15 new mushrooms exactly at time 20.
      • She had 5 mushrooms at time 30. We know from our minimum speed that she must’ve eaten 10 out of the 15 mushrooms she previously had. She then left the 5 remaining mushrooms on her plate and walked away.

      So, if Kaylin ate at a constant rate, she must’ve eaten at least 10 + 5 + 10 = 25 mushrooms.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        Thanks. I got it after reading ""we'll look at how many pieces of mushroom are on her plate", but sadly, that was after the contest.

        You should have been the one in charge of writing the statement, not the one who actually did it.

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Thanks (:

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Thanks a lot I understood the problem after reading your comment!

        → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    I really didn't think the statement was unclear at all: you had to calculate the number of mushrooms the girl had eaten supposing he followed each of the two given strategies.

    The first strategy was pretty straightforward, so, I guess the problem was with the second one.

    In the second one, you assume that, as long as there are mushrooms in her plate, she eats them at a constant rate, that is, (number of shrooms eaten / second) is constant.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      I didn't have a problem understanding the second strategy. The first strategy was the problem. What the hell does it mean with "any number of mushroom pieces at anytime"? Just for the record, I still don't understand. If she eats "any number of pieces", I could just assume she never eats anything, and so the answer is always 0.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Not if a[i + 1] < a[i]

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Then, how would you explain an input like

        2

        10 5

        if the only way mushrooms disappear from the plate is by being eaten?

        In this case, she can't eat 0 mushroom, she has to eat at least 5.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
          ← Rev. 2   Vote: I like it -42 Vote: I do not like it

          That's because the problem statement was written by a monkey.

          It wasn't clear that the numbers given in the input were the amount of mushrooms on the girl's plate every 10 seconds. I interpreted the numbers were the amount of mushrooms Bartholomew puts on her plate every 10 seconds, because the statement is such a mess that by the time you get to the actual input, you're already confused.

          Wouldn't it be easier to just write a few more words like "If the given input is 10 5 15 5, then initially there are 10 mushrooms on her plate. Then she eats 5, and 5 remains. After that 10 more are put on her plate, then she eats 10, and there remains the final 5 mushrooms". With something like that, no one would have gotten confused.

          Seriously, the challenge has to be coming up with a solution and coding it, not deciphering the problem statement.

          I wouldn't be surprised if next time, they write a statement in latin. Everyone would have to use a translator, and that would add to the extra difficulty of the problem.

          → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            "That's because the problem statement was written by a monkey." Lool :D

            I too couldn't understand the problem for a long time :P

            → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it +32 Vote: I do not like it

            You say "it wasn't clear that the numbers given in the input were the amount of mushrooms on the girl's plate every 10 seconds". Yet, the input description says that m_i are exactly "the number of mushrooms on Kaylin's plate at the start, and at 10-second intervals".

            I agree it could be clearer, but you should stop blaming it all on the problemsetter (especially with such anger) and take your part of the guilt. That's a way to become not only a better competitive programmer, but a better reader overall :)

            → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        if m[i-1] > m[i], then she must have eaten at least m[i-1]-m[i] mushrooms in that time interval. There is nothing more to it :)

        → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    I spent about 20 minutes to understand. After n-th rereading statement, I saw "we'll look at how many pieces of mushroom are on her plate" and understood what we have and how solution can be implemented...

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Yes, A was very difficult to understand. I just guessed what I should do, fortunately I guessed correctly.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i could understand statement of the task A only in last 20 minutes of contest. really bad problem.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it -26 Vote: I do not like it

      Yes, you're not the only one. A few friends of mine got only 15 points because they couldn't understand that statement. And apparently, a lot of Codeforces users had serious trouble understanding it as well.

      What happened to Code Jam? Last year was wonderful, this year, so far, it's a mess.

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +53 Vote: I do not like it

    Yes, I can solve task B + C under 16 minutes , but have spent another 16 minutes to solve task A (including 10+ minutes of guessing the meaning of this task).

    When I read the sentence after:

    For example, if the input is 10 5 15 5:

    I thought: "what the hell? did you miss to write the 'Input Format' part?".

    So the big secret is hidden in this line:

    we'll look at how many pieces of mushroom are on her plate at 10-second intervals

    And in order to decrypt it you need to understand what means "10-second intervals", which is much beyond my language skill..

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      I think it is better to say:

      we'll look at how many pieces of mushroom are on her plate every 10 seconds.

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Problem A ruined my whole contest. What was the purpose for that stupid 10 second interval?? Even after the contest ended I was banging my head because I could not figure out how the result for the last sample case could be 244 (using the second strategy).

    Very poor, ambiguous, trite description unnecessarily prolonged.

    → Reply
»
10 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

I got WA for task B (Small). My soln:

if N <= B: 

then answer is N.

else:

Consider time instants from 1 to Max(B[i]).

Find the seats that become available at time[i].

Add those seats to a list in increasing order of index.

Let final list size be K.

Ans will be (N % K)th element in the list.

I basically thought that the values will repeat cyclically after a point. Is my method incorrect?

Code with Max(B[i])

EDIT: Got Correct Answer, after considering time instants upto LCM(B[i]).

Code with LCM(B[i])

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the solution to B large?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can someone explain the Binary Search solution please?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it +11 Vote: I do not like it

      Notice as more time passes, more customers get served i.e. with increasing time customers served keep increasing. So you can do a binary search on the maximum time till which less than n customers have been served.

      Let this time be t and the customers served till t be n1. Therefore, n1 < n and customers served till t + 1 is greater than or equal to n.

      Now iterate through all the barbers. Those barbers for which Mi divides t will take a new customer at time t. Whenever, you encounter such a barber increase n1. The barber for which n1 becomes equal to n is the answer.

      Note: When I say served I mean either served or being served

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    You can perform a binary search on the time when the n th customer gets served. Once you have found correct time then finding the barber is also a simple matter. Let me know in case more explanation is needed.

    → Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

In B, the most obvious way(that led to a TLE [O(N*BlogB)]) was:

n = N - B;
for i in range(1,n+1):
    sort(M[]);    // M=Original=pair<int,int>, M[i].first = time, M[i].second = index of that barber
    ans = M[0].second;
    M[0].first += Original[M[0].second].first;
return ans;

I realize that the order of the indices will be cyclical. But how do you find that pattern and solve this quickly?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    For finding the cycle, I just found out which seats were getting empty at time[i], and did that for all time instants uptil Max(M[i]).

    However, that gave WA, because we should consider LCM(M[i]), not Max(M[i]).

    Check out my implementation — Link to code

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It'll cycle every lcm(m[0], m[1], ...). But this solution will pass the small data only.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please explain this in more detail?

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it +2 Vote: I do not like it

        For every i the i-th barber will be free after n seconds if n % m[i] = 0 so you need the least number that divides them all which is the least common multiple.

        Then you can reduce n to n % lcm(...) and iterate through the rest.

        → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't think it would work for Large — it will be cyclical, but with so many barbers it can be too long. I solved it with binary search — first determining the minute when last customer before n-th customer will get in (not get served, just gets in) and from there you can find which barber gets n-th customer.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What was the approach to solve Problem C small input.I got the solution for large input but lets say we would like to solve small input particularly what would be the approach ?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Try all possible sets of trees being left and find convex hull for each of them?

    → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    You can also go with the same approach as large input, but instead of using 2 pointers just iterate over all O(N2) lines connecting the points and for each line look how many points we can remove from either side of the line. Overall complexity is O(N3).

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      This could actually pass the large input too if you have a fast enough computer. I was downloading the top solutions for C-large and I saw quite a few of those.

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain how to reduce the O(N3) solution to O(N2) using two pointers?

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +21 Vote: I do not like it

        As soon as you fixed the first point you sort the rest of the points by their polar angle relative to the first point. Then basically you will do a sweeping line and you will rotate it around that fixed point. This line will separate the plane into two halfplanes, also it will separate your set of points into two contiguous subsets (if you imagine your list being circular). So you introduce two pointers to keep track of first and last element in "left" halfplane for example. Then you rotate the line and move both pointers which will take O(N) to rotate it 360 degrees.

        And because of sorting it will be O(N2logN), not O(N2).

        → Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can anyone tell me when will this round be added to the gym ?

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I had to read problem A like 5 times to understand it and I didn't even understood it because of the text per se but because of the test cases trying to figure out a way to produce them.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me how the question B is done? i mean the algorithm..? Thanks

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My solution was to find the time, when the Nth customer is served. This can be binary searched -> guess the time and count how many customers can be served by individual barbers and sum it together. When you have exact time T -> you have to find which one is going to serve Nth customer. This can be done in numerous ways. I counted the number of served customers in time T-1. And then I searched for barbers which were serving new customers in time T. And choose the appropriate one. The complexity is some logarithm from maximum time for binary search multiplied by the number of barbers. So it is something like O(log N * B).

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What i did took long for it to finish running. I made an array of the barbers minutes and reduced it one by one and subtracted 1 from the N for each time the minutes became zero. then i repeated it until (while N>0) the array became the same as in the beginning. then i made N=N%(number deducted) and made it continue from there. Please find my mistake.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        If the lengths to cut would have very big least common multiply your solution would be same as simulation, thus very slow. Good example are prime numbers — test case:

        1
11 1000000000
2 3 5 7 11 13 17 19 23 29 31

        The length have lcm much bigger than N, thus the array would be same later than N will reach 0.

        → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 4   Vote: I like it +1 Vote: I do not like it

    Note that, after T minutes, you can easily calculate how many people have been assigned a barber (including people that have finished). It is simply summing over the amount of people that each barber has, i.e.

    where ⌈·⌉ represents the ceiling function.

    Clearly, this sum grows as T grows, hence you can do a binary search for the highest time Tmax when less than N people are assigned a barber (i.e. such that cnt(Tmax) < N).

    At that exact time, you know that a barber will be available to service the N-th person. All you need to do is go through all available barbers (the k-th barber is available at this point if Tmax ≡ 0 (mod Mk)). Whenever encountering an available barber, we increment a variable X, which is initially set to X = cnt(Tmax). Once X = N, we have assigned a barber to the N-th person, and we only need to return that barber's id.

    Here's my code: http://hastebin.com/vigefudase.vala

    → Reply
»
10 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Just noticed — among the people who passed thus far into Round 2:

http://www.go-hero.net/jam/15/languages

Python is placed second after C++ with 106 people vs 81 people using Java. Before it was always C++, Java, Python. Is it statistical quirk or a new trend?

I bet Java will regain its second place in Round 2, but still worth noting I think.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's a trend. After 3 (1A, 1B, 1C) rounds we have:

    C++ : 2260 Python: 456 Java: 336.

    So summing up: Among approximately 3,000 best active competitive programmers, without running speed restrictions, Python is more popular then Java. Would be interesting to see statistics for 500 best in three weeks.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Got 0/100

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Maybe you'd do better if you trained more and shitposted less?

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Contest Analysis for Round 1A: Analysis

→ Reply