Lewin's blog

By Lewin, 7 years ago, In English

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
  • Vote: I like it
  • +88
  • Vote: I do not like it

| Write comment?
»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        7 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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 :

        1. If order is {1, 2, 3}, then payment done in cards = 1 + 1 = 2
        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.

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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
    
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      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.

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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?

        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            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

»
7 years ago, # |
  Vote: I like it -11 Vote: I do not like 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 :(

»
7 years ago, # |
  Vote: I like it -24 Vote: I do not like it

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

»
7 years ago, # |
  Vote: I like it -6 Vote: I do not like it

wow, this Editorial is even faster than my Internet speed

»
7 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

»
7 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

    • »
      »
      »
      7 years ago, # ^ |
      Rev. 4   Vote: I like it -10 Vote: I do not like it

      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

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

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

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I had a problem with understanding it too.

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

»
7 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

..

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

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Editorial posted 13 hours ago? :/

»
7 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
7 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    7 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i had written every variant... Idk.

»
7 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Div2 D is such a fun problem :D

»
7 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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)

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
7 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Could anyone explain Div2.D more detail please?

  • »
    »
    7 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    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.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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?

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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 = 8

    Every 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 log2(n) questions are needed for every triangular. If n = 1000, then 20 questions will be made!

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      Yes, this is the intended way of parallelization that I was thinking of.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        i made the same thing and it worked

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How are you bounding the number of questions by 2 * log2(n)

»
7 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

I think something is wrong here one code with 2 different verdict

23067626 hack

23072618 accept

EDIT : PS for more detail see my blog

»
7 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

»
7 years ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

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.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It takes a day to buy something. So if you buy n things there are n extra days.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Hi !

The simplest solution for 744C - Hongcow Buys a Deck of Cards is here : 23076523. Because the number of dp states are O(2n·n2), this code workes in ( because of map).

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I am having problem understanding Div 2D. Could someone please suggest more problems like it? What is the topic that it falls under?

»
7 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
7 years ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

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.

:)

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
7 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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.

»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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
             }
          } 
          
          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Looks all right.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like 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.

»
7 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
7 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    7 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?