Блог пользователя Shafaet

Автор Shafaet, история, 2 месяца назад, По-английски,

I invite you to take part in HackerRank HourRank 19 starting on April 2nd 2017. The contest duration is 1 hours. There will be three algorithmic problems of various difficulty.

The chief author of this round is torquecode. The chief tester is pkacprzak. Thanks to Piotr Gajowiak and wild_hamster for pre-solving the problems and giving valuable opinions.

The problems will have subtasks to make them interesting for everyone. I strongly recommend to read all the problems.

The contestants are ranked by score. If two contestants get the same score, the person who reached the score first is ranked higher.

Happy Coding!

 
 
 
 
  • Проголосовать: нравится  
  • +16
  • Проголосовать: не нравится  

»
2 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Wow a 1 hour event again.......Thanks for the info :0 Hoping for better rating this time .

»
2 месяца назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

For the last question,instead of removing each edge and calculating the diameters of the 2 trees obtained..it would be sufficient to just remove edges incident on the center of the tree and which are part of diameter(ie only 2 edges). Although I'm not aware of the proof,I'm quite sure that this should also be correct.

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Third problem is similar to a COCI problem which I think is the reason why people solved it so quickly.

  • »
    »
    2 месяца назад, # ^ |
    Rev. 4   Проголосовать: нравится +5 Проголосовать: не нравится

    Are your certain that's correct? What would be your answer for this tree?

    UPD: Don't know how to post images :-(

  • »
    »
    2 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Also, reducing this problem to calculating the longest path in every subtree (also for the subtrees "going up") is pretty easy, and the latter problem is incredibly standard and well known... So I would guess some of the fastest contestants just copied their solutions from some other problem which required the same thing, not necessarily the one you mentioned. I couldn't remember any of those problems though, had to implement it again :P

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain how to solve the second problem.

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Read Nim

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    let indexes are 0..n-1.
    
    1.   s[b] XOR s[b+1] XOR ... XOR s[e] == s[0] XOR s[1] XOR ... XOR s[n-1] = stotalxor = const.
    2.   s[b] XOR s[b+1] XOR ... XOR s[e] == ( s[0] XOR s[2] .. XOR s[b-1])  XOR ( s[0] ... s[e] ) =
         =  v[b] XOR v[e+1]
    3.  for each 0 <= e < n   need find how many b <= e, that v[b] XOR v[e+1] == stotalxor.
        or  v[b] = stotalxor XOR v[e+1].
    
    where v[i] = s[0] xor s[2] ... s[i-1] .
    v[i] - easyliy computeted, because  v[0] = 0,  v[i] = v[i-1] xor s[i-1], for i > 0.
    
      and v[i] <= 2^17.
    
    Let  xorcnt[ i ] - number of that j,   v[j] = i.
    
    xorcnt[i] - also easyly computed.
    
    xorcnt[v[0]] = 1;
    ans = 0;
    for(int i= 1; i <= n; ++i){  ans += xorcnt[ v[ i ] ^ sxortotal ];  xorcnt[ v[i] ] ++; }
    cout << ans; 
    
    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      well if i got you right finding all combinations of v[b] ^ v[e] == stotalxor is the main idea of solution?

      • »
        »
        »
        »
        2 месяца назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        Nim game: first player can win if only if xor sum s[] elements is not zero.

        But, our case need count winning situations of second player, so need achieve xor sum of s[] elements to zero, after remove s[b]...s[e] elements.

        i.e.

        s[0] xor s[1] xor ... xor s[b-1] xor s[e+1] xor ... s[n-1] == 0.

        add xor to both sides to (s[b] xor s[b+1] xor .. s[e]) — gives

        stotalxor = xor_sum(s[i], i= 0..n-1) = 0 xor xor_sum(s[j], j = b..e) = xor_sum(s[j], b..e).

        xor_sum(s[j], j = b..e) = xor_sum(s[j], j = 0..b-1) xor xor_sum(s[j], j = 0..e)

        Let v[k] = xor_sum(s[j], j =0..k-1);

        so need find that (b,e) pairs (0 <= b <= e < n ), that v[b] ^ v[e+1] == stotalxor.

        if we know e, so can calculate number of b, that 0 <= b <= e, and v[b] ^ v[e+1] == stotalxor. because,

        v[b] = stotalxor ^ v[e+1].  if we store number of v[i] ,  0<=i<=e  in xocrcnt[] array, number

        of b is xorcnt[ stotalxor ^ v[e+1] ].