halin.george's blog

By halin.george, history, 3 years ago, ,  Tutorial of Codeforces Round #381 (Div. 1) Tutorial of Codeforces Round #381 (Div. 1) Tutorial of Codeforces Round #381 (Div. 2) Tutorial of Codeforces Round #381 (Div. 2) Comments (30)
 » 3 years ago, # | ← Rev. 2 →   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)?
•  » » 3 years ago, # ^ | ← Rev. 2 →   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'
•  » » 3 years ago, # ^ | ← Rev. 3 →   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) for any vertex v, and its ancestors a1, a2, ..., ai,a1 being the furtherest ancestor (root of the tree) and ai the closest (immediate parent vertex),we can see that dist(root, a1) < dist(root, a2) < ... < dist(root, ai) < dist(root, v), a sorted sequence that is binary searchable. for each vertex v, we want to find the number of vertices u it controls, i.e.:dist(v, u) ≤ value(u) dist(root, u) - dist(root, v) ≤ value(u) dist(root, u) - value(u) ≤ dist(root, v) with #2 and #3 in mind, let's try to think of this problem in another way: for each vertex u, which vertices v could control u?
•  » » » 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?
•  » » » » this can be maintained using segment tree on the path from root to current vertex
•  » » » 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 = DA = D + DA = D + D + DA = D + D + D + DA = D + D + D + D + D If we can somehow first construct a difference "array" D for this problem, then we can reconstruct the answer "array" A from 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
•  » » 3 years ago, # ^ | ← Rev. 3 →   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?
•  » » » 3 years ago, # ^ | ← Rev. 2 →
•  » » Hi,your approach looks amazing, I just learned binary lifting through this problem and now you propose another way of doing the problem... Where did you learn this technique from, I want to learn this too,is there some blog post associated with it , or some source where I can learn the merging set technique,because I cant understand your solution , can you also explain it just a little..?Thanks a ton!
•  » » »
 » Can someone please elaborate the binary lifting method for problem D?
•  » » My Code 22652723easy to understand
 » in Div2CI 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?
•  » » You want to maximize the minimum mux so if u fill the whole array with zeroes the answer will be 1 but u can fill it from 0 to the length of the array so the closest non-negative integer can be the maximum which is the length of the array.
 » In 739E — Gosha is hunting, The editorial writes "Not hard to prove that in group Y we should throw Poke Balls to Pokemons with greatest u - p." I think that we want to maximize PokeBalls probability when we throw PokeBalls. So shouldn't we throw pokeballs to pokemons with greatest p-u?
 » In Div1-A or Div2-C Why not to just fill the whole array with the maximum available value which is 10^9-1 and the maximum minimum mex becomes 10^9 ?You didn't mention anything like : the array(or subarray) elements need to be unique !What am I getting wrong here ?
•  » » "The mex of a set S is a minimum possible non-negative integer that is not in S."if you fill array with max value your ans will be 0
•  » » » Oooops , yes thanks.
 » 2 years ago, # | ← Rev. 2 →   import java.security.MessageDigest;import java.security.NoSuchAlgorithmException;public String get_SHA_512_SecurePassword(String passwordToHash, String salt){String generatedPassword = null; try { MessageDigest md = MessageDigest.getInstance("SHA-512"); md.update(salt.getBytes("UTF-8")); byte[] bytes = md.digest(passwordToHash.getBytes("UTF-8")); StringBuilder sb = new StringBuilder(); for(int i=0; i< bytes.length ;i++){ sb.append(Integer.toString((bytes[i] & 0xff) + 0x100, 16).substring(1)); } generatedPassword = sb.toString(); } catch (NoSuchAlgorithmException e){ e.printStackTrace(); } return generatedPassword;}
 » Why does my code fail at test 9?It takes 45 to get from 80 to 25, and 45 is greater than 25http://codeforces.com/contest/739/submission/43924000