300iq's blog

Avito Code Challenge 2018 — editorial
By 300iq, 6 years ago, translation, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Thank you for your participation, see you soon (I hope)!

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

Comments Comments (41)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In english?

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

Excuse me, where can I read about dp? Thanks.

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

Here are my solutions to the problems of this contest that I could do.

I have written an editorial about D here, in case anybody requires further explanation. :) I have also written a post about the O(n) solution to A here.

P.S. — What is the bonus solution to Problem D ?

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

    Awesome explanation !!!

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

      Thanks a lot :). I appreciate the encouragement :)

      P.S. — Are you refering to A or D ?

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

        I was refering to problem D, again awesome explanation !!! I'm adding you to my friends list :)

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

          Please follow me on Quora and read my answers there. I've written a few posts :)

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

            No. Who cares about your Quora?

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

              The people I was talking to do :)

              The real question you need to be asking yourself is who cares about your imaginary dragons and weird, snarky comments from a fake account ?

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

                Lol. Making a personal attack doesn't change the fact that you are a shameless advertiser.

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

                  I am writing posts so that it clarifies my concepts and can share my knowledge to help others. That's my only intention.

                  When you have a cheap mentality, everything looks cheap. Advertisement for what ? Quora doesn't give me any money if people read my answers.

                  Moreover, I'm on CF so that I can learn and increase my knowledge, not get drawn into random fights. My suggestion is that if you don't like my posts, don't read them. :)

                  I wish you well and have no intention in interacting further with you. :)

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

For bonus question of C,

Call a vertex a root if it's degree > 2.

Case 1 : There is atleast one vertex with degree > 2

If there is more than one root, then the solution stays the same as a decomposition is not possible. If there was exactly one root, then we have to make it the root and the solution stays the same. Making any other vertex the root will not satisfy the given conditions.

Case 2 : All vertices have degree <= 2

To minimise the number of paths, we must choose a leaf vertex since it has only one child and it will result in 1 simple path from one leaf to another.

For maximising the number of paths, we will have to pick any non-leaf vertex which has a degree of 2. There will be two paths, one to each leaf.

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

problem E is clearly visible from D&C ...how to solve by DP in an easy way..

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

I'm really curious about how to solve F in O(n⋅logn). Could someone tell me the method?

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

    Think about randomized binary search in O(log(n2))

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

      I tried to do binary search in O(log(n2)) which equals O(logn), but I failed. If a number doesn't equal any |ai - bj|, it can't be the answer. So there are O(n^2) numbers which can be the answer. But I don't know how to find the k-th of them quickly. What does "randomized binary search" mean?

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

        You can choose random distance  ≥ l and  ≤ r, (just find good interval for each element, and take random element from these intervals), because if you will take random element (not n/2-th) it will work in O(log(n2)) too.

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

          I'll use |ai - bj| to indicate the shortest distance bewteen ai and bj.

          Do you mean if we know the answer is in [l, r]，then we randomly select a number from numbers which are in [l, r] and are equal to some |ai - bj|?

          If so, is there any convenient way to randomly select a number? It's not uniform that randomly select an i , then randomly select a number from |ai - bj|. In fact for a fixed i, there may be no such j. A solution is calculating how many j satisfying l ≤ |ai - bj| ≤ r for each i using two pointers, then selecting an i using weighted random. But I think this is too complex.

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

            I don't know any other way ╮(╯▽╰)╭

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

              OK, thanks. It's a very interesting idea!

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

Can someone explain last paragraph of editorial of problem F, as I can't understand which segments we are talking about and why the intersection of segments is the validation for possible matching for that specific answer.

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

For problem F

"So we can solve the problem in O(n * L) — fix the cut, and match i-th bridegrom (in increasing order) with i-th bride (if we will order brides in the traversal order starting from border), and relax answer with current inconvenience."

Why this solution is always optimal?

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

    I know that this comment is 3 years old but

    Suppose the $$$i$$$-th bridegroom is match with the $$$p[i]$$$-th bride (in increasing order).

    Then we can see that if there exist two indices $$$i < j$$$ such that $$$p[i] > p[j]$$$, then swapping $$$p[i]$$$ and $$$p[j]$$$ does not increase the maximum distance that needs to be travelled.

    Thus $$$p[i] = i$$$ for all $$$i$$$ is an optimal solution.

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

For problem F Round Marriage.

I find a solution in O(n * log_2(L)) with the key idea in the tutorial.

What I do is just optimizing the progress of finding the range of x.

We can use two-pointers to work out it.

More in the code: 39254791

→ Reply
»
6 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Can someone please explain why this DP in pD is wrong : dp[i][j][k] as maximum value obtained by distributing books in segment [i, j] into k shelves? Complexity O(n^3.n^2) ? 300iq ghoshsai5000 Can you help me out?

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

    Can you share your logic or your program ?

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

      ps[] prefix sum Base case : dp[i][j][0] = ps[j] — ps[i-1] all books in segment are in same shelf

      Transition : dp[i][j][k] = max(dp[i][j][k], (dp[i][be][x] & dp[be+1][j][k-x]))

      Ans : dp[0][n-1][k-1]

      Complexity : O(n^3) for states and O(n^2) for each transition

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

      Any success ghoshsai5000

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

        I think the main problem is AND-ing may not necessarily have optimal substructure !

        What I mean is ... If we want to know the best AND of a segment [1, 4] into 2 segments, it might not necessarily be the best [1, 2]&[3, 4].

        I'm not able to come up with a good counter example. I hope you understood my point.

        You make one segment [3, 4] ... Now to know the maximum AND with the last segment [3, 4], you might not necessarily need the best AND of [1, 2]. You might need something less than best in that segment.

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

          Thank you :)

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

            I hope you understood. I tried my best. Wasn't able to come up with a counter example :)

            That's why the intended solution greedily sets as many higher order bits as possible.

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

Can someone explain me problem C?

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

For problem F, is the following correct :

First, binsrch on ANS, now we will check whether such answer exists using hall's theorem. So we want to count for each 1 <= L <= R <= N whether number of brides reachable from grooms of [L,R] is atleast R-l+1. So start with [1,i] for all 1<=i<=N. Get the count for these. Now, we update our values for [2,i], then [3,i] and so on using Lazy propagation on Segment tree. Basically, when we remove some element, we invalidate a range of brides for the segment [j,i]. Note that since its cyclic, we wont update all i from j <= i <= n when updating from [j-1,i] to [j,i], because some of them might be accessed for say i = n. Thus, we need Lazy range addition and min. Overall, logL * nlogn.

Is this correct though? I am not confident in applying Hall's theorem.

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

I think I have a simpler solution for problem E:

Sort the queries in increasing $$$r_i$$$. Then mantain $$$dp[i]$$$ which is the rightmost index in the array which we can achieve a maximum of $$$i$$$ in. Iterate through the queries, initially setting $$$dp[0]=r_i$$$ and then iterating backwards like the knapsack DP trick (I think this is covered in Errichto's AtCoder DP video in the knapsack problem) to update all the $$$dp[i]$$$. Complexity $$$O(nq)$$$.

73507542

→ Reply