### Shafaet's blog

By Shafaet, history, 5 years ago,

Hello CodeForces Community!

I am glad to share that HackerRank's WorldCup (CodeSprint on Algorithmic Programming Challenges) starts 11-September-2015 at 16:00 UTC.

Go ahead and register now at www.hackerrank.com/worldcup to show off your coding chops, and win amazing prizes like Video chat with HackerRank founders or Ahmed Aly, DJI Phantom Vision Quadcopter, Phantom 2 Vision+ Quadcopter, Apple Sport Watch, HackerRank hoodies and t-shirts! All participants who completely solve one challenge (that’s just 1 out of 6 questions!) will get \$100 of AWS credits. Prizes are restricted to University Students Only.

Also, you'll get an opportunity to connect for a career opportunity with WorldCup contest sponsors — Alarm, Asana, Capital One, Fidessa, Ooyala, Shift, Sightline Systems, Wipro Digital, Verizon, Zendesk, Zenefits.

Contest scoring is 25 — 40 — 50 — 75 — 100 — 120. Tiebreaker is person to reach the score.

I invite everyone from experts to beginners to participate and solve challenges. This is going to be a really awesome contest :)

This is a multi-stage team contest. Top 50%* of teams on the Leaderboard qualify to Semi Finals. *All teams whose final score is the same as the team in the 50% rank qualify (including teams ranked lower because of time penalty tiebreaker).

GL&HF

• +51

 » 5 years ago, # |   +3 Auto comment: topic has been updated by Shafaet (previous revision, new revision, compare).
 » 5 years ago, # |   +3 Auto comment: topic has been updated by Shafaet (previous revision, new revision, compare).
 » 5 years ago, # |   +3 Auto comment: topic has been updated by Shafaet (previous revision, new revision, compare).
 » 5 years ago, # |   0 1) Is contest rated?2) Should team use only 1 PC?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +13 1) No.2) As it can't be enforced, there is no limit on number of PC.
 » 5 years ago, # |   +12 I have a question, which round prizes will be given, semi-finals or qualifiers?
•  » » 5 years ago, # ^ |   +3 Finals.
•  » » » 5 years ago, # ^ |   +24 but finals has fewer than 250 participants
•  » » » 5 years ago, # ^ |   +32 on the basis of which rounds will the T-shirts and hoodies be given?
•  » » » 5 years ago, # ^ |   +36 I really don't understand how the prize system works. The contest page does not contain any comprehensible information on that. Furthermore, the information it contains is contradictory. How can there be prizes for top 250 teams if only those qualified for finals are eligible for prizes? Please elaborate on that.
 » 5 years ago, # |   +8 Can graduated participants receive top prizes?
•  » » 5 years ago, # ^ |   0 Sorry, prizes are only for university students.
•  » » » 5 years ago, # ^ |   +42 Can high school students get prize?
•  » » » » 5 years ago, # ^ |   -29 cout << ( "University" == "High School" ? "YES" : "NO" );
 » 5 years ago, # |   0 when will it start .i mean is it a 2 day contest?
•  » » 5 years ago, # ^ |   +3 Yes.
•  » » » 5 years ago, # ^ |   0 So, a contestant has complete 48 hours to solve 6 tasks ?
•  » » » » 5 years ago, # ^ |   0 Yes, its the qualification round, so we decided to give long time.
 » 5 years ago, # |   0 Auto comment: topic has been updated by Shafaet (previous revision, new revision, compare).
 » 5 years ago, # |   -8 Auto comment: topic has been updated by Shafaet (previous revision, new revision, compare).
 » 5 years ago, # |   +14 Constant optimization requirement in Ikbal's Arrays is too damn high.
•  » » 5 years ago, # ^ |   +5 I don't know what you talking about. My first submit got AC with max running time 1.1 sec.What kind of solution requires so much optimizations?http://pastie.org/private/ugykrmgzr5nefig1z5ohca
•  » » » 5 years ago, # ^ |   +8 I tried with dynamic segment trees. My submission which got AC was getting TLE when I tried submitting it again.
 » 5 years ago, # |   +45 Here's to hoping the next rounds' hard problem will not be "implement segment tree (or some other data structure) for the 597th time".
•  » » 5 years ago, # ^ |   -8 The semifinal will contain better problems for sure :).
 » 5 years ago, # |   +13 6th problem had too strict time limit , I had to do stupid optimizations like fast input , fast output , and some other shits to get AC.Also hackerrank is strange , it didnt let me create an array of size 2 * 10 ^ 7 but it let me create 10 arrays of size 10 ^ 7
•  » » 5 years ago, # ^ |   -16 It didn't let me create an array of size 1<<26 but allowed an array of size 107.
•  » » » 5 years ago, # ^ |   +5 1 << 26 = 67,108,864 = 6.7 * 10 ^ 7
 » 5 years ago, # |   +1 My submissions still haven't been processed (actually its just processing and processing). Is there a problem with the grader?
•  » » 5 years ago, # ^ |   +1 same here
 » 5 years ago, # | ← Rev. 2 →   0 Problem with Inversions (2nd last problem, Semi-final):Our team managed to score 109 points out of 120, with correct answer on all except 2 testcases. Can someone who used segment tree / fenwick tree in their solution please explain their algorithm briefly?
•  » » 5 years ago, # ^ |   +5 Which problem? The one with the inversions?
•  » » » 5 years ago, # ^ |   0 Yes, that one — Lauren and Inversions.
•  » » » » 5 years ago, # ^ | ← Rev. 5 →   0 Well, we didn't solve it using fenwick tree.We did the following while there was time left (for 1950 ms or so): Look at the i for which i - a[i] is largest (and i hasn't been chosen before). Take this as the right index to swap. We can find the best left index to swap it with in . If this is better than the current best, save it.We didn't expect this to pass, but apparently it did :) Also, we have no argument why this would work guaranteed; but the heuristic makes sense.[My teammate solved it, so what I posted before was not what we actually did.]
•  » » » » » 5 years ago, # ^ |   0 For fixing the right index to swap, we found out the largest number which had minimum inversions on its left side, and found the best left index to swap with in n*logn . Turns out that ours wasn't that good a heuristic :) Thanks!
•  » » 5 years ago, # ^ | ← Rev. 2 →   +27 Our solution passes all test cases and works 0,39sec (and what is more important, we can prove it).First, lets look at this chain (we will call it "left chain"): a sequence, which starts with a[1] and every next term is the closest to the right that has larger value (than the previous term). For example, for permutation 2, 1, 4, 5, 3, 6; their "left chain" is [2], 1, [4], [5], 3, [6].Second, lets look at the "right chain". It's like the "left chain", but starts at a[n] and goes left (every next term is closest to the left, that has smaller value). So, for permutation 2, 1, 4, 5, 3, 6; it is 2, [1], 4, 5, [3], [6].Nice! Now, lets notice, that the best swap pair should have its left number in the "left chain" (otherwise, we can improve that swap pair). Similarly, the best swap pair should contain its right number in the "right chain".Good! Now we can move on. Lets look at some number, which is not term of the left nor the right chain. This number has some range of terms in the left chain, which are "to the left and bigger" and some range of terms in the right chain, which are "to the right and smaller". So, this number makes "+1" for some rectangle on the plane (indexes of the left chain, indexes of the right chain).So now, our problem is this: we have some rectangles, find how many rectangles has non-zero intersection. This is a classic problem, which can be easily solved with a segment tree.The complexity of the solution is O(n log n).
•  » » » 5 years ago, # ^ |   0 "this number makes "+1" for some rectangle on the plane" Can you please explain how is a rectangle defined here exactly?
•  » » » » 5 years ago, # ^ |   0 Imagine a plane, where there are terms of the left chain as one axis, and terms of the right chain as the other axis. On the intersection you have number of inversions, which will be produced by this pair, if we swap them.Then for a fixed number which is nor a term of the left chain nor a term of the right chain, there is a fixed range in OK-terms in the left chain and a range in the right chain. range x range = rectangle =)
 » 5 years ago, # |   +3 How to solve problem World Cup City?We've writed this solution: if K is less than sqrt(N), then just interate over all possible pairs of indexes and calculate LCA in O(1). So, this case complexity is O(K2). Otherwise, if K is bigger than O(sqrt(N)), than just run standart dynamic programming solution in O(n).I believe, that the complexity of this algo is O(Nsqrt(N)). But, our solution works 1.95sec (with TL 2sec) and barely passes TL (even after some optimizations). Is there some faster solution?
•  » » 5 years ago, # ^ |   +8 We did centroid decomposition with O(Nlg(N) + Mlg(N)2)) complexity and same TL problems.
•  » » » 5 years ago, # ^ | ← Rev. 4 →   0 What kind of centroid dec. did you write? My centroid dec. O((n+k)logn) solution works with max 0.6 sec. K is sum of set sizes.Here is the code : Link
•  » » 5 years ago, # ^ |   +3 We had the same solution in O(Nsqrt(N)) but didn't manage to pass TL on 5 test cases, with all optimisations :/Then we wrote solution with central decomposition — you can fix one central node, count all pairs of residents which should go through the fixed node (you can do that in O(Rlog(R)) where R is the total number of residents), and then delete fixed node and do recursivly the same thing for it's subtrees. So the total complexity is O(log(N) * (Rlog(R) + N)) and it works in 1.5s.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +71 We had O((sumk + n) log (n)) solution.For each query we sort all cities by tin, find all lca of neigbours and then create "mini-tree" of this lca's and vertices. it has <= 2k vertices maximum.Now what you need is to solve in O(TreeSzie). it may be done by calculating for each vertex number of elements in its subtree.
•  » » » 5 years ago, # ^ |   0 thanks, nice solution!
•  » » 5 years ago, # ^ | ← Rev. 3 →   0 We did a method similar to finding LCA via HLD.Initially, when a query comes we put all nodes in a priority_queue. Now at each step whichever node has the deepest chain head is shifted up to correct position and corresponding number is added to the answer.By correct position I mean the node is shifted up to the first node above it in its chain, if it exists, or to the parent of the chain head. If another node exists above it in its chain then after moving the node up I just merge them and treat the entire thing as a single node in the future.And by corresponding number I mean if a bunch of x nodes were shifted up by distance y, then I add x.(k - x).y to my answer, where k is the number of total nodes.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +5 In case anyone is interested, here is our code, using the same approach as Alex Dmitriev. In retrospect, we overcomplicated the actual calculation, since we first calculate , and then subtracted the paths from the LCAs to the root.link to code It runs in about 1 second.
•  » » 5 years ago, # ^ |   0 What is the "standard dynamic programming solution" that you used for K > O(sqrt(N)) ? Can you provide some link/explanation for that approach?
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 for each edge calculate how many times we pass from this edge. if edge goes from u to v, it will be cnt[v] * (m — cnt[v]) where m — count of residents. cnt[v] — count of residents in subtree
 » 5 years ago, # |   +10 I decided to solve "World Cup City" after contest, but when I try to submit, it shows this message,"Individual submissions are not allowed in this contest. Please create a team for this contest in order to participate."But we have a team, and I can't submit my solution. Is it a bug or you decide to don't accept the practice?
•  » » 5 years ago, # ^ |   +6 Once Finals will be over contest will be open for individual submissions.
•  » » » 5 years ago, # ^ |   0 Are you sure about it?
•  » » » » 5 years ago, # ^ |   0 Yup I have the practice contest ready and waiting for approval, once done It'll be launched in 2 days.
•  » » » » » 5 years ago, # ^ |   +8 Thanks!
 » 5 years ago, # |   +98 So, regarding finals:Initially you don't say anything(by saying I mean notif.) about partial scoring or additional test cases. But you are actually being shown partial scoring in prelim. tests, so you think obviously there is partial scoring. Halfway into contest you release a notif. about no partial scoring after additional testing. Then you release a notif. in last 45 minutes about partial scoring being present. Certainly not the best way to go about it. It only makes sense to decide things before contest and not the halfway around or not after the contest(based on how many people have solved what).
•  » » 5 years ago, # ^ |   +68 Yes this bugged me as well. Whether or not partial scoring is available has a huge influence on your strategy. The decision afterwards to only do binary scoring for the third problem was very arbitrary as well (I hated it especially because I was two testcases away from a full score), it says "after considering very few AC only challenge bear and safe is binary.", even though at the time of writing it hadd less full-score submissions than the second problem, and more than the fourth..
•  » » 5 years ago, # ^ |   +45 It's very difficult to understand the decision of the organizers. The problems were great, but they decided to spoil the whole round by changing the scoring system two times in the middle of the round. Now the final round was more like a joke.
 » 5 years ago, # |   +16 How to solve Alice and Bob (and string)? We've got AC, but our solution is ~500 lines of code, with suffix tree, suffix array and some additional magic. Is there simplier solution?
•  » » 5 years ago, # ^ |   0 Our solution is suffix automaton + suffix array + binsearch on answer.adamant has said that our solution is overkill :)
•  » » 5 years ago, # ^ |   +8 Build suffix automaton on reversed string and calculate winning states. On the next step you have to deal with lexicographical order. There is a fact that suffix link tree in suffix automaton is a suffix tree to the reversed string. Given this, you can calculate winning states and find k-th winning string using suffix link tree. Also, this solution is described in editorial.
 » 5 years ago, # | ← Rev. 3 →   +10 Regarding finals :P
 » 5 years ago, # | ← Rev. 2 →   +34 In qualifications there wasn't a single problem with with binary scoring.In semifinals there wasn't a single problem with with binary scoring.5 hours into the contest, not single sing of binary scoring. No notifications, nothing.You were showing partial scoring during the contest.And then "... Binary scoring is only for challenge bear and safe."Thanks a lot.
 » 5 years ago, # |   +47 When are we suppose to receive the email regarding the prizes ?
•  » » 5 years ago, # ^ |   +30 Has someone received an email?
•  » » 5 years ago, # ^ |   +31 Sorry to be that guy, but is there any news regarding the prizes ?
•  » » » 5 years ago, # ^ |   0 I've sent the organizer(shafaet) a mail. I hope he replies.
•  » » » » 5 years ago, # ^ |   0 yes waiting for my first tshirt
•  » » » » » 5 years ago, # ^ |   0 Did you participate in Finals?
•  » » » » » » 5 years ago, # ^ |   0 nope
•  » » » » » » » 5 years ago, # ^ |   0 And did you recieve a mail?
•  » » » » » » » » 5 years ago, # ^ |   0 nope
•  » » » » 5 years ago, # ^ |   0 The process has started, winners can expect email with few days.
 » 5 years ago, # | ← Rev. 2 →   +33 Alright, I got an email, but when I clicked the "Claim your prize" (I am eligible for a hoodie) button I was redirected to my profile settings. Was that a silent hint that I'm supposed to make sure my address is filled in, or am I missing something?
•  » » 5 years ago, # ^ |   0 As I remember we will get another email which is not from Hackerrank.
•  » » 5 years ago, # ^ |   +5 Our team hasn't received an email.Is there someone else who hasn't received ?
•  » » » 5 years ago, # ^ |   0 You can expect an email in next few days, if you don't you can inbox me your user-name.
•  » » 5 years ago, # ^ |   0 I asked for support and they told me this:"I hope you have the access to click the “Claim Prizes” button that will take you to your profile page where you have to complete your shipping address within your profile and we will get your prizes delivered within 2 weeks."
 » 5 years ago, # |   +13 hi guys did anyone receive the t-shirt ?
•  » » 5 years ago, # ^ |   +5 I am still waiting for the T shirt! :(
•  » » 5 years ago, # ^ |   +14 Still no T-shirts here. Has anyone received one ?
•  » » 5 years ago, # ^ |   +5 Please wait a bit longer. Given high volume participation, your prize will be delivered to you a few weeks after you completed your address on HackerRank.com. Please make sure your address is 100% complete including Country and area code
•  » » » 5 years ago, # ^ |   0 It's been 4 months, I still haven't got the sweatshirt. Also, no mails have been replied to. PS- Both my teammates received theirs' a month ago and mine hasn't been dispatched and shows the same status since more than a month.
 » 5 years ago, # |   +24 I think T-shirts are "made in mars". Not reached yet :(. Sorry hackerrank.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +13 Has anyone received a T-shirt/Hoodie yet? :/
 » 5 years ago, # |   +17 did anyone receive the t-shirt ?
•  » » 5 years ago, # ^ |   +3 Nope
•  » » 5 years ago, # ^ |   +3 no.
•  » » » 5 years ago, # ^ |   +8 xD
•  » » » » 5 years ago, # ^ |   0 Did you received email? Did anybody received email about hoodies?
•  » » » » » 5 years ago, # ^ |   +6 People have started to receive the prizes though a bit slowly because of high volume. Please wait patiently for a little longer, all eligible people will surely get the prizes.
•  » » 5 years ago, # ^ |   -13 I received mine about 10 days ago.
•  » » » 5 years ago, # ^ |   0 :O
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +55 Winter has come, the hoodies haven't. UPD : The hoodie has finally arrived :)
•  » » » » » 5 years ago, # ^ |   +4 Can we see the photo?
•  » » » » » » 5 years ago, # ^ |   0 Yeah.
•  » » » » » » » 5 years ago, # ^ |   0 Wow, I like it, thanks!
 » 5 years ago, # |   +9 Still no t-shirt :( Has anyone else got their t-shirt?
•  » » 5 years ago, # ^ |   0 I received mine a week ago. Make sure all your address details including country are filled properly. You should receive a mail from DHL once you're done. They require a photo of your identity proof before they dispatch.
 » 5 years ago, # |   +16 No tshirts yet !!
 » 5 years ago, # |   +14 It's been 4 months, I still haven't got the sweatshirt. Also, no mails have been replied to. PS- Both my teammates received theirs' a month ago and mine hasn't been dispatched and shows the same status since more than a month.
•  » » 5 years ago, # ^ |   0 Same here!!!
•  » » 5 years ago, # ^ |   0 same here
 » 5 years ago, # |   0 I kind of feel sad: My brother got his T-shirt but I didn't :D