Quintomania Div 3 hard version

3 недели назад, # |

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

→ Ответить

3 недели назад, # |

What is the expected time complexity?

→ Ответить

3 недели назад, # ^ |

O(nlogn)

→ Ответить

3 недели назад, # ^ |

Don't know the tc but I am assuming it is possible in nlogn

→ Ответить

SkibidiPilav

3 недели назад, # |

what are the constraints on a[i]?

→ Ответить

3 недели назад, # ^ |

1e9

→ Ответить

3 недели назад, # |

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.

→ Ответить

3 недели назад, # ^ |

Why dont you post it here so everybody can ser

→ Ответить

3 недели назад, # ^ |

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

→ Ответить

3 недели назад, # ^ |

even i dont know the solution

→ Ответить

3 недели назад, # ^ |

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

→ Ответить

3 недели назад, # ^ |

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.

→ Ответить

3 недели назад, # ^ |

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

→ Ответить

3 недели назад, # ^ |

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

→ Ответить

anucode

3 недели назад, # |

Nice problem

→ Ответить

JulSjlv

3 недели назад, # |

← Rev. 2 →

ignore plz

→ Ответить

3 недели назад, # ^ |

in my question you can rearrange the element.

→ Ответить

3 недели назад, # |

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.

→ Ответить

3 недели назад, # ^ |

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.

→ Ответить

3 недели назад, # ^ |

i also thiking of the same approach.

→ Ответить

3 недели назад, # ^ |

← Rev. 2 →

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.

→ Ответить

3 недели назад, # ^ |

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

→ Ответить

3 недели назад, # ^ |

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

→ Ответить

3 недели назад, # ^ |

I realised :(

→ Ответить

3 недели назад, # ^ |

still my approach will work for that testcase

→ Ответить

little_dog

3 недели назад, # ^ |

+15

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))$$$.

→ Ответить