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

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

This is my solution I used DP to solve it. The state was current number, and three boolean variables representing if the intersection of two lists is empty or not. Complexity is O(N*2*2*2)

You could also solve it as a combinatorics problem.

Here's a link to my solution : http://ideone.com/nmTHJo

Here's a link to possible explanation : http://math.stackexchange.com/a/1701866

Ideone

Link to my AC solution

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.

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.

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.

They have announced results on their website: https://www.searsindia.co.in/hackathon/. However hackerrank leaderboard isn't updated.

Unable to parse markup [type=CF_MARKDOWN]

https://www.hackerrank.com/contests/sears-onsite/challenges

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

yes

No.

No.

NO. Probably it will come next year :(

No. !

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

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

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

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