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

Auto comment: topic has been updated by Shafaet (previous revision, new revision, compare).Auto comment: topic has been updated by Shafaet (previous revision, new revision, compare).Auto comment: topic has been updated by Shafaet (previous revision, new revision, compare).1) Is contest rated?

2) Should team use only 1 PC?

1) No.

2) As it can't be enforced, there is no limit on number of PC.

I have a question, which round prizes will be given, semi-finals or qualifiers?

Finals.

but finals has fewer than 250 participants

on the basis of which rounds will the T-shirts and hoodies be given?

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.

Can graduated participants receive top prizes?

Sorry, prizes are only for university students.

Can high school students get prize?

cout << ( "University" == "High School" ? "YES" : "NO" );

when will it start .i mean is it a 2 day contest?

Yes.

So, a contestant has complete 48 hours to solve 6 tasks ?

Yes, its the qualification round, so we decided to give long time.

Auto comment: topic has been updated by Shafaet (previous revision, new revision, compare).Auto comment: topic has been updated by Shafaet (previous revision, new revision, compare).Constant optimization requirement in Ikbal's Arrays is too damn high.

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

I tried with dynamic segment trees. My submission which got AC was getting TLE when I tried submitting it again.

Here's to hoping the next rounds' hard problem will not be "implement segment tree (or some other data structure) for the 597th time".

The semifinal will contain better problems for sure :).

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

It didn't let me create an array of size

`1<<26`

but allowed an array of size 10^{7}.1 << 26 = 67,108,864 = 6.7 * 10 ^ 7

My submissions still haven't been processed (actually its just processing and processing). Is there a problem with the grader?

same here

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?

Which problem? The one with the inversions?

Yes, that one — Lauren and Inversions.

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

ifor whichi-a[i] is largest (andihasn'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.

Code: https://github.com/TimonKnigge/Competitive-Programming/blob/master/HackerRank/lauren-and-inversions.cpp

[My teammate solved it, so what I posted before was not what we actually did.]

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!

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).

Can you please explain how is a rectangle defined here exactly?

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 =)

How to solve problem World Cup City?

We've writed this solution: if

Kis less thansqrt(N), then just interate over all possible pairs of indexes and calculate LCA inO(1). So, this case complexity isO(K^{2}). Otherwise, ifKis bigger thanO(sqrt(N)), than just run standart dynamic programming solution inO(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?We did centroid decomposition with

O(Nlg(N) +Mlg(N)^{2})) complexity and same TL problems.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

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)) whereRis the total number of residents), and then delete fixed node and do recursivly the same thing for it's subtrees. So the total complexity isO(log(N) * (Rlog(R) +N)) and it works in 1.5s.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.

thanks, nice solution!

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).yto my answer, where k is the number of total nodes.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.

What is the "standard dynamic programming solution" that you used for K > O(sqrt(N)) ? Can you provide some link/explanation for that approach?

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

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?

Once Finals will be over contest will be open for individual submissions.

Are you sure about it?

Yup I have the practice contest ready and waiting for approval, once done It'll be launched in 2 days.

Thanks!

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).

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..

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.

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?

Our solution is suffix automaton + suffix array + binsearch on answer.

adamant has said that our solution is overkill :)

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.

Regarding finals :P

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.

When are we suppose to receive the email regarding the prizes ?

Has someone received an email?

Sorry to be that guy, but is there any news regarding the prizes ?

I've sent the organizer(shafaet) a mail. I hope he replies.

yes waiting for my first tshirt

Did you participate in Finals?

nope

And did you recieve a mail?

nope

The process has started, winners can expect email with few days.

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?

As I remember we will get another email which is not from Hackerrank.

Our team hasn't received an email.

Is there someone else who hasn't received ?

You can expect an email in next few days, if you don't you can inbox me your user-name.

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."hi guys did anyone receive the t-shirt ?

I am still waiting for the T shirt! :(

Still no T-shirts here. Has anyone received one ?

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

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.

`I think T-shirts are "made in mars". Not reached yet :(. Sorry hackerrank.`

Has anyone received a T-shirt/Hoodie yet? :/

did anyone receive the t-shirt ?

Nope

no.

xD

Did you received email? Did anybody received email about hoodies?

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.

I received mine about 10 days ago.

:O

Winter has come, the hoodies haven't.

UPD : The hoodie has finally arrived :)

Can we see the photo?

Yeah.

Wow, I like it, thanks!

Still no t-shirt :( Has anyone else got their t-shirt?

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.

No tshirts yet !!

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.

Same here!!!

same here

I kind of feel sad: My brother got his T-shirt but I didn't :D