i_am_not_special's blog

Quintomania Div 3 hard version
By i_am_not_special, history, 3 weeks ago, In English

You are given an array a of integers with n elements. You are allowed to rearrange the elements of the array in any order. Your task is to determine if it is possible to reorder the array such that for every i from 0 to n-2 (i.e., for all adjacent elements), the absolute difference between consecutive elements is either 5 or 7. That is, for all i such that 0 <= i < n — 1, you need to check if: abs(v[i] — v[i + 1]) = 5 or abs(v[i] — v[i+ 1]) = 7.

  • Vote: I like it
  • -1
  • Vote: I do not like it

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

Auto comment: topic has been updated by i_am_not_special (previous revision, new revision, compare).

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the expected time complexity?

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

what are the constraints on a[i]?

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I think I solved it. Lets discuss in the dm. But damn this was such a good question. You should have offered it as a problem in a contest. Please ping in dm.

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

    Why dont you post it here so everybody can ser

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

      First let me be sure if my approach is correct or not :)

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

        even i dont know the solution

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

        Yea well I am curious about the solution, share it in my DMs if you are comfortable sharing here i guess? Thanks

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

          i have some solution but i dont know is it correct or not. i am thinking that first sort the array then define the range as l = v[0] and r = v[0] then select the next element and insert the element on either side of range and then update thhe range.

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

            And how will you determine which side of the range to insert it on?

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

              i am thiking first on right side if it is not possible on right side then on left side.

              → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice problem

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

ignore plz

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Just writing whatever comes into my faulty memory at this point, but I think I faced a similar problem in an OA once and later found out that such problems are solved my building a graph out of it and determining the maximum flow or something similar on that line, I am not educated on the algorithm yet.

I dont believe theres a simpler solution but I'd be happy if someone figures it out.

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

    I tried it out and initially thought it would work, bu then found myself a testcase where it would fail

    The approach was like store all the elements in a multiset, and choose an elenment that is smallest and then find its neighbouring elements, that are either situated at a distance of +5 or +7. If you find it, put it adjacent to that element and erase them from the multiset and continue till the multiset is empty.

    Ex: let us take a simpler testcase. {3 5 8 10}, smallest is 3 so now answer looks like

    ...3...

    search for possible adjacent elements, ie 8 and 10, we find here both, so the array looks like

    ...8 3 10... now for 8, neighbours could be 3,13,15, we find none.

    So search for neighbours of 10 we find 5. so the array now is 8 3 10 5, and our multiset is now empty.

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

      i also thiking of the same approach.

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

      But this fails miserably on a testcase like {10 3 10 17 22 15 8} Here, comes the problem, the neighbours could be 8 3 10 or 10 3 10

      Unfortunately, if we take neighbours to be 8 3 10, we cant always empty the multiset.

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

        for this, if you take 8 3 10 15 22, you are stuck, now no edge element have corresponding neighbour in set :(

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

      Well again, I am sorry but that is a wrong greedy.

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

    If you construct a graph such that there exists an edge $$$(u,v)$$$ if and only if $$$|a_u - a_v| = 5$$$ or $$$|a_u - a_v| = 7$$$, then the problem is a Hamiltonian Path Problem, and cannot be solved in poly time.

    I bet this problem cannot be solved better than $$$\mathcal O(2^n \text{poly}(n))$$$.

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

      Right, this problem is indeed NP-Complete.

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

      This is a clever observation. Well done !

      → Reply