300iq's blog

By 300iq, 2 months 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  
  • +157
  • Vote: I do not like it  

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In english?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please link the editorial to the English version of the contest 300iq

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 months 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 ?

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

    Awesome explanation !!!

    • »
      »
      »
      6 weeks 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 ?

      • »
        »
        »
        »
        6 weeks 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 :)

        • »
          »
          »
          »
          »
          6 weeks 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 :)

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

            No. Who cares about your Quora?

            • »
              »
              »
              »
              »
              »
              »
              6 weeks 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 ?

              • »
                »
                »
                »
                »
                »
                »
                »
                6 weeks 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 weeks 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. :)

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 weeks ago, # ^ |
                  Rev. 2   Vote: I like it 0 Vote: I do not like it

                  Lol. Learn and increase your knowledge? I am seriously curious about what you have learnt. Writing unreadable code and cranking out solutions to unrealistic problems? Stop bluffing yourself!

»
7 weeks 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.

»
7 weeks 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..

»
7 weeks 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?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      7 weeks 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?

      • »
        »
        »
        »
        7 weeks 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.

        • »
          »
          »
          »
          »
          7 weeks 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.

          • »
            »
            »
            »
            »
            »
            7 weeks ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

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

            • »
              »
              »
              »
              »
              »
              »
              7 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

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

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

                yeah, it's a fascinating ideal,So good, :D

»
7 weeks 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.

»
7 weeks 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?

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E(DP solution), I am unable to crack the logic behind size of DP array(size = N = 1e4+7). Can you explain. Also the case of taking random number to avoid hacking.Why??

»
5 weeks 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

»
2 weeks 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?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you share your logic or your program ?

    • »
      »
      »
      2 weeks 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

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      Any success ghoshsai5000

      • »
        »
        »
        »
        2 weeks 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.

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thank you :)

          • »
            »
            »
            »
            »
            »
            2 weeks 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.