Single Round Match 712 Editorials

Editorials for SRM 712 are now here. Thanks to abhinavagg96, mmaks, stni, marcose18 and cgy4ever for contributing. Also thanks to Egor for helping us review the submissions.
If you would like to discuss or suggest some changes in the editorials you may reach out to the writers in the discussion forum

Single Round Match 712 Round 1 - Division II, Level One RepeatNumberCompare by stni

According to constraints 1 <= x <= 1,000,000,000, 1 <= k <= 50,
v = repeat(x, k) could be as large as 10^450.
We can't store such a integer normally. So we need to convert them to strings then do the comparison. To do the conversion, we make an empty string and append to it the string converted from x k times.
To do the comparison,
- If one of the strings is longer, its value is bigger.
- If lengths of the strings are equal to each other,
- We traverse all digits of the strings from the beginning (index 0, the most significant digit).
- If one digit is bigger than the other, the integer this digit is from is bigger.
- If we reached the end, the two integers are equal.
Complexity is O(max(len(x1)*k1,len(x2)*k2))
 
class RepeatNumberCompare{
public:
string compare(int x1, int k1, int x2, int k2){
string s1=to_string(x1);
string s2=to_string(x2);
string str1="",str2="";
for(int i=0;i<k1;i++){
str1+=s1;
}
for(int i=0;i<k2;i++){ str2+=s2; } if(str1.length()>str2.length()){
return "Greater";
} else if(str1.length()<str2.length()){ return "Less"; } if(str1>str2){
return "Greater";
} else if(str1<str2){
return "Less";
}
return "Equal";
}
};


Single Round Match 712 Round 1 - Division II, Level Two MakePalindrome by mmaks

Let's try and look at the two important things here in this problem.
1.Why in a palindromic string at most one character can have odd occurrence :
Consider an string of odd length, S = FXF'
where F is first half of string and F' is second half of the string.
As "A palindrome is a string that reads the same forwards and backwards.", to be true
reverse(F') = F
For every character F[i], there must be same character F'[n-i], where n is the size of F.
So, every character has even number of occurrence in S except middle character 'X'.
Therefore each palindromic string can at most have one character with odd occurrence. ( For even length palindrome there will not any X )
2. Why this solution gives minimum number of palindromic strings :
As in a palindrome we can only have at most one character with odd occurrence.
So, for each character with odd occurrence we have to make a separate palindromic string.
But we can use all characters with even occurrences in a single palindromic string.
So, add all characters with even occurrences in this palindrome and add at most one character with odd occurrence. And after that all remaining characters with odd occurrence will form different palindromes.
C++ implementation :
public class MakePalindrome
{
vector constructMinimal(string card) {
map<char, int> mp;
mp.clear();
vector ret;
ret.clear();
for(int i=0;i<card.size();i++) {
mp[card[i]] ++;
}
string f = "";
for(char i = 'a'; i <= 'z'; i++) {
// cout<<i<<" "<<mp[i]<<"\n";
if(mp[i] % 2 == 0) {
for(int j=0;j<mp[i]/2;j++) {
f.push_back(i);
}
mp[i] = 0;
}
}
bool flag = 0;
// Add character with odd occurrence
for(char i = 'a'; i <= 'z'; i++) {
if(mp[i]&1) {
flag = 1;
for(int j=0;j<mp[i]/2;j++) {
f.push_back(i);
}
string temp = f;
cout<<temp<<"\n";
reverse(temp.begin(), temp.end());
f = f + i + temp;
mp[i] = 0;
break;
}
}
// if all characters are of even occurrence
if(!flag){
string temp = f;
reverse(temp.begin(), temp.end());
f = f + temp;
ret.push_back(f);
return ret;
}
ret.push_back(f);
f = "";
// for all other characters of odd occurrence
for(char i = 'a'; i <= 'z'; i++) {
f = "";
// cout<<i<<" "<<mp[i]<<"\n";
if(mp[i]&1) {
for(int j=0;j<mp[i];j++) {
f.push_back(i);
}
ret.push_back(f);
}
}
return ret;
}
}

Single Round Match 712 Round 1 - Division II, Level Three AverageVarianceSubset by abhinavagg96

If we can find the sum of Var(S) for all valid subsets in the whole array, we can divide by count of total valid subsets in the end to get the result.
For the first part,
It can be worked out that Var(X) = E(X^2) - (E(X))^2, where E(X) = expectation/mean.
Now problem reduces to finding the terms in RHS independently for all valid subsets in a given range. If we can calculate this for a particular range (l, r), we will look at how to extend it to find answer for the whole array.
Subproblem 1 : Finding sum of Var(S) for all valid subsets in range (l, r) :
Using the earlier mentioned relation for Variance, we can break this into finding the sum of first term in RHS and the second term in RHS independently for all valid subsets.
For the first term, we can iterate over the elements in range (l, r) and the contribution of each element can be computed as follows :
for every element in range l, r:
for k in 1..r-l+1:
contribution is element^2*(number of subsets of size k in which this element is present)/k


For the second term, we can build a simple dynamic programming approach. Build two DP arrays sum[i][k] and sq[i][k], where sum[i][k] denotes the sum of sum of elements of all possible subsets in range l..i having size k, and sq[i][k] denotes the sum of sum of squares of elements of all possible subsets in range l..i of size k.
Let's denote number of subsets of size k-1 in range l..i-1 by cnt (This can be precomputed using nCr recurrence)
sum[i][k] = sum[i-1][k] + sum[i-1][k-1] + A[i]*cnt
sq[i][k] = sq[i-1][k] + sq[i-1][k-1] + A[i]*A[i]*cnt + 2*A[i]*sum[i-1][k-1]
Subproblem 2: Using the Subproblem 1 to solve the original problem:
Idea is to sort the array and use a standard 2 pointer approach to find the maximum index r for every i such that all possible subsets in range(i,r) are valid. One important point to note here is, we have to subtract the repeated ranges to avoid over counting.
For the second part, finding the total possible subsets can be done along with moving the two pointers, counting all possible subsets in the current range, and subtracting already counted subsets of previous range to avoid over counting.
 
#include<bits/stdc++.h>
using namespace std;
#define SZ(a) (int)(a.size())
long long ncr[51][51];
double sq[51][51], sum[51][51];
class AverageVarianceSubset {
public:
double average(vector , int);
};
double term1(vector &s, int l, int r)
{
double ans = 0;
for(int i = l ; i <= r ; i++)
for(int k = 1 ; k <= r - l + 1 ; k++)
ans = ans + double(s[i])/k*s[i]*ncr[r-l][k-1];
return ans;
}
double term2(vector &s, int l, int r)
{
memset(sq, 0, sizeof(sq));
memset(sum, 0, sizeof(sum));
for(int i = l ; i <= r ; i++)
for(int k = 1 ; k <= r - l + 1 ; k++) { if(k-1 > i - l) break;
double cnt = ncr[i-l][k-1];
sum[i][k] = (i-1 >= 0 ? (sum[i-1][k] + sum[i-1][k-1]) : 0)
+ s[i]*cnt;
sq[i][k] = (i-1 >= 0 ? (sq[i-1][k] + sq[i-1][k-1] + 2*s[i]*sum[i-1][k-1]) : 0)
+ double(s[i])*s[i]*cnt;
}
double ans = 0;
for(int k = 1 ; k <= r - l + 1 ; k++)
ans = ans + sq[r][k]/(k*k);
return ans;
}
double AverageVarianceSubset::average(vector s, int R) {
for(int i = 0 ; i <= 50 ; i++)
ncr[i][0] = 1;
for(int i = 1 ; i <= 50 ; i++)
for(int j = 1 ; j <= 50 ; j++)
ncr[i][j] = ncr[i-1][j-1] + ncr[i-1][j];
sort(s.begin(), s.end());
int r = -1, oldr = -1;
double num = 0;
double N = 0;
for(int i = 0 ; i < SZ(s); i++)
{
r = max(r, i);
while(r + 1 < SZ(s) && s[r+1] - s[i] <= R) r++;
N += (1LL<<(r-i+1)) - 1; num += term1(s, i, r) - term2(s, i, r); if(i && oldr >= i) num -= term1(s, i, oldr) - term2(s, i, oldr), N -= (1LL<<(oldr-i+1)) - 1;
oldr = r;
}
return num/N;
}


Single Round Match 712 Round 1 - Division I, Level One LR by marcose18

It won’t matter if we do right shifting or left shifting because the contents of the array will remain same.
Consider initial array as [2 3 4 5 6].
Left shifted array will be [8 5 7 9 11]
Right shifted array will be [5 7 9 11 8]ll
So we can see left shifted array is same as right shifted array, just the content is shifted by one position. We need to determine if we can change S array to T array.
So change the S array by right shifting operation. If the solution exists then that means our S array (after some operations) will be same as T array or a shifted version of T array because we just proved above that contents of array will remain same.
So after each right shifting operation we will check if S is equal to T or some shifted version of T.
If the array is shifted by i positions. Then we will have to add i left shift operations in place of right shift operations because left shift operation adds a shift of 1 unit to the right.
Make sure to check that i should be less than total right shift operations you have done else there is no solution.
 
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
public class LR {
// stores the amount of shift.
static int deg;
// check if S is a shifted version of T .
static void check(long s[], long t[]) {
long temp[] = new long[2 * t.length];
for (int i = 0; i < t.length; i++) {
temp[i] = temp[i + t.length] = t[i];
}
for (int i = 0; i < t.length; i++) {
boolean flag = true;
for (int j = 0; j < s.length; j++) {
if (temp[i + j] != s[j]) flag = false;
}
if (flag) {
deg = i;
return;
}
}
}
// right shifting operation
static void add(long s[]) {
long temp[] = s.clone();
for (int i = 0; i < s.length - 1; i++) {
s[i] += temp[i + 1];
}
s[s.length - 1] += temp[0];
}
/* checking if continuing right shift operations can help anymore. If max is greater than max1 in below method then no way S can be transformed to T.
*/
static boolean compare(long s[], long t[]) {
long max = 0, max1 = 0;
for (int i = 0; i < s.length; i++) {
max = Math.max(max, s[i]);
}
for (int i = 0; i < t.length; i++) { max1 = Math.max(max1, t[i]); } if (max > max1) return false;
return true;
}
public String construct(long[] s, long[] t) {
String ans = "";
deg = -1;
for (int test = 1; test <= 101; test++) { check(s, t); if (deg >= 0) {
if (deg > ans.length()) {
return "No solution";
}
int var = ans.length();
ans = "";
for (int i = 1; i <= deg; i++)
ans += 'L';
while (ans.length() < var)
ans += 'R';
return ans;
}
add(s);
boolean check = compare(s, t);
if (!check) return "No solution";
ans += 'R';
}
return "No solution";
}
}

Single Round Match 712 Round 1 - Division I, Level Two  AverageVarianceSubtree by cgy4ever

There can be a lot of subtree, so we can’t compute variance for each of them and then calculate the average. It means there must be something special with variance. (For example, if we replace variance with standard deviation then the idea mentioned below will not work)
Note that var(x1,x2,…,xn) is a quadratic function and it only contains second-degree terms. By symmetry we must have x1,x2,….xn:

where c1 and c2 are coefficients depends only on n but not xi, more specific, we have:

That means the sum of variance can be computed by:

where i and j are vertexes on the tree and n is the size of subtree, countTree(i, n) is the number of subtree that contains i, countTree(i, j, n) is the number of subtree contains both i and j.
The problem of of calculating countTree(i, n) and countTree(i, j, n) can be done by dynamic programming and they are classic. You can see the details in Petr’s solution (see countWithA and countWithAB).
Note that there is still something tricky: the precision. Since weight i are very large and we are doing subtraction we can have subtraction issues. Here are some possible solution:

1. Subtract the weight i by the mean. See Petr’s solution

2. Store the number as integer part (in Int128) + decimal part (in double). See IvL’s solution.

3. Use BigDecimal or float 128.

Single Round Match 712 Round 1 - Division I, Level Three  BinaryTreeAndPermutation by cgy4ever

First let’s give p[i] a meaning: let’s say we have n balls: ball 0 to ball n-1. Each of them will be placed in a vertex on the tree and no two balls are in same vertex. So p[i] is the location of ball i.
Then let’s see what does LCA(p[a], p[b]) = c mean: it means two things:
1.Ball a and ball b must under subtree c.
2.Ball a and ball b can’t be under subtree c.left or c.right together.
Let’s focus on condition 1 first, it says for a ball, we know the subtrees and we know the ball should under all of them. Suppose there are two subtree x and y:
1.If x is under subtree y, then we can remove y. (since under x leads to under y).
2.If x is not under y and y is not under x. Then this is a contradiction and there is no solution.
So after all we just need to keep one subtree. Thus for each ball x, we will have belong[x], which is the subtree it belongs. For balls not mentioned by any LCA, we don’t have this information (in this case we say belong[x] = -1).
Then we process the tree from leaf to root and assign balls. When we process vertex v, we will go through all balls x such that belong[x] = v and try to assign them under subtree v. By this way we can guarantee we can satisfy condition 1 for all constraints.
Let’s see how to do this for a vertex v:

1.     At this time we know how many empty slots left in left subtree and right subtree.

2.     We decide which ball will be on vertex v: it can be a ball x such that belong[x] = v or belong[x] = -1.

3.     Then for each constraints LCA(p[a], p[b]) = v, if neither a and b is on vertex v, we know that they must in different subtree (one in left and another one in right). Note that if we already placed a or b, we know which subtree it belongs to.

4.     We can construct a graph to express these constraints. We may have contradiction. If not, then we will have few connected components. For each one we know:

5.     The number of nodes on each side (n1 and n2)

6.     Can we swap sides. (If we already know one of them balls belong to, then we can’t swap).

7.     After that we can do knapsack to allocate these connected components to free slots (or find that is impossible).

After all there may be some unlocated balls and same number of free slots, we can allocate them arbitrarily.
And there are few more corner cases you need to handle correctly. (like the contradiction LCA(p[a], p[b]) = c and LCA(p[b], p[a]) = d where c and d are different).
 
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class BinaryTreeAndPermutation {
int n;
int[] parent;
boolean[][] isAncestor; // i is j's parent
int[][] LCA;
boolean[][] belong; // p[j] is under i
void prepare(int[] lef, int[] rig) {
n = lef.length;
isAncestor = new boolean[n][n];
LCA = new int[n][n];
parent = new int[n];
parent[0] = 0;
for(int i = 0; i < n; i++) {
if(lef[i] != -1) {
parent[lef[i]] = i;
parent[rig[i]] = i;
}
}
for(int i = 0; i < n; i++) {
int t = i;
isAncestor[t][i] = true;
while(t != 0) {
t = parent[t];
isAncestor[t][i] = true;
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
for(int k = 0; k < n; k++) {
if(isAncestor[k][i] && isAncestor[k][j])
LCA[i][j] = k;
}
}
}
}
List[] e;
boolean[] consider;
boolean[] visited;
int[] color;
boolean findOddCycle;
List side1, side2;
int[] side;
class TwoSides {
List side1, side2;
boolean canSwap;
}
List sideList;
void dfs(int x) {
if(visited[x]) return;
visited[x] = true;
if(side[x] == 0) {
if (color[x] == 1) {
side1.add(x);
} else {
side2.add(x);
}
}
int otherColor = 3 - color[x];
for(int i : e[x]) {
if(color[i] == color[x])
findOddCycle = true;
if(visited[i]) continue;
color[i] = otherColor;
dfs(i);
}
}
void addSides(int start, boolean canSwap) {
side1 = new ArrayList();
side2 = new ArrayList();
dfs(start);
TwoSides t = new TwoSides();
t.side1 = side1;
t.side2 = side2;
t.canSwap = canSwap;
sideList.add(t);
}
TwoSides findWays(int n1, int n2) {
int t = sideList.size();
boolean[][][] dp = new boolean[t+1][n1+1][n2+1];
boolean[][][] prev = new boolean[t+1][n1+1][n2+1];
dp[0][0][0] = true;
for(int i = 0; i < t; i++) {
for(int j = 0; j <= n1; j++) {
for(int k = 0; k <= n2; k++) {
if(dp[i][j][k]) {
{
int nj = j + sideList.get(i).side1.size();
int nk = k + sideList.get(i).side2.size();
if(nj <= n1 && nk <= n2) {
dp[i+1][nj][nk] = true;
prev[i+1][nj][nk] = false;
}
}
if(sideList.get(i).canSwap)
{
int nj = j + sideList.get(i).side2.size();
int nk = k + sideList.get(i).side1.size();
if(nj <= n1 && nk <= n2) {
dp[i+1][nj][nk] = true;
prev[i+1][nj][nk] = true;
}
}
}
}
}
}
for(int i = 0; i <= n1; i++) {
for(int j = 0; j <= n2; j++) {
if(dp[t][i][j]) {
TwoSides ret = new TwoSides();
ret.side1 = new ArrayList();
ret.side2 = new ArrayList();
int u = i;
int v = j;
int l = t;
while(l > 0) {
List to1 = null;
List to2 = null;
if(prev[l][u][v]) {
to1 = sideList.get(l-1).side2;
to2 = sideList.get(l-1).side1;
} else {
to1 = sideList.get(l-1).side1;
to2 = sideList.get(l-1).side2;
}
u -= to1.size();
v -= to2.size();
l --;
for(int val : to1) {
ret.side1.add(val);
}
for(int val : to2) {
ret.side2.add(val);
}
}
return ret;
}
}
}
return null;
}
public int[] findPermutation(int[] lef, int[] rig, int[] a, int[] b, int[] c) {
for(int i = 0; i < a.length; i++) {
for(int j = i+1; j < a.length; j++) {
if(a[i] == a[j] && b[i] == b[j] && c[i] != c[j])
return new int[]{};
if(a[i] == b[j] && b[i] == a[j] && c[i] != c[j])
return new int[]{};
}
}
prepare(lef, rig);
boolean[] mentioned = new boolean[n];
List[] ta = new List[n];
List[] tb = new List[n];
for(int i = 0; i < n; i++) {
ta[i] = new ArrayList();
tb[i] = new ArrayList();
}
belong = new boolean[n][n];
for(int i = 0; i < a.length; i++) {
ta[c[i]].add(a[i]);
tb[c[i]].add(b[i]);
int v = c[i];
belong[v][a[i]] = true;
belong[v][b[i]] = true;
while(v != 0) {
v = parent[v];
belong[v][a[i]] = true;
belong[v][b[i]] = true;
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(LCA[i][j] == i || LCA[i][j] == j) continue;
for(int k = 0; k < n; k++) {
if(belong[i][k] && belong[j][k]) {
return new int[]{};
}
}
}
}
int[] p = new int[n];
boolean[] assigned = new boolean[n];
List[] holes = new List[n];
for(int i = 0; i < n; i++) {
holes[i] = new ArrayList();
}
for(int i = n-1; i >= 0; i--) {
consider = new boolean[n];
for(int j = 0; j < ta[i].size(); j++) {
consider[ta[i].get(j)] = true;
consider[tb[i].get(j)] = true;
}
side = new int[n]; // 0 : not assign, 1 : left, 2 : right
List notAssigned = new ArrayList();
for(int j = 0; j < n; j++) {
if(consider[j]) {
if(assigned[j]) {
if(belong[lef[i]][j])
side[j] = 1;
else
side[j] = 2;
} else {
notAssigned.add(j);
}
}
}
for(int j = 0; j < ta[i].size(); j++) {
int u = ta[i].get(j);
int v = tb[i].get(j);
if(u == v && side[u] != 0) {
return new int[]{};
}
if((side[u] == 1 && side[v] == 1) || (side[u] == 2 && side[v] == 2)) {
return new int[]{};
}
}
if(notAssigned.size() == 0) {
if(lef[i] != -1) {
for (int v: holes[lef[i]]) {
holes[i].add(v);
}
}
if(rig[i] != -1) {
for (int v: holes[rig[i]]) {
holes[i].add(v);
}
}
holes[i].add(i);
} else {
boolean solved = false;
for(int r : notAssigned) {
consider[r] = false;
visited = new boolean[n];
e = new List[n];
color = new int[n];
for(int j = 0; j < n; j++) {
e[j] = new ArrayList();
}
for(int j = 0; j < n; j++) {
color[j] = side[j];
}
for(int j = 0; j < ta[i].size(); j++) {
int u = ta[i].get(j);
int v = tb[i].get(j);
if(u == r || v == r)
continue;
e[u].add(v);
e[v].add(u);
}
findOddCycle = false;
sideList = new ArrayList();
// parse components that have fixed color
for(int j = 0; j 0) {
addSides(j, false);
}
}
// then parse components don't have fixed color
for(int j = 0; j < n; j++) {
if(!visited[j] && consider[j] && color[j] == 0) {
color[j] = 1;
addSides(j, true);
}
}
consider[r] = true;
if(findOddCycle)
continue;
List holesLeft = new ArrayList();
List holesRight = new ArrayList();
if(lef[i] != -1) {
holesLeft = holes[lef[i]];
}
if(rig[i] != -1) {
holesRight = holes[rig[i]];
}
TwoSides ways = findWays(holesLeft.size(), holesRight.size());
if(ways == null) {
continue;
}
assigned[r] = true;
p[r] = i;
for(int j = 0; j < holesLeft.size(); j++) {
if(j < ways.side1.size()) {
assigned[ways.side1.get(j)] = true;
p[ways.side1.get(j)] = holesLeft.get(j);
} else {
holes[i].add(holesLeft.get(j));
}
}
for(int j = 0; j < holesRight.size(); j++) {
if(j < ways.side2.size()) {
assigned[ways.side2.get(j)] = true;
p[ways.side2.get(j)] = holesRight.get(j);
} else {
holes[i].add(holesRight.get(j));
}
}
solved = true;
break;
}
if(!solved) {
return new int[]{};
}
}
}
List unused = new ArrayList();
for(int i = 0; i < n; i++) {
if(!belong[0][i]) {
unused.add(i);
}
}
for(int i = 0; i < unused.size(); i++) {
p[unused.get(i)] = holes[0].get(i);
}
return p;
}
}