Code Jam Round 1A starts in a few hours.
GL & HF.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | atcoder_official | 156 |
4 | cry | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
9 | Um_nik | 151 |
10 | djm03178 | 146 |
Code Jam Round 1A starts in a few hours.
GL & HF.
Name |
---|
Are you that only person from Mozambique? That's cool.
http://www.go-hero.net/jam/15/regions
Yeah and you seem to be in the same situation :)
How to solve large input version of C (Logging)?
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
.
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.Sounds right, maybe you have an issue with corner case N = 1? That was my bug on which I spent almost the entire contest.
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.
You should have used Excel.
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.
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.
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?
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).
You don't need rate per second, you only need rate per 10 seconds, which is always integral.
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...
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???
Well, for example, 90 kilometers per hour is 1.5 kilometers per minute. That's in our universe, not sure about yours :)
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.
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
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:
So, if Kaylin ate at a constant rate, she must’ve eaten at least 10 + 5 + 10 = 25 mushrooms.
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.
Thanks (:
Thanks a lot I understood the problem after reading your comment!
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 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.
Not if a[i + 1] < a[i]
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.
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.
"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
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 :)
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 :)
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, 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.
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..
I think it is better to say:
we'll look at how many pieces of mushroom are on her plate every 10 seconds.
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.
I got WA for task B (Small). My soln:
if N <= B:
else:
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])
They will repeat starting from lcm(B[i]) (lowest^Wleast common multiple), not max(B[i])
*least
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
You missed a[2] in LCM
Thanks a lot slycelote :) It feels good to see "Correct!", although in Practice :P
What is the solution to B large?
Can someone explain the Binary Search solution please?
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
Thanks!
Thanks for a great explanation akulsareen
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.
In B, the most obvious way(that led to a TLE [O(N*BlogB)]) was:
I realize that the order of the indices will be cyclical. But how do you find that pattern and solve this quickly?
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.
Can you please explain this in more detail?
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.
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.
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 ?
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(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).
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.
Can you explain how to reduce the O(N3) solution to O(N2) using two pointers?
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).
Got it. Thanks a lot.
Can anyone tell me when will this round be added to the gym ?
You can practice on codejam webpage.
https://code.google.com/codejam/contest/4224486/dashboard
Yes I know, but I wanted to solve some of the questions in codeforces too, just like the qualification round. Anyways thanks.
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.
Can anyone help me how the question B is done? i mean the algorithm..? Thanks
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).
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.
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:
The length have lcm much bigger than N, thus the array would be same later than N will reach 0.
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
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.
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.
Got 0/100
Maybe you'd do better if you trained more and shitposted less?
Contest Analysis for Round 1A: Analysis