Shafaet's blog

HackerRank World Codesprint April
By Shafaet, history, 9 years ago, In English

Hello CodeForces Community!

I am glad to share that HackerRank's World Codesprint April is scheduled on 29-April-2016 at 16:00 UTC. Contest duration is 24 hours.

Go ahead and register now to show off your coding abilities, and win upto $2000 Amazon gift cards/bitcoins and tshirts. [Note: Winners from US and India will receive Amazon Gift Cards. Winners from other countries will receive equivalent USD amount in bitcoins.]

The problems were prepared by malcolm, Radewoosh, svanidz1, ma5termind and Shafaet. Thanks to wanbo for testing the problems and forthright48 for helping with editorials.

The contest will be rated. If two person gets same score, the person who reached the score first will be ranked higher.

Editorials will be live soon after the contest ends, I invite everyone from experts to beginners to participate and solve challenges. I hope everyone will enjoy the contest.

Edit: The contest is less than 15 minutes away.

Score distribution: 15-20-40-60-60-80-80-100

Update:

The contest is over! Congratulation to the winners:

Ratings will be updated soon. Let us know if you like this round and don't forget to join the next contest HourRank-8!

Update:

Details editorial for Move the Coins problem is posted here.

  • Vote: I like it
  • +128
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +11 Vote: I do not like it

win upto $2000 Amazon gift cards/bitcoins, medals and tshirts.

I can't find medals amongst the prizes.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oops the Medals was for last world codesprint, not this one, edited the post. Thanks.

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +91 Vote: I do not like it

Unfortunate intersection with Codeforces Round.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This was scheduled since like forever, CF round was only announced a short while before the contest.

    → Reply
»
9 years ago, # |
  Vote: I like it +53 Vote: I do not like it

I enjoyed the problems. Much better than the last CF round.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +30 Vote: I do not like it

    Really glad to hear that. There will be another world code-sprint in May, hoping to see you there!

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    I have not seen problems from the latest CF but I don't regret that I missed that round because of Codesprint. Very cool problems, especially one about coins on the tree.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      I am very happy to know a top guy like you liked my game problem :D. Thanks.

      → Reply
»
9 years ago, # |
  Vote: I like it +32 Vote: I do not like it

problem 7 was really great. I enjoyed it a lot! Thanks for all your effort (and nice prizes — which will make a great dinner with my family)

→ Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Missed CF round because of the Codesprint — and people say I've done nothing wrong.

Unfortunately I have no much time to participate, but I liked the tasks I was able to solve. Tasks about greedy KMP and nim on the tree (4th and 5th) were already enjoying, so I wonder how cool might be the next ones?

→ Reply
»
9 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Can someone explain like I'm five a solution to the "Sum of the Maximums" problem? I don't understand how to boost the solution in editorial.

I solved it using MO's techinque in (after some fight it passed).

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Hey.Can you share your approach?I was trying this with MO's algorithm but couldn't figure out a way to add/remove a new number to the existing subarray in sublinear time.

    Thanks.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      I also did it using MO's but only when we can add an element to the range and not subtract. It passed well in time. My approach was as follows :
      For every block , sort the queries by increasing R (as in MO's). Now for every query [L,R] , calculate the answers independently for [L,mid] and [mid,R] where mid is the end point of that block. For every query we can spend O(root(N)) for [L,mid] and since R is always increasing the overall time for all [mid,R] queries of this square root block would be O(N). Now the only step left is the merging step i.e. getting the answer of [L,R] from [L,mid] and [mid,R]. To do this, while processing the [mid,R] interval maintain an array containing only elements in increasing order (that occur along the path). Then, iterate over all elements from [L,mid] and to get the contribution of i'th element (i.e. sum of max of all subarrays starting at this point) we binary search to get the first position j in the increasing array maintained such that A[arr[j]] >= (max of all A[k], k goes from i to mid) and then add the contribution accordingly (see code for more implementation details.)

      You can have a look at my code here : http://pastebin.com/DhDgmY4V

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it +15 Vote: I do not like it

      We use standard MO — aproach. So we sort queries, start with first query and then change one query to another. There are four types of moves:

      • add-left

      • add-right

      • subtract-left

      • subtract-right

      Let us first focus on add_left: We have the answer for the interval [L, R] and we want to compute the answer for the interval [L - 1, R]. So we just want to know

      How to compute that? I use "ladder" technique. We have two tables: $next_right[N][log_N]$ and result_right[N][log_N], which means:

      • next_right[i][h] is 2h-th element to the right on the longest increasing sequence starting at A[i].

      • result_right[i][h] is

      Those tables can be easly computed for example next_right[i][h] = next_right[next_right[i][h - 1]][h - 1] and result_right[i][h] = result_right[i][h - 1] + result_right[next_right[i][h - 1]][h - 1] and so on.

      In order to compute F(L - 1, R) we use that ladders. We start at L - 1 and want to reach R. We process ladders from log_N to 0, if the ladder goes before R then we use it, otherwise we skip it.

      In the same manner we deal with add-right, subtract-left, subtract-right.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I also used Mo's algorithm but did all add and subtract operation in O(1) with some precalculation. It's useful to see that when going from [L-1,R] to [L,R],and we want to add sum of maximums of segments [L,x] , L<=x<=R.You go to first element bigger than A[L] (let's say it has position x),add to solution (x-L)*A[L],then next bigger than A[x] .... and so on.(until next bigger >R,when you add (R-x+1)*A[x]). Array nextbig[i]=first bigger element from right of i,and can be computed in O(n).

        Ok,this approach is slow,it can take O(R-L+1)steps. We can do better. Make a tree with edges(nextbig[i],i) ,precalculate partial sums on tree (root being position n+1),like val[i]=(nextbig[i]-i)*A[i] and sum[i]=sum[nextbig[i]]+val[i]. Now moving to nextbig[i] is just going up on tree. It would be nice if we can find the last node we reach until we go after limit R.

        And this is actually the maximum element on segment [L,R] with minimum position of all positions in segment. Now this can be answered with RMQ table precalculated in O(n*log). Take care that val[max_seg] can include segments with are not in [L,R]. So let's say minimum position of maximum is x. The answer is sum[L]-sum[x]+(R-x+1)*A[x].(for every node from path L to x excluding x is safe to add all segments where that node is maximum,which is equivalent to val[i])

        → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +30 Vote: I do not like it

    For O(NlgN) solution, imagine a N * N grid filled with RMQ[i, j]. In such grid, there is N rectangle (which is derived from every element) filling whole grid.

    To enumerate these rectangles, you can use this divide & conquer algorithm. This algorithm calculates the area where the given elements affect the grid, and it's clear that this algorithm fills the whole grid.

    void solve(int s, int e){
	if(s > e) return;
	pi t = query(s, e); // returns {minvalue, position which minvalue occurs} pair
	v.push_back({s, t.second, t.second, e})// add [s, t.second] x [t.second, e] rectangle with value t.first
	solve(s, t.second-1);
	solve(t.second+1, e);
}

    Now it became a geometry problem. For every queries (which is also a rectangle) , you should calculate the sum of (intersection area) * (value of rectangle).

    This problem can be solved offline using segment tree + plane sweeping. split every rectangle [sx, ex, sy, ey, v] to [1, sx-1, sy, ey, -v] + [1, ex, sy, ey, v] and sweep from x coordinate. Now answer each query by

    • Building two segment tree which can add value in range, and calculate sum in range
    • Answer is form of [LinearSum] * xcoord + [TotalSum]. Maintain these sums and answer the queries.

    code : http://ideone.com/rLzNjF

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you describe reduction to geometrical problem in more details again?

      → Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +38 Vote: I do not like it

Problem 8 : this problem can be solved without HLD.

For every vertex v. maintain ans[i] = sum of value from path [root — i]. If we maintained it correctly, we can answer the query by returning ans[s] + ans[e] — ans[lca(s,e)] — ans[parent(lca(s, e))].

For speedup, we use the identity Sum(F(i)) = F(i+2) — 1. Now addition query "U v k" can be transformed into "add F(k + depth[x] — depth[v] + 2) — F(k + 1) for all x lying in subtree of v"

Adding -F(k+1) to subtree can be done with matrix + binary power + dfs numbering + fenwick tree.

To add F(t + depth[x]) to subtree, we can do the same with above — just store matrix in fenwick tree. We add F^(t) (F = {{1, 1}, {1, 0}} to range, and calculate F^(depth) * BIT.Query(v) matrix in query stage. Now the problem is solved in O((N + Q)lgN).

Note that the t in F^(t) might be negative, but it can be solved by powering inversion matrix of F.

code : http://ideone.com/MigTNx (sorry for messy codes)

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone suggest me some other problems like "Lovely triplets" (prob 6) ? I really like this problem.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Maybe you want to look at problems with tag "constructive algorithms" on CodeForces.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Would anyone care to explain why, in Move the Coins, the nimber is the xor of all odd-level nodes' values? Maybe proving this once you have the hypothesis is not so difficult, so, more importantly, how did you come to that idea?

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

I really like the problem set! All problems are nice, most especially the middle ones:

  • Yet Another KMP Problem
  • Move the Coins
  • Lovely Triplets

For Fibonacci Numbers Tree, I used Binet's formula to convert Fibonacci numbers to powers of φ. Then I just worked on the field in all my calculations. Using powers of φ allows for simple identities like φa + b = φaφb in replacement of Fa + b = Fa - 1·Fb + Fa·Fb + 1. It's not necessarily more efficient, but that's okay.

→ Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Where can I specify my BTC wallet number to receive the money? Or the organizers will contact me by email?

→ Reply
»
9 years ago, # |
  Vote: I like it +30 Vote: I do not like it

In the order of difficulty order: easy, easy, a bit harder, good, good, good, boring, boring.

In particular, I knew how to solve the sum of maximums because I contemplated it in a problem I set here on CF (you can find it easily). At that time, I thought it's too much work with nothing creative (just non-trivial Fenwick trees) and decided to let O(NQ) solutions pass.

The last problem was easily solvable with sqrt decomposition: after each update queries, recalculate the sums on all paths from the root; when computing an answer to a query, take the last sum obtained that way and add everything from update queries (a prefix sum of Fibonacci numbers is a Fib. number again, big indices can be dealt with by matrix multiplication). Problems 4-6 were far more interesting to me than this.

→ Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

There must be something wrong <(") Though I like it more this way :P

→ Reply