Trilogy Intern Hunt Online Round Discussion (18th Dec. '22)

17 месяцев назад, # ^ |

No, I don't have them. Thought they'd post an editorial or something.
The IDE was kind of unintuitive as well, had to rewrite more than 60 lines of code because the text-area wouldn't accept any text that I had written in my editor.
Plus there was a grey area around whether one could create additional functions and classes, or only the solution function could be modified.
The testing apparatus could have also been better.
Overall, not a great experience.

→ Ответить

17 месяцев назад, # ^ |

I also hate the IDE of InterviewBit. Worst experience I have with the IDE.

→ Ответить

ShivanshJ

17 месяцев назад, # ^ |

+18

Exactly its soo hard to debug there!

→ Ответить

17 месяцев назад, # |

← Rev. 2 →

First Problem___

You are given a range l,r. We have to count total no of beautiful numbers in that range.

Numbers are beautiful if, xor of all digits of that number is greater than the avg(max digit of that number + min digit of that number)

return result%1e9+7

→ Ответить

17 месяцев назад, # ^ |

Could someone share the intended approach / an elegant solution?
Mine was clumsy and complicated and full of bugs; 6D DP's never a good idea, ig.

→ Ответить

17 месяцев назад, # ^ |

Mine was 5D digit dp and cancerous as it involved finding the maximum and least set bit of a number. The 6d digit dp is better and easier to write.

→ Ответить

17 месяцев назад, # ^ |

Did u get ac for this?

→ Ответить

17 месяцев назад, # ^ |

yes

→ Ответить

angry_pikachu

17 месяцев назад, # ^ |

can you share the solution of 6-D dp?

→ Ответить

KaI777

17 месяцев назад, # ^ |

do you have any idea what will be the final cutoff for the shortlisting process?

→ Ответить

17 месяцев назад, # ^ |

Could you please share the DP approach?

→ Ответить

onlyerror

17 месяцев назад, # ^ |

← Rev. 3 →

Mine is 6D Dp. Could not find the bug in contest time Later found it.

class Solver{
    final long MOD=(long) 1e9+7;
    String s;
    long [][][][][][]dp;
    Solver(String s){
        this.s=s;
        this.dp=new long[2][2][10][10][16][20];
        for(long [][][][][]x:dp){
            for(long [][][][]xx:x){
                for(long [][][]xxx:xx){
                    for(long [][] xxxx:xxx){
                        for(long []xxxxx:xxxx){
                            Arrays.fill(xxxxx,-1);
                        }
                    }
                }
            }
        }
    }
    public long solve(int index,int smalltaken,int nonzero,int mind,int maxd,int xorv){
        if(index==s.length()){
            return (nonzero==1&&2*xorv>(mind+maxd))?1:0;
        }
        if(dp[nonzero][smalltaken][mind][maxd][xorv][index]!=-1){
           return dp[nonzero][smalltaken][mind][maxd][xorv][index];
        }
        int range=(smalltaken==1)?9:s.charAt(index)-'0';
        long ans=0;
        for(int d=0;d<=range;d++){
            int n_nonzero=(nonzero==1||d>0)?1:0;
            int n_mind=(n_nonzero==1)?Math.min(d,mind):mind;
            int n_smalltaken=(smalltaken==1||d<range)?1:0;
            ans+=solve(index+1,n_smalltaken,n_nonzero,n_mind,Math.max(d,maxd),xorv^d);
            ans%=MOD;
        }
        return dp[nonzero][smalltaken][mind][maxd][xorv][index]=ans;
    }
}
class Test{
    public static void main(String[] args) {
        // A -> 170888 B -> 676277
        Solver solve1=new Solver("170887");//use A - 1 where A is the smaller number
        Solver solve2=new Solver("676277");
        System.out.println(solve2.solve(0,0,0,9,0,0)-solve1.solve(0,0,0,9,0,0));
    }
}

→ Ответить

angry_pikachu

17 месяцев назад, # ^ |

← Rev. 2 →

I dont know what is wrong with my code, but I have used 5-D dp and used digit DP . Is there any silly mistake? or some wrong approach?

int dp[18][10][10][16][2];
const int N = 1e9+7;
int get(int pos , string &s, int mx, int mn, int xr, int tgt){
    if(pos == 0) return (2*xr>mx+mn);
    if(dp[pos][mx][mn][xr][tgt] != 1) return dp[pos][mx][mn][xr][tgt];

    int ans = 0, ub = (tgt? (s[s.size()-pos]-'0'):9);
    for(int i = 0; i <= ub; i++){
        ans += get(pos-1,s,max(mx,i),min(mn,i),(xr^i),tgt&(i==ub));
        ans %=N;
    }
    return dp[pos][mx][mn][xr][tgt] = ans;
}
int Solution::solve(string A, string B){
    memset(dp,-1,sizeof(dp));
    int a = get(A.size(),A,0,9,0,1);
    memset(dp,-1,sizeof(dp));
    int b = get(B.size(),B,0,9,0,1);
    int mx=0,mn=9,xr=0;
    for(auto it: A)mx=max(mx,it-'0'),mn=min(mn,it-'0'),xr^=(it-'0');
    if(2*xr>mx+mn)ans--;
    return ans;
}

→ Ответить

17 месяцев назад, # ^ |

You need one more state known to handle cases where you haven't started building numbers. For example if you start building from the second digit and put a 0 there it is not considered a part of the number as it is a leading zero.

→ Ответить

Snapper_001

17 месяцев назад, # ^ |

What was the constraint over l and r

→ Ответить

17 месяцев назад, # ^ |

(1, 10^18)

→ Ответить

17 месяцев назад, # |

Btw, what is the selection criteria for the Online Round?
Is it based on the number of problems solved, or quality of submissions, or something else?
There wasn't even a rankings page, afaik.

→ Ответить

17 месяцев назад, # ^ |

← Rev. 3 →

Ig first they will go with number of problems with 100% acceptance rate, then quality of code. Then rest others.

→ Ответить

17 месяцев назад, # ^ |

I think they take various factors into account like your resume quality, college, CGPA, branch etc.

→ Ответить

lamellama

17 месяцев назад, # ^ |

its based on points scored

→ Ответить

hackerbhaiya

17 месяцев назад, # ^ |

+10

I solved 3 and submitted 4th at the end (don't know if it was accepted or not as the test ended while compiling) and I got the clearance of Online Round mail.
The ranking should be the only selection criteria I think which will be based on the points scored, in case of a tie, time will be considered.

→ Ответить

17 месяцев назад, # ^ |

← Rev. 2 →

From Interview-Bit or from Trilogy?
I have received one for successful completion from Interview-Bit.
Don't know if it's in any way related to the actual selection process.

→ Ответить

hackerbhaiya

17 месяцев назад, # ^ |

From Trilogy, for completing the aptitude test as the next round.

→ Ответить

aKILLL

17 месяцев назад, # |

first was digit dp, second was usual prefix sum, third I did using Manachers algo.

→ Ответить

17 месяцев назад, # ^ |

Manacher's Algo?
Just found something new to learn.
Thought of applying KMP or ZF in some way, but knew it wouldn't work.

→ Ответить

17 месяцев назад, # ^ |

← Rev. 2 →

which one you did by prefix sum?the problem in which we need to give x1^x2 where x1 and x2 are bitwise and of range l1,r1,l2 and r2?

If yes how?I did it using seg trees.

upd got it from a below comment.

→ Ответить

k_rishabh

17 месяцев назад, # ^ |

Simple method: We have to find the values of x1 and x2 then xor them. So, first we create a prefix array pref[i][j] of size n*32 which represents the sum of jth bit of the indices in the range [0, i]. Now, when we want to calculate value of x1, we find the number of set bits of the jth bit and check if it is equal to r1 — l1 + 1 (size), because for bitwise and to be 1, we need all the bits to be equal to 1. Similarly, we can find x1 and x2, then xor them

→ Ответить

___LoneWolf___

17 месяцев назад, # ^ |

← Rev. 3 →

Third problem can be also done by some simple string hashing and binary search.

Make prefix and suffix hash using some mod value (I used 1e9+9). Now just binary search on the length uptil which the string [i,i+mid] from prefix hash and [i-mid,i] from suffix hash is same. This problem can be solved using binary search in log(n) time.

→ Ответить

onlyerror

17 месяцев назад, # ^ |

can you please share some similar question like this?

→ Ответить

17 месяцев назад, # |

3rd Problem

Given a string s and a vector Q containing queries. For each element i in Q we have to find the length of longest odd palindrome whose middle index is i in string s. 1 <= Len(s), Len(Q) <= 1e5. We have to return vector of results of each query

→ Ответить

mr_golem

17 месяцев назад, # ^ |

Does Q representing the indexes i?

→ Ответить

https://leetcode.com/discuss/interview-question/2924881/intern-hunt-challenge-trilogy-innovations-2023/

17 месяцев назад, # ^ |

yes

→ Ответить

__iOTA

17 месяцев назад, # |

In second problem just store prefix of every bit for all element and check if bit[r][j] — bit[l-1][j] == r-l+1...if yes add that bit to answer. Calculate the same for both given range and store the xor of both!!

→ Ответить

Tony_Kakkar

17 месяцев назад, # |

+13

Here are the problems:

problem 1

problem 2

problem 3

problem 4

→ Ответить

mr_golem

17 месяцев назад, # ^ |

how did u get them

→ Ответить

Neothermal

17 месяцев назад, # ^ |

telegram xd:

→ Ответить

Tony_Kakkar

17 месяцев назад, # ^ |

+23

Don't directly jump to conclusions idiot!

→ Ответить

Tony_Kakkar

17 месяцев назад, # ^ |

From here:

https://leetcode.com/discuss/interview-question/2924881/intern-hunt-challenge-trilogy-innovations-2023/

→ Ответить

coderdhanraj

17 месяцев назад, # |

+15

Here is my approaches...

Problem A

Problem B

Problem C

Problem D

→ Ответить

vrintle

17 месяцев назад, # ^ |

Just an addition, C was basically a direct implementation of Manacher's algo, which gives linear runtime.

→ Ответить

17 месяцев назад, # ^ |

did u solution for the problem c got ac i got tle for a few tc.My code get 286/300.

→ Ответить

sangeeta

17 месяцев назад, # ^ |

This was my code for 3rd problem and I got an AC for that.

def solve(s, b):
    n = len(s)
    s = '('+s+')'
    p = [0]*(n+1)
    l = 1
    r = 1
    for i in range(1, n+1):
        p[i] = max(0, min(r - i, p[l + (r - i)]))
        while(s[i-p[i]] == s[i+p[i]]):
            p[i] += 1
        if(i + p[i] > r):
            l = i - p[i]
            r = i + p[i]
    ans = []
    for i in b:
        ans.append(p[i]*2-1)
    return ans


s = "abacaba"
b = [2, 3, 4]
print(solve(s, b))

→ Ответить

17 месяцев назад, # ^ |

thanks.

→ Ответить

yeetholmes619

17 месяцев назад, # ^ |

Yeah, my binary search + hashing solution gave 296/300 initially, then I removed the unecessary %mod operations during addition, i.e (a%m + b%m > m) ? (a%m + b%m — m) : (a%m + b%m). that was enough for my submission to then get a full score.

→ Ответить

17 месяцев назад, # ^ |

oh i see.Thanks for the reply..

→ Ответить

tandonjiii

17 месяцев назад, # ^ |

Can You Please share Your approach for problem C of binary search with hashing

→ Ответить

coderdhanraj

17 месяцев назад, # ^ |

Sure! so I just hashed the string in both the directions i.e. forward and backward/reverse. Then for a query of 'i' I searched for the maximum length that has the center 'i' and is odd. i.e. maximum x for [i — x... i + x] is palindrome. you may check palindrome nature by taking hash between [i — x .... i] for reverse hash table and [i ... i + x] for forward hash table and just compare the result. They should be equal for a substring being palindrome!

→ Ответить

tandonjiii

17 месяцев назад, # ^ |

thanks

→ Ответить