### Shafaet's blog

By Shafaet, history, 4 years ago,

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: xyz111 shik Egor simonlindholm Stilwell Happy Coding! • +67  » 4 years ago, # | 0 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? •  » » 4 years ago, # ^ | ← Rev. 3 → +13 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. •  » » 4 years ago, # ^ | ← Rev. 2 → +8 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. •  » » » 4 years ago, # ^ | +32 Agreed, BTC is really good. You get sent$x and after a financial happening, it's suddenly \$10x :D
•  » » 4 years ago, # ^ |   +8 I recieved cash prizes for May and April codesprints, but no T-shirts for both, and for January codesprint too.
•  » » 4 years ago, # ^ |   0 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 :)
 » 4 years ago, # | ← Rev. 2 →   +78 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
 » 4 years ago, # |   +19 Can you announce tiebreaking rules in advance?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 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
•  » » » 4 years ago, # ^ |   +4 Damn. It clashes with SRM. :( But I am not going to get under 100 anyway. ;)
 » 4 years ago, # |   +3 When can we hope to see a team codesprint like last year?
 » 4 years ago, # |   0 Auto comment: topic has been updated by Shafaet (previous revision, new revision, compare).
 » 4 years ago, # |   +6 I wish there was one more problem :)
•  » » 4 years ago, # ^ |   +7 Still only 15 people got full score so far!I hope you liked the problemset :).
 » 4 years ago, # |   +12 By the way, when are you going to complete the change to Elo rating?
•  » » 4 years ago, # ^ |   +3 I don't know the exact time or date but as far as I know it will be live soon.
 » 4 years ago, # |   +8 How to solve Vertical Path?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +18 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
•  » » » 4 years ago, # ^ |   0 Thanks!
•  » » 4 years ago, # ^ |   +8 I used LP but I have no idea if it's actually correct... Maximize subject to for all edges j and 0 ≤ xi ≤ 1 for all paths i.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +10 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
•  » » » » 4 years ago, # ^ |   +10 Thanks, I used the first simplex implementation from this editorial.
 » 4 years ago, # | ← Rev. 2 →   +46 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,
•  » » 4 years ago, # ^ |   +21 Yeah, same :) I guess most people used this link
•  » » 4 years ago, # ^ |   +5 Nah, it was expected that solving challenges is more interesting for participants than googling them.
 » 4 years ago, # |   0 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
•  » » 4 years ago, # ^ |   +4 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.
•  » » » 4 years ago, # ^ |   0 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
•  » » » » 4 years ago, # ^ |   +16 2i > 2i - 1 + 2i - 2 + ...20 So instead of taking an edge of weight 2i , 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.
•  » » » » » 4 years ago, # ^ |   0 Thank you
 » 4 years ago, # |   +28 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.
•  » » 4 years ago, # ^ |   0 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.
 » 4 years ago, # | ← Rev. 2 →   0 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. my code#include using namespace std; //0 1->codeforces #define LL "%lld" #define fi first #define se second #define pb push_back #define mp make_pair #define PN printf("\n") #define MAXL 1500 typedef long long ll; typedef double dbl; typedef vector vi; typedef pair pi; typedef vector> vvb; int gi(){int a;scanf("%d",&a);return a;} ll gll(){ll a;scanf(LL,&a);return a;} char vs[2][605]; ll pw[2][MAXL]; struct mhash { static const int MODA=1000000007; static const int MODB=1000000009; static const int BA=31; static const int BB=29; static bool done; pi h; int len; mhash():h({0,0}),len(0){} mhash(char c){h.fi=h.se=(c-'a')+1;len=1;} void reset(){h.fi=h.se=len=0;} void merge(char c){ h.fi=(ll(BA)*h.fi+(c-'a')+1)%MODA; h.se=(ll(BB)*h.se+(c-'a')+1)%MODB; len++; } void merge(const mhash &o){ if(!done){ calcpw(); } if(o.len==0)return; h.fi = (h.fi*pw[0][o.len]+o.h.fi)%MODA; h.se = (h.se*pw[1][o.len]+o.h.se)%MODB; len+=o.len; assert(len res; //la, ra row 1 to row 0; lb,rb row 0 to row 1 for(int ii=0;ii<2;ii++){ vector la(n),lb(n),ra(n),rb(n); for(int i=0;i=0;i--){ ra[i].merge(vs[1][i]); rb[i].merge(vs[0][i]); if(i!=(n-1))ra[i].merge(ra[i+1]), rb[i].merge(rb[i+1]); ra[i].merge(vs[0][i]); rb[i].merge(vs[1][i]); } for(int left=0;left<=n;left++){ //ha ends on row 0; hb ends on row 1 mhash ha, hb; if(left){ ha.merge(la[left-1]); hb.merge(lb[left-1]); } for(int mid=0;mid+left<=n;mid++){ int right=n-(mid+left); if(mid){ int mix=left+mid-1; ha.merge(vs[0][mix]); ha.merge(vs[1][mix]); hb.merge(vs[1][mix]); hb.merge(vs[0][mix]); swap(ha,hb); } mhash ta=ha, tb=hb; if(right){ int rix=n-right; ta.merge(rb[rix]); tb.merge(ra[rix]); } assert(ta.len==2*n);assert(tb.len==2*n); res.insert(ta.geth()), res.insert(tb.geth()); } } reverse(vs[0], vs[0]+n); reverse(vs[1], vs[1]+n); } cout<
•  » » 4 years ago, # ^ |   +3 probably because of set. Change it to vector and you should not be TLE.
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 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)?
•  » » » » 4 years ago, # ^ |   +1 Yes, but set is much slower.
 » 4 years ago, # | ← Rev. 2 →   +5 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.