### HolkinPV's blog

By HolkinPV, 7 years ago, translation, ,

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.

• +38

 » 7 years ago, # |   +1 Can someone please explain problem D in more detail, I am not able to understand anything from what is posted. Thanks
•  » » 7 years ago, # ^ | ← Rev. 5 →   +3 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,...,7suppose 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.
•  » » » 7 years ago, # ^ |   0 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.
•  » » » » 7 years ago, # ^ |   0 it does not matter whether it was vertical block or 2 horizontal block. (i,3) tells that all the blocks in first i-1 columns are filled and in this column there is only last row left to be filled.
 » 7 years ago, # | ← Rev. 3 →   0 .d.
•  » » 7 years ago, # ^ |   0 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.
 » 7 years ago, # |   0 Could you please tell me the complexity of the Problem E?
•  » » 7 years ago, # ^ |   0 Here is my solution: http://codeforces.com/contest/342/submission/4509629 The complexity seems to be O((n+m)*sqrt(m)). But it still gets TLE.
•  » » » 18 months ago, # ^ |   0 O(n*sqrt(m)*log(n))
 » 6 years ago, # |   0 In E problem , there isn't any boundary case like chain. Then O(N*N) solution can get AC.
•  » » 6 months ago, # ^ |   0 did u code in cpp?
•  » » » 6 months ago, # ^ |   0 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 :)
•  » » » » 6 months ago, # ^ |   0 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
 » 6 years ago, # | ← Rev. 2 →   0 Any online solutions for problem E ? Or different solutions to E?
•  » » 6 years ago, # ^ |   +3 My solution uses Heavy-light decomposition and segment trees. Complexity is O(N log^2 N). http://codeforces.com/contest/342/submission/6999318
•  » » » 6 years ago, # ^ |   0 Could you explain your idea ?
•  » » » 5 years ago, # ^ |   0 very good. It was really helpful.
•  » » » 21 month(s) ago, # ^ |   -8 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)
 » 5 years ago, # |   0 in problem E, the complexity is O(N * sqrtN * logN).... logN because of the LCA part it doesn't pass the timehow did you handle this !!?
 » 5 years ago, # |   0 In problem A why 5 & 7 are bad?
•  » » 5 years ago, # ^ |   0 Because that are prime, and there is no x <= 7, x != 5, x != 7 such that 5 | x and 7 | x
•  » » » 5 years ago, # ^ |   0 Thanks nam2012abcd
 » 4 years ago, # | ← Rev. 2 →   0 Deleted
 » 3 years ago, # | ← Rev. 2 →   0 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?
•  » » 8 months ago, # ^ |   0 I'm a bit late but the solution is explained here.
 » 3 years ago, # |   0 How to solve Div1,C if we have to return the maximum distance to any red node instead of min distance...?
 » 3 years ago, # | ← Rev. 2 →   0 "Distance between two nodes dist(u, v) can be got using preprocessing for lca." - Xenia and TreeCan anyone explain me how to do it?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +3 Notice that dist(u, v) = dist(root, u) + dist(root, v) - 2 * dist(root, l), where l is the LCA of u and v1) 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 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: If u has a smaller depth than v, swap them Find the ancestor of u with the same depth of v If u and v are the same node, return it Find the highest (least depth) ancestor of u and v (let's call them u' and v') such that u' is not v' 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
•  » » » 3 years ago, # ^ |   0 Thanks for your help. You explained very well.
 » 23 months ago, # |   0 How to do this - Calculate minimum distances from every node to the closest red node using bfs.
•  » » 22 months ago, # ^ | ← Rev. 2 →   0 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 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; } } } } 
 » 20 months ago, # |   0 Hi, can anyone please help me debug this code for Problem E. https://codeforces.com/contest/342/submission/39819558It has been days and I've not been able to find the error.I used 'Centroid Decomposition'.Thanks in Advance!
 » 3 months ago, # |   0 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 weeks ago, # |   0 For Div2 C, what comments?