Participated in the Codeforces Round 943 (Div. 3) and managed to solve 6 problems out of 8.
Here I am trying to give a short description of the problems.
Problem A :
given a value x and need to find a value y such that gcd(𝑥,𝑦)+𝑦
is the maximum possible. Since the range of y is [1,1000], it is done by brute force.
Problem B :
given two binary strings a and b, need to find the maximum k such that the k length prefix of a is a subsequence of b. I do it with a simple two-pointer.
Problem C :
given an array x2,x3,x4,.....xn and need to find an array a such that x[i] = a[i]%a[i-1] for all i, 2 < i <= n;
The first thing is that a[i-1] must be greater than x[i]. since a[i] < 1e9 so that i need to place a[i] as small as possible. I put a[1] = x[2] +1 and fill the next values with the help of this eq -> a[i] = ((x[i + 1] / a[i - 1]) + 1) * a[i-1] + x[i].
Problem D :
Since the way is unique here, I will go up to position i and the remaining k can be taken as a[i]. I can easily take the maximum value from all the positions. Here I use a visited array for break loop.
Problem E :
This a constructive algorithms problem. Here max-size of the set H can be
(2 * n) - 2. I take 2 points as (1,1) and (n, n), then I take n-3 points as (2, 1), (3, 1), (4, 1)......... if(n > 2) I take the last point as (2, n-1). this will fulfill the requirement.
Problem G1 :
In this problem, I use Z_Algo to find the prefix of each position and then apply binary search on that array to find the maximum value.
#happycoding
