Problem D video editorial for N log^2 N approach: Link

Problem D video editorial for N log N approach: Link

Hey man , I got the point why it will be minimum at an angle of pi/4n but still not able to derive that cos/sin formula .. could u help?

Me too, and i really hope that someone could teach me using degree measure, not the radian measure.

This could be helpful Here

Just consider the hexagon example in the editorial , You notice that the square has the same side length as the distance between the two opposite vertices(touching the square) in fig 1 , (2 units in the case of hexagon) Now draw a horizontal line between the 2 vertices (touching the square) in fig 1 , If you rotate this line anticlockwise , its horizontal component will start to decrease , but the horizontal component of the diagonal line between the vertices will start to increase , If you rotate a full (90/n) degrees it restores to its original fig1 (why 90/n , because at the center , the angle for each side is (360)/(2n) = 180/n , rotate half that is 90/n , and you achieve symmetry , or in other words the same figure ) Now , if after 90/n , the horizonal component of the diagonal turns to 2 , and for the horizontal vertices it decreases , then there must be a point where they both were same That point by symmetry has to be 90/2n i.e. in the middle

Another simple approach is to iterate over the string and keep track of the most recent indices where each of the 3 digits appear. And at each step, if all 3 indices have valid values, take the difference between the maximum one of them and the minimum one plus one as candidate for the shortest length. Pick the minimum candidate as the answer.

Sorry guys but I don't understand why this comment is downvoted too much. Any explanation thanks?

I believe your Java solution is fast enough, but Scanner is extremely slow. You can still use BufferedReader, but you need to write your own I/O function like I explained here.

Your (modified) submission

No BledDest replied on announcement page that pbds shall not pass.

Segment tree works on this problem with $$$O(4*N)$$$ memory and $$$O(nlogn)$$$ time complexity. You can check my submission for details here.

I will try to explain it in simpler terms for you. First, you need to understand that there cannot be any odd cycles in the graph. You can see this for yourself by drawing a cycle of length 3 and inducing for larger cycles.

With that out of the way, let's run BFS on each component, keeping track of the distance to each node from the starting node. If we ever encounter any odd cycles (i.e. the depth of an adjacent visited node is the same parity of the depth of the current node), we can terminate the program and print NO. Otherwise, let's group all nodes with even distance from the starting node and claim that we can assign 2 to each of these. This is possible since they will each be separated by one and only one node, which we can assign 1 or 3. With similar logic, we can assign 2 to all nodes with odd distance from the starting node. If the graph was guaranteed to be connected, we would already be done, by simply checking whether the number of odd distance nodes or the number of even distance nodes equals n_2. However, there can be multiple components, leading us to the second part of the solution.

Let's add the number of nodes with even distance as an item's weight in a knapsack problem, and do the same with the number of nodes with odd distance. These will also have a type number, which can just be its component id. This is crucial to understanding the rest of the solution. The type of an item represents which component it is in, and the weight of an item represents that we can assign exactly weight with nodes the number 2 in that component.

To "merge" the components, we will run a very basic knapsack dp, with our state as dp[i][j] = 1 if it is possible to reach total weight j with the first i types of items, and dp[i][j] = 0 otherwise. The transition should be obvious, but notice that we cannot always do dp[i][j] = max(dp[i][j], dp[i - 1][j]) since we must include exactly one item of each type (after all, we can't just forget to assign numbers to a component).

Finally, we will check whether it is possible by checking whether dp[total_components][n_2] = 1, since this represents that there is a way to assign n_2 nodes the number 2 using all component types. If it is possible, we can simply backtrack for our solution, and we are done.

Hopefully, this helps you understand the solution slightly better without any complicated terms.

Which data structure ?

The memory limit was there I think to discourage the use of pbds. They most likely use extra memory to provide those extra functions. Sets and maps are anyway more memory hungry than simple vectors.

I didn't use lazy in my solution, I updated the tree each time. It just take log(n) to update the tree. Total time complexity n log(n)
You may check my submission here

No, because it's single point update.

The first for loop is straightforward, just count the number of elements less than or equal to x. In the second for loop, if the query is > 0 and if it is less than or equal to x then no matter when it is inserted it'll always contribute to count. As for the negative query, we now have count of elements less than or equal to x till this negative query, hence if the ordered statistics is more than count it won't affect our count as only numbers larger than x are removed. If the order statistics is less than our count, then we have to remove some smaller element hence we are decreasing count. Hope it helps.

$$$f(x)$$$ — number of elements $$$<= x$$$ in the multiset.

When we go from $$$x$$$ to $$$x + 1$$$, all the elements $$$<= x$$$ will still be $$$<= x + 1$$$, but new elements (with value exactly $$$x$$$) may also contribute to $$$f(x + 1)$$$. So the value never decreases, thus $$$f(x)$$$ is monotonous.

The function actually returns the no of elements less than equal to x ,so for all elements less than the minimum element the function return a zero value as there are no elements less than the minimum element and for all elements greater than or equal to the min element the fun returns a non zero value(this value may increase by increasing the query element (or index))So it is monotonous because it returns 0 till a certain index and then returns non zero value till the last index.

The first thing i assume that the square will be somehow related to outer circle of polygon. And equation of outer circle of a regular polygon is very easy to figure out. You can search on google for this equation.

And finally came to an equation for C1 that a be sides of square, r be radius of outer circle then, a*a/4+0.5*0.5=r*r. You can simply get it drawing figure.

For C2 i get it that a polygon having 2*n sides will fit in a square having sides equal to half of radius of polygon having 4*n sides. Although i don't have a solid proof for this but it passed.

I can tell you my weird approach during the contest but editorial is much simpler. I divided the square into 4 quadrants just like a cartesian coordinate system and then we can tell each quadrant contains $$$(n / 2)$$$ vertices since $$$n$$$ is even. Now see the pic we are starting from the coordinate $$$(0, 0)$$$ then finding the next coordinate $$$(x_i, y_i)$$$.

The main idea is to find the distance between the initial position and the final position. During the contest, I was not sure if that is true or not.

for finding the final position we can iterate $$$n$$$ times and use this simple formula $$$(x_{i + 1}, y_{i + 1}) = (x_i + cos(theta), y_i + sin(theta))$$$, and increase $$$theta$$$ by $$$δ$$$ in every iteration.

Did you notice the formula is not giving the expected value?. here is the reason-

logically our initially starting position should be $$$(x_1, y1)$$$ instead of $$$(0, 0)$$$, but what I did is shift the $$$(x_1, y_1)$$$ by $$$(-0.5)$$$, and ultimately you will land upon the final position according to the figure.

my submission

Just consider a horizontal line through the center of the polygon in fig. 1 of Tutorial. This is the side of the square initially. Now rotating the polygon by angle x, this line also rotates by same angle and the new square side becomes cos(x) times initial. In this problem x=pi/(4*n) and you just need to figure out the initial square side which is nothing but distance between two opposite vertices of the polygon.

Let us rotate point $$$B$$$ clockwise, and point $$$D$$$ against. This is the same as rotating the point $$$D^{'}$$$. On the one hand, the projection onto the line increases, and on the other, decreases. To select the side of the square, we need to choose the maximum of these projections. Then the minimum side of the square will be under conditions when both projections are equal, that is, on the bisector $$$OM$$$. Now consider the $$$BOD^{'}$$$ triangle, it is isosceles and we know what $$$OB$$$ is equal to. Then, from the condition that $$$OB$$$ is equal to $$$OM$$$, we find the desired projection.

This is the half part of the square side.

For C1, I solved it with a different approach. Basically the formula for internal angle of a n-sided polygon is given by theta = ((n-2)*180))/n We form a triangle as shown in the editorial. The side bisects the internal angle, lets say theta1 = theta/2 So tan(theta1) = x/0.5 Therefore x = tan(theta1)/2 Inorder to find the length of square we multiply x with two. Thus final ans is ans = tan(theta1) Link to my submission

Try this. You are actually trying to get the length of the purple line, which can be divide into (n-1) parts. In this case, 3 parts. I've separated the purple line with blue lines. The first part(from down to up) should be 1 * sin(theta). The second part should be 1 * sin(theta * 2). The third part should be as same as the first part, which is 1 * sin(theta). btw, theta = 180° / n P.S. this is written in degree, not radian.

For C1, note that for a regular polygon with even number of sides, opposite sides will be parallel. For even n, 2*n will also be divisible by 4. And by symmetry argument, there will be two pairs of opposite parallel sides perpendicular to each other. So we can align the polygon so that this 4 sides will be parallel to the sides of the square, and also touching them to minimize the size of the square.

Now consider the center of symmetry of the regular polygon, which is also the center of the inscribed circle, of the circumscribed circle, as well as of the square. Construct the triangle with one of the sides of the polygon as base and the center of the polygon as third vertex. The height of this isosceles triangle will be half of the side of the square. The angle of the triangle with tip in the center of the polygon measures 360 deg / (2*n) or 2* pi / (2*n). Construct the height of the triangle. It will split the isosceles triangle into 2 rectangular triangles, whose angle with the tip in the center of the polygon will measure half of the previous angle or pi / (2*n). Tangent of the angle equals to the ratio of the opposite cathetus (half of the side of the regular polygon) to the adjacent cathetus (the height we are looking for). So h = 0.5 / tan(pi / (2*n)), and the side of the square is twice that.

For C2, if we try to align the polygon to have a pair of sides parallel with a pair of sides of the square, then the other 2 sides of the square will touch 2 opposite vertices of the regular polygon, and the distance between 2 opposite parallel sides of the polygon will be shorter than the side of the square, leaving a gap. The long diagonal connecting the 2 vertices touching the sides of the square will also be parallel to 2 opposite sides of the polygon. If we rotate the polygon by the angle pi / (2*n), the situation will be the same, except now vertices of the polygon are touching the other pair of sides of the square. By symmetry, the optimal rotation angle should be midway between these 2 positions, i.e. it is equal to pi / (4*n). The long diagonal will now touch 2 opposite sides of the square like before, but it is at a slant angle (equal to pi / (4*n)) respective to the other pair of sides, instead of parallel.

To calculate the diagonal length, construct the similar isosceles, and then rectangular triangles as we used in problem C1. The hypotenuse of the rectangular triangle is half of the diagonal, and it equals 0.5 / sin(pi / (2*n)), since sine of the angle is the ratio of the opposite cathetus and the hypotenuse. The full diagonal is 1 / tin(pi / (2*n)).

To calculate the length of the side of the square, project the diagonal on to the direction parallel to the side of the square (this can also be thought of as constructing a rectangular triangle with the side of the square as one of the catheti and the diagonal of the polygon as the hypotenuse), to obtain the side of the square being equal to cos(pi / (4*n)) * 1 / sin(pi / (2*n)).

May be this will be helpful for you to understand the derivation of formulas to both C1 and C2 problems.

Problem C1 and C2 Vedio Explanation | Educational Codeforces Round 87

I think Geogebra should do the trick.

Have a try at wolfram alpha. It is an online application,but I think it is a good choice for you.

We will use binary search on the length of the substring. Notice if the substring of size t contains all the characters, then the substring of size t+1 also contains all the characters.

Let say we have a function check(t) which returns True if there exists a substring of size t such that it contains all the characters. Then we can use something like this.

lo = 3, hi = n, ans = -1
while(lo <= hi):
	mid = (lo + hi)/2
	if(check(mid)):
		ans = mid
		hi = mid-1 
	else:
		lo = mid+1

if(ans == -1):
	print(0)
else
	print(ans)

Now to implement check(t) we can use sliding window technique. Try implementing it yourself.

You're looking for this : Comment Here's the 2/3 Pointers(?)

For Binary search, you do it on the length and find the minimum length of the subarray with at least one of each character. You need to have the count of each character beforehand and you can use prefix sums for that: Binary Search

We will use the frequency array to build the Fenwick tree. Let's say we have an array freq[1..n] that contains the frequency of all the numbers given in the array, i.e if freq[y] = x, then the number y appears x times in the given array.

For the query of the first type "add integer K to the multiset" we simply need to increase the freq[k] by 1.

For the query of second type, we need the smallest number x such that freq[1] + freq[2] + freq[3] + ... + freq[x] is greater than or equal to k. Then we can just decrease the freq[x] by 1.

Let's say we have functions update(t, val) and getSum(t).

update(t, val) increases the value of index t by val. freq[t] += val.

getSum(t) returns freq[1] + freq[2] + freq[3] + ... + freq[t] in log(n) time.

Then for the query of type one simply use update(t,1). For the query of the second type use Binary search to find the required number and use update(t,-1).

To find the required number use something like this

k = abs(k);

int lo = 1, hi = n;
int idx;
while(lo <= hi){
    int mid = (lo + hi)/2;
    if(getSum(mid) >= k){
        idx = mid;
        hi = mid-1;
    }else{
        lo = mid+1;
    }
}
update(idx, -1); 

Finally for the output, just do a linear search to find smallest t such that getSum(t) > 0 and output t.

Here is my submission. 80502866

AVOID COPY PASTING ENTIRE CODE IN COMMENT SECTION

you can maybe try i/p 1 122321223

o/p for this will be 3. If you need a reason, do let me know :D

essentially, they're using the height of the octagon (or n-gon) from one midpoint of a side to another as the height of the square. any other rotation would increase the size due to pythagorean theorem. take for example, if you used opposite vertices, that would be greater than the two midpoint solution because of pythag theorem (the legs are always smaller than hypotnuse)

edit: wait nvm it's either the midpoint or the vertice, but either way its guaranteed to be one of those because those are the maximums and minimums respectively

Look at an inscribed circle of $$$2n$$$-gon. Since $$$2n$$$-gon should be embedded in the square and the circle is embedded in $$$2n$$$-gon then the circle must be embedded in the square. And there is no way to embed the circle in the square with side lower than the diameter of the circle.

But we've shown the example with the square side equal to the diameter, so it's the best answer.

DUDE, I had the same solution but i kept on getting double error or something, like my solution was 0.3 off for test case N=200 for c1. I think I either messed up my implementation or java is poop

Sorry for off-topic but can you please tell the graphing tool that you are using ?

have a look on https://mirror.codeforces.com/contest/1354/submission/80605650

I created a vector A which tells the order of 1,2,3's , and vector B storing their particular frequencies...

As in if you have a string 332111111221132, then

A : 3 2 1 2 1 3 2

B : 2 1 6 2 2 1 1 (hope u get what I've done till now)

Now just simply iterate A from 2nd to 2nd last position and check that if A[i-1],A[i],A[i+1] all are different (if they are different we can get substring of form 122...223(or something similar), in that substring A[i] will occur B[i] times and A[i-1] and A[i+1] will occur once). Finally we will be finding min of (B[i]+2) whenever A[i-1],A[i],A[i+1] are different...

Hope this helps, do let me know if you need more help :D

I did the same but I am said about it

The cos function takes the angle in radians as the argument, not the angle in degrees. Also, beg shouldn't be an int.

so you test every possible combination of opposite vertice and midpoint height and take the maximum?

I also solved it by brute force in O(n/2) time complexity: 80679036

It is quite obvious from the image that if we know the angle we can find the orange line, so looping through n/2 angles we need to find the longest orange line, which leads us to the answer = 2 times longest orange line.

It is definitely not the best solution, but at least it is simple enough to understand for the beginners like me ))

Please can you explain me how to solve D.Multiset without segment tree or anything like it.I am unable to understand the tutorial.Thanks in advance

Can you give a brief explanation? Thank you

I think you're looking at the judge output, your output had

2
2 1

It's already in the editorial

$$$\angle{CAB} = 45^{\circ}$$$ only for a hexagon, so it works only for a hexagon.

Can you please explain how to perform the binary search in this case ?

I understood the rest of the part.We are finding length of the diagonal such that the square it forms just covers whole polygon.Thus during binary search , we will see if it covers the polygon .How to do that ?