Hi everyone,
I'm excited to invite you to participate in 101 Hack 47. The contest starts at 1500 UTC, March 21. Note the unusual timing!
All problems have been prepared by me. You might have seen some problems and contests set by me on various platforms. This is my third round on HackerRank, after 101 Hack 26 and 101 Hack 40. Also, here is an old collection of my problems.
There will be five tasks and two hours for you to solve them. Contest will be rated and top-10 contestants on the leaderboard will receive amazing HackerRank T-shirts!
I'd like to thank kevinsogo for testing the problems and his contribution towards fixing problem statements and editorials. It's always a pleasant experience to work with him.
I have tried to create a balanced and interesting problem set. I suggest you read all problems, since there are subtasks and partial scoring. Problems are very much on the easier side compared to previous contests and I bet a lot of full scores(like a lot, seriously!).
Editorials(written by me) will be published right after the contest.
Update 1: Scoring will be 15 — 30 — 45 — 65 — 80. Update 2: Contest has ended. Congratulations to top 10 for getting full scores. Top 10 are:
- I_love_Tanya_Romanova
- dreamoon_love_AA
- arsijo
- KrK
- kraskevich
- uwi
- LHiC
- MadNick
- HellKitsune
- black_horse2014
Update 3: Editorials are up.
Auto comment: topic has been updated by darkshadows (previous revision, new revision, compare).
Bump: Begins in 2 hours!
Why it gives me a "Privacy Error" ?
EDIT : Hackerrank opened on firefox and doesn't want to open on chrome.
Try clearing your cookies and cache.
How could you come up with such nice p4 & p5, and such a terrible p3? It is more fit to be in some physics textbook to make schoolers suffer.
Luckily we aren't schoolers with pen&paper and we can write a code to solve a problem :) Applying ternary search allows you to avoid solving any equations and inequalities.
Problem 3 can be cheesed by doing ternary search the point that the opponent should catch the ball.
Just iterate over 10000 points :)
Sadly I first coded this solution, got WA on all tests because I thought ball is moving from p1 to p2, not from p2 to p1, assumed "oh, so tests must be good there" and wrote a ternary search.
In fact checking 100 points is already enough to get AC :D
Damn, I looked at those submissions of yours and felt so proud! Thank you for bursting my bubble.
Don't get upset, some of the other problems were pretty nice :)
Yes, I agree, it wasn't something ingenious. But, I loved how people didn't realize initially that you don't have to compare the time ball takes and the time player takes to reach the hoop.
You can refer to other approaches in editorial, if you don't like pen/paper approaches. :)
@darkshadows:Is the second approach flawed? How could inequality remain the same on squaring(what if time taken is less than 1)
Is stack for "Summing in a Tree" small?
Presumably yes. I've lost 1 hour trying to find a bug in my solution until I wrote an iterative dfs after the contest.
So sad to see this :(
And with that binary scoring -_-
I too was getting exactly the same cases passed.Was it because of stack limit?
Yes most likely due to that. I compared output for one of the cases and it matched.
Well I don't think so. I passed from first try with a recursive DFS.
If you are interested here is the idea:
My solution was just a couple of binary liftings + a fenwick tree — it is
. I think just posting the code will be enough for you to understand it.
Link: https://ideone.com/D5NDoT
It should be enough for 2 DFS.
I didn't have any trouble with recursive DFS.
If you are interested, I used Mo algorithm to solve this problem.
How did you solve it using Mo?
First, renumber all the vertices by it's visiting order, and create a new array arr with arri is the level of the vertex with visiting order i. We will notice now that a subtree is actually a continuous segment on arr. So we will have something like "Given n queries, each queries require us to find the number x that there's at least ax elements in segment [l, r] equal to x". This can be solved by Mo algorithm.
Can't this be solved by a simple dfs, with the HLD idea? When we are at node v, we want the information for all nodes in subtree(v) already computed, and then we know the contribution of this node to the final answer. This is O(n2) if implemented naively, but I think it can be made O(n log n) by doing something similar to HLD. Did anyone do this approach?
I did. What you described is the DSU on tree technique, I guess, i.e. merge smaller subtrees into the larger one. Time complexity is O(n*logn).
Code
Thanks!
I did some testing and it seems, it's in hundreds of MBs. Not sure about exact value. I'll ask admins.
Edit: Admins say it's 32 MB.
Why set it so low though? In comparison, the memory limit is 512 MB.
Weird thing is happening!
If I create the adjacency list considering undirected edges i.e
adj[u].push_back(v);adj[v].push_back(u);Segmentation fault occurs on above mentioned 3 cases most likely due to Stack overflow. But if i change the adjacency list to directed i.e just
adj[u].push_back(v);The code gets accepted.
Why does this happen ?
I think it's because less parameters in recursion will decrease the usage of stack memory. So your second code needs less memory in stack and still fit in stack memory.
My code also gets segmentation fault because I used some local variables. And after I change these local variables to global variables then gets accepted.
Task were great !
Whether someone has the same problem with understanding texts ? I am not sure that I understand third task correctly even after contest.
Same. But still problems were nice.
I was coding p3 in the last minutes, when I am nearly done the page suddenly refresh and wipe out all my work. Nice intercept hackerrank.