offtop

This is first time that this question is logical to be asked :)

.

it's just because KAN is the coordinator of rounds.

exm???

Actually lolzano and Cydiater got downvotes because they copied his comment.

Codeforces rounds are rated by default. If a round is unrated they will write that in the announcment.

Why would you "come to increase your contribution"? Do you write comments just for meaningless internet points? Contribution should be the result of your comments, but not the reason for it.

If I were you, I would never comment lol :P

How do the screenshots help exactly ?

Well, due to the unrated, maybe I have lost more than 100 rating.

But...

Where is my Akagi?

(ノ=Д=)ノ┻━┻

+1 :p

you're not the only one

I guess BBT stands for Big Bang Theory. Anyway, this strategy proven to yield the best results during the last 2 div2 rounds...

Because A, B are extremely shitty, I guess

you're Right -_-

I think brute-force + math is enough!

I fixed 2 points 1 and 2 and checked all the of the angle with third point. Say n = 5, so interior angle is 108 and increment in angle is 36 so possible values are 36,72,108. I dont know if it is correct

The angles are integral multiple of (180/n)*i where 1<=i<=n-2.

I think when you experiment with a few n-sided polygons then you realize that the total number of angles you can form with three points is n-2. Then you just iterate through all possible angles to get your optimal answer.

The idea in my mind is about: Calculate the angles of 0-1-(n-1), 0-1-(n-2) ... iterately by using sine & cosine theorem, then just binary search for the answer.

Say you are considering angle A-0-X with fixed A and unknown X, this angle equals to (0-1-2) — minus the angles at the two sides, which you can lookup and binary search from the preprocessed values, use binary search to find the two Xs which are just below & above the desired angle.

I think what you try to pair V[1], V[i] and to a binary search for the third one.

this my approach :

each angle = 180 * (n — 2) / n

you can divide each angle to (n-2) parts , the degree of each part = angle / # of parts

start withe one part and loop , each time add a part and optimize your ans.

O(N)

It isn't much math, really. There's no need for ternary search. You have to consider the circumference the the polygon is inside, then the only observation you have to make is that after fixing the size of the arc, any point would suffice as midpoint. (consider a, b and c as points of the polygon. For simplicity, a=1. Also, a < b < c. Then, for every c you choose the angle formed by acb (in this order) is the same).

How to solve B:

First notice that any interior angle for a regular polygon is (n — 2) * 180.

Second note that if we take 2 1 as V1 and V2 we can see that we can iterate from 3 to n and try each one as v3 because N is small enough.

Now we see that the difference between 2 1 x and 2 1 (x + 1) is always the same which is (((n — 2) * 180) / (n — 2)).

So just look up all possible v3 and choose the best one.

Just realize the angle with Vj-1 Vi Vj+1 formula is equal to eachother, then i just do some stuff with some conditions.

Actually stupid case analysis is necessary as far as I understood.

You can divide cases with b >= a and a > b, and again, r-l+1 >= period and r-l+1 < period where period = 2*(b+a)

Consider these cases a = 4, b = 2 : abcd,dd,abef,ff repeats in optimal answer, and a = 2, b = 2 : ab,bb,ac,cc repeats in optimal answer. In the first case, if the query interval is equal to or longer than the period, then answer is clearly 2*a-b, and in the latter case, it's a+1. If the length of query is shorter than the period, then we can just loop over the string which contains only one period.

I solved it by checking the length of the interval, and if the interval is small (say R-L <= 100) then I brute-force the solution with simulation, and if the interval is bigger, I just calculate the worst case and print that.

Case analysis and modulo?

For instance when b < a, I was thinking maybe the first 2*a+b characters can be repeated. Knowing this we can iterate from min(L%n, R%n) to max(L%n, R%n) where n=2*a+b. But I don't know if this is correct. :(

No need for case analysis actually. I used bruteforce to compute first 12 * (a + b) characters (random constant) and then, if r - l was long enough — print number of different characters in string, otherwise modulo l with length of the pattern and count distinct characters in substring of right size.

By your way to solve, I think you will ask about A B C D :)

Check the angle between the diagonals starting from one verticle.

Because of symmetry, you can fix the first vertex of the angle, and itterate the other 2 vertices. To avoid O(N^2) complexity, you can only itterate the second vertex, and find the optimal third vertex using binary-search. All you need is a function that calculates the angle of 3 given vertices in a regular n-gon.

You can calculate dev[i] = deviation of permutation with i cyclic shifts. You can calculate it fast with prefix sums.

Problem is Div2B

I tried but failed. Maybe try to use prefix sums? Here's my code:

/**
3
3 2 1
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define mod(x) ((x+n)%n)
int main()
{
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	int n;
	cin >> n;
	int p[n];
	for (int i = 0; i < n; i++)
	{
		cin >> p[i];
		p[i]--;
	}
	ll x[n];
	for (int i = 0; i < n; i++)
		x[i] = 0;
	for (int i = 0; i < n; i++)
	{
		if (i < p[i])
		{
			x[mod(1)]++;
			x[mod(n &mdash; p[i] &mdash; i)]++;
			x[mod(n &mdash; p[i] &mdash; i + 1)]++;
		}
		if (i > p[i])
		{
			x[mod(1)]--;
			x[mod(i &mdash; p[i])]++;
			x[mod(i &mdash; p[i] + 1)]++;
		}
		if (i == p[i])
		{
			x[mod(1)]++;
		}
		x[mod(i + 1)]--;
		x[mod(i + 2)]--;
		x[i + 1] += n &mdash; 2 * p[i];
		x[i + 2] -= n &mdash; 2 * p[i];
	}
	for (int i = 1; i < n; i++)
	{
		x[i] = x[i &mdash; 1] + x[i];
	}
	ll k = 0;
	for (int i = 0; i < n; i++)
	{
		k += abs(p[i] &mdash; i);
	}
	for (int i = 0; i < n; i++)
	{
		x[i] += k;
	}
	ll mini = 10000000000000ll;
	ll id = 0;
	for (int i = 0; i < n; i++)
	{
		if (x[i] < mini)
		{
			mini = x[i];
			id = i;
		}
	}
	cout << mini << " " << id << endl;
}

Given a[], foreach a[i] — i > 0 push (a[i] — i + t) where t is the current time into a heap, for each iteration, update the value that has been newly pushed to the front, plus one for each element which is not in the heap, minus one for each elemnet which is not in the heap, pop elements from the heap if time = a[i] — i + t, as now a[i] — i should be >= 0.

Edit: It appears that O(nlogn) is not good enough, to achieve O(n), use prefix sum as others mention to store the updates instead of using a heap. The idea remains simular.

I greedily generated string upto 2*(a+b) length such that Mr. B always choose the last character from the generated string so far. Ex — If the string so far is "abcde" then Mr. B will form string "eeee..." and merge it to the original string i.e "abcdeeee...". After generating the string I mapped the value of 'l' to smaller string by taking mod with (a+b). http://mirror.codeforces.com/contest/820/submission/28096854

I didn't solve the problem at contest time, but I think that the first thing to do here is to split the problem in two cases:

if r — l + 1 >= 2 * (a + b)

in this case the person A is going to put a different letters for sure, since there is at least a segment of a letters in which person A is going to put his different letters. Since person B should play optimally then he's going to put the same letter and it should be one of the letters from the first A segment. but since there are 2 segments for A, then A cannot put the same letters as in the first segment since B already put one letter and A look for a suffix of at least 1.

So, in this case the solution is a + 1

else

simulation, starting from l to r starting with the letters from A or B depending on l % (a+b)

I did BS then I realized it's 10^5

I did the same :D

Why? I thought that it was interesting.

I don't know whether it's good or not, but I am sure that people won't like that task ))

UPD : It is also very bad lolololol

*the whole contest

Solution for A:

1. Prove that the best strategy the human player may use is repeating the last character in the string b times.
2. Show the string generated by this strategy is periodic with period 2·(a + b) ≤ 48 (or strongly believe it holds so hoping you are right). Generate the first 48 characters by means of brute force.
3. If r - l + 1 > 2·(a + b) then lower r so that brute forcing [l, r] becomes manageable.
4. Freak out and increase 2 to 6 and 48 to a + 400·(a + b) just to make sure.
5. Profit ...

Edit: It fails like most passing solutions, unfortunately. Details below.

Could you explain your solution a little more.

Third paragraph:

"Initially the players have a string s consisting of the first a English letters in alphabetical order (for example, if a = 5, then s equals to "abcde")."

You don't need Law of Cosines to solve B.

Кажется, оно предполагалось за O(N), судя по ограничениям)

Вы знаете слишком много алгоритмов, это вам вредит

The constraints are small enough that you can just simulate reading every page. No need for some fancy solution :)

EDIT: I forgot that div1 exists, my mistake... :)

You just have to check cases. If the gap between l and r is too big, then the answer can be calculated just from a and b, if the gap is small enough, then you can generate the string, and simply check.

I agree. E is the easiest, I think.