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

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 .

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

You should have used Excel.

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

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

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

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?

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.

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...

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

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

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..

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.

They will repeat starting from lcm(B[i]) (lowest^Wleast common multiple), not max(B[i])

Can someone explain the Binary Search solution please?

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.

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

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

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.

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

You can also go with the same approach as large input, but instead of using 2 pointers just iterate over all O(N²) 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(N³).

You can practice on codejam webpage.

https://code.google.com/codejam/contest/4224486/dashboard

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).

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 T_max when less than N people are assigned a barber (i.e. such that cnt(T_max) < 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 T_max ≡ 0 (mod M_k)). Whenever encountering an available barber, we increment a variable X, which is initially set to X = cnt(T_max). 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

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.

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