shashank21j's blog

Sears Dots and Arrows Coding Contest[HackerRank]
By shashank21j, history, 8 years ago, In English

Hi coders

Sears is hosting its first ever online Hackathon on HackerRank- Sear Dots & Arrows with some really big prizes on offer. Register yourself now at https://www.hackerrank.com/sears-dots-arrows

The contest commences on Sunday, 23 October at 5PM IST, and remains open for 7 hours.

  • 1st prize — 400,000 INR
  • 2nd prize — 200,000 INR
  • 3rd prize — 100,000 INR
  • 4th to 15th — I Pad
  • 16th to 100 — 2,000 INR
  • 101 to 200 — 1,500 INR

Prizes are only for Indian programmers residing in India.

Please check out the contest page (https://www.hackerrank.com/sears-dots-arrows) for more details on the contest.

UPD Final leaderboard is generated. Congratulations to the winners.

GL & HF

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

Comments Comments (59)
| Write comment?
»
8 years ago, # |
  Vote: I like it -13 Vote: I do not like it

12 ipads and  ≥  1500 bucks for the top 200. What. The. Fuck.

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

Will the prizes be given on the basis of online round ranklist or onsite ranklist?

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

    Prizes will be given on the basis of onsite rank list.

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

      How many spots are there in the onsite?

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

        Its not yet finalized but it will be somewhere in the range of 150-200.

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it 
          We are invested in this initiative sincerely and for that we will ensure we cover your travel expenses and make your travel worthwhile.

          To be clear, this means you will be covering travel expenses for everyone? And the prize money mentioned is seperate from this expenditure right? Also, where is the final scheduled?

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

            Yes, we will be covering the travel expenses. Also, Prize money is independent of the travel expenses.

            Five finalized locations are: Delhi, Mumbai, Kharagpur, Bangalore and Hyderabad. We may add more locations later.

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

          200 slots and everyone with 101 <= rank <= 200 get 1500 bucks .

          Everyone participating in onsite would get a prize ? o.O

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

            Holy shit! Not only that, but the travel expenses will be covered too.
            So if you're in the top 200, you basically get to travel to another city for negative cost.

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

            Yes.

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

          Exactly how many spots are there in the onsite?

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

Is the onsite event a Hackathon or a usual coding contest?

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

What is INR ?

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

how to apply for a Indian citizenship?

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +74 Vote: I do not like it

Can you please clarify what you mean by Hackathon? Normally hackathons are used to develop software, but then in the contest details page it is mentioned that "To power the same, Sears India invites coding talent from pan India to compete in a 2 tier 'algorithm intensive' programming Hackathon". Is it going to be an algorithmic programming contest similar to the first round or not?

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

What's the solution for Simple Paths?

I check if some color is included in the set by seeing the components made by edges that are of colours =/= that color offline. This only gets 83.33. WA on test case #6. Submission

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

    Your submission is not visible. However, In case of a forest, did you checked if initially both x,y are in the same component?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 4   Vote: I like it +5 Vote: I do not like it

      I did check that. Ideone.

      pika is the component array of original graph. comp is the component array of graph after removal of coloured edges.

      UPD: Also, I was not 100% sure, so I had tried answer to be 0 and C both(that is, replaced || by && at line 68).

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

        It should be:

        if(comp[Q[j].first] != comp[Q[j].second] && (pika[Q[j].first] == pika[Q[j].second]))

        They need to be in the same component initially.

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

How to solve the problem Sublist Riddle?

https://www.hackerrank.com/contests/sears-dots-arrows/challenges/sublist-riddle

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

Can somebody post their accepted code for D Connection Queries? I implemented Mo's Algorithm but the solution was giving TLE. I am using Mo's + Hashing.

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

How to solve connection queries?

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

    I solved Connection Queries using MO's Algorithm.

    Keep cnt[] array where cnt[i] = 1 if node i is present in the range [current_left(cl) , current_right(cr)].

    Lets say ,we have answer (ans) for [cl,cr] in mos algo.

    1. Explanation of add(): adding a node (a[i]) in the current range of nodes. if cnt[a[i]+1] == 1 and cnt[a[i]-1] == 1, then adding a[i] will join 2 components hence ans--. if cnt[a[i]+1] == 0 and cnt[a[i]-1] == 0, then adding a[i] will add 1 component which is single node (a[i]) hence ans++.

    2. Explanation of remove(): removing a node (a[i]) in the current range of nodes. if cnt[a[i]+1] == 1 and cnt[a[i]-1] == 1, then removing a[i] will break 1 component into 2 components hence ans++. if cnt[a[i]+1] == 0 and cnt[a[i]-1] == 0, then removing a[i] will remove 1 component which is single node (a[i]) hence ans--.

    Handle the cases when a[i] = 1 and a[i] = n in both the functions.

    My AC code using same Algorithm.

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

Can connection queries be solved using segment trees?

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

Can someone explain what sublist riddle wanted us to do? I'm still confused.

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

Approach for the last problem ?

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

    Use Matrix Multiply and make the Transform Matrix T, use Exponentiation by Squaring to get Bib(x) fast.

    Also Bib(x+y) = Bib(x) * T^y.

    List all the elements to add up S (assume N = 4), we get

    row_1 => Bib(A1),

    row_2 => Bib(A1+A2), Bib(A2)

    row_3 => Bib(A1+A2+A3), Bib(A2+A3), Bib(A3)

    row_4 => Bib(A1+A2+A3+A4), Bib(A2+A3+A4), Bib(A3+A4), Bib(A4)

    sum(row_2) = sum(row_1) * T^A2 + Bib(A2)

    sum(row_3) = sum(row_2) * T^A3 + Bib(A3)

    sum(row_4) = sum(row_3) * T^A4 + Bib(A4)

    Then sum all of them up to get S.

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

    Problem: https://www.hackerrank.com/contests/sears-dots-arrows/challenges/modified-fibonacci-1

    Algo: Matrix Expo.

    let the array elements be { a[1] , a[2] ... a[n] }.

    Then b(a[i]) = T^a[i]-1, where T is the transformation matrix.

    Now , all the sub-arrays ending at index i-1 will be.

    S1 = (a[1] + a[2] ... a[i-1])

    S2 = (a[2] + a[3] ... a[i-1])

    . .

    Si-2 = (a[i-2] + a[i-1])

    Si-1 = (a[i-1])

    Now, contribution of all the sub-arrays ending at i-1 will be,

    tans = b(S1) + b(S2) ... b(Si-1) = T^(a[1]+a[2] ....a[i-1]-1) + T^(a[2]+a[3]...a[i-1]-1) + ... T^(a[i-1]-1).

    now, the contribution of all the sub-arrays ending at i will be,

    T^(a[1]+..a[i]-1) + T^(a[2]+...a[i]-1) ... T^(a[i-1]+a[i]-1) + T^(a[i]-1)

    which is equal to,

    (tans * T + I) * T^(a[i]-1).

    My AC code using same Algorithm.

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

Can anyone provide some information about the timings and exact venue of the onsite contest?

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

Does anybody know when the onsite results will be announced?

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

How to solve "Cut into Palindromes" problem..??

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

Where can we see onsite problems ?

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

How to solve "greedy strategy"?

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

    TL DR: Brute-force — O(n^4): http://ideone.com/w3J7Lk

    Naive solution is obvious: While we can find a solution try all O(n^4) top-left and bottom-right vertices of submatrix, and take the best in each iteration. Since, there can be at most O(n^2) solutions the runtime is O(n^6) which gives 36 points.

    To optimize the above for 100 points, iterate on each O(n^4) submatrix only once. If we can check if to take this submatrix or not in O(1), we are done since we have an O(n^4) solution which fits the time limit.

    1). To check if to take A[x..c][y..d] or not in O(1) is simple — if we have calculated B[i][j] = number of ones in A[1..i][1..j], then check percentage condition by calculating number of ones in A[x..c][y..d] by the formula B[c][d]-B[x-1][d]-B[c][y-1]+B[x-1][y-1]. To update matrix B, note that it needs to be updated only when we choose a submatrix, so only O(n^2) time. So just rewrite whole B, first by making the chosen submatrix largely negative A[i][j] = -n*m-1 for all x<=i<=c and y<=j<=d. Then re-calculate whole B using B[i][j] = A[i][j] + A[i-1][j] + A[i][j-1] — A[i-1][j-1]. Number of ones will come negative in a submatrix if it overlaps with some other already chosen submatrix.

    2). The iteration order of submatrices is dictated in the question itself: take decreasing order of area, then all start points from (1,1) to (n,m) then increasing order of lengths which divide the area: You can code to iterate on each submatrix exactly once by using two pointers on lengths with fixed area(refer to above code).

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

did anyone get the reimbursement or prize money for the onsite ?

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

Did everyone get their prizes ??

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

I still haven't received my prize money. Will it ever come? :p

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

    Me too and few of my friends also haven't received the prize money

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

    I messaged them on Facebook a week ago and this was their reply — "Yes you will be getting it. The team is working on it. Apologies for the delay.."

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

    I kept bugging them over email and finally, got my cash prize as well as cab amount in Dec or Jan.

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

    Well, I have got my prize today and couple of my friends too.

    → Reply
»
8 years ago, # |
  Vote: I like it -28 Vote: I do not like it

mdzz...........垃圾比赛，毁我青春

我怎么连E都不会做2333333

看不懂？辣鸡 translate

→ Reply