### Блог пользователя lewin

Автор lewin, 17 месяцев назад, ,

Short solutions:

• Div2A: How many times do we need to do a cyclic shift to consider all possible ones? Afterwards, what data structure allows us to easily check number of distinct elements?
• Div2B: Imagine the process in reverse. What types of identical shapes can I get if I cut a rectangle into two pieces? Remember, pieces cannot be rotated or flipped.
• Div2C / Div1A: How do we handle components with special nodes? What do we do with the ones without special nodes?
• Div2D / Div1B: We don't get many questions, so is there a way to "parallelize" questions? Another approach, can we split up the condition i != j somehow using bits?
• Div2E / Div1C: First, somehow reduce it so r_i,b_i <= n. Now, we can bound the excess tokens by a small number, so we can do bitmask dp from here.
• Div1D: The optimal circle must touch a blue point. Now, either consider the inversion, or do a binary search
• Div1E: What makes a list good? How fast can we do this check, and how many times do we need to do this check?

Long solutions:

## Hongcow Learns the Cyclic Shift

We only need to consider at most |s| cyclic shifts (since |s| cyclic shifts returns us back to the original string).

So, we can put these all in a set, and return the size of the set.

code

## Hongcow Solves A Puzzle

I really apologize for the ambiguity of this problem. We worked hard to make it concise and accurate, but we left out too many details.

Basically, the idea is we want to overlay two of these pieces together so that no square has more than 1 X, and the region of X's forms a rectangle.

Now for the solution:

First, let's look at it backwards. I have a rectangle, and I cut it in two pieces. These two pieces have the same exact shape. What shapes can I form?

A necessary and sufficient condition is that the piece itself is a rectangle itself! There are a few ways to check this. One is, find the min/max x/y coordinates, and make sure the number of X's match the bounding box of all the points.

code

## Hongcow Builds a Nation

First, let's make all connected components cliques. This graph is still stable.

Now, there are some components without special nodes. Where should we connect them?

If there is a component with size A and a component with size B, we can add A*B edges if we connect these two components. So, it makes sense to choose the largest component.

code

## Hongcow's Game

For the bits solution: We want to create 20 questions where for every i != j, there exists a question

that contains j and not i, and also a qusetion that contains i and not j. If we can do this, we can find the min for each row.

Note that i != j implies that there exists a bit index where i and j differ.

So, let's ask 2 questions for each bit position, one where all indices have a value of 0 in that position, and one where all indices have a value of 1 in that position. This is a total of at most 20 questions, and we can show that this satisfies the condition above, so this solves the problem.

Parallelization will basically reduce to the above solution, but is another way of looking at the problem.

First, let's ask {1,2,...,n/2} and {n/2+1,...,n} This handles the case where the min lies on the opposite half.

[
OOOOXXXX
OOOOXXXX
OOOOXXXX
OOOOXXXX
XXXXOOOO
XXXXOOOO
XXXXOOOO
XXXXOOOO
]


For example, this handles the case where the min lies in the X part of the matrix, and we split it into two identical problems of size n/2 within the O matrix.

Now, we can ask questions for each submatrix, but we can notice that these two don't interact so we can combine all the questions at this level.

However, we should ask the questions in parallel, as we don't have that many questions For example, for n=8, we should ask

First level:
[1,2,3,4]
[5,6,7,8]

Second level
[1,2],[5,6] (i.e. ask 1,2,5,6 all together, but this is actually two different subproblems, one for the top left, and one for the bottom right).
[3,4],[7,8]

Third level
[1],[3],[5],[7]
[2],[4],[6],[8]


As you can see, this reduces to the bit approach above if N is a power of 2.

code

## Hongcow Buys a Deck of Cards

Also note that if r_i or b_i >= n, we need to collect tokens no matter what since those costs can't be offset. So, we can assume that r_i, b_i <= n.

Let's only buy tokens when we need them. Note that after buying a card, you will have either 0 red tokens or 0 blue tokens, so our dp state can be described by [mask][which one is zero][how many of the other] The dimensions of this dp table are 2^n * 2 * (n^2) (n^2 because the costs to buy cards is at most n).

See the code for more details on how to update this dp.

code

## Hongcow Draws a Circle

First to check if an answer can be arbitrarily large, we can see if there is any red point that is on the convex hull of all our points. So from now on, we can assume the answer is finite.

We can show that the optimal circle must touch a blue point. To see this, consider any optimal circle that doesn't touch a blue point. We can make it slightly bigger so that it does touch one.

So, let's binary search for the answer. However, you have to very careful and notice that the binary search isn't monotonic if we only consider circles touching blue points. However, if we consider circles that touch either a red or blue point, then the binary search is monontonic, so everything works out.

To check if a radius works, we can do a angle sweep around our center point. We have a fixed radius and fixed center, so each other point has at most two angles where it enters and exits the circle as we rotate it about the center point. We can keep track of these events and find an interval where the circle only contains red points.

code for binary search

For the inversion solution, let's fix the blue point that our circle touches. Then, let's take the inversion around this point (i.e. https://en.wikipedia.org/wiki/Inversive_geometry). Now, circles that pass through our center points become lines, and the interior of those circles are in the halfplane not containing the center point. The radius of the circle is inversely proportional to the distance between our center point to the line after inversion.

So, we can say we want to solve the following problem after inversion. Find the closest line that contains no blue points in the halfplane facing away from our center point and at least one red point. We can notice that we only need to check lines that contain a blue point on the convex hull after inversion.

To make implementation easier, you can make the additional observation that the sum of all convex hull sizes will be linear through the process of the algorithm. Some intuition behind this observation is that only adjacent nodes in a delaunay triangluation can appear on the convex hull after inversion, so the sum is bounded by the number of edges in such a triangulation (of course, we do not need to explicitly find the triangulation).

code for inversion

## Hongcow Masters the Cyclic Shift

Let M denote the total number of characters across all strings.

Consider how long it takes to compute f(L) for a single list.

Consider a graph where nodes are suffixes of strings. This means we already spelled out the prefix, and still need to spell out the suffix.

There are at most M nodes in this graph. Now, draw at most N edges connecting suffixes to each other. We can find the edges efficiently by doing suffix arrays or z algorithm or hashes.

Now, we claim is the list is good if and only if there is no cycle in this graph. You can notice that a cycle exists => we can construct a bad word. Also, if a bad word exists => we can form a cycle. So, we can check if there is a cycle, which takes O(N*M) time.

Next step is to notice that extending a bad list will never make it good. So we can do two pointers to find all good intervals, which requires O(n) calls to the check function. So, overall this runs in O(N^2*M) time.

You might be wondering why this problem asks for sublists rather than the entire list. To be honest, it's just to make tests slightly stronger (i.e. I get ~30^2x the number of tests in the same amount of space).

code
Разбор задач Codeforces Round #385 (Div. 1)
Разбор задач Codeforces Round #385 (Div. 2)

•
• +88
•

 » 17 месяцев назад, # |   +10 For Div1C, why is the size of the dimension "how many of the other" n^2?
•  » » 17 месяцев назад, # ^ |   0 "First, somehow reduce it so r_i,b_i <= n"
•  » » 17 месяцев назад, # ^ |   0 That dimension represents how much of the payment is done by cards and not by tokens. Since for ith card at max (i — 1) payment can be done by cards, hence its size is n^2.I had the same idea but couldn't get it AC in contest.:)
•  » » » 17 месяцев назад, # ^ |   0 You don't need extra dimensions for that, you can directly derive it from the bitmask of which cards you've already visited (at least, I assume that's what the 2n represents).
•  » » » » 17 месяцев назад, # ^ | ← Rev. 2 →   0 The amount of payment done in cards depends on the order of the cards also, not just the mask. Eg. if there are 3 cards {(2, 0), (1, 0), (1, 0)}, then : If order is {1, 2, 3}, then payment done in cards = 1 + 1 = 2 If order is {2, 3, 1}, then payment done in cards = 1 + 2 = 3 Payment for getting a card can be done in 2 ways — token or using previous cards. Each card can assist in payment of all subsequent cards. ith card can be used in payment of n-i subsequent cards. This sum is obviously n^2.
•  » » 17 месяцев назад, # ^ | ← Rev. 2 →   0 Yeah I don't buy that either. For the following input you ended up with  > n2 tokens of one color as intermediate value: 4 R 100 0 R 100 0 B 0 100 B 0 100 
•  » » » 17 месяцев назад, # ^ |   +15 For the token R 100 0 at some moment you pay max(100-r,0), where r is the current amount of red tokens collected. Note that it will always be 100-r as r<=4 here. You can transform it to 96+max(4-r,0) which means you buy 96 red tokens at some other moment and change the token description to R 4 0. By doing this kind of transformation to all of the tokens (in any case, not just this example) you can end up with every token price <=n and some additional price to pay separately.
•  » » » » 17 месяцев назад, # ^ |   0 If i transform it to 96+max(4-r,0),i should buy 96 red cards at some other moment,but when i buy 96 red cards,i also have another 96 blue cards.These bule cards can also contribute to the answer,so i doubt how to handle with these 96 blue cards?
•  » » » » » 17 месяцев назад, # ^ |   0 My idea is that you can shift the payments to any moment in time (you may be in debt at some point but have to pay it at the end). I would shift all the additions (e.g. this 96 red) to the end and have a total of R and B to add after the dp is done. This seems complicated though, I wonder if the author had something simpler in mind.
•  » » » » » » 17 месяцев назад, # ^ | ← Rev. 2 →   0 I am not quite convinced on the point you can shift the payment if you can buy it earlier, wouldn't it contributes to the discount caused by owning that card incorrectly?Edit: I think I've got it
 » 17 месяцев назад, # |   -11 For Div1D, if any nice circle of radius r does not touch any blue point, I assumed there exist a circle of radius r which has center on one of the red point, is it wrong? since I'm getting wa for this idea :(
 » 17 месяцев назад, # |   -24 Too bad I solved Div2D but I did not count properly the number of indexes which I was asking as a question.
 » 17 месяцев назад, # |   -6 wow, this Editorial is even faster than my Internet speed
 » 17 месяцев назад, # |   +7 the description of Div2 B may be hard to many contestants.
•  » » 17 месяцев назад, # ^ |   +47
•  » » » 17 месяцев назад, # ^ |   0 lol!same here!
 » 17 месяцев назад, # |   +15 How to use Binary Search to solve D? Anyone could explain it in more detail?
•  » » 17 месяцев назад, # ^ |   +6 First, the circle has to touch some point red or blue.Try each of these points, and call this the center point. Now, we can rotate the circle about the center point. Notice that every other point forms an interval on the angles, so this reduces to a pretty standard problem. Note you count the center point as part of the condition (i.e. when we rotate around a red point, we don't necessarily have to include a different red point).
•  » » » 17 месяцев назад, # ^ | ← Rev. 4 →   -10 For Div2 Problem B Hangcow And Puzzle This is also a valid test case 5 5X X X X X. . . . .X X X X X. . . . .X X X X Xbecause final rectangle made just by shifting second rectangle one unit down and five units left both will fit together (without rotating or overlap or picking up some part)X X X X XX X X X X X X X X XX X X X XX X X X XX X X X X
•  » » » » 17 месяцев назад, # ^ |   +11 It is guaranteed that the puzzle pieces are one 4-connected piece.
•  » » » » » 17 месяцев назад, # ^ |   +10 So sir you mean such a test case is not possible ????????
•  » » » 17 месяцев назад, # ^ |   0 I had a problem with understanding it too.After reading editorial I've concluded that need binary search by angle too :)
 » 17 месяцев назад, # | ← Rev. 3 →   0 ...XXXin Div2B i can't understand why this is wrong ! as it's mentioned in the problem statement that i'm allowed to move any piece so if i moved the bottom left piece 3 timesi can get this .X.X.X and then i can make a rectangle ,, what is the thing that i misunderstood ?
•  » » 17 месяцев назад, # ^ |   +1 I made the same mistake because of the ambiguity of the question. The pieces (or the Xs) are all connected together (in one 4-connected piece). So you either move them together as a whole, or don't move any of them.
•  » » 17 месяцев назад, # ^ |   +1 The whole thing is a piece, you cannot move individual parts of the piece.
•  » » 17 месяцев назад, # ^ |   0 actually what I understood is, the given input is a single piece in a whole..it does not cosists of pieces,i.e. 'X' blocks are not single pieces.
 » 17 месяцев назад, # |   0 Editorial posted 13 hours ago? :/
•  » » » 17 месяцев назад, # ^ |   +12 It was saved as a draft 13 hours ago
 » 17 месяцев назад, # |   +13 This contest is excellent! Thank you authors(lewin) and MikeMirzayanov!!!
 » 17 месяцев назад, # |   0 My friends and I have a better solution which is easier understood for Div2E/Div1C. We can make the problem reversed. The solution is also bitmask dp. We can start from the state (0,0), which means we cost no red tokens and blue tokens at first. And then we can buy one cards each time, whose cost is ( max( red_cost[i]-red_left, 0 ), max( blue_cost[i]-blue_left, 0 ) ), while i is the card we are ready to buy and red_left means how many red cards we haven't bought except i. We say a state (a,b) is better than another state (a2,b2) when max(a,b) < max(a2,b2). But my program has a little bug and I could not find it until 2 minutes after the contest. QAQ.
 » 17 месяцев назад, # | ← Rev. 2 →   +1 In DIV2B why the answer for the below test case would be NO.2 5.XXX..X.X.We can move the X at (2,2) to (1,1) and the X at (2,4) to (1,5). So in this way we can form a rectangle. But the answer for the above test case is NO. Why ???
•  » » 17 месяцев назад, # ^ |   0 i have the same problem ! i can't get what in the statement that make the answer for this testcase is no !
•  » » 17 месяцев назад, # ^ |   +3 You can only move all Xs (all the component) to any direction.
•  » » 17 месяцев назад, # ^ | ← Rev. 3 →   0 I think the whole structure can be moved not a single part XXX X.X We can move this whole structure not a single X. I am not sure though. But I hacked a solution using the similar test case. UPD : My solution for B failed system test. So, at this moment I have no clue what the fuck is the problem with problem B :(
•  » » 17 месяцев назад, # ^ |   +1 I came up with exact same thing and passed pretest. Few mins later.. Unfortunately your solution for B is Hacked :'(
•  » » 17 месяцев назад, # ^ |   0 The idea of the problem is to check if you can make a rectangle with 2 exactly pieces as given in the input. You are allowed to move the whole piece, not part of the piece. So if there are any way to make a rectangle with the 2 exactly pieces, then you have print "YES", otherwise "NO".
 » 17 месяцев назад, # |   0 Can someone help me about problem D. My ten solutions dont work on pretest 1, but i have been using any flushes and endl's. Plz explain me my fault :http://codeforces.com/contest/745/submission/23071323.
•  » » 17 месяцев назад, # ^ |   0 Maybe it is because you only need to write fflush(stdout) after you write a complete line instead of writing it after every number on your list.
•  » » » 17 месяцев назад, # ^ |   0 i had written every variant... Idk.
 » 17 месяцев назад, # |   +13 Div2 D is such a fun problem :D
 » 17 месяцев назад, # | ← Rev. 2 →   0 In div1E, I've tried to do almost the same thing. But I don't know how to "check the match of the suffix with the end." So we start from a suffix adding words and going into new suffixes and achieve different suffixes. But we are not looking for a cycle in this graph, we are looking for an achievable suffix that, after adding at its end the prefix of the initial state, could get to a string that can be partitioned into more strings. So how do we do that? Wouldn't it be M^2*N?(fixing an initial state and then moving through the edges and checking whether we could have achieved to certain nodes that could be combined with the prefix of this initial state)
•  » » 17 месяцев назад, # ^ |   +10 I'll add more description above, but as a quick reply.The part you're quoting is more for creating the edges rather than checking the condition of the problem. What you're saying is correct, but you have to notice that "need to spell out suffix starting at position i" and "already spelled out letters up to position i" are the same state, so it is sufficient to check if we have a cycle in our graph.
•  » » » 17 месяцев назад, # ^ |   0 Ohh... Yeah, I think I got it now. So close:))Anyway, very nice problemset:)Congrats!
 » 17 месяцев назад, # | ← Rev. 2 →   +1 Could anyone explain Div2.D more detail please?
•  » » 17 месяцев назад, # ^ |   -10 For row i, you need to cover all all j!=i. This means for some j!=i, there is a question where we did not take i but j was present. So write i and j in their binary expression(<=10 bits are needed), there will exist a bit where they differ. Acc to editorial solution, you would have asked a question where either i was present or either j. This is exactly what we needed.
 » 17 месяцев назад, # |   0 Could someone explain more about Div2E.
 » 17 месяцев назад, # |   0 When the problem can be submit at the problem set? I want to try my solution for Div2D. :)
 » 17 месяцев назад, # |   0 Problem B Div2 was extremely ambiguous !
 » 17 месяцев назад, # |   0 problem statement of div2B was really bad,many people misunderstood the question and got hacked.
 » 17 месяцев назад, # |   +1 In Div 2 bif the input is X.X.Xthen it should print yes as moving one piece to one step right would make a rectangle. But according to editorial as count =3 the output should be no. can anyone explain where am i wrong?
•  » » 17 месяцев назад, # ^ |   0 This input is not valid because it is not a 4-connected piece: "The region is 4-connected if for any two cells X there is a path between them that uses only X cells and any two neighbouring cells of this path share a side."
 » 17 месяцев назад, # |   0 Has anybody solved D2D/D1B using the "parallelization solution"?
•  » » 17 месяцев назад, # ^ |   +13 I don't know if my solution was the expected "parallelization" solution.My solution is:First, work with a matrix of dimension 2M where 2M is the smallest power of two that is bigger or equal than N.Now, in order to guess the matrix, I make questions over the upper triangular and lower triangular matrix.For example, given n = 8Every entry of this matrix represent a question. Every entry that has the same value is asked in the same question (except the diagonal). The same is done with the lower triangularNow, using this method only log2(n) questions are needed for every triangular. If n = 1000, then 20 questions will be made!
•  » » » 17 месяцев назад, # ^ |   +7 Yes, this is the intended way of parallelization that I was thinking of.
•  » » » 17 месяцев назад, # ^ |   +3 I used almost the same approach, and came up with asking questions like: 1, 3, 5, 7, 9... 2, 4, 6, 8, 10... 1, 2, 5, 6, 9... 3, 4, 7, 8, 11... 1, 2, 3, 4, 9... 5, 6, 7, 8, 13... But its failing on test 7 don't know why :(
•  » » » » 17 месяцев назад, # ^ |   0 i made the same thing and it worked
•  » » » 17 месяцев назад, # ^ |   0 How are you bounding the number of questions by 2 * log2(n)
 » 17 месяцев назад, # | ← Rev. 2 →   +5 I think something is wrong here one code with 2 different verdict23067626 hack23072618 acceptEDIT : PS for more detail see my blog
 » 17 месяцев назад, # | ← Rev. 2 →   0 My solution on div 1 c Number of final pairs isnt exceed 16^4 Also for every a1
 » 17 месяцев назад, # |   0 We can notice that we only need to check lines on the convex hull of all blue points. How to check them? And why we shouldn't check tangents from red points to this polygon?
•  » » 17 месяцев назад, # ^ | ← Rev. 2 →   0 To check that if a line has a red point on the opposite side, you can find the convex hull of all points, and only blue-blue edges that aren't on the entire convex hull will be covered by a red point, so you only need to check those. Checking a line is checking the distance from the line to our center point (the radius of the circle is equal to the reciprocal of the distance from the center point to the line).Also, an easier way to implement, but harder to notice is to see that the sizes of all the convex hulls across all inversions will be linear (the intuition is that the points on the convex hull after inversion are the ones that are closest to the center point). So, you can also just do this by brute force also.
•  » » » 17 месяцев назад, # ^ |   0 Also, an easier way to implement, but harder to notice is to see that the sizes of all the convex hulls across all inversions will be linear (the intuition is that the points on the convex hull after inversion are the ones that are closest to the center point) Wow, can you elaborate on this?
•  » » » » 17 месяцев назад, # ^ |   0 I realize I misspoke in an earlier post, you do need to check those tangents, but what I said to solve the original problem is still relevant (i.e. you can either find the convex hull of all points or you make this observation and do it by brute force).I don't have a formal proof for this, but some intuition is to look at the delaunay triangulation. After inverting about a point P, only points that are connected to P in the delaunay triangulation will lie on the convex hull, so this shows that the sum of all convex hull sizes will be linear.
 » 17 месяцев назад, # | ← Rev. 5 →   0 I think that following solution to Div2B is really simple and easy to code. All we have to do is check every "square" (four fields). For every (1 ≤ i < n, 1 ≤ j < m) we count how many letters 'X' are in the square formed by a[i][j], a[i][j + 1], a[i + 1][j], a[i + 1][j + 1]. If there is at least one "square" with number of 'X's equal to 3 then the answer is NO, if not the answer is YES.
 » 17 месяцев назад, # |   0 For the div1C/div2E solution of setter, there is int ans = base + n; Why should we add an n there? I think base should be enough (which is incorrect).
•  » » 17 месяцев назад, # ^ |   0 It takes a day to buy something. So if you buy n things there are n extra days.
•  » » » 17 месяцев назад, # ^ |   0 I see, I was confused by the number of tokens and failed to consider the number turns. Thanks.
 » 17 месяцев назад, # |   0 For div2 C / div1 A I cant see the testcases and i failed at test 15, can someone tell whats wrong in this code .here is my code https://codeshare.io/21j0z5
•  » » 17 месяцев назад, # ^ |   0 maybe problem in size of array as n or n+1 0 indexed or 1 indexed
•  » » » 17 месяцев назад, # ^ |   0 No, I found the problem, thanks anyway.
•  » » » » 17 месяцев назад, # ^ | ← Rev. 2 →   0 Stuck on the same testcase What was the problem that you identified?This is my submission 23256857
•  » » » » » 17 месяцев назад, # ^ |   0 I was not adding edges to the components with less number of edges, for example if we have three components 1-2-3-4, 5-6-7 and 8-9, where 1 and 5 are government cities, then I was combining 1-2-3-4-8-9 but forgot to add the edges in 5-6-7 component.
•  » » » » » » 17 месяцев назад, # ^ |   0 i thought the same thing when I looked at your code, did you try fixing it and resubmitting?
•  » » » » » » » 17 месяцев назад, # ^ |   0 No, I didn't try my exams are going on but I know that's the problem, someone had commented a testcase, my code was failing with previous approach, with the one which I told you, it will give correct output, the code given in the editorial is pretty easy to understand, check it once.
•  » » » » 17 месяцев назад, # ^ |   0 had the same problem. thanks :)
 » 17 месяцев назад, # | ← Rev. 2 →   0 Hi !The simplest solution for 744C - Коровоконг покупает колоду карт is here : 23076523. Because the number of dp states are O(2n·n2), this code workes in ( because of map).
 » 17 месяцев назад, # |   0 Div 2C, what should be the output for this test case? 10 13 2 1 6 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5 6 7 6 8 6 9 I saw an ac code produced 8 as output, while another ac code produced 7 as output.Which is the correct one? Is the test case valid? I tried to solve it manually and got 7 as output.
•  » » 17 месяцев назад, # ^ |   +1 It should be 8. You can put edges 1,2,3,4,5-10 and edges 7-8, 8-9, 7-9
•  » » » 17 месяцев назад, # ^ |   0 Oh I see. I forgot to consider completing the other government components. Thanks!
 » 17 месяцев назад, # |   0 Guys, what is special about testcase #15 in DIV2 C? My approach: find available nodes or components to add. then result is (n * (n — 1)) / 2 — currentEdges where n is the number of vertices
 » 17 месяцев назад, # |   0 In Div1E, This means we already spelled out the prefix, and still need to spell out the suffix. What does this sentence mean? And what's the condition of connecting two nodes to each other?
 » 17 месяцев назад, # |   +1 I am having problem understanding Div 2D. Could someone please suggest more problems like it? What is the topic that it falls under?
 » 17 месяцев назад, # | ← Rev. 2 →   0 I tried to solve Div2-D by first asking the first half of the elements, and then the second half. This would leave us with two smaller recursive problems which could be solved together as they don't intersect. Hence o(n) = 2 + o(n/2). Here is an ac using this solution http://codeforces.com/contest/744/submission/23080098
 » 17 месяцев назад, # |   0 Hi Help me please understand why I get RUNTIME_ERROR http://codeforces.com/contest/745/submission/23080649 Because code works good on my machine
•  » » 17 месяцев назад, # ^ |   0 oops. I see.
 » 17 месяцев назад, # |   +10 I think your binary search for Div1D runs in time O(n^2 log n log W)? Probably there can be some hard cases to make it TLE.... During the contest I basically implemented the same algorithm, but with a random_shuffle among blue points and red points... That can bring the complexity down to something like O(n^2 log n + n log n log W)...
•  » » 17 месяцев назад, # ^ |   0 But if you do binary search individually for each point,the answer may not be right since it's no longer monotonic,did I just miss something?
•  » » » 17 месяцев назад, # ^ |   0 The very key thing of this to work is that you should also include the red points and calculate their individual answers first...After that, suppose the best radius for touching those red points is R, you can somehow prove that for the remaining blue points, either its individual answer is smaller than R, or it is monotonic after R...
 » 17 месяцев назад, # | ← Rev. 2 →   +11 I'm sorry but the solution for Div 1 C/ Div 2 E has stumped me...Could someone please elaborate I've tried reading a a few codes but it was to no avail...:)UPD: I got it now if someone wants to know how to solve it my submission might help (I've filled it with comments to help make things easier)C++ code:23346668.:)
 » 17 месяцев назад, # |   0 Div.1 C could be solved by Simulated Annealing....
 » 17 месяцев назад, # |   0 If anyone has tried DIV2- C Build a Nation using Union-Find algo, please comment. Im stuck with the understanding using this implementation.
•  » » 17 месяцев назад, # ^ |   0 I did. Here's the code: 23060103.While building the DSU, we need to update components' sizes and count of edges in them. Then, turn each component into a clique. Find the largest component that contains a capital. Finally, merge it with components that do not contain a capital. Be sure to perform the final step only once for each component.
•  » » » 17 месяцев назад, # ^ |   0 Thanks. Pretty neat coding style. I messed up the entire DSU code for computing size and got lost. Im still not sure where my code is failing though.
 » 17 месяцев назад, # | ← Rev. 4 →   0 For Div1 E, I don't quite understand. It seems you're connecting suffix u of word a and suffix v of word b whenever there's a word c such that c completes word a and goes through a prefix of word b up to suffix v. Is this right? If so, why are there "at most N edges" for each suffix? I would think that a word can lead a suffix to different ones.Consider for example words:aaaaa aaaa aaaand a suffix aaa of aaaaa. Then, word aaaa takes you to prefix aa, which is a prefix of every word and so is represented by three different suffix nodes. What to do with this?EDIT: It seems AC solutions have assumed that being at a suffix of word A and then using word B necessarily takes you to a suffix of word B. Why is this?EDIT2: I understand now. The edge isn't using a complete word to jump, it's deciding to put that word after the current one, and using the current suffix as a prefix to it.
 » 17 месяцев назад, # |   +5 When will the test cases be made public... Or is it just me who can't view the test cases?
 » 17 месяцев назад, # |   0 How do we count the number of edges in a graph component? Is there any optimal way ?
•  » » 17 месяцев назад, # ^ | ← Rev. 2 →   0 If you know the vertices that belong to the component, it is enough to take the number of neighbors for each vertex, add them up, and halve the result (every edge was counted twice, once for every endpoint).
•  » » » 17 месяцев назад, # ^ |   0 Then I will have to use extra memory to store vertices of each component, and then sum the indegrees. Will it not be too costly?
•  » » » » 17 месяцев назад, # ^ |   0 No extra memory is needed, you can compute the sum during the traversal, something similar to this: sum = 0 dfs(v): sum = sum + degree(v) [dfs stuff] And even if you did have to store vertices separately, it is not that big of a cost.
•  » » » » » 17 месяцев назад, # ^ |   0 Did I get it right?Suppose there are 3 cc's of a graph. Each time I run dfs on each component, sum is initialized to zero. for( int i= 0; i< V; ++i ){ if( !visited[i] ){ sum= 0; dfs( i ); // num sum/2 is the number of edges in the this graph component } } 
•  » » » » » » 17 месяцев назад, # ^ |   0 Looks all right.
•  » » » » » » » 16 месяцев назад, # ^ |   0 hey! I implemented the code , need some help on test case 15! 23722340
 » 17 месяцев назад, # |   0 can somebody please explain easily why asking 2 questions for each position works in Div2D? i tried it by hand and it works, but i want to understand it...
•  » » 17 месяцев назад, # ^ |   +3 As each position must have different bitmask representation, by asking 2 questions for each position, every two integers are guaranteed not to be grouped into the same question for at least once, therefore avoiding the query being diluted by the [0] at position i on each row.
 » 17 месяцев назад, # | ← Rev. 2 →   0 Can anyone help me find why 23268578 got WA for Div1 C ?
 » 17 месяцев назад, # | ← Rev. 2 →   0 Regarding div2c, stuck on testcase 15 23256857,any ideas?also is there a difference between a clique and completely connected component for a given graph?
•  » » 17 месяцев назад, # ^ | ← Rev. 3 →   0 Got It Your solution is failing for this test case. It's answer is 18 10 6 2 2 7 1 2 2 3 5 6 7 8 8 9 9 10
•  » » » 17 месяцев назад, # ^ |   0 Thanks for the help.
 » 17 месяцев назад, # |   0 Can anyone please give the code for DIV 2 Problem C (Hongcow builds a nation) in C++?
•  » » 17 месяцев назад, # ^ |   0 You can see all solutions here Here is my C++ AC solution 23417630
 » 15 месяцев назад, # |   0 In div2 E Hongcow buys a deck of cards, is it possible to use a map instead of static array, then we can solve without the first optimization. Has anyone done that?
 » 12 месяцев назад, # |   0 For problem 745B.. Following two solution is accepted.27559899 and 27559890.but for following case bith give different ans. Why? 4 4 .... .X.X .X.X ....I think its ambiguous.