Fcdkbear's blog

HackerRank Weekly Challenges — Week 7
By Fcdkbear, 10 years ago, In English

Let's discuss problems here.

Here is very-very short explanation of my solutions.

Die Hard 3

Use dfs/bfs on a graph, where vertice is represented by a pair of integers, each of which denotes the amount of water in a jug.

Chocolate in Box

This problem requires very basic knowledge about game theory and nim game. It is also important to notice, that we can do exactly 0 or 1 optimal moves in one heap.

String Function Calculation

Let's build suffix array and calculate LCP array. Now we can calculate maximum of occurrences of a substring with some fixed length using some sets/multisets

Savita And Friends

Have no idea how to solve this problem. I tried ternary search, but obviously it won't give the correct answer. I'll be very grateful if someone posts his solution to this problem

The crazy helix

One can use treap to answer all the queries. However, i used treap to answer the queries of type 1 and 2. For the third type of query I used sqrt-decomposition on the queries.

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

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For Savita and Friends i first submitted ternary search, then ternary search with additional checking of border points — it failed pretests because of problems with checker.

Then I submitted binary search of max_distance (in doubles, It also gave WA). I thought it was because of precision problems, so i rewrited it to do all calculations in integers. It passed. And then problem was fixed, all solutions rejudged, and even my first solution with ternary search passed pretests)

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

    Surprisingly, my ternary search with some extra checkings passed system test (as I can see, your implementation also passed system test). But let's consider the test:

    3 3 3
    1 2 1
    1 3 1
    2 3 2

    The function for ternary search is going down from 0 to 0.5; then it goes up from 0.5 to 1; then it goes down from 1 to 1.5; then it goes up from 1.5 to 2. I think, that ternary search shouldn't work on this type of tests. So, judges have weak tests, I guess

    → Reply
»
10 years ago, # |
← Rev. 5   Vote: I like it +8 Vote: I do not like it

Savita and Friends I solved without binary/ternary search. (A,B) lets go from point A to B, and choose best answer. At the beginning, some points will go through Point A, others through B (when distance from point A equals 0),

Lets vertex v, goes through vertex A, and we must find first time when it will change to B (i.e going through B is profitable than going A).

D[A][v] + t >= D[B][v] + weight — t

t >= (D[B][v] — D[A][v] + weight) / 2

where D[A][v] = shortest distance from point A to v. weight is weight of (A, B)

So we will consider all distances (D[B][v] — D[A][v] + weight) / 2 for every v,

Sort them, and line sweep;

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

About Savita:

First two steps are obvious — just two Dijkstras from both nodes of our edge. Let's call results of Dijkstras di and ei. Note that they can be infinite as we exclude our edge from the search.

Now we know that if ans is the answer then we can go left and spend ans + di time to reach the i-th node or we can go right and spend D - ans + ei where D is the size of our edge. We are interested in minimum. So we must find such ans for which maximin(ans + di, D - ans + ei) is as small as possible.

Now let's sort our d's and e's according to the difference between them. Then for all ans we will take ans + di for some prefix of distances and D - ans + ei for some suffix. That gives us n + 1 interval of values of ans. Now we check for each of these intervals max(ans + dmaxfromleft, D - ans + emaxfromright and choose the minimum of these values.

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

About The Crazy helix.

3 type query can be solved also using treap.

First we will find sequence of moves from root to the node. After that starting from the root go down to the our node. If needed we must push vertex(i.e swap left and right children, and mark them)

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

And when will be system tests or smth like this?

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

For Savita And Friends you can look at similar problem 266D - BerDonalds

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

    Wow, it is actually the same problem, just that we have to compute the answer for each edge. I did something similar except that instead of ternary search, I computed the actual point where we get the minimum for each sub-interval using some computations.

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

Savita and Friends: I used binary search on the max-distance. I first implemented the double version (passed all preliminary tests) and later, just in case, also implemented the integer version (since the answers were either integers or integers + 0.5), which also passed all preliminary tests.

The crazy helix: I maintained an array of intervals (each interval represents a sequence of positions from the "base" array). Each type 1 operation splits at most 2 intervals and then reverses the intervals in the array. When there are too many intervals in the array (about O(sqrt(N))), simply rebuild the "base" array (and you get again 1 single interval). The same array of intervals is used for answering type 2 and type 3 queries. The overall time complexity is O(sqrt(N)) per operation.

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

Results has been published already. It seems that testcases for problem String Function Calculation are not valid. Problem statement says that 1 ≤|T|≤ 10^5, but in tests #6, #7, #8, #9 string has bigger size; as a result, some submissions (like mine) got WA/RE on these tests.

Upd. Oh, sorry, I got it, current standings are not final, system testing is in progress. Anyway, problem with bad testcases is pity one; I posted question about it in problem disqussion.

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

    Yes, mine, too. And I used a limit twice as large as the one from the problem statement (but the test cases are even larger than that). I guess it's just impossible to have a smooth contest at Hackerrank :)

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

      The setter said that he has changed his test data to satisfy the limits given in the problem. Guess some admin should rejudge all accepted submissions. But indeed, who cares? XD

      Edit: ashashwat pointed to me that the tester's code had MAXN set to 111111. Now, how did that possibly pass? :D

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

    Strange things occured: i submitted solution, which got RE on test cases mentioned above, during upsolving, and it passed all tests! What on earth does it all mean?

    UPD: i read discussion about it on https://www.hackerrank.com/contests/w7/challenges/string-function-calculation/forum/questions/7206. Seems that test cases were updated.

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

I'm very surprised that forth problem was much easier than third

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

    On the contrary, I'm very surprised at the number of downvotes you're getting.

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

For the first problem we can take the gcd of the volume of the two jugs. If this gcd divides the target volume then the target volume can be achieved.

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

    I wanted to write a formal proof for this, but couldn't. Can someone please help me proving it?

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

      The link to the proof is given in this alternate editorial.

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      General idea is to show that all volumes that can be achieved can be written in the form of ax + by, where x and y are integers (can be negative), and a, b are the volumes of the jug.

      Let v be the volume which can be attained by the pouring operations. Assume that v can be expressed in the form of ax+by. Then, we can exhaust a list of all possible pouring operations (eg pouring from a to b, emptying the jug, etc). For each action, we can show that the volume attained is still expressable in the form of ax + by. There are several cases but most are trivial (eg pouring all the water away), so I will omit the exhaustion of cases here.

      Once it is shown that v = ax + by, from Bezout's Identity (which is a corollary of Euclidean algorithm) we know that v is divisible by the gcd of a and b. By the way, remember to check if the target volume is smaller than a and b, otherwise there will be jug overflow :P

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

www.hackerrank.com is interesting site. Is there some prize? =)

→ Reply