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**

For Div1C, why is the size of the dimension "how many of the other" n^2?

"First, somehow reduce it so r_i,b_i <= n"

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.:)

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 2

^{n}represents).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 :

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.

Yeah I don't buy that either. For the following input you ended up with >

n^{2}tokens of one color as intermediate value: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.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?

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.

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

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 :(

Too bad I solved Div2D but I did not count properly the number of indexes which I was asking as a question.

wow, this Editorial is even faster than my Internet speed

the description of Div2 B may be hard to many contestants.

lol!same here!

How to use Binary Search to solve D? Anyone could explain it in more detail?

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).

For Div2 Problem B Hangcow And Puzzle This is also a valid test case

5 5

X X X X X

. . . . .

X X X X X

. . . . .

X X X X X

because 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 X

X X X X X

X X X X X

X X X X X

X X X X X

X X X X X

It is guaranteed that the puzzle pieces are one 4-connected piece.

So sir you mean such a test case is not possible ????????

I had a problem with understanding it too.

After reading editorial I've concluded that need binary search by angle too :)

..

.X

XX

in 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 times

i can get this

.X

.X

.X and then i can make a rectangle ,, what is the thing that i misunderstood ?

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.

The whole thing is a piece, you cannot move individual parts of the piece.

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.

Editorial posted 13 hours ago? :/

I am also curious about this.

It was saved as a draft 13 hours ago

This contest is excellent! Thank you authors(lewin) and MikeMirzayanov!!!

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.

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 ???

i have the same problem ! i can't get what in the statement that make the answer for this testcase is no !

You can only move all Xs (all the component) to any direction.

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 :(

I came up with exact same thing and passed pretest. Few mins later.. Unfortunately your solution for B is Hacked :'(

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".

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.

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.

i had written every variant... Idk.

Div2 D is such a fun problem :D

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)

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.

Ohh... Yeah, I think I got it now. So close:))Anyway, very nice problemset:)Congrats!

Could anyone explain Div2.D more detail please?

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.

Could someone explain more about Div2E.

When the problem can be submit at the problem set? I want to try my solution for Div2D. :)

Problem B Div2 was extremely ambiguous !

problem statement of div2B was really bad,many people misunderstood the question and got hacked.

In Div 2 b

if the input is X.X.X

then 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?

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."

Has anybody solved D2D/D1B using the "parallelization solution"?

I don't know if my solution was the expected "parallelization" solution.

My solution is:

First, work with a matrix of dimension 2

^{M}where 2^{M}is the smallest power of two that is bigger or equal thanN.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 triangular

Now, using this method only

log_{2}(n) questions are needed for every triangular. Ifn= 1000, then 20 questions will be made!Yes, this is the intended way of parallelization that I was thinking of.

I used almost the same approach, and came up with asking questions like:

But its failing on test 7 don't know why :(

i made the same thing and it worked

How are you bounding the number of questions by 2 *

log_{2}(n)I think something is wrong here one code with 2 different verdict

23067626 hack

23072618 accept

EDIT: PS for more detail see my blogMy solution on div 1 c Number of final pairs isnt exceed 16^4 Also for every a1<a2 and b1<b2 we can throw out this pair So number of final pair isn't exceed 16^2 so for every subset of cards save pairs we can get from these cards :)

How to check them? And why we shouldn't check tangents from red points to this polygon?

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.

Wow, can you elaborate on this?

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.

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 bya[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.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).It takes a day to buy something. So if you buy n things there are n extra days.

I see, I was confused by the number of tokens and failed to consider the number turns. Thanks.

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

maybe problem in size of array as n or n+1 0 indexed or 1 indexed

No, I found the problem, thanks anyway.

Stuck on the same testcase

What was the problem that you identified?

This is my submission 23256857

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.

i thought the same thing when I looked at your code, did you try fixing it and resubmitting?

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.

had the same problem. thanks :)

Hi !

The simplest solution for 744C - Коровоконг покупает колоду карт is here : 23076523. Because the number of dp states are

O(2^{n}·n^{2}), this code workes in ( because of map).Div 2C, what should be the output for this test case?

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.

It should be 8. You can put edges 1,2,3,4,5-10 and edges 7-8, 8-9, 7-9

Oh I see. I forgot to consider completing the other government components. Thanks!

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

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?I am having problem understanding Div 2D. Could someone please suggest more problems like it? What is the topic that it falls under?

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

Hi Help me please understand why I get RUNTIME_ERROR http://codeforces.com/contest/745/submission/23080649 Because code works good on my machine

oops. I see.

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)...

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?

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 thanR, or it is monotonic after R...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.

:)

Div.1 C could be solved by Simulated Annealing....

If anyone has tried DIV2- C Build a Nation using Union-Find algo, please comment. Im stuck with the understanding using this implementation.

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

notcontain a capital. Be sure to perform the final step only once for each component.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.

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 aaa

and 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.

When will the test cases be made public... Or is it just me who can't view the test cases?

How do we count the number of edges in a graph component? Is there any optimal way ?

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).

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?

No extra memory is needed, you can compute the sum during the traversal, something similar to this:

And even if you did have to store vertices separately, it is not that big of a cost.

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.

Looks all right.

hey! I implemented the code , need some help on test case 15! 23722340

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...

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.

Can anyone help me find why 23268578 got WA for Div1 C ?

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?

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

Thanks for the help.

Can anyone please give the code for DIV 2 Problem C (Hongcow builds a nation) in C++?

You can see all solutions here

Here is my C++ AC solution 23417630

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?

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.

Those who didn't understand Hongcow Builds A Nation .My code with neat and clean and important comments line

https://github.com/joy-mollick/Problem-Solving-Solutions/blob/master/Codeforces-A%20-%20Hongcow%20Builds%20A%20Nation.cpp