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.

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)

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

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;

About Savita:

First two steps are obvious — just two Dijkstras from both nodes of our edge. Let's call results of Dijkstras

d_{ i}ande_{ i}. Note that they can be infinite as we exclude our edge from the search.Now we know that if

ansis the answer then we can go left and spendans+d_{ i}time to reach thei-th node or we can go right and spendD-ans+e_{ i}whereDis the size of our edge. We are interested in minimum. So we must find suchansfor whichmax_{ i}min(ans+d_{ i},D-ans+e_{ i}) is as small as possible.Now let's sort our

d's ande's according to the difference between them. Then for allanswe will takeans+d_{ i}for some prefix of distances andD-ans+e_{ i}for some suffix. That gives usn+ 1 interval of values ofans. Now we check for each of these intervalsmax(ans+d_{ maxfromleft},D-ans+e_{ maxfromright}and choose the minimum of these values.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)

And when will be system tests or smth like this?

It will be finished in a couple of hours

For

Savita And Friendsyou can look at similar problem 266D - BerDonaldsWow, 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.

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 (aboutO(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 isO(sqrt(N))per operation.Results has been published already. It seems that testcases for problem

String Function Calculationare 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.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 :)

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

Rejudging has been started, as far as I know.

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.

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

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

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.

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

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

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

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

not for you