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

Автор Fcdkbear, 10 лет назад, По-английски

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.

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

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

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)

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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

»
10 лет назад, # |
Rev. 5   Проголосовать: нравится +8 Проголосовать: не нравится

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;

»
10 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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.

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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)

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

And when will be system tests or smth like this?

»
10 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +24 Проголосовать: не нравится

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.

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +24 Проголосовать: не нравится

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.

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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.

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

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

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

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

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

      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

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

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