### yamih23436's blog

By yamih23436, history, 3 months ago, 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 . By yamih23436, history, 5 months ago, 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 ? By yamih23436, history, 7 months ago, 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.com/contest/713/problem/C By yamih23436, history, 7 months ago, 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 :) By yamih23436, history, 7 months ago, 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=,[1,7,8]$

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

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

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

$Ans= 12$

(3-3)+(6-1)+(9-2)=12 By yamih23436, history, 7 months ago, 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+ 