Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

# | User | Rating |
---|---|---|

1 | tourist | 3534 |

2 | Petr | 3400 |

3 | moejy0viiiiiv | 3257 |

4 | W4yneb0t | 3183 |

5 | ainta | 3118 |

6 | mnbvmar | 3059 |

7 | Merkurev | 3055 |

8 | V--o_o--V | 3031 |

9 | matthew99 | 3014 |

10 | izrak | 2996 |

# | User | Contrib. |
---|---|---|

1 | rng_58 | 170 |

2 | Errichto | 168 |

3 | Petr | 163 |

4 | Swistakk | 152 |

5 | Zlobober | 151 |

6 | csacademy | 149 |

7 | zscoder | 148 |

8 | GlebsHP | 147 |

8 | Um_nik | 147 |

10 | Xellos | 136 |

10 | Edvard | 136 |

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial of Codeforces Round #381 (Div. 1)

Tutorial of Codeforces Round #381 (Div. 2)

↑

↓

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/25/2017 05:10:02 (c3).

Desktop version, switch to mobile version.
User lists

Name |
---|

Could someone please look at my code for 739B? I was getting WA on pretest 15 and am not sure why...

I store the 2^k ancestors and the distance to them in bparent[][] and bdist[][]. I then binary search for each node that controls the node that I am on and store the start and end segments in event[]. The function solve() dfs's through the tree, keeping track of how many nodes each node controls.

Thanks!

For problem D, how do we store the ancestors of all nodes in O(n)?

You only store the (2^k)th ancestors of a node -> O(n*log n)

Can someone explain the approach for the problem 'Alyona and Tree'

This is the binary search method that may not be the easiest, I recommend checking out zawini54's comment too!

A few observations could be made:

dist(v,u) =dist(root,u) -dist(root,v)v, and its ancestorsa_{1},a_{2}, ...,a_{i},a_{1}being thefurtherestancestor (root of the tree) anda_{i}theclosest(immediate parent vertex),we can see that

dist(root,a_{1}) <dist(root,a_{2}) < ... <dist(root,a_{i}) <dist(root,v), a sorted sequence that is binary searchable.v, we want to find the number of verticesuit controls, i.e.:dist(v,u) ≤value(u)dist(root,u) -dist(root,v) ≤value(u)dist(root,u) -value(u) ≤dist(root,v)for each vertexu, which verticesvcould controlu?Ok, for each vertex u, I can find how many ancestor controls it, but how do I use this information to find out the reverse?

Let u is controlled by x vertices. Then the immediate x parents of u could control this vertex u.

But a simple approach in getting the answer requires O(n^2) which would fail on the time limit. Can you suggest a better approach?

Consider the array,

A= [6, 1, 6, 9, 3]We can compute an array of differences between the neighbouring two elements, a difference array,

D= [6, - 5, 5, 3, - 6],Note how we can reconstruct the array A from its difference array D,

A[0] =D[0]A[1] =D[0] +D[1]A[2] =D[0] +D[1] +D[2]A[3] =D[0] +D[1] +D[2] +D[3]A[4] =D[0] +D[1] +D[2] +D[3] +D[4]If we can somehow first construct a difference "array"

Dfor this problem, then we can reconstruct the answer "array"Afrom it.Nice thought.Thanks a lot.

Sorry, I still do not get it. How do you get this difference array?

Actually there's another solution that doesn't use binary lifting, but the merging sets technique. I think it's easier, because at first I thought of doing something with binary lifting but wasn't able to come up with anything. Check it out: 22490570

Nice approach, btw are you making reference to the technique disscused at this post?

I considered merging set approach during contest, but couldn't find a way to count the number of elements <= d in O(logn) using std::set, now I know it's unnecesary for this problem after reading you code.

However, if the condition change to that v controls u if dist(v, u) <= a(v) (instead of a(u)), it seems we must have a way to count the number of elements <= d in O(logn) using merging set approach, and std::set doesn't satisfy this.

Actually, I don't think my approach works with the harder version of the problem, since it relies on that fact that d(v) is monotonically increasing as you go down the tree. I think there should be a solution involving segment tree and coordinate compression, but I haven't thought about it that much. Please feel free to correct me on anything.

But Ordered Statistics Tree does. Can't we use it instead of sets?

An explanation please?

my solution using ordered statistics

Can someone please elaborate the binary lifting method for problem D?

My Code22652723easy to understand

in Div2C

I can't understand why not to fill our resulted array with zeroes and printing answer as 1? is there any restriction about our resulted array, that must contain different numbers?