Codeforces functionality may be limited from June 18, 19:00 (UTC) to June 19, 3:00 AM (UTC) due to technical maintenance. Polygon will work as usual. ×

### awoo's blog

By awoo, history, 4 years ago, translation,

1354A - Alarm Clock

Idea: BledDest

Tutorial
Solution (pikmike)

1354B - Ternary String

Idea: BledDest

Tutorial
Solution (BledDest)

1354C1 - Simple Polygon Embedding

Tutorial

1354C2 - Not So Simple Polygon Embedding

Tutorial

1354D - Multiset

Idea: BledDest

Tutorial
Solution (BledDest)

1354E - Graph Coloring

Idea: BledDest

Tutorial
Solution (pikmike)

1354F - Summoning Minions

Idea: BledDest

Tutorial
Solution 1 (BledDest)
Solution 2 (neal)
Solution 3 (pikmike)

Tutorial
• +267

| Write comment?
 » 4 years ago, # |   +5 Was skeptical about my approach of C2 but editorial gives a very simple easy to understand proof!
•  » » 4 years ago, # ^ | ← Rev. 2 →   -31 Problem D video editorial for N log^2 N approach: LinkProblem D video editorial for N log N approach: Link
•  » » » 4 years ago, # ^ |   +21 I think you have mistakenly replied to me instead of commenting on main post, but anyway I will find it helpful as I couldn't solve D!
•  » » » » 4 years ago, # ^ |   +13 Well I guess your comment is at the top ( If he posts a new comment it will go to the bottom)
•  » » » » » 4 years ago, # ^ |   +13 True that, many people prefer a video explanation, so just to reach out to everyone. I put it at here.
•  » » » 4 years ago, # ^ |   0 the problem D doesn't need any data structures.it only needs binary search of answer.Link : Link
•  » » » » 4 years ago, # ^ |   +2 The link is broken!
•  » » » 4 years ago, # ^ |   0 please help, I have implemented problem D-Multiset with binary search on fenwick tree.Expected time complexity(query*((log n)^2)) . but my code is showing TLE in test case 6. my code: please help .... thanks in advance.
•  » » » » 4 years ago, # ^ |   +5 You are getting TLE because of the slow input method. You can either use cin with ios_base or scanf I got AC with your code + ios_base::sync_with_stdio(0); cin.tie(0) Submission link : 80917472
•  » » » » » 11 months ago, # ^ |   0 Same problem happened with me, I wasted a lot of time in this , thanks a lot brother :)
•  » » » 4 years ago, # ^ |   0 bro you are doing good dont care about the downvotes
•  » » 4 years ago, # ^ |   0 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?
•  » » » 4 years ago, # ^ |   0 I'll send you an image
 » 4 years ago, # |   +1 Can someone please explain 1354C2 not so simple polygon embedding. I am not able to grasp editorial solution. Thank you.
•  » » 4 years ago, # ^ |   0 Me too, and i really hope that someone could teach me using degree measure, not the radian measure.
•  » » » 4 years ago, # ^ |   +3 Just replace every π with 180 in editorial. Thus it will be using degree measure.
•  » » 4 years ago, # ^ |   +1 This could be helpful Here
•  » » 4 years ago, # ^ |   0 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
 » 4 years ago, # |   0 took a lot of time to prepare the tutorial. hope it's worth.
 » 4 years ago, # |   +14 Although the tutorial for B is beautiful, I'd say Binary search was easier to think and implement!
•  » » 4 years ago, # ^ | ← Rev. 2 →   +14 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.
•  » » » 4 years ago, # ^ |   0 hey! I implemented this approach. Getting the wrong answer. can you please tell me where it went wrong. Link:-https://codeforces.com/contest/1354/submission/80659788
•  » » » » 4 years ago, # ^ |   0 Don't reset the values & decrement i when all three are present.
•  » » » » » 4 years ago, # ^ |   0 Got AC. Thanks :)
•  » » » » » » 4 years ago, # ^ |   0 can u send the link of ur corrected code
•  » » » » » » » 4 years ago, # ^ |   0
•  » » » » » » » » 4 years ago, # ^ |   0 thanks
 » 4 years ago, # | ← Rev. 3 →   -34 Comment deleted!!
•  » » 4 years ago, # ^ |   0 Sorry guys but I don't understand why this comment is downvoted too much. Any explanation thanks?
 » 4 years ago, # |   0 I feel like the king who won the war at 7th attempts. I solved D with Java and submitted 6 times, either got MLE or TLE but submitted the same solution with C++ and got accepted. There may be other possible solutions but if you want to use tree data structure, then I think you have to use either- - BIT(Binary Indexed Tree)/fenwick tree which may get accepted in any languages.(I am bad at BIT) - Or you can use segment tree with C/C++. (Segment tree might not gonna work with other languages. like my java solution.)
•  » » 4 years ago, # ^ | ← Rev. 2 →   +8 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
•  » » » 4 years ago, # ^ |   +3 Thanks PizzaLovers007 for the idea and the modified submission. From now on I will use your idea for fast I/O function in Java.
•  » » » » 4 years ago, # ^ |   0 1354D — Multiset My submission: 80598227 why i got wrong answer in test 52?Please help
 » 4 years ago, # | ← Rev. 4 →   0 is it possible to solve D with policy based data structures? i tried and got MLE on test 4.update: so apparently the PBDS tree has two pointers per node plus the two values of the node, which gives us 4 ints per node in this case, and we have a maximum of 2 mil elements in the set (1m + 1m insertion queries), and so 2 mil * 16 bytes per node is well over the 28MB limit.
•  » » 4 years ago, # ^ |   0 No BledDest replied on announcement page that pbds shall not pass.
•  » » » 4 years ago, # ^ |   -8 but why, if n<=1e6, then total memory will be 4*1e6 bytes => 4MB which is less than 28MB, so why it gave MLE?
•  » » » » 4 years ago, # ^ |   +4 The ordered_set in pbds is implemented with balanced binary search tree. In order to have order statistics, more information need to be stored in each node.
•  » » 4 years ago, # ^ |   0 Segment tree works on this problem with $O(4*N)$ memory and $O(nlogn)$ time complexity. You can check my submission for details here.
 » 4 years ago, # |   +11 Anyone explain E please !
•  » » 4 years ago, # ^ |   +22 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.
•  » » » 4 years ago, # ^ |   +3 while trying to solve the problem on my own I was able to deduce the impossiblity with odd length cycles.But then never did I realize that this would be using dp.So my question is what would be my intution to detect that this problem requires dp? Please Sir,if you can kindly help....
•  » » » » 4 years ago, # ^ |   +3 For me, it was realizing that the question would be impossible without being able to "merge" two components together, after solving the problem on one component. The second step is to really think about what the numbers you get from each component actually mean, and what n_2 really means. How does having x nodes at an even distance help you? Only then will you realize that you are actually trying to find some set of numbers that sum to a specific number, which is a classical dp problem. You don't need much intuition to realize the correlation, just a lot of practice with solving questions of similar type, and knowing how to solve many classical problems.
 » 4 years ago, # |   0 Why am I getting MLE in D if I use policy based data structures in C++?
•  » » 4 years ago, # ^ |   0 Which data structure ?
•  » » » 4 years ago, # ^ |   0 pbds ordered set.....search fot it in geeks for geeks
•  » » » » 4 years ago, # ^ |   +1 Data structures like set, map or ordered set as you mentioned always require extra memory for pointer.
•  » » » » » 4 years ago, # ^ |   0 1354D — Multiset My submission: 80598227 why i got wrong answer in test 52?Please help
•  » » 4 years ago, # ^ |   0 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.
 » 4 years ago, # |   0 Is lazy needed for problem D?
•  » » 4 years ago, # ^ |   +4 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
•  » » 4 years ago, # ^ |   +5 No, because it's single point update.
•  » » » 4 years ago, # ^ |   0 1354D — Multiset My submission: 80598227 why i got wrong answer in test 52?Please help
•  » » » » 4 years ago, # ^ |   0 Try this case: 4 3 1 1 2 2 -4 -2 -1 Should be 2, yours is returning 0.
•  » » » » » 4 years ago, # ^ |   0 Thanks!Solved
•  » » » » » 4 years ago, # ^ |   0 1354D — Multiset Getting W.A. on test case 12, Can someone provide a test case for why this fails?
•  » » » » » » 4 years ago, # ^ |   +1 3 3 1 1 3 -2 3 -3 
•  » » » » » » » 4 years ago, # ^ |   0 thanks!
•  » » » » » » » 4 years ago, # ^ |   0 Sir,plz can you kindly explain how this binary search in problem D is working?What is it doing?Why it is taking the left bound as 0 and right bound as 10^6+1 all the time?I know the constraints on n and q but then the role of the binary search based on those 2 limits is not clear to me...Please Sir,I request you to guide me in this matter..Otherwise How will newbies learn?
•  » » » » » » » » 4 years ago, # ^ |   0 $count\_le(x)$ is counting the number of elements in the multiset that are less than or equal to $x$. We're using this function to find the minimum element in the multiset. Suppose $L$ is the minimum element in the multiset. Then we know that for $x < L$, $count\_le(x) = 0$, and for $x \ge L$, $count\_le(x) > 0$. If we can find the smallest $x$ such that $count\_le(x) > 0$, then we know that $x$ has to be in the multiset.The bounds on the binary search are set to be a value lower than any element in the multiset ($0$) and a value higher than any element in the multiset ($10^6+1$). I believe using $1$ and $n$ as bounds would work as well since all possible values of $x$ are in that range.
•  » » » » » » » 4 years ago, # ^ |   0 Please tell me why I am getting TLE in this submission for Multiset problem: https://codeforces.com/contest/1354/submission/80763648
•  » » » » » » » » 4 years ago, # ^ |   0
 » 4 years ago, # |   -7 Why it takes too much time for rating changes?
 » 4 years ago, # |   +11
 » 4 years ago, # |   0 Can somebody explain how the count_le(int) in D works? I see the fairly simple code but still dont get it.
•  » » 4 years ago, # ^ |   +5 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.
 » 4 years ago, # |   +3 Can someone explain how the function is monotonous in problem D editorial?"The minimum in the resulting multiset is the minimum x such that this function returns non-zero for it, and since the function is monotonous, we can find the answer with binary search."
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 $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.
•  » » » 4 years ago, # ^ |   0 Thanks, I got it why binary search is valid in this problem.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 How is it guaranteed that the final value of rg will be present in the final array?
•  » » » » 4 years ago, # ^ |   +3 What's $rg$?I'm supposing the minimum is $x$, so $f(x - 1) = 0$, while $f(x) > 0$, the same for all $x' > x$. So at the point $x$ $f(x)$ becomes positive, and we know that the element $x$ exists.
•  » » » » » 4 years ago, # ^ |   0 I was referring to the code in the editorial. Anyways, your reply solved my doubt, thanks!
•  » » 4 years ago, # ^ |   +4 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.
 » 4 years ago, # |   +1 Can anyone explain me How they are coming with solution for C1? I know people are saying it is easy to come up with this solution. But, still i'm not able to figure out this. Thanks.
•  » » 4 years ago, # ^ |   +1 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.
•  » » 4 years ago, # ^ | ← Rev. 3 →   +23 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
 » 4 years ago, # |   +5 Can anyone please explain how the final expression in C2 is obtained?
•  » » 4 years ago, # ^ |   +1 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.
•  » » » 4 years ago, # ^ |   0 Thanks for the explanation. I understood
•  » » » 4 years ago, # ^ |   0 Can you explain why angle x = 90 / 2 * n?
•  » » » » 4 years ago, # ^ |   0 See the Tutorial, its explained beautifully!
•  » » » » » 4 years ago, # ^ |   0 I just see "if we rotate, not a reason why are you doing it. Is it that intuitive?
•  » » » » » » 4 years ago, # ^ |   0 Suppose you are given a square and hexagon of fixed size. You want to fit the hexagon in the square. How will you do it? First you will try to fit it in a straight forward way by placing the hexagon above the square. If it dosen't fit , you will rotate and try to fit.
•  » » » » » » » 4 years ago, # ^ |   0 Also this doesn't answer to my question. How do you come up with that angle?
•  » » » » » » » » 4 years ago, # ^ |   0 Symmetry! You can also prove it mathematically. Start from 0 degrees. Now start rotating, at first the length decreases and width increases. After pi/(4*n) the reverse thing happens. This cycle is repeated once the angle becomes pi/(2*n). So, between 0 to pi/(2*n) the side length of square(which is max(length,width) ) first decreases then increases. So minima at pi/(4*n).
•  » » » » » » » » » 4 years ago, # ^ |   0 I understand that, but why divided by 2 * n?
•  » » » » » » » » » 4 years ago, # ^ |   0 I strongly feel that you haven't spent much time with the tutorial. This much of explanation is enough for anyone to understand. Nevertheless , try searching concepts like ternary search, maxima/minima. Try watching videos on rotating polygon and visualizing.
•  » » » » » » » » » 4 years ago, # ^ |   0 A detailed mathematical proof is also given below.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +1 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. $OB = OM = \frac{BF}{sin(\frac{\alpha}{2})}= \frac{1}{2sin(\frac{\alpha}{2})}$ $OF = OM \cdot cos(\frac{\alpha}{4}) = \frac{cos(\frac{\alpha}{4})}{2sin(\frac{\alpha}{2})}$This is the half part of the square side.
•  » » » 4 years ago, # ^ |   0 Thanks for the proof
 » 4 years ago, # |   +1 How do we arrive at the formulas for C1 and C2?
•  » » 4 years ago, # ^ |   +2 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
•  » » » 4 years ago, # ^ |   +3 I understood it same way just now.
•  » » » » 4 years ago, # ^ |   0 did you implement this in CPP?
•  » » » » » 4 years ago, # ^ |   0 Yes, I implemented in Cpp. Here: 80607062
•  » » » » » » 4 years ago, # ^ |   0 I don't get these two lines. can you please explain? double ang = 90-((1.0*90)/n); ang = ang*acosl(-1.0l)/180;
•  » » » » » » » 4 years ago, # ^ |   +3 Maximum radius Circle which can be inscribed in regular polygon is also the maximum radius circle which can be inscribed in square(which embeds the regular polygon). So, size of square is equal to radius of circle*2From pic, you can see clearly that ang = (90-90/n). and in second line(ang = ang*acosl(-1.0l)/180;) I converted angle into radians from degrees.
•  » » 4 years ago, # ^ |   +6 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.
•  » » 4 years ago, # ^ |   +10 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)).
•  » » 4 years ago, # ^ |   +1 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
 » 4 years ago, # |   +10 Any program where I can draw and rotate the drawings in problem C2 ?
•  » » 4 years ago, # ^ |   0 Have a try at wolfram alpha. It is an online application,but I think it is a good choice for you.
 » 4 years ago, # | ← Rev. 3 →   0 Can anyone explain this code to me. 80463378 This is a solution of C1 and C2.
 » 4 years ago, # |   +4 Like both the ideas of C1 and C2. One problem, two datas, two levels of difficulty.
 » 4 years ago, # |   +9 At first I wasn't a huge fan of problem D because I thought Fenwick/segment tree was the only solution. Having seen this editorial though, I realize it's actually very creative and interesting.Overall, I feel I learned a lot from this Educational Round. Thank you to all the problem writers!
 » 4 years ago, # |   -14 PLEASE explain the BINARY SEARCH and the TWO POINTERS solution for the problem 1354B. I will be grateful.Thank you.
•  » » 4 years ago, # ^ |   0 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.
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 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
•  » » » 4 years ago, # ^ |   0 That does not look like "two pointer" to me.
•  » » » » 4 years ago, # ^ |   0 Yeah, that's 3-Pointer actually, but it serves the purpose, I think.
•  » » » » » 4 years ago, # ^ |   0 Regardless of how many "pointers" you can count, that has nothing to do with two pointer technique. It is rather a sort of dp where at each step you have the shortest substring ending at the given position.
•  » » » » » » 4 years ago, # ^ |   0 If there are 3-pointers keeping track of each of the character's latest position, I think I'll use that term. I may be wrong!
 » 4 years ago, # |   0 Please explain D solution via Fenwicks tree.
•  » » 4 years ago, # ^ | ← Rev. 3 →   +2 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
•  » » » 4 years ago, # ^ |   0 Can't understand why getSum(t) use log(n) time.
•  » » » » 4 years ago, # ^ |   0 Update and query takes log(n) time in Fenwick Tree.
•  » » » 4 years ago, # ^ |   0 Not working in java
 » 4 years ago, # |   -30 Can anyone please tell what is wrong in this approach... #include using namespace std; int i=0; bool flag=false; int find_sub(string s){ char _1='r',_2='r',_3='r'; int curr_len=0; _1=s[i]; for(;ires){ min_len=res; } flag=true; } cout<>t; while(t--){ string s; cin>>s; solve(s); i=0; flag=false; } } this is showing wrong ans on 2 test case set at 163rd entry...please kindly help..
•  » » 4 years ago, # ^ | ← Rev. 5 →   +5 AVOID COPY PASTING ENTIRE CODE IN COMMENT SECTIONyou can maybe try i/p 1 122321223o/p for this will be 3. If you need a reason, do let me know :D
 » 4 years ago, # |   +3 How to solve c2 by ternary search ?
 » 4 years ago, # |   0 In problem c1 , how to prove that solution in the editorial is the best one ? Since we can rotate the polygon , there might exist some other orientation such that answer is better than the one editorial ?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 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
•  » » 4 years ago, # ^ |   0 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.
 » 4 years ago, # | ← Rev. 2 →   +21 I had another approach to C1 (which then can easily be related to C2, as I just checked after seeing the editorial) and I'm not sure if it was explained in the comments.I noticed that when you have a $2n$-gon with $n$ even, you can see that (knowing that the best disposition of the polygon inside the square is when two paralel sides of it are also paralel with a pair of ones in the square) the width of the square, and hence, its side length, is the sum of the lengths of one of the legs of each of the right triangles defined by the number of "not-right" sides in a quadrant, times two, as it replicates symmetrically on the opposite quadrant, and also add it $1$, as it's the length of one of the sides that is paralel to the ones I mentioned in the square:Note how the internal angle of each of the triangles formed between the vertices and the center of the polygon are the same as in the triangles I mentioned before. Here's another example in a dodecagon ($n = 6$):Knowing all of this, and the fact that I can get the angle of those triangles that "make" the polygon as the amount of sides in half of the polygon (which is $n$) and the total angle that makes it ($\pi rad$ or $180°$), given that it's a regular polygon, it would be $\frac{\pi}{n}$. And then each of the angles you see it's a multiple of one of them (in the dodecagon, $30°, 60°...$) as they are all equal and adjacent. Finally, the length of the leg of each right triangle I mentioned before, would be $cos(\frac{\pi}{n}*j)$ (taking for example, the horizontal one), being the $j$-th counting, for example, from the bottom. And as it also adds symetrically, it is $2*cos(\frac{\pi}{n}*j)$.I can repeat doing that for all $j$ in $[1,\frac{N}{2}]$ with a loop, then add it one, and there's your answer.As some pointed out, one way to see C2, is by calculating the distance between opposite sides of the polygon (taking it with a segment perpendicular to both), and then it seems the optimal solution is to rotate the polygon by $\frac{\pi}{4n}$. As my approach exactly gets that value, for C2 the only thing to do multiply the answer by $cos(\frac{\pi}{4n})$, which is getting the rotated segment, and by so the optimal width of the square. My solution may be worse than the editorial as it has a complexity of $O(n)$, but I think it's still a nice approach to the problem.Submissions: C1 C2I hope I explained it well and may be useful to someone :)
•  » » 4 years ago, # ^ |   0 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
•  » » 4 years ago, # ^ |   0 Sorry for off-topic but can you please tell the graphing tool that you are using ?
•  » » » 4 years ago, # ^ |   0 I used GeoGebra's Geometry Tool.
 » 4 years ago, # |   +1 Can anyone tell me what is wrong in my submission of 1354B- Ternary String question! Please have a look at the following submission:https://codeforces.com/contest/1354/submission/80626322
 » 4 years ago, # |   0 Can anyone explain the editorial for B more elaborately?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +2 have a look on https://codeforces.com/contest/1354/submission/80605650I 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 2B : 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
 » 4 years ago, # | ← Rev. 4 →   0 I tried to develop a solution for problem 1354C1 - Simple Polygon Embedding by using each triangle rectangle with hypotenuse = 1. My solution just makes the sum over the cosine of each angles below the right angle of the triangles i talked before. The cosine of each angle in blue on the image is the length of the red segment, and i make the sum until i get to the right segment in blue, then i multiply what i already got by 2 because this is the part above the straight segment in blue, and sum 1 which is the length of the straight segment in blue. The code: constexpr double PI = 3.14159265359; constexpr double toRad = PI/180.; long double total = 0; int beg = (2*n-2)*180/(2*n) - 90; long double r = 2.0*beg/(n-2.0); for(int i = 1; i < n/2; i++){ total += cos((beg-(i-1)*r)*toRad); } cout << setprecision(11) << (total*2+1) << "\n"; I start with the first angle and then i decrease the angle by a rate. The angle i start with is just the angle of the regular polygon minus 90. And the angle should decrease after each vertex until it gets to 0 ( when we reach the straight segment). The rate is the first angle divided by n/2-1 which is the number of vertices until the straight segment and after the first vertice.For the test case: 1 200My solution gives the answer: 127.46243899 Which is not the correct one, but i can't find out if the solution is not correct or i'm just having a lot of floating point errors on the sum. Thank you.
•  » » 4 years ago, # ^ |   0 I did the same but I am said about it
•  » » » 4 years ago, # ^ |   0 I'm sorry, did you mean sad?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +1 The cos function takes the angle in radians as the argument, not the angle in degrees. Also, beg shouldn't be an int.
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 Thank you very much. I was thinking that the starting angle would always be an integer, and my fear of losing precision made me use int.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 I still had to simplify some equations, the final solution is 80647479
 » 4 years ago, # |   0 Problem C1/2 can also be solved by brute force. In detail, you can rotate the polygon within [0, pi/n) for 1000 times. [submission:80507571]
•  » » 4 years ago, # ^ |   0 so you test every possible combination of opposite vertice and midpoint height and take the maximum?
•  » » » 4 years ago, # ^ |   0 no need for midpoint
•  » » 4 years ago, # ^ | ← Rev. 2 →   +6 I also solved it by brute force in O(n/2) time complexity: 80679036It 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 ))
 » 4 years ago, # |   0 The editorial of D , which was explained without data structures was simply awesome.
•  » » 4 years ago, # ^ |   0 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
•  » » » 4 years ago, # ^ |   0 Ok, so if we look carefully at the problem statement what matters after all is that we need to return any element that still belongs to the multiset. Now generally in these types of questions the easiset is to track something like minimum or the maximum element, so here it is easy to keep track of the min element. Now as the queries are offline, so we can simply keep track of the smallest element using binary search.
 » 4 years ago, # |   0 Actually D could be solved in linear: 80679881 (It cost me a few times to shrink the memory >_<)
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 Can you give a brief explanation? Thank you
•  » » » 4 years ago, # ^ |   +20 Firstly we can do some preprocessing to make each number inserted exactly once. Then while doing the binary search, the insertion and deletion in the rest half part could be discarded. Then the complexity would be $T(n) = T(n/2) + \Theta(n)$.
•  » » » » 4 years ago, # ^ |   0 Wouldn't that be O(nlogn) ?
•  » » » » » 4 years ago, # ^ |   +5 N + N / 2 + N / 4 + N / 8 + N / 16 + ... is 2*N so it's O(N)
 » 4 years ago, # |   0 in div2 D, what is guarantee that if count_le(mid) > 0 ,then element is present in multiset and even if it is present , then how do we know it will not be removed as a result of k operations. e.g : 5 4 1 2 3 4 5 -5 -1 -3 -1 Here, for element 4, count = 1, but it gets removed from the multiset. How is the solution working?
 » 4 years ago, # | ← Rev. 3 →   0 Edit: all good.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 I think you're looking at the judge output, your output had 2 2 1 
•  » » » 4 years ago, # ^ |   0 Oh crap, sorry, you're right.
 » 4 years ago, # |   0 1354D — Multiset Getting W.A. on test case 12, Can someone provide a test case for why this fails?
 » 4 years ago, # | ← Rev. 3 →   0 Could someone let me know how this solution for E is wrong? It's not the conventional method used in the solution, but I thought it would still work: https://codeforces.com/contest/1354/submission/80695289
 » 4 years ago, # |   0 how to solve D without using any data structure. Someone please explain
•  » » 4 years ago, # ^ |   0 It's already in the editorial
•  » » » 4 years ago, # ^ |   0 i am not able to understand the tutorial for problem D.Can you please explain ??
 » 4 years ago, # | ← Rev. 3 →   +6 adedalic Thanks for nice editorial and problem set . I have a doubt in c2. Since angle cab = 45 (in degrees) and AB has length 0.5 implies BC has length 0.5 . Similarly for other corner also . Hence over all length of the diagonal is $1 + 1/tan(π/(2*n))$ . The $1/tan(π/(2*n))$ term comes from c1 (i guess it will be same for all polygons) . We can get the length of the side of the square after dividing by square root of 2.But this is giving incorrect answer for figures other than hexagon . Is there any error in my assumption ?my submission : linkThanks
•  » » 4 years ago, # ^ |   0 $\angle{CAB} = 45^{\circ}$ only for a hexagon, so it works only for a hexagon.
 » 4 years ago, # | ← Rev. 5 →   +1 I have a solution for C2 which uses binary search: we can see that a pair of points with the longest distance between them in the 2n-gon, here hexagon, are B and D.So, we may try to keep these points along the diagonal of the square (as diagonal is the longest distance between two points on a square)But we still have to leave out some distance ED = BH = x from both ends of the diagonal, and then only place the hexagon's vertices. Because if we try to co-incide the opposite vertices, with the end points of the squares diagonal then since the interior angle of the figure > 90, hence it won't work, it will leave the square.So, we look for some minimum length x = ED = BH which on leaving out from both ends we may fit the figure inside the square.On this length x, we may perform a binary search!80725776
•  » » 4 years ago, # ^ |   +5 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 ?
•  » » » 4 years ago, # ^ |   0 let the longest distance in the hexagon be 'dist'. Then diagonal of square is 2x + dist let the square have its bottom left corner at 0,0 then we can find point E at (x/sqrt(2), x/sqrt(2)).Then using knowledge about the angles of the hexagon, we shoot a vector of length 1 at the appropriate angle from E, then from that point we shoot another vector of length 1 and so on.... to get the points of the hexagon, then we simply check whether these points lie within the square, by checking their x and y co-ordinates all must be between 0 and 'side.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 E might not necessarily lie on the corner of the square so how it's coordinate is (x/sqrt(2),x/sqrt(2)).can you please elaborate the process ?
•  » » » » » 4 years ago, # ^ |   0 the bottom left corner of the square is (0,0) then E is at x distance from it along the diagonal, hence it is at (x/sqrt(2), x / sqrt(2))
 » 4 years ago, # |   0 In case anyone need Detail explanation for C1 and C2 Here
 » 4 years ago, # |   +3 Why is segment tree expected to pass in D when ordered_set fails. Only reason to not use ordered_set in C++ is because it will have 2*n nodes at worst. But segtree also needs 4*n nodes. Please clarify.
 » 4 years ago, # |   0 can anyone explain why my solution gives TLE on test case 4 . even though it is O(N*log(N)*log(N)) code — 80806088
 » 4 years ago, # |   0 I don't understand why my solution gets TLE on testcase 4 . here is the link. can anyone help please?
•  » » 4 years ago, # ^ |   0 I think the same happened with me too. like how does O(N*logN * longN) solution gives TLE.
 » 4 years ago, # |   0 #include #define MAX 1000006 typedef long long int ll; using namespace std; int fenwick[MAX], arr[MAX], n; void update(ll x, ll delta){ for(;x<=n;x+=x&-x){ fenwick[x] += delta; } } int query(int x){ int sum = 0; for(;x>0;x-=(x&-x)){ sum += fenwick[x]; } return sum; } int element_idx(int rank){ int l=1, r = n; int idx = MAX; while(l<=r){ int mid = (l+r)/2; if(query(mid)>=rank){ idx = min(idx, mid); r = mid -1; } else{ l = mid + 1; } } return idx; } int main(){ int q; cin >> n >> q; for(int i=1;i<=n;i++){ cin >> arr[i]; update(arr[i], 1); } int i; while(q--){ cin >> i; if(i>0){ update(i, 1); } else{ i = abs(i); i = element_idx(i); update(i, -1); } } int final = element_idx(1); if(final == MAX){ printf("%d", 0); } else{ printf("%d", final); } return 0; Code for Multiset 1345-D I am getting Time Limit exceeded for test case 6 can someone pls help?
•  » » 4 years ago, # ^ |   0 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);try to put these lines at the begin of your main, this will make your code faster.
 » 4 years ago, # |   +8 Here's my problem solving stream. I didn't bother explaining what I was doing (like when teaching), only thinking out loud.
 » 4 years ago, # |   0 Can someone please help me with problem F, don't know why this solution is TLEing on test 32: https://codeforces.com/contest/1354/submission/81679962
 » 4 years ago, # |   0 According to the author 's solution to problem F, I wonder why the constraints are too small and time limit is too high?
 » 4 years ago, # |   0 Can someone please discuss the binary search approach of the ternary string question?
 » 4 years ago, # | ← Rev. 2 →   0 Can someone please tell me what is wrong in my java solution for D. I am getting a MLE on Case 8.import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.StringTokenizer;public class Solution{ static int[] BIT; static int n; public static void main(String[] args) throws Exception{ FastScanner fs = new FastScanner(); PrintWriter out = new PrintWriter(System.out); n = fs.nextInt(); int q = fs.nextInt(); BIT = new int[n+1]; for(int i=0;i0) { int k = fs.nextInt(); if(k>0) { update(k,1); } else{ k = -1*k; int l = 1; int r = n; while(r>l) { int mid = (l+r)/2; if(prefixSum(mid)>=k) { r = mid; } else { l = mid+1; } } update(r,-1); } } boolean bool = false; for(int i=1;i<=n;i++) { if(prefixSum(i)>0) { out.println(i); bool = true; break; } } if(!bool) { out.println(0); } out.close(); } static void update(int i, int inc) { while(i<=n) { BIT[i] += inc; i = i + i&(-i); } } static int prefixSum(int i) { int sum = 0; while(i>0) { sum += BIT[i]; i = i - i&(-i); } return sum; } static class FastScanner{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(""); public String next(){ while(!st.hasMoreElements()){ try{ st = new StringTokenizer(br.readLine()); } catch(IOException e){ e.printStackTrace(); } } return st.nextToken(); } public int nextInt(){ return Integer.parseInt(next()); } } }
 » 4 years ago, # |   0 Solved D using the Fenwick tree + Binary search without any optimization. Here is the submission. Idea is to keep frequency bit array.
 » 4 years ago, # |   0 Question G — Find a Gift This can be solved deterministically with 4*logn i.e. 40 queries in the worst case. You can find a stone deterministically in 20 queries. Method -> let a = {1,2,...n/2,...n} -> Divvy it up in two sets and compare their weight. Then change a to the set with greater weight. If a is odd, remove one element and append to another vector say 'B'. Finally doing it recursively, we would stop with a single element. Add this element to B. The above task in done with 10 queries. Now, simply find the max element in B by asking at most of logn queries. Then the rest is similar to the editorial. Submission 100589414 for reference [Although the code is extremely messy]
•  » » 3 years ago, # ^ |   0 If I understood correctly it may not work for this case, am I missing something? A = (9, 9, 7, 10, 1, 10, 10, 10) s1 = (9, 9, 7, 10) s2 = (1, 10, 10, 10) A = (9, 9, 7, 10) s1 = (9, 9) s2 = (7, 10) A = (9, 9) A = (9) B' = 9 But 9 is not a stone.
 » 11 months ago, # |   0 Can anyone please tell me a test case where my code is giving wrong answer?problem B linkMy solutionI have checked my code with all visible test cases.TIA
 » 7 months ago, # |   0 For D I have written a n(logn^2) solution using segment tree and fenwick tree separatelybut my segment tree solution gave TLE and fenwick tree passed but both of these data structures have same complexity, which is nlogn, right?? or if not how fast is fenwick tree?Segment tree solution which gave TLE — https://codeforces.com/contest/1354/submission/233261831 Fenwick tree solution which passed — https://codeforces.com/contest/1354/submission/233262440