halin.george's blog

By halin.george, history, 13 months ago, In Russian,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Vote: I like it  
  • +48
  • Vote: I do not like it  

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

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!

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

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

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

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

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

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

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

    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:

    1. dist(v, u) = dist(root, u) - dist(root, v)
    2. 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.
    3. 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)
    4. 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?
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

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

        this can be maintained using segment tree on the path from root to current vertex

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

      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?

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

        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" D for this problem, then we can reconstruct the answer "array" A from it.

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

          Nice thought.Thanks a lot.

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

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

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

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

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

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

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

    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.

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

      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.

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

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

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

    An explanation please?

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

    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!

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

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

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

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?

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

    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.

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

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?

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

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 ?

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

    "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

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

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;

}