Does Arpa know russian language?

Do we need to try all posible GCDs in Div2 D ?

Has anybody got AC on div2C/div1A without using the logic in the editorial and without doing an O(n^3) brute ?

Can someone help me with complexity analysis of Div1C — Arpa and a game with Mojtaba (Grundy Number) ??

Div2C could be solved just with naive solution

And why do we calculate small number of DP values in Div2E?

For Div2B, why there is no solution when a, b, c are collinear in given order such that dis(a,b) = dis(b,c). Our rotation point is b and rotation angle is 0 deg.

Actually, one can observe that in Div2 C (with n greater than two of course, with the other case being trivial), it is impossible to have more than one good point, and that point must be one of the endpoints of the shortest segment.

Let A and B be good points, and C be another point. Points A,B,C define either a line or a triangle, in both cases there can only be one angle that is not acute.

For the second part, let AB be the shortest segment and C be the good point. Then AB is the shortest edge of triangle ABC, making the angle between AC and BC acute, a contradiction.

Something that might be good to have in mind:

If you just calculate only for the primes on problem Div1B/Div2D the complexity is O(maxvalue * log(log(maxvalue)))

In the five dimension points problem, isnt there 64 quadrants instead of 10? that is, 2^k instead of 2*k in k-dimension

UPD: I got it now, 2^k is the number of quadrants in k dimention and even though it is a correct upperbound for n in which it is impossible to have a "good" point, 2*k is a still correct and smaller upperbound. Think about a 3 dimensional coordinate system. Put a point in origin. Now try to put as much points as you can so that the origin is a good point. Well, the best you can do is to put points equally espaced by the minimun angle that they need to be good, that is, 90 degrees. So you put one point in every axis, both in positive and negative directions, that is, +x, -x, +y, -y, +z, -z. There are 2*3=6 points, if you put any other point, the origin point will no longer be good. So 2*k+1 is the maximun number of points you can have in k-dimensionso that there can exist a good point

div2 B: I know that I'm dumb, but why the point around which we rotate the plane and the angle are always exist if ABC is a isosceles triangle?

Where's this point and what's the angle? -_-

My solution for Div1B is different so I thought I'd share. We can basically treat this problem as three different cases. Case 1: x<=y. If x<=y then it is never better to increment a value, so we just find the prime number that is a divisor of the most numbers and the answer is x*(n-(number of given numbers that said prime number is a divisor of)). Case 2: y<x and x<=2y. If this is true then it is never better to increment a value more than once. Let a[i] be the number of given numbers that are divisible by i, and b[i] be the number of given numbers that are one less than a number divisible by i. The answer is then the minimal value of y*b[i]+(n-a[i]-b[i])*x among all prime numbers. Last Case 3: y < x and x > 2y. We know that the answer will be <= n*y because we can increment or not increment every value to make it even. Let's say the gcd we are trying to achieve is a multiple of prime number "p". Let z be ((the number of given numbers p is a divisor of) + (the number of given numbers p is a divisor of if we add 1 to all given numbers)), then when z<n/2 the cost of trying to achieve its gcd would be >= (n/2)*2y which is >= 2ny which we can always achieve. Thus we can brute force checking the minimal cost for all prime numbers that have z>=n/2 (and trying the prime number 2). There are at most 4*log(n) such prime numbers. Thus overall solution is O(N log N).

Could anyone please provide a proof of problem Div2B?or any link!I couldn't find any proof.Thanks!

I think there are some mistakes in the equations in the editorial of Div1B/Div2D. According to the given definitions of letters, shouldn't the implication look like this ?

Sadly, such mistakes make understanding the tutorial a lot harder or even impossible :/

The Lemma for Div2C/Div1A is also an important lemma for APMO 2017 Problem 5.

See http://artofproblemsolving.com/community/c6h1446917p8273269

Can someone, please, elaborate on how (and why it works) to build the tournament graph given the list of out degrees of every node in problem D?

No analysis on the maximum number of DP states in the worst case in Div1-C?

Can anyone explain why the DP in Problem F is t(r) = p / 2 × t(r - 1) + p / 2 × t(r + 1) + r / S but not t(r) = p / 2 × t(r - 1) + p / 2 × t(r + 1) + 1?

Can anyone please explain this in Div2D/Div1B,

Now for each multiple of g like k, let's find the cost of numbers in the range (k - g, k], and sum up these values. We must find the best f and divide the range into two segments (k - g, f] and (f, k] and delete the numbers in the first range and add the numbers in second range till they become k.

Div2B : Can anybody tell me, what is difference in these codes ? One is accepted, but other one is not.

Accepted code

Failed code

I got accepted in Div2 D problem. But I don't understand how can we ensure the final number list is non-empty?

Arpa Can you please share the proof of complexity in problem Div1C

in div2 B the given hints is that if the three points cannot form a circle then the answer is NO....but the test case 6 (49152 0 0 0 0 81920 ) answer is NO but we can form a circle using any (a, 0), (0, 0), (0, b) with it's centre at (a/2, b/2).....if i am missing something then please correct me!

Proof of time complexity of Div1C:

Each bitmask has at most 30 bits (because 2^30 < 10^9), and let's think how many bitmasks appears when we calculate grundy number:

If bitmask for prime p has k bits (1<=k<=30), the number of possible bitmasks which has m bits is:

(1<=m<=k/2) at most 2^m (this is obviously true)

(k/2<=m<=k) at most 2^(k-m) (because later 2*m-k bits of m bits never change)

so,the number is at most 2^1+....2^(k/2)+....2^0, which is at most 10^5.

And, there are at most 9*n prime numbers which divides at least one element of a. (because 2*3*...*29>10^9, and 29 is 10-th prime number)

In conclusion, the number of calculation of grundy number must be at most 10^5*9*n <= 9*10^7, and which is too large in relation to the true number, so it works very fast in practice.

Wouldn't there be 32 quadrants in 5 dimensions?If we put a point (0,0,0,0,0) and other points such that vector between 0 and those points is 45 degree inclined from each axis in each quadrant we can set points such that angle between two vectors are not acute. Hence for 33 points we can get (0,0,0,0,0) as a good point. Correct me if i am wrong.

problem B div2: 851B - Arpa and an exam about geometry any 3 non co-linear points could generate a triangle, and any triangle could generate a circle. https://en.wikipedia.org/wiki/Circumscribed_circle and the center of the circle is the intersection point of the triangle medians ,so we now have a circle and we are just need to prove that the angle of rotation between (A,B) equals the angle of rotation between (B,C) let the angle (x) and from the shape below we can see that those two triangles must be identical cause of three equal angles and two equal sides , we just need to check that dis(a,b)==dis(b,c) so that the two angles are equal. sol : http://codeforces.me/contest/851/submission/30098274

Thanks for the interesting contest and editorial.

The following is a C++14 main() function of the brute-force algorithm for Problem 851C - Five Dimensional Points:

int main()
{
    multi_dimensional_points< 5, 1000 > problem;

    problem.brute_force();

    problem.write_solution();
}

template< const size_t M, const size_t N > class multi_dimensional_points { .... };

is a generalization of the brute-force algorithm, where the problem is generalized to M-dimensional points, and N is the maximum number of points. The full-implementation is shown in submission 30115750.

Best Regards

Problem E is just a complicated statement combine with a well-known xor convolution.

For problem 850B — Arpa and a list of numbers If the input is: 1 2 6 1 What should the output be? If we delete the only element, then does the gcd exist? Sorry for my poor English.

For 850B — Arpa and a list of numbers. We could solve in this way! Maybe the test data is a little week?

Anyone getting Wrong Answer on test case 40 on Div2 B? I can't see why... Maybe floating point errors?

In Div1F, it is possible to find t(r) using a recurrence relation: t(0) = 0, and . The first is trivial, the second can be found experimentally, and the third easily follows from .

About Div1D. Does someone prove that there are no "Impossible case" or construct such one?

Can someone explain how to solve div1 E?

I think in problem F it's clearer to let t(r) = E(number of steps taken if we reach S at the end, otherwise 0), then everything that follows makes perfect sense. If we make it conditional on reaching S first, then probabilties of moving to r-1 and r+1 aren't equal and overall it's a bit messier(but still doable).

Anyone find my bug that gets WA on 25 for Div 1 B?

include

include

include

define MAXN 500500

using namespace std; typedef long long ll; vector factors[2*MAXN]; ll c[2*MAXN][3]; ll N, x, y; int a[MAXN]; ll ans, cur; int main() { ans = 1e18; for(int i=2; i<(2*MAXN); i++) { if(factors[i].empty()) { for(int j=1; j<((2*MAXN)/i); j++) { factors[i*j].push_back(i); } } } cin>>N>>x>>y; for(int i=0; i<(2*MAXN); i++) { c[i][2] = N; } for(int i=0; i<N; i++) { cin>>a[i]; for(int j=0; j<factors[a[i]].size(); j++) { c[factors[a[i]][j]][2]--; c[factors[a[i]][j]][0]++; } for(int j=0; j<factors[a[i]+1].size(); j++) { c[factors[a[i]+1][j]][2]--; c[factors[a[i]+1][j]][1]++; } } if(x < y) { for(int i=0; i<(2*MAXN); i++) { ans = min(ans, x*(N-c[i][0])); } } else if(x < (2*y)) { for(int i=0; i<(2*MAXN); i++) { ans = min(ans, y*c[i][1] + x*c[i][2]); } } else { for(int i=0; i<(2*MAXN); i++) { cur = 0; if(c[i][2] <= N/2) { for(int j=0; j<N; j++) { cur += min(x, y*(((i*10000000)-(ll)(a[j]))%i)); } ans = min(ans, cur); } } } cout<<ans<<endl; }

In div2D/div1B,

Now for each multiple of g like k, let's find the cost of numbers in the range (k - g, k], and sum up these values. We must find the best f and divide the range into two segments (k - g, f] and (f, k] and delete the numbers in the first range and add the numbers in second range till they become k. Now to find the best value for f,(g-f)*y=x/y => f=g-min(g,x/y).

How do you get the equation (g-f)*y=x/y => f=g-min(g,x/y)?what does this mean? Is this some feature of this problem? Can someone explain please,thank you in advance.

Hi, for 850B I simply just brute-forced the top 10 most popular prime factors, can anyone hack this idea or prove why it works?

submission: 74588035