Hello Codeforces community!
I am glad to announce that HackerRank 101 Hack 43rd edition will be held on 17th Nov 2016 at 16:30 UTC. You can sign up for the contest here. Though what's priceless is solving interesting problems and the thrill of competition, prizes make the competition fierce. Top 10 performers will get a HackerRank T-shirt.
Problems have been set by SkyDec and tested by wanbo. The contest will consist of 5 problems with variable scoring distribution. You’ll have 120 minutes to solve them. We have tried our best to prepare a nice problem set. Hopefully everyone will enjoy. Also, you'll be able to enjoy the detailed editorials written by the setter.
If anyone are interested in sharing their knowledge, you can comment in this post or send message to wanbo. We eagerly need bunch of good problems.
Good luck and have fun!
Auto comment: topic has been updated by SkyDec (previous revision, new revision, compare).
Would the problems be in English ?
yes, it will be in English.
Yes
in K-inversions do you mean k <= nC2 as well as nc2 <= 1e5 or k <= nc2 and k <= 1e5
AC solution on Maximal And-Or Product
just checking i and i + 1 works too
At Maximal And-Or Product,Just the | and & of the largest 2 different number should solve it :D
That's just because of weak testcases.
Here's an anti test case for sorting and then taking max of every a[i] and a[i+1].
4
1 8 16 65
Yeah,the editorial is overcomplicated,there is an easy brute:
the solution with just two maximal numbers gets 100%, that's fine.
system tests was very weak!
By the editorial we can prove that we only need to consider the top log(a_i) number。 We didn't find it before contest. I'm very sorry.
My solution :
Full score in D — sort the array and while we have time, take two random indices greater than N-1000 and compare their f to the answer.
WTF, taking only the 2 largest numbers gives full score, too. Simple counter-example is {1, 1, 2^27, 2^28}, the answer is 1.
Problem E
1) Last problem was similar to https://www.hackerearth.com/problem/algorithm/perfect-permutations-september-clash/description/
2) Tests for this problem are weak, my O((k - n)2) solution passed
(nevermind)
Can someone please explain the approach in editorial for Problem D? Thanks!
For the j-th bit and for set S,you partition numbers in 2 sets. S0-those who have j-th bit set to 0, S1-those who have j-th bit set to 1. Let's call the answer for j-th bit and set S f(S,j).
Now we got three cases:
If cardinal of any of them is 0, our answer will surely take only numbers from one set. So there is no need to make the choice now, we will make it later and apply same algorithm for (j-1)-th bit. So we call f(S,j-1).
|S1| = 1 and the rest are in S0. Now the answer could be in S0 or the x in S1 and some number in S0. Let's brute-force through all y in S0, relax the answer with (x&y)*(x|y), then call f(S0,j-1).
|S1| > 1. This needs some observation. It's better from now on to choose only numbers from S1. Why? Because choosing 2 numbers with j-th bit 1 would make the answer have the 2*j-th bit 1 at least, which is the best and cannot be done with other 2 numbers in S. So we will make the choice later and call f(S1, j-1).
You can see that we actually relax the answer in step2, but it's not necessarily to go there for some input(ex. all numbers are equal). You got to be careful. Also 2nd step is done at most log times. When I say we make the choice later, it's something like f(S,j) = F(S',j-1).
For a better intuition of why it works, it's like excluding at every step some numbers we surely know it won't give the best answer,if that's the case. The key was to make the observation at 3rd step.
For the third case, where |S1| 1, there is a mistake in the proof.
Choosing a number from |S1| and a number from |S0| may result in a number with 2 * j - th bit equal to 1. E.g. 111, 011 (Read as binary numbers of course).
The following is a correct proof:
Let the current bit is j.
We want to disprove that there exists some x, z, y, such that x S1, z S1, y S0, and f(x, y) f(x, z).
Well, it's obvious that for an arbitrary x, f(x, y) is maximized when y = 2j - 1. And also f(x, z) is minimized when z = 2j. Hence, it's sufficient to just disprove this case.
Let a be x - 2j. Then:
Nevermind (got it finally).