### pikmike's blog

By pikmike, history, 4 months 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  Comments (248)
 » Was skeptical about my approach of C2 but editorial gives a very simple easy to understand proof!
•  » » 4 months ago, # ^ | ← Rev. 2 →   Problem D video editorial for N log^2 N approach: LinkProblem D video editorial for N log N approach: Link
•  » » » 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!
•  » » » » Well I guess your comment is at the top ( If he posts a new comment it will go to the bottom)
•  » » » » » True that, many people prefer a video explanation, so just to reach out to everyone. I put it at here.
•  » » » » » » Thanks for this amazing service :)
•  » » » the problem D doesn't need any data structures.it only needs binary search of answer.Link : Link
•  » » » » The link is broken!
•  » » » » This guy is posting video editorial every day after the contest. Not to forget that, he explains really well and in deep. It should not be an issue if he posts the comment on someone's thread and if the video is able to help someone, who does not understands by reading the editorial. Be fair to someone who is helping out everyone. P:S- I am awaiting downvotes.
•  » » » » » How you were sure about getting downvotes? and why people downvoted your comment? How does this work?
•  » » » » » Dude,Read the comments properly. Nobody accused him of replying on a thread. Just the person was curious on why he was posting there and I explained. Since your comment is wrong people are downvoting it i guess
•  » » » 4 months ago, # ^ | ← Rev. 2 →   i get downvoted that i understand butwhy people downvoted this guy i dont understandno worries buddy keep going
•  » » » 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.
•  » » » » 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
•  » » » » » thanks bro...
•  » » » bro you are doing good dont care about the downvotes
•  » » » o striver thank u for your videos
•  » » 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?
•  » » » I'll send you an image
•  » » » May be this will be helpful for you to understand the derivation of C2 problem solution.Problem C1 and C2 Vedio Explanation | Educational Codeforces Round 87
 » Can someone please explain 1354C2 not so simple polygon embedding. I am not able to grasp editorial solution. Thank you.
•  » » Me too, and i really hope that someone could teach me using degree measure, not the radian measure.
•  » » » Just replace every π with 180 in editorial. Thus it will be using degree measure.
•  » » This could be helpful Here
•  » » 4 months ago, # ^ | ← Rev. 2 →   May be this will be helpful for you to understand C2 problem solution.Problem C1 and C2 Vedio Explanation | Educational Codeforces Round 87
•  » » 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
 » took a lot of time to prepare the tutorial. hope it's worth.
 » Why rating changes are not made its now almost 24 hours
 » Although the tutorial for B is beautiful, I'd say Binary search was easier to think and implement!
•  » » 4 months ago, # ^ | ← Rev. 2 →   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.
•  » » » 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
•  » » » » Don't reset the values & decrement i when all three are present.
•  » » » » » Got AC. Thanks :)
•  » » » » » » can u send the link of ur corrected code
•  » » » » » » »
•  » » » » » » » » thanks
•  » » » And, of course, the maximum is always the current index, and if we increment it before taking the difference then there is no need to add 1 to it.
 » 4 months ago, # | ← Rev. 3 →   Comment deleted!!
•  » » Sorry guys but I don't understand why this comment is downvoted too much. Any explanation thanks?
 » 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 months ago, # ^ | ← Rev. 2 →   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
•  » » » 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 months ago, # | ← Rev. 4 →   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.
•  » » Same with me
•  » » No BledDest replied on announcement page that pbds shall not pass.
•  » » » oops...thanks
•  » » » but why, if n<=1e6, then total memory will be 4*1e6 bytes => 4MB which is less than 28MB, so why it gave MLE?
•  » » » » 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.
•  » » Segment tree works on this problem with $O(4*N)$ memory and $O(nlogn)$ time complexity. You can check my submission for details here.
•  » » » oh, that explains the inefficiency, thanks a lot
•  » » oh..thanks
 » Anyone explain E please !
•  » » 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.
•  » » » 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....
•  » » » » 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.
•  » » » » » thank you so much !
•  » » » » » Sir,extremely sorry for my late response.Thank you so much for your helpful reply
•  » » » Thank You so much !
•  » » Here is the video explanation that i found useful for me. May be helpful for you. Take a look at it. Problem E. Graph Coloring video explanation | Educational Codeforces Round 87
 » Why am I getting MLE in D if I use policy based data structures in C++?
•  » » Which data structure ?
•  » » » pbds ordered set.....search fot it in geeks for geeks
•  » » » » Data structures like set, map or ordered set as you mentioned always require extra memory for pointer.
•  » » » » » Thanks!
•  » » 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.
•  » » the same question has been answered above by @tissue_eater64. His solution is quite intuitive.
 » Wow I like tutorial of c1,C2 whose approach is based on your imagination
 » Is lazy needed for problem D?
•  » » lol segment tree might give you memorylimit exceeded and you are talking about lazy
•  » » 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.
•  » » » » Try this case: 4 3 1 1 2 2 -4 -2 -1 Should be 2, yours is returning 0.
•  » » » » » Thanks!Solved
•  » » » » » 1354D — Multiset Getting W.A. on test case 12, Can someone provide a test case for why this fails?
•  » » » » » » 3 3 1 1 3 -2 3 -3 
•  » » » » » » » thanks!
•  » » » » » » » 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?
•  » » » » » » » » $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.
•  » » » » » » » » » Thanks Sir very very much
•  » » » » » » » Please tell me why I am getting TLE in this submission for Multiset problem: https://codeforces.com/contest/1354/submission/80763648
•  » » » » » » » »
 » Why it takes too much time for rating changes?
 »
 » Can somebody explain how the count_le(int) in D works? I see the fairly simple code but still dont get it.
•  » » 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.
 » 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 months ago, # ^ | ← Rev. 2 →   $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.
•  » » » Thanks, I got it why binary search is valid in this problem.
•  » » » » Sorry sir, but can you kindly explain why we are doing that binary search with those limits?What role is it playing?
•  » » » 4 months ago, # ^ | ← Rev. 2 →   How is it guaranteed that the final value of rg will be present in the final array?
•  » » » » 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.
•  » » » » » I was referring to the code in the editorial. Anyways, your reply solved my doubt, thanks!
•  » » 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.
 » 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.
•  » » 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.
•  » » » Thanks for explaining. Finally i understood.
•  » » 4 months ago, # ^ | ← Rev. 3 →   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 months ago, # ^ | ← Rev. 2 →   but if we do $(max(x_{i}..)-min(x_{i}..))*(max(y_{i}..)-min(y_{i}..))$ shouldn't it give the answer?
•  » » May be this will be helpful for you to understand C1 and C2 problem solution.Problem C1 and C2 Vedio Explanation | Educational Codeforces Round 87
 » Can anyone please explain how the final expression in C2 is obtained?
•  » » 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.
•  » » » Thanks for the explanation. I understood
•  » » » Can you explain why angle x = 90 / 2 * n?
•  » » » » See the Tutorial, its explained beautifully!
•  » » » » » I just see "if we rotate, not a reason why are you doing it. Is it that intuitive?
•  » » » » » » 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.
•  » » » » » » » Also this doesn't answer to my question. How do you come up with that angle?
•  » » » » » » » » 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).
•  » » » » » » » » » I understand that, but why divided by 2 * n?
•  » » » » » » » » » 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.
•  » » » » » » » » » A detailed mathematical proof is also given below.
•  » » 4 months ago, # ^ | ← Rev. 2 →  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.
•  » » » Thanks for the proof
•  » » May be this will be helpful for you to understand C1 and C2 problem solution.Problem C1 and C2 Vedio Explanation | Educational Codeforces Round 87
 » How do we arrive at the formulas for C1 and C2?
•  » » 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
•  » » » I understood it same way just now.
•  » » » » did you implement this in CPP?
•  » » » » » Yes, I implemented in Cpp. Here: 80607062
•  » » » » » » I don't get these two lines. can you please explain? double ang = 90-((1.0*90)/n); ang = ang*acosl(-1.0l)/180;
•  » » » » » » » 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.
•  » » » » » » » » very good explanation! Thanks :)
•  » » 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)).
•  » » » Thank you so much man, I finally got it !
•  » » for C2 , the length of square used is equal to the length of the longest diagonal of the polygon
•  » » 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
 » Any program where I can draw and rotate the drawings in problem C2 ?
•  » » 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.
 » 4 months ago, # | ← Rev. 3 →   Can anyone explain this code to me. 80463378 This is a solution of C1 and C2.
•  » » yes I am also not able to understand this approach
 » Like both the ideas of C1 and C2. One problem, two datas, two levels of difficulty.
 » 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!
•  » » ok boomer
 » PLEASE explain the BINARY SEARCH and the TWO POINTERS solution for the problem 1354B. I will be grateful.Thank you.
•  » » you keep one pointer to the leftmost element that is unique and same for rightmost now increase rightmost one and if you found the leftmost element somewhere else then unfix that point
•  » » » sorry but i couldn't get you.can you be a little bit descriptive please..:)
•  » » » Thank you :) I got it now.
•  » » » » And I have not. :(
•  » » 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 months ago, # ^ | ← Rev. 3 →   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
•  » » » Thanks a lot.
•  » » » That does not look like "two pointer" to me.
•  » » » » Yeah, that's 3-Pointer actually, but it serves the purpose, I think.
•  » » » » » 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.
•  » » » » » » 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!
•  » » » » » » » You can call it anything you want, but in two pointer technique there are two pointers each moving separately. Here, on the other hand, there is only one pointer moving forward with the last position of each of the tree characters being memorized.
 » Please explain D solution via Fenwicks tree.
•  » » 4 months ago, # ^ | ← Rev. 3 →   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 + freq + freq + ... + 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 + freq + freq + ... + 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
•  » » » Can't understand why getSum(t) use log(n) time.
•  » » » » Update and query takes log(n) time in Fenwick Tree.
•  » » » Not working in java
 »
 » In problem B we are first accepting the string into a char array and then assigning it to a string object(s). My question is why aren't we just accepting the string directly into the string object(s)?__
 » why there are no python solutions for problem D ?
 » 4 months ago, # | ← Rev. 2 → » 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 months ago, # ^ | ← Rev. 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
•  » » » thank you for help...I will not post the entire code again... Now I understand what is my mistake. Thank you once again
 » How to solve c2 by ternary search ?
 » 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 months ago, # ^ | ← Rev. 2 →   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.
 » For problem D, why O(QlogN) solution is not working?
 » 4 months ago, # | ← Rev. 2 →   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 :)
•  » » 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 ?
•  » » » I used GeoGebra's Geometry Tool.
 » 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
 » Can anyone explain the editorial for B more elaborately?
•  » » 4 months ago, # ^ | ← Rev. 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
•  » » » Thanks R.aZ.eWhy does the answer look like abb...bbbbbc? If the first character of the substring appears somewhere else in it, it can be deleted. The same applies for the last character. So, the first and the last characters should be different, and should not appear anywhere else within the string. Since there are only three types of characters, the answer always looks like abb...bbbbbc.Can you explain this part of the editorial?
•  » » » » though this is a little intuitive, but I'll try to explain this a little..Imagine u have aabbbbaaaccc , in this case the first 2 a's are followed by 4 b's which are further followed by 3 a's and finally we have 3 c's. Now we will be using aab(first 3 letters) as using aabb is very stupid as we are re including b at 4th position, this doesn't increases types of char in my sub string but increases the length of sub string, or we can take abbbba(2nd to 6th position)(& not abbbbaa or aabbbba because of similar logic stated above) but till now both aab and abbbba have only 2 types of char, but we are still left with another option of baaac (we wont be considering bbaaac or baaacc, reason already given in bold)Simply replace 1,2,3 with a,b,c ... :D
 » 4 months ago, # | ← Rev. 4 →   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.
•  » » I did the same but I am said about it
•  » » » I'm sorry, did you mean sad?
•  » » 4 months ago, # ^ | ← Rev. 2 →   The cos function takes the angle in radians as the argument, not the angle in degrees. Also, beg shouldn't be an int.
•  » » » 4 months ago, # ^ | ← Rev. 3 →   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 months ago, # ^ | ← Rev. 2 →   I still had to simplify some equations, the final solution is 80647479
 » 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]
•  » » so you test every possible combination of opposite vertice and midpoint height and take the maximum?
•  » » » no need for midpoint
•  » » 4 months ago, # ^ | ← Rev. 2 →   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 ))
 » The editorial of D , which was explained without data structures was simply awesome.
•  » » 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
•  » » » 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.
 » I have seen its editorial and solution For D. Multiset in C++. And I have Implemented it in Python but still I am getting TLE. Even there is no one who have solved this problem with python in Status. So How can I solve this ?. and even there is no one who have solved this problem in any language other than c,c++.My Python Solution: https://codeforces.com/contest/1354/submission/80654693
 » Actually D could be solved in linear: 80679881 (It cost me a few times to shrink the memory >_<)
•  » » 4 months ago, # ^ | ← Rev. 3 →   Can you give a brief explanation? Thank you
•  » » » 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)$.
•  » » » » Wouldn't that be O(nlogn) ?
•  » » » » » N + N / 2 + N / 4 + N / 8 + N / 16 + ... is 2*N so it's O(N)
 » 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 months ago, # | ← Rev. 3 →   Edit: all good.
•  » » 4 months ago, # ^ | ← Rev. 2 →   I think you're looking at the judge output, your output had 2 2 1 
•  » » » Oh crap, sorry, you're right.
 » 1354D — Multiset Getting W.A. on test case 12, Can someone provide a test case for why this fails?
 » 4 months ago, # | ← Rev. 3 →   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
 » how to solve D without using any data structure. Someone please explain
•  » » It's already in the editorial
•  » » » i am not able to understand the tutorial for problem D.Can you please explain ??
•  » » » » I will try to explain what has been done in the editorial.We aim at finding the Minimum value of the multi set(as any one of the values is allowed). Now we create a function such that it gives the number of elements with value less than x.We apply binary search on all such x(any x with value less than minimum will be returning 0 and what we are seeking for is the minimum value) and find the one with least value greater than zero as this would correspond to the solution.
 » 4 months ago, # | ← Rev. 3 → 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
•  » » $\angle{CAB} = 45^{\circ}$ only for a hexagon, so it works only for a hexagon.
•  » » » 4 months ago, # ^ | ← Rev. 4 →   yes you are right, not only that it might not be necessary that the edge which is facing toward the corner of square will touch the square.Am I right ?
 » 4 months ago, # | ← Rev. 5 → 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
•  » » 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 ?
•  » » » 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 months ago, # ^ | ← Rev. 2 →   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 ?
•  » » » » » 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 months ago, # ^ | ← Rev. 2 →   we shoot a vector of length 1 at the appropriate angle from E (in your previous comment)Is E vertex of polygon or of square . According to your comment it is both . Which is not true for hexagon and other polygons.
 » Can anyone tell me the approach for problem C using brute force or ternary search as i m unable to figure it out. like how can geometric problem be solved using brute force.
 » 4 months ago, # | ← Rev. 2 →   Could someone explain me this part of problem F — Summoning Minions : vector ans1, ans2; int cur = k; for (int i = n; i > 0; --i){ if (p[i][cur] == cur) ans2.pb(a[i - 1].y + 1); else ans1.pb(a[i - 1].y + 1); cur = p[i][cur]; } reverse(all(ans1)); reverse(all(ans2)); Also, whats the purpose of array p[][] here?
 » In case anyone need Detail explanation for C1 and C2 Here
 » 4 months ago, # | ← Rev. 3 →   Please tell me why I am getting TLE in this submission for Multiset: https://codeforces.com/contest/1354/submission/80763648
 » 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.
 » can anyone explain why my solution gives TLE on test case 4 . even though it is O(N*log(N)*log(N)) code — 80806088
 » I don't understand why my solution gets TLE on testcase 4 . here is the link. can anyone help please?
•  » » I think the same happened with me too. like how does O(N*logN * longN) solution gives TLE.
•  » » » my solution doesn't even run in o(n*logn*logn),it's just nlogn.but with the time constraints given both of our solutions should run well within time.let me know if you solve this issue
 » #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?
•  » » 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 months ago, # | ← Rev. 2 →   Is it possible to find kth-order statistics in the problem 1354D-Multiset using the non-recursive implementation of segment trees (like the one mentioned in this blog -> blog) in which the array is arbitrarily sized(i.e the segment tree array size is not some power of 2)?
 » 4 months ago, # | ← Rev. 2 →   hey guys In problem E I didn't understand y i got wrong in test case 5 please can anyone explain it to me my code is here: https://codeforces.com/contest/1354/submission/80919561 here if you run the code I got a bipartite graph with only edge at 444 and 789 so only these two have 2 and 3 others are also 2 and 3. it forms a complete bipartite graph then y is the answer no? i just want to know y is the answer no?
•  » » 81997893 u can check this it passed upto 11th testcase ...if u can modify. it will be great...MY approach is I considered 1 and 3 as odd and 2 even and assigned all nodes to 2 and 3 ......then in place of 3 I replaced no of 1's in that place and atlast i counted no of 2's and 3's after assigning the 1's ...if count matches then printed YES else NO..... but 12th testcase where did it went wrong not able to encounter.
 » Has anyone solved D through Segment trees? https://codeforces.com/contest/1354/submission/81477222I am getting TLE on 8th test case. Please Help me!
 » Here's my problem solving stream. I didn't bother explaining what I was doing (like when teaching), only thinking out loud.
 » 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 months ago, # | ← Rev. 3 →   anyone have any better approach in problem E. editiorial code seems complicated for me to understand..?? thanks in advance 81997893 u can check this it passed upto 11th testcase ...if u can modify. it will be great...MY approach is I considered 1 and 3 as odd and 2 even and assigned all nodes to 2 and 3 ......then in place of 3 I replaced no of 1's in that place and atlast i counted no of 2's and 3's after assigning the 1's ...if count matches then printed YES else NO..... but 12th testcase where did it went wrong not able to encounter.
 » 4 months ago, # | ← Rev. 2 →   Problem G. The idea of step 2 is not correct. You may get EQUAL all the times. Equal doesn't mean stones. The simple example: n=16, k=5. Boxes weights: 9, 9, 10, 8, 10, 10, 10, 6, 10, 10, 10, 10, 10, 10, 10, 2
»

# include <bits/stdc++.h>

using namespace std;

# define MOD 1000000007

ll cou; string str;

bool check(ll idx,ll mid){ for(ll i=1;i<4;i++){ ll c = cou[mid][i] — cou[idx-1][i]; if(c < 1 ) return false; }

return true;

}

ll binarySearch(ll i,ll n){ ll start = i,end = n,mid; ll ans = INT_MAX;

while(start <= end ){
ll mid = start +(end - start)/2;

if(check(i,mid)){
ans = mid - i + 1;
end  = mid - 1;
}
else
start = mid +1;
}

return ans;

}

int main() {

ll t;
cin>>t;
while(t--){
cin>>str;

ll n = str.size();

memset(cou,0,sizeof cou);

for(ll i=1;i<=n;i++){
cou[i][str[i-1]-'0']++;

cou[i] += cou[i-1];
cou[i] += cou[i-1];
cou[i] += cou[i-1];
}

ll ans = INT_MAX;
for(ll i=1;i<=n-2;i++)
ans = min(ans,binarySearch(i,n));

if(ans == INT_MAX)
cout<<0<<endl;
else
cout << ans <<endl;

}

}

above is my code for problem B using binary search please its gibing tle .HELP!!

 » According to the author 's solution to problem F, I wonder why the constraints are too small and time limit is too high?
 » Please anyone give me problem B solution in Binary Search?
•  » » Create a bool function which takes all the sub arrays for a given length x and finds whether count of all the element is greater than one or not(which is condition for the problem). Then, apply binary search on all such lengths of sub arrays to find the minimum one with true value .
•  » » » ok..Thanks..
 » Amazing Problemset. Especially C1,C2 and D.
 » In problem D, I have used Fenwick Tree. I am getting runtime error unable to figure out where i am accessing array out of bounds. Please help, been stuck in this ques for quite long.My submission 86277253
 » 5 weeks ago, # | ← Rev. 2 →   Why am I getting TLE in problem D on test case 4 my code CODE
 » Can someone please discuss the binary search approach of the ternary string question?
 » 2 weeks ago, # | ← Rev. 2 →   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()); } } }