Single Round Match 753 Editorials
Div II Easy: KerimJavati
For each l like L, it takes 2 * distance(‘a’, L) + 1 seconds for Kerim to type it.
Time complexity is O(text.size())
public static int howLong(String text) {
int ans = 0;
for (char c : text.toCharArray())
ans += 1 + 2 * (c - 'a');
return ans;
}
Div II Medium: CCChecker2
Simulate the process, several things to check:
All elements in arrays int[] moveStartRow, int[] moveStartCol, int[] moveDestRow, int[] moveDestCol, must be between 1 and n.
Never two cubes could take the same position.
Cubes must arrive at their destination at the end.
Moves must be valid.
Time complexity is O(moves * m), could be improved to O(moves + m + n ^ 2).
public static String check(int n, int[] startRow, int[] startCol, int[] destRow, int[] destCol, int[] moveStartRow, int[] moveStartCol, int[] moveDestRow, int[] moveDestCol){
int m = startCol.length, moves = moveStartCol.length;
if (checkArray(n, moveDestRow) || checkArray(n, moveStartRow) || checkArray(n, moveDestCol) || checkArray(n, moveStartCol))
return "invalid";
for(int i = 0; i < moves; i++) {
int id = -1;
for(int j = 0; j < m; j++)
if(startRow[j] == moveStartRow[i] && startCol[j] == moveStartCol[i])
id = j;
for(int j = 0; j < m; j++)
if(startRow[j] == moveDestRow[i] && startCol[j] == moveDestCol[i])
return "invalid";
if(abs(moveStartCol[i] - moveDestCol[i]) + abs(moveStartRow[i] - moveDestRow[i]) != 1)
return "invalid";
if(id == -1)
return "invalid";
startCol[id] = moveDestCol[i];
startRow[id] = moveDestRow[i];
}
for(int j = 0; j < m; j++)
if(startRow[j] != destRow[j] || startCol[j] != destCol[j])
return "invalid";
return "valid";
}
private static boolean checkArray(int n, int[] destRow) {
for(int x : destRow)
if(x < 1 || x n)
return true;
return false;
}
Div II Hard: MaxCutFree
Consider bridges, they form a forest graph, solve the problem for each tree of this forest independently. Now the problem is converted to find the maximum independent set in a tree (a set that no two vertices out of that are adjacent). Use Dynamic Programming. For each vertex, keep two values:
Close: Answer for the subtree of this vertex.
Open: Answer for the subtree of this vertex if you don’t choose this vertex.
Now, dp[root].close is the answer.
public static class Edge{
int v, u;
public Edge(int v, int u) {
this.v = v;
this.u = u;
}
}
public static class Dp{
int open, close;
public Dp(int open, int close) {
this.open = open;
this.close = close;
}
}
public static final int maxn = (int) 3e5 + 17;
static int edge[], comp[], h[], gp, d[], cnt[];
static boolean bl[];
static boolean seen[];
static ArrayList<ArrayList<Integer g = new ArrayList<();
static Edge e[] = new Edge[maxn];
static int hi(int v, int p){
int ret = h[v];
seen[v] = true;
int parEdge = 0;
for(int i : g.get(v)){
int u = edge[i] ^ v;
if(!seen[u]){
h[u] = h[v] + 1;
int t = hi(u, v);
if(t == h[u])
bl[i] = true;
ret = min(ret, t);
}
else if(u != p && u != v)
ret = min(ret, h[u]);
else if (u == p)
parEdge++;
}
if(parEdge 1)
ret = min(ret, h[v] - 1);
return ret;
}
static void hello(int v){
cnt[ comp[v] = gp ]++;
for(int i : g.get(v)){
int u = edge[i] ^ v;
if(!bl[i] && comp[u] == -1)
hello(u);
}
}
static void build_tree(int m){
for(int i = 0; i < m; i++)
if(bl[i]) {
g.get(e[i].v).add(e[i].u);
g.get(e[i].u).add(e[i].v);
}
}
static Dp dfs(int v, int p){
seen[v] = true;
Dp ans = new Dp(0, 1);
for(int u : g.get(v))
if(u != p) {
Dp child = dfs(u, v);
ans.open += child.close;
ans.close += child.open;
}
ans.close = max(ans.close, ans.open);
return ans;
}
static public int solve(int n, int a[], int b[]){
int m = a.length;
edge = new int[maxn];
comp = new int[maxn];
h = new int[maxn];
d = new int[maxn];
cnt = new int[maxn];
bl = new boolean[maxn];
seen = new boolean[maxn];
comp = new int[n];
g = new ArrayList<();
for(int i = 0; i < n; i++)
g.add(new ArrayList<());
Arrays.fill(comp, -1);
for(int i = 0; i < m; i++) {
int v = a[i];
int u = b[i];
//System.err.println(v + " " + u);
e[i] = new Edge(v, u);
edge[i] = v ^ u;
g.get(v).add(i);
g.get(u).add(i);
}
for(int i = 0; i < n; i++)
if(!seen[i])
hi(i, -1);
for(int i = 0; i < n; i++)
if(comp[i] == -1){
hello(i);
cnt[gp] = cnt[gp] - 1;
gp++;
}
g = new ArrayList<(n);
for(int i = 0; i < n; i++)
g.add(new ArrayList<());
build_tree(m);
Arrays.fill(seen, false);
int ans = 0;
for(int i = 0; i < n; i++)
if(!seen[i])
ans += dfs(i, -1).close;
return ans;
MojisBag:
Keep trie of numbers at each moment and two elements that maximize the answer, e1, and, e2.
If number x added to the bag, at first try to update the answer and if updated, update e1 and e2. Then add x to trie. Time complexity: O(log MAXV).
If number x become removed from the bag, remove it from trie. If it’s e1 or e2, clear trie, insert elements one by one again and update the answer. Time complexity: O(q * log MAXV) if x is e1 or e2, O(log MAXV) otherwise.
What do you think about time complexity? The point is because queries are generated randomly, the probability of that x equals to e1 or e2 is 2 / n. So the mathematical expectation of time complexity is: q * (2 / q * q * log MAXV + (q - 2) / q * log MAXV) = q log (q).
static class Node {
int cnt, index;
Node left;
Node right;
public Node() {
cnt = 0;
left = null;
right = null;
index = -1;
}
}
static class Pair {
int key, value;
public Pair(int key, int value) {
this.key = key;
this.value = value;
}
}
static Node root = new Node();
static void insert(int value, int index) {
Node cur = root;
cur.cnt++;
for (int i = 31; i = 0; i--) {
if (((1 << i) & value) == 0) {
if (cur.left == null) {
cur.left = new Node();
}
cur = cur.left;
}
else {
if (cur.right == null) {
cur.right = new Node();
}
cur = cur.right;
}
cur.cnt++;
}
cur.index = index;
}
static void remove(int value) {
Node cur = root;
root.cnt--;
for (int i = 31; i = 0; i--) {
if (((1 << i) & value) == 0) {
cur = cur.left;
}
else {
cur = cur.right;
}
cur.cnt--;
}
}
static Pair getMax(int value) {
Node cur = root;
if(root.cnt == 0)
return new Pair(-1, 0);
int res = 0;
for (int i = 31; i = 0; i--) {
int add = 0;
if (((1 << i) & value) == 0) {
if (cur.right != null && cur.right.cnt != 0) {
cur = cur.right;
add++;
}
else {
cur = cur.left;
}
}
else {
if (cur.left != null && cur.left.cnt != 0) {
cur = cur.left;
add++;
}
else {
cur = cur.right;
}
}
res = 2 * res + add;
}
return new Pair(cur.index, res);
}
public static int maximumXor(int q, int base, int add, int rate) {
final int Mod = (int) 1e9 + 7;
int ans = 0;
int a[] = new int[q];
int y[] = new int[q];
int z[] = new int[q];
boolean deleted[] = new boolean[q];
int cur = 0, sz = 0, cera = -1, cerb = -1;
for(int i = 0; i < q; i++){
cur = (int) (((long) cur * base + add) % Mod);
if(cur % rate != 0){
//System.out.println("+ " + cur);
Pair tmp = getMax(cur);
if(ans < tmp.value){
ans = tmp.value;
cera = sz;
cerb = tmp.key;
}
insert(cur, sz);
a[sz++] = cur;
}
else if(sz 0){
int remIndex = cur % sz;
//System.out.println("- " + remIndex + " (" + a[remIndex] + ")");
if(!deleted[remIndex]) {
deleted[remIndex] = true;
remove(a[remIndex]);
if (remIndex == cera || remIndex == cerb) {
root = new Node();
ans = 0;
cera = cerb = -1;
for (int j = 0; j < sz; j++)
if(!deleted[j]){
Pair tmp = getMax(a[j]);
if (ans < tmp.value) {
ans = tmp.value;
cera = j;
cerb = tmp.key;
}
insert(a[j], j);
}
}
}
}
y[i] = ans;
//System.out.println("= " + ans);
}
z[0] = y[0];
for(int i = 1; i < q; i++)
z[i] = (int) (((long) z[i - 1] * base + y[i]) % Mod);
return z[q - 1];
}
MojiDeletes:
Consider xor of range [L, R] be X, we are searching for some i (L <= i <= R), such that maximizes the value X ^ a[i];
We know how to find value maximizing xor in a trie (like problem 706D from codeforces). Let’s keep a trie for each prefix of the array, name the trie constructed from numbers in the range [0, i], t[i]. For each node, keep count of the number of nodes in its subtree. Now, for answering query [L, R], we can subtract values written on nodes in t[L] from t[R + 1], from this trie we can find the answer.
One problem remains. Time complexity is now O(n ^ 2 * log MAXV). The key idea is to use persistent trie instead of constructing n tries, it reduces the time complexity to O(n * log MAXV).
private final static int Mod = (int) 1e9 + 7;
static class PersistentTrie
{
int node;
int left[],right[],data[];
int maxN=20000001;
PersistentTrie()
{
node=0;//0 is dummy node
left=new int[maxN];
right=new int[maxN];
data=new int[maxN];
}
/**Finds the number in this trie which maximizes xor with val.
* @param n is the root number of the version which is being queried.
* @param val is a 32 bit positive integer.
* @return A value from trie which maximizes the xor with val.
*/
int queryMax(int n, int m, int val)
{
int ans=0;
int y=1<<30;
while(y0)
{
if((val&y)0)//current bit is 1
{
if(data[left[m]] - data[left[n]]!=0)
{
ans+=y;
n = left[n];
m = left[m];
}
else if(data[right[m]] - data[right[n]]!=0) {
n = right[n];
m = right[m];
}
else
return ans;
}
else//current bit is 0
{
if(data[right[m]] - data[right[n]]!=0)
{
n=right[n];
m = right[m];
ans+=y;
}
else if(data[left[m]] - data[left[n]]!=0)
{
m = left[m];
n=left[n];
}
else
return ans;
}
y=1;
}
return ans;
}
/**
* Insert the value val in the trie version with root n.
* @param n Root number of trie version in which insertion is to be done.
* @param val Value to be inserted.
* @param y pow(2,30) in this case.
* @return
*/
int insert(int n,int val,int y)//returns the root of new trie
{
//create a new node
int cur=++node;
if(y==0)
{
data[cur]=1+data[n];
return cur;
}
if((val&y)0)//current bit is 1
{
left[cur]=left[n];
data[cur]=data[left[n]];
int r=insert(right[n],val,y1);
right[cur]=r;
data[cur]+=data[r];
}
else
{
right[cur]=right[n];
data[cur]=data[right[n]];
int l=insert(left[n],val,y1);
left[cur]=l;
data[cur]+=data[l];
}
return cur;
}
}
public static long maximumXor(int n, int q, int base, int add, int qBase, int qAdd){
PersistentTrie pt = new PersistentTrie();
int a[] = new int[n + 1];
int ps[] = new int[n + 1];
int root[] = new int[n + 1];
root[0] = ps[0] = a[0] = 0;
for(int i = 1; i <= n; i++) {
a[i] = (int) (((long) a[i - 1] * base + add) % Mod);
root[i] = pt.insert(root[i - 1], a[i], 1 << 30);
ps[i] = ps[i - 1] ^ a[i];
//System.out.print(String.valueOf(a[i]) + ' ');
}
//System.out.println();
int cur = 0;
long ans = 0;
while(q-- 0){
cur = (int) (((long) cur * qBase + qAdd) % n);
int l = cur;
cur = (int) (((long) cur * qBase + qAdd) % n);
int r = cur;
if(r < l) {
int t = l;
l = r;
r = t;
}
ans += pt.queryMax(root[l], root[r + 1], ps[r + 1] ^ ps[l]);
//System.out.println(String.valueOf(l + 1) + ", " + String.valueOf(r + 1) + " = " + pt.queryMax(root[l], root[r + 1], ps[r + 1] ^ ps[l]));
}
return ans;
}