Single Round Match 803 Editorials

SRM 803 Editorial by Arpa and misof.

Don’t be tired (it’s a phrase that after class is finished in school or university Persians say).

The goal of statements was to clarify the challenges of marriage. It was my fourth round at TopCoder. I’m proud of setting this contest and ready to have your feedback.

The test data for the whole set was prepared in less than 24 hours. I predict that div. 1 participants will have a hard time solving problems.

At the very beginning of the contest an issue happened, in the Circling problem the value to be returned was not clearly stated. We are sorry for the confusion this caused.

MarriageAndTravellingChallage

This problem just needs a little observation. Consider the word P be the word that produced S after the echo. For example if P = “abcde”, S = “abbcccddddeeeee”.

We can notice that:

P[0] = S[0]
P[1] = S[1]
P[2] = S[3]
P[4] = S[6]
P[5] = S[10]
…

(These are the indices of the first occurrence of each letter of P in S.)

Let A be the sequence {0, 1, 3, 6, 10, 15, 21, …}. (In maths, these numbers are called triangular numbers.) Then, P[i] = S[A[i]].

The rule behind the sequence A is A[0] = 0 and A[i] = A[i - 1] + i. Also, A[i] = i * (i - 1) / 2.

Here is my code:

public static String solve(String S) {
String ans = "";
for (int i = 0, j = 1; i < S.length(); i += j++) {
ans += S.charAt(i);
}
return ans;
}


MarriageAndChargingChallenge

The first thing we can notice is that we can start only from a position where there is a relative: if we start anywhere else, the phone will shut down immediately.

So our task is for any relative, check if we can start from it and do a complete cycle. It’s just a simulation task. Keep current charge and go step by step from a relative to the next one, subtract distance from charge, if some time charge < 0, we can’t start from this relative. Otherwise it will be ok.

Python solution by misof:

def solve(self, circuitLength, station, charge):
N = len(station)

distance = []
for n in range(N-1): distance.append( station[n+1] - station[n] )
distance.append( circuitLength + station[0] - station[N-1] )
charge = list(charge)

answer = 0
for start in range(N):
fuel = 0
allOK = True
for f, d in zip( charge, distance ):
fuel += f
fuel -= d
if fuel < 0: allOK = False
if allOK: answer += 1
distance = distance[1:] + [distance[0]]
charge = charge[1:] + [charge[0]]

return answer


Java solution by me:

public static int solve(int forumLength, int[] relative, int[] greeting) {
int n = relative.length;
int ans = 0;
for (int i = 0; i < n; i++) {
int cur = 0;
boolean good = true;
for (int j = i; j < i + n; j++) {
cur += greeting[j % n];
int dist = relative[(j + 1) % n] - relative[j % n];
if (j == n - 1)
dist = forumLength - relative[n - 1] + relative[0];
cur -= dist;
good &= cur = 0;
}
ans += good ? 1 : 0;
}
return ans;
}


MarriageAndCyclingChallenge

Let’s fix A, C. To prevent overcounting, we fix that A is the smallest out of all four numbers on the cycle and thus we only iterate over C > A.

For each A, C, let’s calculate the possible options for selecting B and D. Note that B and D can be selected independently. Also, B and D can’t be the same. (We don’t actually need to do anything in our code: in any valid solution we must have the edges A->B and D->A and that implies that B and D cannot be the same person.)

Let’s count the candidates for B: these are all vertices v such that there is an edge from A to v and from v to C. The situation for D is reversed.

Now we multiply the options we have for selecting B and the options we have for selecting D. Again, to stop overcounting we just count the possible B, D which are greater than A.

The code below makes the solution clear.

Java code by me:

public static int state;
public static boolean[][] g, rg;

public static int rnd() {
state = (int) (((long) state * 1103515245 + 12345) % (1 << 31));
return state % 100;
}

public static long solve(int N, int threshold, int state) {
MarriageAndCirclingChallenge.state = state;
g = new boolean[N][N];
rg = new boolean[N][N];
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
if (rnd() < threshold)
rg[j][i] = g[i][j] = true;
else
rg[i][j] = g[j][i] = true;
}
}
long ans = 0;
for (int i = 0; i < N; i++)
for (int j = i + 1; j < N; j++) {
int c1 = 0, c2 = 0;
for (int k = i + 1; k < N; k++) {
c1 += g[i][k] & rg[j][k] ? 1 : 0;
c2 += rg[i][k] & g[j][k] ? 1 : 0;
}
ans += c1 * c2;
}
return ans;
}


The above solution runs in O(N^3) time. It can easily be improved to O(N^3 / W), where W is the size of the machine word, by using bitmasks to compute set intersections. (E.g., candidates for B are the intersection of the people loved by A and the people who love C.)

Other iteration orders are possible. E.g., we can simply iterate over all valid A,B,C to compute the number of paths of length 2 from A to C, for each (A,C), and then we can do the same thing as above: multiply the number of paths from A to C and the number of paths from C to A.

MarriageAndSelectionChallenge

The tricky condition from the problem statement says that whenever you invite two people from the same party, everyone invited between them must also be from the same party. Thus, in the final string each letter has to form one contiguous segment.

When we go from left to right through the given sequence S and decide whom to invite, the current state of the construction can always be described by two parameters: the set of letters we have already used, and the index of the last person invited. (The second parameter implies which letter is the “current” one.) These will be our states.

What about the transitions? If we know our current state, we have the option to terminate there, or we can add another letter. The letter must be either the same as the current letter, or one of the letters that haven’t been used so far. We can iterate over all those options.

Once we have picked the next letter, we know we can greedily take its earliest occurrence. (Any solution that uses a later occurrence of the same letter can be changed into one that uses the immediately next one.)

This information (for each index i and each letter j, if we start at i, what is the first occurrence of j?) is easy to precompute in linear time by going backwards through the string.

And now we have everything we need. First, we can use dynamic programming to compute, for each state, what is the maximum number of letters we can still add to the string. This gives us the length of the optimal solution. And once we know that, we can construct the lexicographically smallest optimal solution by starting with the empty string and then always appending the smallest letter that still leads to some optimal final solution. (Here we reuse the values previously computed by dynamic programming.)

Java code by misof:

public String solve(String S) {
int N = S.length() + 1;
int[] party = new int[N];
int[][] memo = new int[N][1<<12];
int[][] dalsi = new int[N][12];

// we add a sentinel: a new character 0 that differs from
// everyone else and is always selected -- so our starting
// state is “we are at 0 and no actual letters are used”
party[0] = -1;
for (int n=1; n<N; ++n) party[n] = S.charAt(n-1)-'a';

// precompute dalsi[i][j] = the next occurrence of character
// j after position i
for (int i=0; i<12; ++i) dalsi[N-1][i] = -1;
for (int n=N-2; n=0; --n) {
for (int i=0; i<12; ++i) dalsi[n][i] = dalsi[n+1][i];
dalsi[n][party[n+1]] = n+1;
}

for (int last=N-1; last=0; --last) {
for (int present=0; present<(1<<12); ++present)
if (last == 0 || ((present & 1<<party[last]) != 0)) {
int answer = 0;
for (int i=0; i<12; ++i)
if (i == party[last] || ((present & 1<<i) == 0)) {
int nxt = dalsi[last][i];
if (nxt != -1)
answer = Math.max( answer, 1 + memo[nxt][present | 1<<i] );
}
memo[last][present] = answer;
}

int optlength = memo[0][0];

String answer = "";
int last = 0, present = 0;

while (answer.length() < optlength) {
for (int i=0; i<12; ++i) if (i == party[last] || ((present & 1<<i) == 0)) {
int nxt = dalsi[last][i];
if (nxt != -1 && answer.length() + 1 + memo[nxt][present|1<<i] == optlength) {
answer += (char)('a'+i);
last = nxt;
present = present | 1<<i;
break;
}
}
}
return answer;
}


MarriageAndGamingChallenge

Welcome to the last problem.

Fact 1: The groom wins if and only if each number in range [lo, hi] appears even number of times. (In these cases the groom always covers an edge with the same weight as the one chosen by the bride. If any number appears an odd number of times, the bride’s first move will be to the smallest such number and then she can follow the same strategy.)

Fact 2: Let path(v, u) be a boolean array of length N, where path(v, u)[x] is 1 iff x appears in the path from v to u odd number of times, groom wins iff there is no 1 in [lo, hi].

Fact 3: path(v, u) = path(0, v) ^ path(0, u). By ^ we mean xoring each element with the same element in the other array (just like bitset in C++).

Fact 4: Given v, u, hi, we want to find the minimum lo which path(0, v)[lo:hi + 1] = path(0, u)[lo:hi + 1]. I’m using Python syntax, by A[L:R] I mean A[L], A[L + 1], A[L + 2], …, A[R - 1].

This can be done using persistent segment tree. 

Let S[v] = path(0, v). S[0] is simply an array with N zeros. Let v be the parent of u and the weight of this edge be w, S[u] is almost the same as S[v], just flipping the w-th bit.

We keep S’s in the persistent segment tree. In each node we keep the hash of elements in subtree of this node.

We can simply flip a bit in the segment tree and update it.

The harder part is to find the minimum lo which S[v][lo:hi+1] = S[u][lo:hi+1]. The easier method is to do this job in O(log^2 N). Use binary search and get hash from both of the segment trees and compare them. The O(log N) method is more complex, refer to the code.

The overall time complexity is O((N + Q) log N). The memory complexity is O(N log N + Q).

Java solution by me:

public class MarriageAndGamingChallenge {
static final int MAX_N = (int) 1e5 + 14, MOD = aLargeRandomPrime;
static int state, N;
static int[] po = new int[MAX_N];
static Node[] root = new Node[MAX_N];
static ArrayList<Edge[] g;

public static class HashKeeper {
int hash, len;

public HashKeeper(int hash, int len) {
this.hash = hash;
this.len = len;
}

public HashKeeper merge(HashKeeper r) {
return new HashKeeper((int) (((long) hash * po[r.len] + r.hash) % MOD), len + r.len);
}

public boolean equals(HashKeeper o) {
return hash == o.hash && len == o.len;
}

}

public static class Node {
HashKeeper hash;
Node left, right;

void build(int l, int r) {
if (l + 1 == r) {
hash = new HashKeeper(0, 1);
return;
}
int mid = (l + r) / 2;
left = new Node();
right = new Node();
left.build(l, mid);
right.build(mid, r);
hash = left.hash.merge(right.hash);
}

void update(Node guide, int p, int l, int r) {
if (l + 1 == r) {
hash = new HashKeeper(guide.hash.hash == 0 ? 1 : 0, 1);
return;
}
int mid = (l + r) / 2;
if (p < mid) {
left = new Node();
left.update(guide.left, p, l, mid);
right = guide.right;
} else {
right = new Node();
right.update(guide.right, p, mid, r);
left = guide.left;
}
hash = left.hash.merge(right.hash);
}

int get_left(Node other, int e, int l, int r) {
if (e = r) {
if (this.hash.equals(other.hash))
return l;
else if (l + 1 == r)
return r;
} else if (e <= l)
return l;
int mid = (l + r) / 2;
int ans = right.get_left(other.right, e, mid, r);
return ans == mid ? left.get_left(other.left, e, l, mid) : ans;
}
}

public static class Edge {
int u, w;

public Edge(int u, int w) {
this.u = u;
this.w = w;
}
}

public static int rnd() {
state = (int) (((long) state * 1103515245 + 12345) & (1 << 31) - 1);
return state;
}

static void dfs(int v) {
for (Edge edge : g[v]) {
root[edge.u] = new Node();
root[edge.u].update(root[v], edge.w, 0, N);
dfs(edge.u);
}
}

public static long solve(int N, int D, int state, int B, int P, int Q) {
po[0] = 1;
for (int i = 1; i < MAX_N; i++) {
po[i] = po[i - 1] * 2 % MOD;
}
MarriageAndGamingChallenge.state = state;
MarriageAndGamingChallenge.N = N;
g = new ArrayList[N];
for (int i = 0; i < N; i++) {
g[i] = new ArrayList<Edge();
}
int[] parent = new int[N];
for (int i = 1; i < N; i++) {
parent[i] = max(0, i - 1 - (rnd() % D));
}
int[] bank = new int[B];
for (int i = 0; i < B; i++) {
bank[i] = rnd() % N;
}
for (int i = 1; i < N; i++) {
int w;
if (rnd() % 100 < P)
w = rnd() % N;
else
w = bank[rnd() % B];
g[parent[i]].add(new Edge(i, w));
}
root[0] = new Node();
root[0].build(0, N);
dfs(0);
long ans = 0;
for (int t = 0; t < Q; t++) {
int v = rnd() % N;
int u = rnd() % N;
int hi = rnd() % N;
int q_ans = hi - root[v].get_left(root[u], hi + 1, 0, N) + 1;
ans += q_ans;
}
return ans;
}
}