This problem is from https://acm.hdu.edu.cn/ I don't have the exact link to the problem though. ![ ]()

I tried many approaches , either they are in efficient or way too complicated .

Saw this problem in a(Leetcode) discussion : https://leetcode.com/discuss/interview-experience/1257566/goldman-sachs-tech-analyst-bengaluru-2021-off-campus-offer

Given 2N words each of length N. We have to arrange all the words in a matrix of size N * N such that all the words can be read in the crossword matrix (horizontally/vertically). Also, find the lexicographically smallest arrangement if many are possible: Not sure about constraints , but is there any better way other than brute force ?

Example:

Input:

N = 3

{$$$abc, bfj, cgk, ade, dfg, ejk$$$}

Output:

$$$abc$$$

$$$dfg$$$

$$$ejk$$$

Any ideas ?

Say , size of given array is $$$N$$$ and $$$abs(a[i])$$$<= 10000000

Example :

$$$ {1,100,100,100,100} $$$

Minimum cost = $$$4$$$

$$${1,100,101,99,102}$$$

I am looking for both $$$O(n*n)$$$ and $$$O(n)$$$ solutions .

Source of the problem : Just occurred to my mind .

My idea : Sort the given array , then apply the algorithm mentioned in this problem : https://codeforces.net/contest/713/problem/C

In this telegram of 2000 members , all solutions for A,B,C,D were shared : https://t.me/GoogleKickStartLearners

![ ]()

Google never runs plagiarism test on Kickstart and finalizes the rank-list as it is . I urge Google to run a plag test so people can get their deserved ranks.

Edit : Seems like they are running plagiarism test this time :)

I know the O(n*n) partitional dp solution for this problem . Looking for a more efficient one . This problem was asked in a coding test of Hacker|earth 10 days back .

How to maximize the total sum of difference of maximum and minimum element in contiguous subarrays of an array ?

We can partition an array into any number of subarrays we want. Each element should belong to exactly one subarray .

$$$A=[3,1,7,8] $$$

$$$Ans=[3],[1,7,8]$$$

$$$Ans= (3-3)+(8-1)=7$$$

If $$$A=[3,1,6,5,9,2]$$$

$$$Subarrays:[3],[1,6,5],[9,2]$$$

$$$Ans= 12$$$

(3-3)+(6-1)+(9-2)=12

Edit : $$$I$$$ $$$have$$$ $$$solved$$$ $$$it$$$ $$$now$$$

This problem is from a coding test/contest on Hackerearth which is over now .

I will be asking a subtask of the original problem as I can solve the original problem if I can solve this subtask .

We are given three integers a,b,c .

Constraints : b>0 , b,a <998244353

c<=10^18

Consider an array of size 'c' .

It only consists of only zeroes and ones .

Calculate the probability that the xor of this array is "1" .

Probability of any array element to be zero , is given by a/b .

Example :

c=2

a=1

b=3

(p1=a/b)

Only the following arrays can make xor = 1 ,

1) {0,1} , (probability1) : (1/3)*(2/3) = (2/9)

2) {1,0) , (probability2) : (2/3)*(1/3) = (2/9)

Final answer : 2/9 + 2/9 = 4/9

Answer to be calculated modulo the prime number , 998244353

Thankyou community of codeforces , I finally solved it!

I solved it by finding the recurrence relation , say , a(n) is the probability, that sequence of length n has xor equal to 1 .

Then , $$$a(n)=a(n−1)∗c+z $$$, where $$$c=2∗p1−1$$$ , $$$z=1-p1$$$

Closed form for this can be found here : https://www.wolframalpha.com/input/?i=g%28n%29+%3D+g%28n-1%29*c++%2B+z+