HolkinPV's blog

By HolkinPV14 months ago, translation, In English,

342A - Xenia and Divisors

In this problem you should guess that exists only three valid groups of three

1) 1, 2, 4

2) 1, 2, 6

3) 1, 3, 6

(You can see that integers 5 and 7 are bad).

So, we will greedy take these groups of three. If some integers will be not used, the answer is -1. In other case, print found answer.

342B - Xenia and Spies

The problem is solved by greedy algorithm. We will pass the note only in correct direction. Also, if we can pass the note at the current moment of time, we do it. In other case, we will hold it and don't give it to neighbors (we can make this action at any moment of time). Obviously this algorithm is correct. You should only implement it carefully.

342C - Cupboard and Balloons

In the problem you should carefully get formula. The optimal solution put marbles by two in a row. And then put one marble upon others if it possible. The most difficulties were to deal with this last phase.

In comments to the post were given formulas how to put the last marble (exactly in the middle). And there was a good beautiful illustration, which describes the situation.

342D - Xenia and Dominoes

In the problem you can count number of correct puzzles or substract number of incorrect puzzles from number of all puzzles. In any case you should count DP, where the state is (j, mask)j — number of the last full column, mask — mask of the last column. This problem is equivalent to the well known problem about domino tiling or the problem about parquet.

To get the solution of the whole problem I did the following. I try to attach one domino to each of 4 directions, then paint all three cells in black and count the number of correct puzzles. But in this case you will count some solutions several number of times. So you need to use inclusion exclusion formula for these 4 directions.

342E - Xenia and Tree

The problem can be solved in different ways. The most easy idea is sqrt-optimization. Split all queries into sqrt(m) blocks. Each block we will process separately. Before processing each block, we should calculate minimum distances from every node to the closest red node using bfs. To answer the query we should update this value by shortest distances to red nodes in current block.

The solution becomes simple. Every sqrt(m) queries we make simple bfs and for every node v WE calculate value d[v] — the shortest distance to some red node from node v. Then to answer the query of type 2 you should calculate min(d[v], dist(v, u)), where u — every red node, which becomes red in current block of length sqrt(m).

Distance between two nodes dist(u, v) can be got using preprocessing for lca.

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

 
»
13 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone please explain problem D in more detail, I am not able to understand anything from what is posted.

Thanks

  •  
    »
    »
    13 months ago, # ^ |
    Rev. 5   Vote: I like it +3 Vote: I do not like it

    Solution is simple. let me explain it with a examples:

    suppose we have filled all the empty blocks from column 0....i-1 and on ith column we have filled some of the empty blocks which is stored using mask 0,1,...,7

    suppose if mask is currently 0 and i=2, so configuration could be something like this.

    AA.X.
    AA.0.
    AA.X.
    

    blocks with A are already filled.

    now we have two options, we might use some vertical block or not:

    1. if we use vertical block and put it in first 2 rows. new state ----> (i,3)
    2. if we use vertical block and put it in last 2 rows. new state ----> (i,6)
    3. if we choose not to use vertical block we have to use 3 horizontal one ----> (i+1,7)
    

    now we are almost ready with solution and need to check while putting block if that box was empty earlier and which we put block near 0, we need to note this also.

    I think, you should be able to understand my code now.

    •  
      »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you please post the link to your solution.

      I got the algorithm but I am lacking clarity over some points like considering the state (i,3), How does one keep track of whether a single vertical block was placed or 2 horizontal blocks covering the squares were placed.

      Anyways, thanks for your explanation.

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

.d.

  •  
    »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Assume that you have the distances from vertex with index 1 to every vertex u in a vector d[].

    Define lca(x, y) the lowest common ancestor for vertex x and y. You must find out the distance from v to u.

    The result is d[u] + d[v] — 2 * lca(u, v) because you add twice the distance from vertex 1 to lca(u, v) (that's where the 2 roads intersects). You can draw a tree on a paper and and work with some examples, it will be clearer.

 
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could you please tell me the complexity of the Problem E?

 
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In E problem , there isn't any boundary case like chain. Then O(N*N) solution can get AC.

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

Any online solutions for problem E ? Or different solutions to E?