Hello, Codeforces!
I want to invite all of you to participate in HourRank 14.
There will be four problems to solve in ONE hour. I am the author of all the problems in this contest and I hope you will enjoy solving them. Also, I would like to say thanks to danilka.pro and Shafaet for helping with contest preparation.
The top 10 will get awesome HackerRank t-shirts.
Editorials will be available at the end as usual.
Good Luck and Have Fun! :)
Score distribution is the following: 25-40-60-80
UPD: Unfortunately, contest will be unrated! :(
I am sorry for everything bad happened during the contest.
Just to clarify on tiebreaker, if two person has the same score, the one who reached the score first will win.
There's some problem with the website. It refreshes every seconds.
The editor is refreshing every minute. Not able to submit the code.
there seems to be a bug in the UI , in this problem , i submitted a different code about 3 — 4 times but then for some reason all of them are the same code which is identical to my second submission and i was able to submit a proper code only after the contest ended. did anyone else experience this as well?
I had the same problem, the code in UI kept changing to previous code.
you should make this round unrated, failed to submit my code in the last 15 minutes. totally disgusting
I couldn't submit only in the last 5 minutes, the code editor was getting refreshed.
my code editor refreshed just from the beginning of the contest, but there was a slight little gap before each refresh. but in the end the code editor started getting refreshed continuously. missed 60 points simply because of this shit.
Does C have something to do with meet in the middle?(Yes, it has, I cleared my idea now)PS: There were also some problems, I couldn't submit in the end because of the frequent refreshing :(
I did dp with bitmasks and got AC.
Bitmask without meet in the middle? What's the complexity?
2d·n·k, where k is the number of operations to or two bitmasks of size 90
Is there any alternate approach to the third problem other than meet in the middle?
Last 2-3 minutes website did not work properly. I could not copy paste my local code in submit form due to permanent autoreloading page. It was critical, because I was late with better solution on 1 minute. After the contest ended all is working properly.
We made the contest unrated due to this problem. Sorry about that.
In the last problem, if you always output "3", you'll get 18.46 score.
I wanted to do it in the last minute, but the web interface didn't allow: it was reloading page just after taking a focus.
And how come you know about it when you haven't submitted one?
I've tried it after contest.
Tried it after contest and you were trying to submit it in the last minute of contest. And still you are getting up votes.
Don't understand, what you are trying to say.
I've supposed, that if solution will always output answer for the first sample, then non-zero score will be received.
Tried to do it in the last minute — bad luck, web interface glitches.
Tried to do it after contest, when the interface became ok again — 18.46 points.
If you rub your eyes open and open my submittions from the leaderboard, you'll see "Did Not Attempt" for the last problem.
Have you any other questions?
For this case in problem D(True Square in a Binary Matrix):
We can exchange the top left 1*2 rectangle with top right 1*2 rectangle and get a 2*2 square. But the answer of author's code is 1.
Nice catch! Do you have ideas how to solve the problem including such cases?
No, I cannot solve it for n=300. I feel this problem is quite hard.
Me, when Red coder says it's quite hard
Wow that's tricky. Is the problem solvable then ?
And for such test:
It returns 3 instead of 4. Their solution isn't just wrong, it is really dumb.
I feel the answer to your test case should be 3. Can you explain how 4 can be achieved?
Swap rectangle ((1,1),(2,2)) with ((3,3),(4,4)). You will get full 4x4 rectangle ((0,0),(3,3)).
how to solve B ??
Editorial is available now
i didn't get the part how the answer is N — number of cycles can u plz explain ??
Let's draw a directed graph, whose vertex set is the set of elements and there's an edge from each B[i] to A[i], for i=1..N, where B is sorted array A. When all elements are distinct, this graph is a collection of disjoint cycles — it's just the cyclic decomposition of permutation of elements. Each swap either splits a cycle into two (when swapped elements are part of the same cycle), or joins two cycles, and so it either increments or decrements number of cycles. Array becomes sorted when there are n cycles, so the lowest bound on number of swaps is n - c, where c is the initial number of cycles.
Make two extra copies of the original array, lets say b[] and c[]. map<int,int> store elements to their index
sort b in increasing and c in decreasing order Now for array b and a check for minimum swaps by iterating from 0 to n-1 and change the index stored in map when you swap. Do same for c and a. The answer is minimum of both cases.
Here is my code
As contest is unrated now, will medals be still given ?
I was hoping for my first Gold medal :D
No, sorry.
and what about tshirts?
any feedback?