By darkshadows, history, 13 months ago, ,

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:

Update 3: Editorials are up.

•
• +95
•

 » 13 months ago, # |   0 Auto comment: topic has been updated by darkshadows (previous revision, new revision, compare).
 » 13 months ago, # |   +11 Bump: Begins in 2 hours!
 » 13 months ago, # | ← Rev. 3 →   +1 Why it gives me a "Privacy Error" ?EDIT : Hackerrank opened on firefox and doesn't want to open on chrome.
•  » » 13 months ago, # ^ |   0 Try clearing your cookies and cache.
 » 13 months ago, # |   +52 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.
•  » » 13 months ago, # ^ |   +32 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.
•  » » 13 months ago, # ^ |   0 Problem 3 can be cheesed by doing ternary search the point that the opponent should catch the ball.
•  » » 13 months ago, # ^ |   +23 Just iterate over 10000 points :)
•  » » » 13 months ago, # ^ |   +10 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
•  » » » » 13 months ago, # ^ |   0 Damn, I looked at those submissions of yours and felt so proud! Thank you for bursting my bubble.
•  » » » » » 13 months ago, # ^ |   +7 Don't get upset, some of the other problems were pretty nice :)
•  » » 13 months ago, # ^ |   0 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. :)
•  » » » 13 months ago, # ^ |   0 @darkshadows:Is the second approach flawed? How could inequality remain the same on squaring(what if time taken is less than 1)
 » 13 months ago, # |   0 Is stack for "Summing in a Tree" small?
•  » » 13 months ago, # ^ |   0 Presumably yes. I've lost 1 hour trying to find a bug in my solution until I wrote an iterative dfs after the contest.
•  » » 13 months ago, # ^ |   +2 So sad to see this :( And with that binary scoring -_-
•  » » » 13 months ago, # ^ |   +1 I too was getting exactly the same cases passed.Was it because of stack limit?
•  » » » » 13 months ago, # ^ |   0 Yes most likely due to that. I compared output for one of the cases and it matched.
•  » » 13 months ago, # ^ |   0 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.
•  » » 13 months ago, # ^ |   0 It should be enough for 2 DFS.
•  » » 13 months ago, # ^ |   0 I didn't have any trouble with recursive DFS. If you are interested, I used Mo algorithm to solve this problem.
•  » » » 13 months ago, # ^ |   0 How did you solve it using Mo?
•  » » » » 13 months ago, # ^ |   0 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.
•  » » » » » 13 months ago, # ^ |   0 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?
•  » » » » » » 13 months ago, # ^ | ← Rev. 3 →   +5 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
•  » » » » » » » 13 months ago, # ^ |   0 Thanks!
•  » » 13 months ago, # ^ | ← Rev. 2 →   +5 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.
•  » » » 13 months ago, # ^ |   +10 Why set it so low though? In comparison, the memory limit is 512 MB.
•  » » 13 months ago, # ^ |   0 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 ? Code -Segfault"#include using namespace std; const int N=500005; int cd[N],sz[N],heav[N]; int depth[N],c[N],curr; long long ans; bool big[N]; vector adj[N]; void getsz(int s,int p){ sz[s]=1; int ma=0; for(auto it : adj[s]){ if(it!=p){ depth[it]=depth[s]+1; getsz(it,s); sz[s]+=sz[it]; if(sz[it]>ma){ ma=sz[it]; heav[s]=it; } } } } void add(int s,int p){ c[depth[s]]++; if(c[depth[s]]==cd[depth[s]]) curr++; for(auto it :adj[s]){ if(it!=p && !big[it]) add(it,s); } } void rem(int s,int p){ c[depth[s]]--; if(c[depth[s]]==cd[depth[s]]-1) curr--; for(auto it :adj[s]){ if(it!=p && !big[it]) rem(it,s); } } void dfs(int s,int p,bool isbig){ for(auto it : adj[s]){ if(it!=p && it!=heav[s]){ dfs(it,s,0); } } if(heav[s]!=-1){ dfs(heav[s],s,1); big[heav[s]]=1; } add(s,p); if(heav[s]!=-1) big[heav[s]]=0; ans+=curr; if(!isbig) rem(s,p); } int main(){ int n,i,h; scanf("%d%d",&n,&h); memset(heav,-1,sizeof(heav)); for(i=1;i using namespace std; const int N=500005; int cd[N],sz[N],heav[N]; int depth[N],c[N],curr; long long ans; bool big[N]; vector adj[N]; void getsz(int s){ sz[s]=1; int ma=0; for(auto it : adj[s]){ depth[it]=depth[s]+1; getsz(it); sz[s]+=sz[it]; if(sz[it]>ma){ ma=sz[it]; heav[s]=it; } } } void add(int s){ c[depth[s]]++; if(c[depth[s]]==cd[depth[s]]) curr++; for(auto it :adj[s]){ if(!big[it]) add(it); } } void rem(int s){ c[depth[s]]--; if(c[depth[s]]==cd[depth[s]]-1) curr--; for(auto it :adj[s]){ if(!big[it]) rem(it); } } void dfs(int s,bool isbig){ for(auto it : adj[s]){ if(it!=heav[s]){ dfs(it,0); } } if(heav[s]!=-1){ dfs(heav[s],1); big[heav[s]]=1; } add(s); if(heav[s]!=-1) big[heav[s]]=0; ans+=curr; if(!isbig) rem(s); } int main(){ int n,i,h; scanf("%d%d",&n,&h); memset(heav,-1,sizeof(heav)); for(i=1;i
•  » » » 13 months ago, # ^ |   +15 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.
 » 13 months ago, # |   +5 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.
•  » » 13 months ago, # ^ |   0 Same. But still problems were nice.
 » 13 months ago, # |   +5 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.