you can read the first line it cleary says that is rated for div2 participants/

king_tsar Is this you? lol

Good luck! :)

when you learn grammar!

LOL, LMAO, ROFL. No, it's not solved like that.

Normal solution: there are three kinds of inversions:

1. Inversions between known elements — they are calculated by your favourite method (Fenwick / mergesort)
2. Inversions between unknown elements — if there are P unknown elements, they form P*(P-1)/4 inversions due to symmetry
3. The last case is when one element is known, and the other is unknown. Let the known element be x, and there are some free places to the left and some free places to the right. For each of free left places, there is an inversion if you put element > x there (find count of these elements by lower_bound). For each of free right places, there is an inversion if you put element < x there (find count of these elements by lower_bound). And the rest is easy.

First idea and very overkill is next: let and , then your sum is coefficient of z^m of a convolution A × B or something like this (if you calculating with modules). Convolution FFT.

Does anyone know why my nlogn solution is timing out?

https://mirror.codeforces.com/contest/1096/submission/47665224

Trivial when you know how to accelerate polynomial multiplication using Fast Fourier Transform.

F is easier than D

Count length of prefix and suffix such that all characters in the prefix/suffix are equal.

if prefix == n, answer is n * (n+1) /2

if first char == last char, answer is (prefix+1) * (suffix+1)

else the answer is 1 + prefix + suffix

Edit: first case won't happen

It showed me Wrong answer on test 1

But it was correct

I'll take that as a yes

i don't know, but my solution is this rsrs.

Yeah, that dp should work.

Me too :( 47654227

Test 4 catches a lot of bugs; from a quick scan of your code, it seems like you made the assumption that the solution must be removing all the occurrences of one letter. This isn't the case. Consider if the string is "harard", where the first a and the last r are very cheap to remove, but everything else is very expensive. Removing those two letters would be the solution.

The general problem is solved using DP.

Multiple of pi(180) which is multiple of alpha angle. Also check that internal angle obtained is greater than or equal to alpha angle.

for every side length k from 3 to 360:

smallest angle = 360/(k*2) biggest angle = 180-360/k

every angle in between is a multiple of the smallest angle. If the angle you're being asked is between the smallest and biggest angle and it is a multiple of the smallest angle, then the answer is k.

I've solved it and here is a link to my solution: https://mirror.codeforces.com/contest/1096/submission/47665926

You may want to read below to understand it.

EXPLANATION:

It's a property from grade 10 (high school) maths.

If you draw a circumscribed circle around the regular polygon, the angle subtended (by any two vertices/arc) at the centre of the polygon will always be double of angle subtended anywhere on the circle.

Here is a youtube link if you want the proof: https://www.youtube.com/watch?v=MyzGVbCHh5M

============ Steps ===========

1) The input needs us to find a suitable "n" for a given query angle "q". What we do is find suitable "n" for angle subtended at the centre of the circle. which is 2* q.

2) But how do we find "n" ?

Total angle subtended at the centre of a circle by any two vertices can be a max of 360 (to be precise, some decimal value < 360). Hence if you have "n" vertices, you can "distribute" this 360 between the vertices.

What I mean by that is that if there are 10 vertices, then every 2 adjacent vertices will subtend 360/10 (=36) at the centre.

To find "n", we need to use a loop , eg: for(n = 3; n <= 360; ++n) Start from n = 3, so that you can get minimum "n" once below condition is satisfied. On finding it, break from the loop.

// NOTE: For this problem, "360/n" must also be an integer. Hence you must // ignore values of "n" if "360 % n != 0"

if( (2*q) % (360/n) == 0 ) {

// found n. 
//Break from loop if you have structured your code that way.

}

This condition means that if our required subtended angle (2*q) is a multiple of the minimum possible subtended angle for a given "n", then we have found "n" (there is an edge case, see Note below)

=======

FINAL NOTE: There is an edge case in the sample input and output given in the problem statement, the 4th input (178) has output 180, and not 90. this is hard to explain in words but much easier to understand visually. I have commented about this in my solution (linked above) as well. Please see that comment and try drawing it out if you don't follow.

Not even with TNT man.

that problem is really hard.

neal did it 47640712

I did it. To avoid precision error, I used the well-known technique that decomposes each integer into two parts. Calculate both on the real and imaginary part to reduce some factors. Basically, it's the template that tourist uses, very well-implemented and works with arbitrary modulos.

Is it that you didn't read problem F and G, or just that you're too weak to learn how to solve them?

Mind your own GOD DAMN business!!!

Prove that the two accounts have something in common. Basically all you do now is accusing 2 innocent people without any proof. Go learn some programming, green boi

I guess u r subscribed to T Series. Get out of my sight

What's the corner case on C?

can u help me with solution for C?

The output is just different... if your compiler is not giving the same answer you should make sure they are consistent but I feel it may just be you not looking closlely

Integer overflow in line 36.

DP[i][j] = minimum cost to delete the first 'j' characters of "hard" from prefix i.

That assumption is incorrect.

It's just the issue with constant. Well-implemented FFT can pass,too.

D&C + polynomail multiplication is .

Or did you use some special version of D&C?

Print 179 instead of 180

range(1,180) is only 179 numbers, since the last value is exclusive. You promised 180 test cases.

I think all cases are included in pretest 3.

Refer to NTT Ahmed- Link: https://mirror.codeforces.com/blog/entry/48798 You can also deal with MOD in FFT:(See trick number 17) https://mirror.codeforces.com/blog/entry/48417

For example when someone has an "if (time(0) > x) exit(0);" and time(0) is now greater than x while it was smaller during contest, the solution will fail when a hack is performed now. Example given: https://mirror.codeforces.com/contest/1088/submission/46594591 . Although it's totally useless to have this in your code, it's a possible way to hack C now.

Even though ERs sound like regular Div2 and behave like regular Div2, we (authors) still believe that it's not a regular Div2. That's why we allow ourselves more freedom in using "well-known" ideas (but still trying hard to find a balance).

Of course, it will lead to some disturbance of ratings, but it's a thing we should deal with.

On the other hand, if newcomers wouldn't confront new for themselves but famous in community tasks, they will not learn them. And I think, ER is a perfect place to meet with such tasks.

It's just . Use the linearity of expectations.

Handle ang = 179 separately, n= 360;
(This is because for every angle less than 179, we can attain it using a polygon with no. of sides n <=180)

For other values of ang:
Start with no. of sides s = min(3, ceil(360/(180-ang)))[This checks if the minimum angle possible in the polygon is greater than or equal to ang ] This was derived from, angle of a regular n-gon = (n-2)*180/n;

Now we need to satisfy,
i*ang == j*180; (for some s<=i<=180, and j<i)
(Idea behind this is: ang/180 == j/i; ie "ratio of ang to the total angle of a triangle" should be equal to the "ratio of no of sides opposite of ang to the total no. of sides of the polygon") This can be done by brute-forcing on i and j;
Thus complexity is O(n^3).
Here's my submission.

Let t = gcd(180, ang). Result will be  - 1 if ang = 180, if , otherwise

I think my solution is similar to yours, however, I find the greedy solution will not work for the following case: "harard", [100, 1, 100, 100, 1, 100]. The minimum cost is 2 when you remove 'a' at 2 and 'r' at 5, and the result string is 'hrad'. It takes me a long time to figure out this, I'm still working on understanding the DP solution after checking the accepted code from others...

Please refer to this :)

Intuition: Kind of modification of the classic 0-1 knapsack DP problem.
For more clarity please look into my top-down implementation of the same.

It is true that you can form angles in increments of 2 with a polygon of size 90. However, the max angle you can form is 176 ((n-2)*180/n).

Build a regular 90-gon and try to find out yourself lmao.

Needed for NTT, one of the solutions for problem G. Specifically, NTT needs that your prime modulo be off the form n*2^k +1. That mod fits. Presumably, they used it through the whole contest to not give too much away.

dp[i][j] is minimum ambiguity when we are at prefix j of string "hard". So,we are at state (i,j) and in next index (prefix j+1) comes, we have two choice, either to remove that letter or continue without removing(increasing prefix) and in next index any other letter arrives,we will be in same state. hence transition will be if(next index is next character after j) dp(i,j)=min(dp(i+1,j+1),dp(i+1,j)+a[i+1]) else dp(i,j)=(dp(i+1,j)).