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 | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
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.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+
Name |
---|