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 .

# | User | Rating |
---|---|---|

1 | tourist | 3707 |

2 | Benq | 3672 |

3 | ksun48 | 3575 |

4 | Radewoosh | 3562 |

5 | Miracle03 | 3480 |

6 | maroonrk | 3406 |

7 | ecnerwala | 3400 |

8 | peehs_moorhsum | 3384 |

9 | sunset | 3338 |

10 | Um_nik | 3320 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 208 |

2 | YouKn0wWho | 197 |

2 | Um_nik | 197 |

4 | Errichto | 181 |

4 | sus | 181 |

6 | awoo | 179 |

7 | tourist | 175 |

8 | -is-this-fft- | 171 |

8 | SecondThread | 171 |

10 | Ashishgup | 170 |

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 ?

How to find the minimum number of increments/decrements needed to make all array elements distinct ?

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

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+

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/27/2021 04:38:20 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|