### Junior94's blog

By Junior94, 6 years ago,

Code Jam Round 1A starts in a few hours.

GL & HF.

• +36

 » 6 years ago, # | ← Rev. 2 →   +20 Are you that only person from Mozambique? That's cool.http://www.go-hero.net/jam/15/regions
•  » » 6 years ago, # ^ |   +3 Yeah and you seem to be in the same situation :)
 » 6 years ago, # |   +10 How to solve large input version of C (Logging)?
•  » » 6 years ago, # ^ |   +8 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 .
 » 6 years ago, # | ← Rev. 4 →   +8 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.
•  » » 6 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.
•  » » » 6 years ago, # ^ |   0 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.
•  » » 6 years ago, # ^ |   +123 You should have used Excel.
•  » » 6 years ago, # ^ |   0 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.
 » 6 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.
•  » » 6 years ago, # ^ |   +8 Same here, I still have no idea what that problem asked me to do...
•  » » 6 years ago, # ^ |   +8 I read the statement 3 to 4 times at the start and found it very, very ambiguous.
•  » » 6 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?
•  » » » 6 years ago, # ^ |   +3 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).
•  » » » » 6 years ago, # ^ |   +9 You don't need rate per second, you only need rate per 10 seconds, which is always integral.
•  » » » » » 6 years ago, # ^ |   +5 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...
•  » » » » » 6 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???
•  » » » » » » 6 years ago, # ^ |   +1 Well, for example, 90 kilometers per hour is 1.5 kilometers per minute. That's in our universe, not sure about yours :)
•  » » » » » » » 6 years ago, # ^ |   0 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.
•  » » » 6 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.
•  » » » » 6 years ago, # ^ |   +2 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.
•  » » » » 6 years ago, # ^ |   +5 Thanks (:
•  » » » » 6 years ago, # ^ |   +5 Thanks a lot I understood the problem after reading your comment!
•  » » » » 6 years ago, # ^ |   0 she wouldn't walk away just like that, she probably ate Batholomew at the end cos she is a monster :D
•  » » 6 years ago, # ^ | ← Rev. 2 →   +6 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.
•  » » » 6 years ago, # ^ |   +5 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.
•  » » » » 6 years ago, # ^ |   0 Not if a[i + 1] < a[i]
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 If she never eats anything, how can you account for the decrease in mushrooms between any 2 consecutive intervals? Which means, she has to eat that difference.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Then, how would you explain an input like210 5if 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.
•  » » » » » 6 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.
•  » » » » » » 6 years ago, # ^ |   0 "That's because the problem statement was written by a monkey." Lool :DI too couldn't understand the problem for a long time :P
•  » » » » » » 6 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 :)
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 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 :)
•  » » 6 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...
•  » » 6 years ago, # ^ |   +8 Yes, A was very difficult to understand. I just guessed what I should do, fortunately I guessed correctly.
•  » » 6 years ago, # ^ |   0 i could understand statement of the task A only in last 20 minutes of contest. really bad problem.
•  » » » 6 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.
•  » » 6 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..
•  » » » 6 years ago, # ^ |   +8 I think it is better to say:we'll look at how many pieces of mushroom are on her plate every 10 seconds.
•  » » » » 6 years ago, # ^ |   -8 i also think it is better to say:we'll look at how many pieces of mushroom that are on here plate on every intervalthe 10 seconds should be ignored IMHO.
•  » » 6 years ago, # ^ |   +3 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.
•  » » » 6 years ago, # ^ | ← Rev. 6 →   0 The problem wording itself is confusing for method 2. But i figured the secret from their example.with input 10 5 15 5 what you need to do is to get the difference between the maximum difference among each eating interval to find her eating rate (forget about the 10 seconds thingy) and then sum every other digit that is less than, equal or has up to that value.i.e the difference between 15 and 5 is 10, so we start from index 0 to sum 10 + 5 + (10 out of the 15) {cos her eating rate is 10} and that gives us 25.
 » 6 years ago, # | ← Rev. 4 →   0 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])
•  » » 6 years ago, # ^ | ← Rev. 2 →   +1 They will repeat starting from lcm(B[i]) (lowest^Wleast common multiple), not max(B[i])
•  » » » 6 years ago, # ^ |   +5 *least
•  » » » 6 years ago, # ^ |   0 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
•  » » » » 6 years ago, # ^ |   0 You missed a[2] in LCM
•  » » » » » 6 years ago, # ^ |   0 Thanks a lot slycelote :) It feels good to see "Correct!", although in Practice :P
 » 6 years ago, # |   0 What is the solution to B large?
•  » » 6 years ago, # ^ |   0 Can someone explain the Binary Search solution please?
•  » » » 6 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 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
•  » » » » 6 years ago, # ^ |   0 Thanks!
•  » » » » 6 years ago, # ^ |   0 Thanks for a great explanation akulsareen
•  » » 6 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.
 » 6 years ago, # |   +1 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, 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?
•  » » 6 years ago, # ^ | ← Rev. 2 →   +1 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
•  » » 6 years ago, # ^ |   0 It'll cycle every lcm(m[0], m[1], ...). But this solution will pass the small data only.
•  » » » 6 years ago, # ^ |   0 Can you please explain this in more detail?
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +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.
•  » » 6 years ago, # ^ |   0 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.
 » 6 years ago, # |   0 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 ?
•  » » 6 years ago, # ^ |   +1 Try all possible sets of trees being left and find convex hull for each of them?
•  » » 6 years ago, # ^ | ← Rev. 2 →   +1 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).
•  » » » 6 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.
•  » » » 6 years ago, # ^ |   0 Can you explain how to reduce the O(N3) solution to O(N2) using two pointers?
•  » » » » 6 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(N2logN), not O(N2).
•  » » » » » 6 years ago, # ^ |   0 Got it. Thanks a lot.
 » 6 years ago, # |   +1 Can anyone tell me when will this round be added to the gym ?
•  » » 6 years ago, # ^ |   +8 You can practice on codejam webpage.https://code.google.com/codejam/contest/4224486/dashboard
•  » » » 6 years ago, # ^ |   0 Yes I know, but I wanted to solve some of the questions in codeforces too, just like the qualification round. Anyways thanks.
 » 6 years ago, # |   0 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.
 » 6 years ago, # |   0 Can anyone help me how the question B is done? i mean the algorithm..? Thanks
•  » » 6 years ago, # ^ |   0 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).
•  » » » 6 years ago, # ^ |   0 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.
•  » » » » 6 years ago, # ^ |   +6 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.
•  » » » » » 6 years ago, # ^ |   0 Sorry I accidentally voted it less :( . Thanks I got the idea! Thanks very much :D :)
•  » » 6 years ago, # ^ | ← Rev. 4 →   +1 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
 » 6 years ago, # |   +13 Just noticed — among the people who passed thus far into Round 2:http://www.go-hero.net/jam/15/languagesPython 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.
•  » » 6 years ago, # ^ |   0 yeah.. java will take over in the next two rounds.
•  » » 6 years ago, # ^ |   0 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.
 » 6 years ago, # |   0 Got 0/100
•  » » 6 years ago, # ^ |   -16 me too. lets do our best in the next round. :)
•  » » 6 years ago, # ^ |   +16 Maybe you'd do better if you trained more and shitposted less?
 » 6 years ago, # |   0 Contest Analysis for Round 1A: Analysis