![](/style/images/good.png)
![](/style/images/bad.png)
Trilogy Intern Hunt Online Round Discussion (18th Dec. '22)
source link: https://codeforces.com/blog/entry/110270
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
I couldn't find any discussion or editorial blog, so am creating a new one.
Was able to solve the 2nd problem with Segment Tree (standard stuff) and attempted to solve the first one with 6D DP (wasn't able to debug an RE).
It would be great if you could share your approaches for the four problems.
24 hours ago, # | Do you have questions? Can you post? |
-
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.
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 |
-
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.-
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.
-
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; }
-
23 hours ago, # | Btw, what is the selection criteria for the Online Round? |
-
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.
23 hours ago, # | first was digit dp, second was usual prefix sum, third I did using Manachers algo. |
-
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.
-
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
-
-
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.
23 hours ago, # | 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 |
23 hours ago, # | 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!! |
7 hours ago, # | Here is my approaches... Problem A Problem B Problem C Problem D |
-
Just an addition, C was basically a direct implementation of Manacher's algo, which gives linear runtime.
-
did u solution for the problem c got ac i got tle for a few tc.My code get 286/300.
-
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))
-
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.
-
-
In C, in test cases where the density of palindromes is high, wouldn't the effective complexity of Polynomial Hashing with Verification on Match be O(N*(LogN)*N)?
The probability of hash collision is extremely low, I know, especially if a large prime is used, but still, without verification wouldn't it be non-deterministic?
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK