ecnerwala's blog

By ecnerwala, 8 years ago, In English

635A - Orchestra

We can iterate over each possible rectangle and count the number of violists enclosed. This can be optimized with rectangular prefix sums, though the simple brute force is sufficient for this problem.

Runtime: O(n6)

634A - Island Puzzle

Notice that, as we move the empty pedestal around the circle, we cyclically permute the statues (and the empty pedestal can be anywhere). Thus, we can reach one state from another if and only if, after removing the empty pedestal, they are cyclic shifts of each other. The starting and ending configurations are permutations, so we can check this in linear time.

Runtime: O(n)

627A - XOR Equation

For any two integers a and b, we have , where is the xor and a&b is the bitwise AND. This is because is non-carrying binary addition. Thus, we can find a&b = (s - x) / 2 (if this is not an integer, there are no solutions).

Now, for each bit, we have 4 cases: , and . If , then ai = bi, so we have one possibility: ai = bi = ai&bi. If , then we must have ai&bi = 0 (otherwise we print 0), and we have two choices: ai = 1 and bi = 0 or vice versa. Thus, we can return 2n, where n is the number of one-bits in x. (Remember to subtract 2 for the cases a = 0 or b = 0 if necessary.)

Runtime:

627B - Factory Repairs

Using two binary-indexed trees, we can maintain the prefix and suffix sums of the amounts we can produce with maximum production rates of B and A, respectively. Then we can just query the binary-indexed trees to find the maximum possible production given the start and end of the repairs.

Runtime: .

627C - Package Delivery

We solve this with a greedy algorithm: for each gas station, we fill our tank to min(n, d) liters of gasoline, where d is the distance to the next gas station with cheaper (or equal) gas. This is optimal, as, if we can make it to a station with cheaper gas without buying expensive gas, we should (and fill up our tank at the cheaper station). Otherwise, all stations within range n are more expensive, so we should buy as much gas as possible right now.

Alternatively, if we say that we always “use” the gasoline we buy in the order we buy it, then the gasoline used in the ith unit must have been purchased within the last n units. Then we can greedily use the cheapest gas within the last n miles. We can maintain this in a queue with range-min-query, which gives us linear runtime (after sorting).

Runtime:

627D - Preorder Test

We binary search on the answer, so we need to answer queries of the following form: is the a depth-first search traversal such that the first k vertices all have value at least v? We can answer this with a greedy tree-DP: for each subtree, we compute whether or not all its vertices have value at least v, and if not, the longest possible prefix with all values at least v. Then, our transition function can be greedy: the maximum possible prefix with all values at least v is the sum of the sizes of all child subtrees which are all at least v plus the largest prefix of all child subtrees.

Runtime:

627E - Orchestra

We can think of a rectangle in the grid as a pair of an (xlo, xhi) interval and a (ylo, yhi) interval. Suppose we fix the x-interval and want to determine the number of corresponding y intervals which create rectangles containing at least k violists. Given a sorted list of the y-coordinates of all violists in the range, this is simple: m violists split the y-coordinates into m + 1 (possibly empty) intervals that span all the columns, and the number of total intervals that work is simply the number of pairs of points that are at least k intervals apart.

As we sweep over the xhi coordinate and maintain the list of violists, we want to insert each violist into a sorted list and look at its k nearest neighbors to determine the change in number of intervals. Inserting violists into a sorted list, however, is difficult to do in constant time. Instead, we sweep in reverse. Start with xhi = r and a linked list containing all the desired violists; decrementing xhi is now a simple process of removing the necessary elements from a linked list and examining their neighbors as we do so.

Runtime: O(r2k + rnk)

627F - Island Puzzle

First, if we never move the empty pedestal through any cycle, then moving the empty pedestal to and from any given position cannot change the location of the statues, as performing a move in the opposite direction as the previous undoes the previous move.

Thus, in our graph with one cycle, we can only do the following two operations: move the empty pedestal from one location to another (without loss of generality, only using the original tree), and cyclically permute the elements along the one cycle (except the element closest to the root).

Now, to check satisfiability, we can greedily first move the empty pedestal from its start position to its end position -- since this procedure can be undone, it will never change the satisfiability of the rearrangement. Then, we only have to check that all changed elements lie on a possible cycle. This uniquely determines the edge to be added.

To compute the minimum number of moves, we compute the minimum moves to move the empty pedestal from the start to the cycle, the minimum moves to permute the cycle as desired, and the minimum moves from the cycle to the end point.

Runtime: O(n)

  • Vote: I like it
  • +113
  • Vote: I do not like it

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

Just out of curiosity, why is the time limit for 627D - Preorder Test 7s?

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

I questioned about problem XOR equation. But I figured out my mistake

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

On "627D — Preorder Test", what will we do after computing this dp? What is the answer?

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

Could you please explain how to take care of the (N — subtree_size[x]) nodes lying above the node x ?

I am unable to understand that case.

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

    Maybe author want to say, that you can choose any vertex as a root of the tree and then consider our tree as oriented (forbid to go 'up'). Seems that it's enought to consider only vertexies set, which are prefixies of dfs, started in some vertex of such oriented tree.

    I was wrong, but you can calculate the second dp: the optimal answer for the 'subtree', which consists from all vertexes, except the vertexes in the subtree of the vertex u. If you reuse values of the first dp, you don't increase the time complexity.

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

In 627C

next gas station with cheaper (or equal) gas

Can someone please explain how do you find this station, i. e. what data structure to use?

  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    Use a stack and scan right to left. Pop the stack until it is either empty or a cheaper station has been found. This is the closest cheaper station. Push the current station onto the stack and start over the loop. This finds the closest smaller element to the right in O(n).

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

What is r2k summand in the time complexity of the problem Orchestra for? Why it's not just r2? Seems that you don't need to change anything if there're no violist with current xhi, but if it's so, you have already counted it in rnk summand.

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

In D (Preorder Test), I can see why this method would work if we started the DP from the root of the DFS tree, but I'm confused because we don't know that root (and iterating would be too costly). If the root of the DP-tree is different from the root of the DFS-tree, then I think it doesn't just work like it is written...

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

    You just need to run another DFS (after calculating DP) while maintaining the value of DP for the supertree of each vertex (ie the whole tree without the subtree of that vertex), then You can treat it like just another subtree and calculate true result for each vertex.

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

    but why this one got TLE ? 16416141

    i think it's also nlogn

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

For problem C, I have a O(m) solution using double ended queue here 16413336

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

    Correct me if I'm mistaken, but you sort the stations, so the runtime is O(mlogm). I would be interested in an O(m) solution though.

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

      oh, you are right, I omitted the sorting part. The solution will be O(m) if the input data is sorted

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

@author : i have C^2 * k * log(R) solution for "Orchestra" problem. will it pass ? got it. make a dynamic array. fix start_row and end_row. merge all the cells into into one cell for each row, so value of each cell will be number of #'s for each corresponding row. merge cells one by one. while merging a cell, look down to cells which are at atmost distance k-1 . it may take O(Columns) time. so to improve the complexity, remove the merged cells which has 0 value which can be done by creating a array with left and right pointers. total complexity = O( R^2*k + RClogC)

Edit : O( R^2*k + RClogC) == TLE , weird :/ . Giving up on this problem, though i dont giveup easily on CF problems atleast. time limit should be more, bcz codeforces allow solution without constant optimization.

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

For Problem D (Preorder test), I attempted to implement the solution as explained in the tutorial. It is not working. Any help on figuring out why this is not working would be great.

http://codeforces.com/contest/627/submission/17882471

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

    Thanks for the code, it helped me to get through test case 9... Good to see you have get through test case 25 too.

    For anyone who are wondering why your code is failing on test case 9 and 25:

    Test case 9: First case that requires the code to consider taking two subtrees which have a prefix length less than its' own size

    Test case 25: First case that requires the code to consider taking two subtrees which have a prefix length less than it's own size from the SAME children (if all other children has a prefix length equals to its' own size)

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

IN 627A — XOR Equation, can you please explain clearly why are we subtracting 2 ? I cannot get over this fact even after hours :( @ecnerwala

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

    Simply because say a = 0. Then, a & b = 0, implying a + b = a ^ b i.e. s = x. So, when you will answering query s, x such that s = x, there is a chance of a = 0, b = s or b = 0, a = s (2 cases). Need to subtract them.