Google Code Jam Round 1A

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

10 years ago, # |

← Rev. 2 →

+20

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

→ Reply

Junior94

10 years ago, # ^ |

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

→ Reply

Tima

10 years ago, # |

+10

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

→ Reply

Xellos

10 years ago, # ^ |

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 $\text{[math]}$ .

→ Reply

eduardische

10 years ago, # |

← Rev. 4 →

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

marat.snowbear

10 years ago, # ^ |

+29

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

eduardische

10 years ago, # ^ |

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

Baklazan

10 years ago, # ^ |

+123

You should have used Excel.

→ Reply

b0mb3r

10 years ago, # ^ |

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.

→ Reply

oversolver

10 years ago, # |

+64

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

rmn

10 years ago, # ^ |

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

→ Reply

10 years ago, # ^ |

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

→ Reply

10 years ago, # ^ |

-13

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

const_int_magic

10 years ago, # ^ |

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

tomlau

10 years ago, # ^ |

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

→ Reply

Betlista

10 years ago, # ^ |

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

sgtlaugh

10 years ago, # ^ |

-16

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

tomlau

10 years ago, # ^ |

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

→ Reply

sgtlaugh

10 years ago, # ^ |

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

Chortos-2

10 years ago, # ^ |

← Rev. 2 →

+55

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, # ^ |

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

oversolver

10 years ago, # ^ |

Thanks (:

→ Reply

vlade087

10 years ago, # ^ |

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

→ Reply

tiagob.reis

10 years ago, # ^ |

← Rev. 2 →

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, # ^ |

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, # ^ |

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

→ Reply

tiagob.reis

10 years ago, # ^ |

← Rev. 2 →

Then, how would you explain an input like

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 →

-42

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

cegprakash

10 years ago, # ^ |

"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

tiagob.reis

10 years ago, # ^ |

+32

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

tomlau

10 years ago, # ^ |

← Rev. 2 →

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

Igorjan94

10 years ago, # ^ |

+21

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

pllk

10 years ago, # ^ |

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

→ Reply

nicky_ua

10 years ago, # ^ |

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

→ Reply

10 years ago, # ^ |

-26

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

cgy4ever

10 years ago, # ^ |

+53

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

RealEyes

10 years ago, # ^ |

I think it is better to say:

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

→ Reply

sgtlaugh

10 years ago, # ^ |

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 →

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

slycelote

10 years ago, # ^ |

← Rev. 2 →

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

→ Reply

Um_nik

10 years ago, # ^ |

*least

→ Reply

10 years ago, # ^ |

I changed my code from Max(a[i]) to LCM(a[i]), still getting WA.

Can someone please have a look at my code and tell me where I am wrong?

Pastebin link — Code

→ Reply

slycelote

10 years ago, # ^ |

You missed a[2] in LCM

→ Reply

10 years ago, # ^ |

Thanks a lot slycelote :) It feels good to see "Correct!", although in Practice :P

→ Reply

cadenza

10 years ago, # |

What is the solution to B large?

→ Reply

10 years ago, # ^ |

Can someone explain the Binary Search solution please?

→ Reply

akulsareen

10 years ago, # ^ |

← Rev. 2 →

+11

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 M_i 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, # ^ |

Thanks!

→ Reply

anshkhanna7

10 years ago, # ^ |

Thanks for a great explanation akulsareen

→ Reply

akulsareen

10 years ago, # ^ |

+14

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

nishad94

10 years ago, # |

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 →

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, # ^ |

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

→ Reply

nishad94

10 years ago, # ^ |

Can you please explain this in more detail?

→ Reply

10 years ago, # ^ |

← Rev. 2 →

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, # ^ |

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

marcose18

10 years ago, # |

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

eduardische

10 years ago, # ^ |

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

→ Reply

slycelote

10 years ago, # ^ |

← Rev. 2 →

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

→ Reply

ffao

10 years ago, # ^ |

+17

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, # ^ |

Can you explain how to reduce the O(N³) solution to O(N²) using two pointers?

→ Reply

marat.snowbear

10 years ago, # ^ |

+21

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(N²logN), not O(N²).

→ Reply

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

10 years ago, # ^ |

Got it. Thanks a lot.

→ Reply

gkeesh7

10 years ago, # |

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

→ Reply

jozef.brandys

10 years ago, # ^ |

You can practice on codejam webpage.

→ Reply

gkeesh7

10 years ago, # ^ |

Yes I know, but I wanted to solve some of the questions in codeforces too, just like the qualification round. Anyways thanks.

→ Reply

martinezgjuan

10 years ago, # |

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

Alpha1467

10 years ago, # |

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

→ Reply

jozef.brandys

10 years ago, # ^ |

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

Alpha1467

10 years ago, # ^ |

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

jozef.brandys

10 years ago, # ^ |

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

PetarV

10 years ago, # ^ |

← Rev. 4 →

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.

$\text{[math]}$

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

→ Reply

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

10 years ago, # |

+13

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

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, # ^ |

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

Fear_Is_An_Illusion

10 years ago, # |

Got 0/100

→ Reply

Xellos

10 years ago, # ^ |

+16

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

→ Reply