### Wild_Hamster's blog

By Wild_Hamster, 6 years ago, translation,

In fact need to do what is asked in the statement. We need to find in a cycle the maximum height h, counting, how many blocks must be in i-th row and adding these values to the result. Iterate until the result is not greater than n.

Jury's solution: 8924831

Sort lanterns in non-decreasing order. Then we need to find maximal distance between two neighbour lanterns, let it be maxdist. Also we need to consider street bounds and count distances from outside lanterns to street bounds, it will be (a[0] - 0) and (l - a[n - 1]). The answer will be max(maxdist / 2, max(a[0] - 0, l - a[n - 1]))

Time complexity O(nlogn).

Jury's solution: 8924823

Sort (ai, bi) in non-decreasing order for number of essays bi, after that go from the beginning of this sorted pairs and add greedily the maximal number of points we can, i.e. add value min(avg * n - sum, r - ai), while total amount of points will not be greater, than avg * n.

Time complexity O(nlogn).

Jury's solution: 8924807

Let's create vector rez with size x + y, in which there will be a sequence of Vanya's and Vova's strikes for the first second. To do this, we can take 2 variables cntx = cnty = 0. Then while cntx < x and cnty < y, we will check 3 conditions:

1) If (cntx + 1) / x > (cnty + 1) / y, then add into the vector word “Vova”, cnty++.

2) If (cntx + 1) / x < (cnty + 1) / y, then add into the vector word “Vanya”, cntx++.

3) If (cntx + 1) / x = (cnty + 1) / y, then add into the vector word “Both” 2 times, cntx++, cnty++.

Then we are able to respond on each query for О(1), the answer will be rez[(ai - 1)mod(x + y)].

Time complexity O(x + y).

Jury's solution: 8924773

As long as gcd(dx, n) = gcd(dy, n) = 1, Vanya will do full cycle for n moves. Let's group all possible pathes into n groups, where 1 - th, 2 - nd, ... , n - th path will be started from points (0, 0), (0, 1), …, (0, n - 1). Let's look on first path: (0, 0) - (dx, dy) - ((2 * dx) mod n, (2 * dy) mod n) - ... - (((n - 1) * dx) mod n, ((n - 1) * dy) mod n). As long as gcd(dx, n) = 1, among the first coordinates of points of the path there will be all the numbers from 0 to n - 1. So we can write in the array all relations between the first and second coordinate in points for the path, that starts in the point (0, 0), i.e. y[0] = 0, y[dx] = dy, ... , y[((n - 1) * dx) mod n] = ((n - 1) * dy) mod n. Now we know, that all points with type (i, y[i]), where 0 ≤ i ≤ n - 1, belong to the group with start point (0, 0). In that case, points with type (i, (y[i] + k)modn) belong to the group with start point (0, k). Then we can add every point (xi, yi) to required group k for О(1): (y[xi] + k) mod n = yi, k = (yi - y[xi] + n) mod n. Then we need just to find group with the maximal amount of elements, it will be the answer.

Time complexity O(n).

Jury's solution: 8924746

P.S. Sorry for my bad English, I hope, I will correct this editorial as much, as possible.

• +50

 » 6 years ago, # |   +5 I cant access the solution codes
•  » » 6 years ago, # ^ | ← Rev. 2 →   +2 Yes, sorry, will be fixed soon. UPD: fixed
 » 6 years ago, # |   +3 There'a typo above for 492D — Vanya and Computer Game. It should be cnty++ in case 1 and cntx++ in case 2.
 » 6 years ago, # | ← Rev. 4 →   +8 Problem D can also be done using binary search. Take an array of 0 to LCM(x,y). Player hitting at x would now hit at lx = LCM / x, similar for y. At every point P, number of hits = P/lx + P/ly. So, find the least point P such that number of hits is a % (x+y). If both divide this point, then answer is both, otherwise the one who divides will be the answer. Complexity -> O(log(x) + log(y)) per query.
 » 6 years ago, # |   0 If (cntx + 1) / x = (cnty + 1) / y then why we add word “Both” 2 times and cntx++, cnty++. Can someone please explain.
•  » » 6 years ago, # ^ |   +1 If i-th hit was in the same time with (i+1)-th hit, it mean that res[i]=both and it also mean that res[i+1]=both
•  » » » 6 years ago, # ^ |   0 Thanks bro :)
•  » » » 6 years ago, # ^ |   0 I was confused by this I thought only one monster gets the shot and it is consider only one shot during the contest
•  » » » » 6 years ago, # ^ |   0 I also thought the same
•  » » 6 years ago, # ^ |   +3 Here vector rez contain who will give i th hit.By (cntx+1)/x or (cnty+1)/y we are calculating the time need to perform cntx+1 th hit for x or cnty+1 th hit for y. If the times are same thats means two hit will be performed simultaneously. Let x perform 5 hits and y perform 4 hits in same time. So 8th hit and 9th hit will be performed simultaneously. If the monster die in 8th hit who will hit last? The answer is Both,because they hits simultaneously. Same for the 9th hit. So for 8th and 9th hit we will add Both in our vector.That is why when (cntx + 1) / x = (cnty + 1) / y then we add word “Both” 2 times in the vector.
 » 6 years ago, # | ← Rev. 5 →   0 Hi! Can anyone explain this test case for D? 7 5 2026272829303132Vova hits twice at 1/20 and 2/20 to knock out first monster. "Vova"Then Vova strikes at 3/20 and Both strike at 4/20 to knock out the second monster. "Both"Again, Vova strikes twice at 5/20 and 6/20 to knock out third.. and so on.Why is the answer VovaVovaVovaBothBothVovaVova ?PS: This is test 3.
•  » » 6 years ago, # ^ |   0 If Vova and Vanya hit at the same time, it will score as two hits. You could find it in notes of problem D: ''In the first sample Vanya makes the first hit at time 1 / 3, Vova makes the second hit at time 1 / 2, Vanya makes the third hit at time 2 / 3, and both boys make the fourth and fifth hit simultaneously at the time 1''.
•  » » » 6 years ago, # ^ |   0 i tgt if both hit at the same time it will be counted as one hit :(
 » 6 years ago, # |   0 I may be wrong, but in problem E:shouldn't it be O(n+m)? I know that the bounds for n and m are of the same order so it shouldn't matter, just asking for technicality of the analysis.Loved this contest, really nice problems! :)
•  » » 6 years ago, # ^ |   0 Yes, but n is 10 times greater than m, so I decided not to include it to time complexity
 » 6 years ago, # |   +12 For problem E, there is also an O(mlogm) solution.Consider two points (x1, y1) and (x2, y2), if we start our move at point (x1, y1) and we can see point (x2, y2) along our path, then following equation will be true:We can multiple each side by dx * dy and get this:So we calculate value xi * dy - yi * dx for each apple tree and count frequency for each of these values by a data structure like map in C++. And answer is an apple tree at point (xi, yi) such that count[xi * dy - yi * dx] is maximum.My submission: 8945734
•  » » 6 years ago, # ^ |   0 good, we can do it without maps, since x1 * dy - y1 * dx(modn) < n, so it will be O(m). I tried to submit it and it got AC.
•  » » » 6 years ago, # ^ |   +3 In your solution memory complexity is O(n), My main target was achieve an efficient solution that is independent of parameter n.
•  » » » » 6 years ago, # ^ |   0 I have the same solution like yours. In this case, we can archive an O(m log m) solution no matter what n is. :)
•  » » 6 years ago, # ^ |   0 Nice solution :) Using unordered_map it should become clearly O(m)
 » 6 years ago, # |   0 For problem D I have different approach that I think is correct ,but it gets wrong answer on test 11 . So,idea is following :We know that Vanya attacks with frequency x hits in second, and Vova y hits in second , 1/x and 1/y for 1 hit respectively or ( lcm(x,y)/x ) / lcm(x,y) and ( lcm(x,y)/y )/lcm(x,y) .Lets x1=lcm(x,y)/x and y1=lcm(x,y)/y.It's easy to see that if(n%(x1+x2)==0 or (n+1)%(x1+x2)==0) than answer is "Both" , after that lets k=y1/x1(lets assume y1>=x1) than if(n%(k+1)==0) than answer is person who shots less productively. Otherways answer is person who shots more productively. this is my solution .Can you help me? Is my approach wrong?
•  » » 6 years ago, # ^ |   0 x=3, y=5 ==> k=1 Hits by user: 1. Y 2. X 3. Y 4. Y 5. X 6. Y 7. Both 8. Both Hits by your algorithm: 1. Y 2. X 3. Y 4. X 5. Y 6. X 7. Both? 8. Both? 
 » 6 years ago, # |   0 Problem C:I got time limit exceeded during the system testing phase.After contest, I compared my code with others and the only difference I found the array size.I increased the array size and got accepted! But I don't understand why?It is given N is 1<=N<=100000 and I took array of size 100005. Why this will give TLE? Can anyone explain please?
•  » » 6 years ago, # ^ |   0 Please, give your codes links for clear understanding.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 As far I saw in your last submissions, the size of array is not the main matter. You did another change in your accepted code which caused TLE before. That is in line 14: if(a.hw == b.hw) return a.score<=b.score;  In the accepted code, you commented it. Thanks.
•  » » » 6 years ago, # ^ |   0 Hello manetsus,Yes, you are correct. The TLE occured due to that line in the compare function. But, still, why this should be?If the homework value equals, I sorted them according to score value. I know that, it doesn't have any significant impact on the result, then why should it get TLE?Anyway, thanks for your favor.
 » 6 years ago, # |   0 I don't get why the output of Test#1 B is 2.5000.Check my drawing :P The answer should be 2.0 not 2.5. I saw some solutions sorting for (nlogn) then doing 14 — 9 = 5/2 = 2.500 but this makes no sense if you think at it as the drawing. Don't see why you need to sort, if you can just pass a sliding window to find the biggest gap and divide by 2.0 to find that d = 2.0.Please enlighten me ^^
•  » » 6 years ago, # ^ |   0 Latterns are points, not squares. So longest distance is 14 - 9 = 5,
•  » » » 6 years ago, # ^ |   0 Thanks for explaining. Approaching the problem this way, I can get 2.5, but I think the problem description failed to inform that.
•  » » » 3 years ago, # ^ |   0 No, It's not that, because if it was like you said, the second sample's answer should be 2.5 also.So, it's just that the answer provided in the editorial is wrong when either we consider the lanterns are squares or points in the middle of squares. So, that should be elaborated in the statement, then the editorial answer should be corrected.Sorry for the annoyance if it's existed.
 » 6 years ago, # |   0 Problem D can be done in O(log(x+y) + n), preprocess costs O(log(x+y)), each query costs O(1). Here is my solution http://codeforces.com/contest/492/submission/9386556
 » 6 years ago, # |   0 hi, can anyone explain me why my O(n*log(n)) solution for problem B get time limit? I used binary search to find the answer... I solve the problem this way:read(n,l); for(i=0;i> a[i]; sort(a); left=0; right=l;while(right-left>eps){ //eps=10e-9 d=(left+right)/2; if(enough(d)) right=d; else left=d;} bool enough(d){ flag=true; for(i=1;i2*d){ flag=false; break; }if(a[0]-d>0 or a[n-1]+d
 » 6 years ago, # |   0 here is my code 12324117
 » 5 years ago, # |   0 For test case 9, codeforces compiler is outputting 16 while my computer gives 12 which is the write answer. Can someone please help? Why codeforce compiler and my computer compiler give different answers??Thank You.
 » 3 years ago, # |   0 In problem C , Why do we subtract ( r — Gradei ) ?
 » 3 years ago, # | ← Rev. 2 →   0 For problem C I think the note for the first sample input is wrong because it says he will get 1 point for writing 2 essays... Nevermind, it's 2 essays because that was the cost.
»
11 months ago, # |
0

# include

using namespace std;

int a[1006];

int main(void) { int n, l; cin>>n>>l;

for(int i= 0; i<n; i++){
cin>>a[i];
}

double mx= 0, temp;
sort(a, a+n);

for(int i= 1; i<n; i++){
temp= abs(a[i]-a[i-1]);

if(mx < temp) mx= temp;
}

mx = (double)mx/2;

// may one explain why are we doing finding the maximum value of the (a[0],max) and max(a[n-1],mx) in the problem .... //

mx= fmax(mx, a[0]);
mx= fmax(mx, abs(a[n-1] - l) );

cout<<fixed;
cout.precision(9);
cout<< mx <<endl;
return 0;

}

»
8 months ago, # |
0

its not printing double values

# include<bits/stdc++.h>

using namespace std;

int main(){ int n,l; double * a=new double[n];

for(int i=0;i<n;i++){
cin>>a[i];
}

sort(a,a+n);

double rez=max(a[0],l-a[n-1]);

for(int i=1;i<n;i++){
rez=max(rez,a[i]-a[i-1]);
}
cout<<rez/2;

}

•  » » 8 months ago, # ^ |   0 use 'fixed' and 'setprecision'
 » 7 months ago, # |   0 Why there's a "binary search" tag for question B?
•  » » 6 months ago, # ^ | ← Rev. 3 →   -10 are tags decided by authors??
 » 4 months ago, # |   0 In B qn , 3rd test case i got 22258200.0000000000 but it is given 22258199.5000000000.I have already printing in float with %0.10f precision in format specifier.Here's my code 102146123
•  » » 6 weeks ago, # ^ |   0 same with me