Shafaet's blog

By Shafaet, history, 8 years ago, In English

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, fedimser, sgtlaugh, nabila_ahmed, and myself. Thanks to niyaznigmatul, ikbal, danilka.pro, 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!

  • Vote: I like it
  • +67
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    8 years ago, # ^ |
    Rev. 3   Vote: I like it +13 Vote: I do not like it

    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.

  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    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.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +32 Vote: I do not like it

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

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
8 years ago, # |
Rev. 2   Vote: I like it +78 Vote: I do not like it

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

»
8 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Can you announce tiebreaking rules in advance?

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Shafaet (previous revision, new revision, compare).

»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I wish there was one more problem :)

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Still only 15 people got full score so far!

    I hope you liked the problemset :).

»
8 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve Vertical Path?

  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it +18 Vote: I do not like it

    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

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 2   Vote: I like it +10 Vote: I do not like it

      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

»
8 years ago, # |
Rev. 2   Vote: I like it +46 Vote: I do not like it

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,

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

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

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        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.

»
8 years ago, # |
  Vote: I like it +28 Vote: I do not like it

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.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
8 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 code
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

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

»
8 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

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.