Hello CodeForces Community!

I am glad to share that HackerRank's World Codesprint #4 is scheduled on 25-June-2016 at 9am PST / 4pm UTC / 9:30pm IST UTC. Contest duration is 24 hours.

You can win up to $2000 Amazon gift cards/bitcoins, medals and t-shirts. [Note: Winners from US and India will receive Amazon Gift Cards. Winners from other countries will receive equivalent USD amount in bitcoins.]

The contest is sponsored by Monsanto, Indeed Prime, Memiah, Argos, Level(3), Rocketfuel and Cloud Academy

The problems were prepared by Zemen, svanidz1, Fedoriaka, sgtlaugh, nabila_ahmed, and myself. Thanks to niyaznigmatul, ikbal, dans, adamant and muratt for testing and pre-solving the challenges. Except couple of problems, the statements are really short :).

The contest will be rated. If two person gets the same score, the person who reached the score first will be ranked higher.

Score of the problems are: **15-25-50-60-80-90-100**

Update: The contest has ended. Congratulation to the winners:

Happy Coding!

I gave up waiting for a HR t-shirt long time ago, but did anyone actually receive a cash prize for the previous World Codesprints?

Many people did receive them, but unfortunately some didn't, if you are one of them, please inbox me, I will try to get it resolved.

For May world code sprint t-shirts, please wait 2-3 more weeks.

I have. Also a friend received two (out of two won), one of which was large. They are much faster about it than other, theoretically more well-respected organizations (think Facebook)... And the BitCoin prizes make it much easier to process the payments.

Agreed, BTC is really good. You get sent $x and after a financial happening, it's suddenly $10x :D

I recieved cash prizes for May and April codesprints, but no T-shirts for both, and for January codesprint too.

I have received money from the last Codesprint. If you haven't yet, you should email them. They are very kind if you ask nicely :)

Well, everybody talks about money, I will too :)

I didn't receive money and t-shirt from any contest, but I think the main reason is that I haven't won it :D

Can you announce tiebreaking rules in advance?

Read the post carefully: "The contest will be rated. If two person gets the same score, the person who reached the score first will be ranked higher."

Also check this https://www.hackerrank.com/june-world-codesprint#rules

Damn. It clashes with SRM. :( But I am not going to get under 100 anyway. ;)

When can we hope to see a team codesprint like last year?

Auto comment: topic has been updated by Shafaet (previous revision, new revision, compare).I wish there was one more problem :)

Still only 15 people got full score so far!

I hope you liked the problemset :).

By the way, when are you going to complete the change to Elo rating?

I don't know the exact time or date but as far as I know it will be live soon.

How to solve Vertical Path?

Min-cost-max-flow.

Let's solve similar problem for an array. We have some

`[l[j], r[j]]`

and are able to subtract 1 from this segments with cost`c[j]`

. Our task is to make all`d[i]`

zero (after adding some`[i, i+1]`

with cost 0). Consider the following array`D = d[0], d[1]-d[0], ..., d[n-1]-d[n-2], 0-d[n-1]`

. Now subtraction from segment`[l, r]`

is in fact moving one unit from`D[l]`

to`D[r+1]`

.Then add input paths with

`cap=INF/cost=-c[j]`

, from source to`i | D[i] > 0`

with`cap=D[i]/cost=0`

, from`i | D[i]<0`

to sink with`cap=-D[i]/cost=0`

.For tree

`D`

will consists of`d[i] - sum_{j son i} d[j]`

.P.S. latex doesn't work for some reason

Thanks!

I used LP but I have no idea if it's actually correct... Maximize subject to for all edges

jand 0 ≤x_{i}≤ 1 for all pathsi.Oh, me too. I figured that if there is a polytime algorithm (especially

O(nm) or so), then maybe this polytope should be integral :) But I only got 35 points. Do you have a fast LP solver?And congrats for the perfect 100th place :P

Thanks, I used the first simplex implementation from this editorial.

There're lots of polyhedrons pictures on the internet like,

But you used this,

So I thought icosahedron have 12 faces and screwed up when copying "Polyhedron Coloring" from internet.

I don't know it's on purpose but,

Yeah, same :) I guess most people used this link

Nah, it was expected that solving challenges is more interesting for participants than googling them.

Can someone discuss his approach to solve this problem: https://www.hackerrank.com/contests/june-world-codesprint/challenges/johnland Editorial is kinda hard to understand . Any help would be appreciated. Thanks in advance

The most important observation is that only the edges in the minimum spanning tree of the graph will be used in any shortest path, because all weights are 2^k and distinct.

The remaining task is to calculate the sum of all paths in a tree which is much easier than in a general graph. This is a nice standard problem.

In addition, some extra code is needed for handling 2^k numbers when k is large.

I didnt get why " the edges in the minimum spanning tree of the graph will be used in any shortest path, because all weights are 2^k and distinct." any intuitive idea thanks for replying

2

^{i}> 2^{i - 1}+ 2^{i - 2}+ ...2^{0}So instead of taking an edge of weight 2

^{i}, if you take every other edge with weight less than this edge , you would have shorter length.So you will only consider the edges which are a part of MST.

Thank you

Vertical Paths problem can be solved in O(N + M^2 log M) if we compress the graph. If an edge in the tree doesn't belong to any path, we can delete it. If we have a simple path of edges without any branching — we can replace it with one edge with capacity equal to minimum capacity of deleted edges. There are only 2 M nodes (path endpoints) that we shouldn't touch. I'm sure it can be proven that after compression the tree will have less than 4 M nodes. After this, my solution is similar to the editorial, except I didn't use any potentials in Dijkstra, because there won't be any negative cycles in the process.

AFAIK, Dijkstra without potentials doesn't work in polynomial time on good tests with negative edges (of course without negative cycles). Correct me if I'm wrong.

Edit: This is regarding Gridland Provinces problem.

Any idea why my code (below) times out. There are submissions which look very similar to mine has got full score.

Submission with full score: https://codepair.hackerrank.com/paper/Dveanrrb?b=eyJyb2xlIjoiY2FuZGlkYXRlIiwibmFtZSI6InNyaWtrYmhhdCIsImVtYWlsIjoic3Jpa2tiaGF0QG91dGxvb2suY29tIn0%3D

my codeprobably because of set. Change it to vector and you should not be TLE.

That turned out to be the case. Isn't sorting the vector at the end and adding every element into the set have same complexity of O(N^2*logN^2)?

Yes, but set is much slower.

Has anybody received Amazon gift card/bitcoins for this contest? I received for the previous (May World CodeSprint) and for the next (World CodeSprint 5), but not for this one. I've written to support, but nobody answered me.