HolkinPV's blog

By HolkinPV, 11 years 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

| Write comment?
»
11 years 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

  • »
    »
    11 years 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.

    • »
      »
      »
      11 years 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.

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

.d.

  • »
    »
    11 years 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.

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

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

»
11 years 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.

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

    did u code in cpp?

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

      I don’t even remember what I had for dinner last night and you’re here asking me about a code I wrote 6 years ago. That’s like a lot of months :)

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

        That can be answered with what language u used to code with... But anyway you have a point... and I got the ans after stalking your profile... Thanks

»
10 years 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?

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

    My solution uses Heavy-light decomposition and segment trees. Complexity is O(N log^2 N). http://codeforces.net/contest/342/submission/6999318

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

      Could you explain your idea ?

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

      very good. It was really helpful.

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

      We can achieve O(NlogN) if we store each "heavy chains" in separate segment trees. For each operation, all queries and updates, except the beginning one, are on the whole chain, and only takes O(1). Therefore, each operation takes O(logN)*O(1)+O(1)*O(logN)=O(logN)

      My solution (it doesn't run faster in practice though)

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

in problem E, the complexity is O(N * sqrtN * logN).... logN because of the LCA part it doesn't pass the time

how did you handle this !!?

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

Deleted

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

For problem 342E - Xenia and Tree, I came across a centroid decomposition solution 23224047. I have gone through the solution, but I am not able to convince myself about the correctness of the algorithm and the reason as to why query method is correct(or works). Please help!

PS: HolkinPV, can you please help?

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

How to solve Div1,C if we have to return the maximum distance to any red node instead of min distance...?

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

"Distance between two nodes dist(u, v) can be got using preprocessing for lca." - Xenia and Tree

Can anyone explain me how to do it?

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

    Notice that dist(u, v) = dist(root, u) + dist(root, v) - 2 * dist(root, l), where l is the LCA of u and v

    1) Use a DFS to find the distance from node 1 (the root) to every other node. Let rootDist[n] by the distance from node 1 to node n. The DFS should also find the parent of each node, and the depth of each node from the root. Let parent[n] be the parent of node n and depth[n] be the depth of node n.

    Example DFS code:

    //Let MAX be the number of maximum nodes
    vector<int> adj[MAX];
    int rootDist[MAX], parent[MAX], depth[MAX];
    
    // cur = Current traversing node
    // prev = Node traversed before this one
    int dfs(int cur, int prev){
        parent[cur] = prev;
    
        for(int child : adj[cur]){
            if(child != prev){
                depth[child] = depth[cur] + 1;
                rootDist[child] = rootDist[cur] + 1;
                // Note: In the case of an unweighted tree,
                // depth[n] == rootDist[n]
    
                dfs(child, cur);
    
            }
        }
    }
    
    dfs(1, -1);
    

    2) Build a sparse table. sparse[u][i] stores the 2**i-th parent of u, or -1 if that parent doesn't exist. Note that sparse[u][0] = parent[n]. The sparse table can be built by:

    // N = number of nodes as given in input
    // LN = ceil(log2(Max number of nodes))
    // Using 1-indexing for nodes
    int sparse[MAX][LN];
    memset(sparse, -1, sizeof sparse);
    
    for(int u = 1; u <= N; u++)
        sparse[u][0] = parent[u];
    
    for(int i = 1; i < LN; i++)
        for(int u = 1; u <= N; u++)
            //if the node has a 2**(i - 1)th parent
            if(sparse[u][i - 1] != -1)
                // the 2**i-th parent of u is equal to
                // the 2**(i - 1)th parent of 2**(i - 1)th parent of u
                sparse[u][i] = sparse [ sparse[u][i - 1] ] [i - 1];
    

    3) To query the lca of u and v, we do the following steps:

    1. If u has a smaller depth than v, swap them
    2. Find the ancestor of u with the same depth of v
    3. If u and v are the same node, return it
    4. Find the highest (least depth) ancestor of u and v (let's call them u' and v') such that u' is not v'
    5. Return the parent of u' (which is equal to the parent of v')

    Here is the code for the query:

    int lca(int u, int v){
        if(depth[u] < depth[v])
            swap(u, v);
    
        // We use sparse table so we jump 2**i parents each time
        // Taking only log time
        for(int i = LN - 1; i >= 0; i--)
            // If the 2**i-th parent of u isn't higher than v
            if(depth[ sparse[u][i] ] >= depth[v])
                // Go up 2**i parents
                u = sparse[u][i];
    
        // At this point, depth[u] == depth[v]
        // If they happen to be the same node, that is the LCA
        if(u == v)
            return u;
    
        for(int i = LN - 1; i >= 0; i--){
            // If their ancestors aren't the same
            if(sparse[u][i] != sparse[v][i]){
                // Go up to their ancestor
                u = sparse[u][i];
                v = sparse[v][i];
            }
        }
    
        // At this point, they're at the highest ancestor
        // such that they're not the same, so one parent above
        // must be their LCA
    
        // 2**0 = 1, return first parent of u
        return sparse[u][0];
        // this is also equal to sparse[v][0]
    }
    

    And finally, to put it all together, to query distance

    int dist(int u, int v){
        int l = lca(u, v);
        return rootDist[u] + rootDist[v] - 2 * rootDist[l];
    }
    

    Building the LCA sparse table takes O(n log n) time while querying takes O(log n) time

    (I wrote this from memory; please tell me if there are any mistakes or if any part is confusing)

    Source/Additional reading

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

How to do this - Calculate minimum distances from every node to the closest red node using bfs.

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

    Store all nodes which are currently red in a vector redlist. Create an queue bfslist for bfs, and create a array dist[v] = Distance from v to the nearest red node, 0 if v is itself red and initialize an empty queue. Now for all red vertices v, let dist[v] = 0 and push all the neighbours u of the red vertices which are not red into this queue, and for all such u, let dist[u] = 1, isdiscovered[u] = 1. Now it's just regular bfs: while the queue is nonempty, pop the first element w from the queue, and add all the neighbours y of w not already discovered to the queue, and let dist[y] = dist[w] +1, isdiscovered[y] = 1. Here's a code implementing it:

    void bfs(){
        std::queue<int> bfslist;
        int isdisc[N] = {0};
        for (int i = 0; i < red.size(); i +=1){
            int a = red[i];
            reddist[a] = 0;
            isdisc[i] = 1;
            for (int j = 0; j < adjlist[a].size(); j +=1){
                int b = adjlist[a][j];
                if ((isred[b] == 1) && (isdisc[b] == 0)){
                    bfslist.push(b);
                    reddist[b] = 1;
                    isdisc[b] = 1;
                }
            }
        }
        while (!bfslist.empty()){
                int a = bfslist.front();
                bfslist.pop();
                for (int i = 0; i < adjlist[a].size(); i +=1){
                    int b = adjlist[a][i];
                    if ((isred[b] ==1) && (isdisc[b] == 0)){
                        bfslist.push(b);
                        reddist[b] = reddist[a]+1;
                        isdisc[b] = 1;
                    }
                }
        }
    }
    
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, can anyone please help me debug this code for Problem E.

https://codeforces.net/contest/342/submission/39819558

It has been days and I've not been able to find the error.

I used 'Centroid Decomposition'.

Thanks in Advance!

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

In problem Div2 E, can someone share the code implementing the sqrt optimization trick. Are there any resources for this technique ? In what all cases can this technique be applied ?

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

For Div2 C, what comments?

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

Can somebody help me with problems 342E. Here's my source code: https://codeforces.net/problemset/submission/342/157723527

I still don't know why I got TLE. Thanks so much!!