US Open 2022 Silver Contest Unofficial Editorial

Hi everyone! TL;DR

You may know me as the problem author for the Sleeping in Class (February 2022 Bronze Contest Problem 1) and Counting Liars (US Open 2022 Bronze Contest Problem 2) problems. You may also know me as a content author for USACO Guide. I am writing this blog to hopefully be able to help you understand how someone who got a perfect 1000 on this contest solved the problems; this is simply to help you understand the problems from an alternative perspective. Please read the disclaimer above for more information.

Problem 1: Visits

After reading the problem for a while, it can be observed that this problem is a graph problem. The problem essentially asks for the maximum sum of edge costs that has no cycles. This can be thought of as the maximum spanning tree of the graph. We can draw a directed edge between $$$i$$$ and $$$p_i$$$. Although we can run Prim's or Kruskals algorithm to find the maximum spanning tree, we can also think of this as a strongly connected components problem (SCC). Specifically, for each SCC, we can add the edge weight cost of each node in the SCC if there is exactly one node in the SCC. Otherwise, we should find the total cost of edge weights in that SCC and subtract the edge with the minimum edge cost. This can be shown to be the maximum cost for a given SCC since no cycles are included and the sum of the edge weights in the SCC is as large as possible. In terms of finding the SCCs efficiently, I used Kosajaru's algorithm to find the SCCs in $$$O(n + m)$$$ time. My C++ code can be found below:

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
using vl = vector<ll>;
using pl = pair<ll, ll>;
using vpl = vector<pl>;
 
#define forn(i, n) for(ll i = 0; i < n; i++)
#define pb push_back
#define f first
#define s second
 
const ll MAXN = 1e5;
 
vl adj1[MAXN], adj2[MAXN];
bool vis[MAXN];
stack<ll> s;
vl cycle;
 
void dfs1(ll v){
   vis[v] = true;
   for(ll u: adj1[v]){
       if(!vis[u]){
           dfs1(u);
       }
   }
   s.push(v);
}
 
void dfs2(ll v){
   vis[v] = true;
   cycle.pb(v);
   for(ll u: adj2[v]){
       if(!vis[u]){
           dfs2(u);
       }
   }
}
 
int main(){
   ll n; cin >> n;
   vl v(n);
   forn(i, n){
       ll a; cin >> a >> v[i];
       adj1[i].pb(a - 1);
       adj2[a - 1].pb(i);
   }
   forn(i, n){
       if(!vis[i]){
           dfs1(i);
       }
   }
   forn(i, n){
       vis[i] = false;
   }
   ll ans = 0;
   while(!s.empty()){
       ll cur = s.top(); s.pop();
       if(!vis[cur]){
           cycle.clear();
           dfs2(cur);
           if(cycle.size() == 1){
               ans += v[cycle[0]];
           } else {
               ll sumEdge = 0, minEdge = 1e9;
               forn(i, cycle.size()){
                   minEdge = min(minEdge, v[cycle[i]]);
                   sumEdge += v[cycle[i]];
               }
               ans += sumEdge - minEdge;
           }
       }
   }
   cout << ans << endl;
}

As always, please DM me if you have anything doesn't make sense, or you have any additional questions regarding my editorial/code.

Problem 2: Subset Equality

Note that this solution likely isn't the intended solution. However, it still works :).

Let's define a "character pair" $$$(a, b)$$$ as the number of times character $$$a$$$ comes before $$$b$$$. Note that characters $$$a$$$ and $$$b$$$ can be any letter between 'a' to 'r'. If two strings were equal after only keeping a certain substring of characters $$$q$$$, then the character pairs for the first string $$$s$$$ must be the same as the character pairs for the second string $$$t$$$ for all character pairs in substring $$$q$$$. We can precompute the number of character pairs $$$(a, b)$$$ for all characters from 'a' tor 'r' by maintaining a running total of all values of $$$a$$$ and fixing $$$b$$$. In other words, suppose that the number of occurrences of $$$a$$$ to the left of the fixed $$$b$$$ is $$$cnt_a$$$; we can add $$$cnt_a$$$ to $$$pairs[a][b]$$$, where $$$pairs[a][b]$$$ represents the number of character pairs for characters $$$a$$$ and $$$b$$$. We can iterate over all characters in substring $$$q$$$ (the provided query) and check if the $$$pairs[a][b]$$$ are consistent for both strings $$$s$$$ and $$$t$$$. This can be done in approximately $$$O(18^2 \times N)$$$ time. My C++ code can be found below:

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
using vl = vector<ll>;
using pl = pair<ll, ll>;
using vpl = vector<pl>;
 
#define forn(i, n) for(ll i = 0; i < n; i++)
#define pb push_back
#define f first
#define s second
 
ll pairs1[18][18], pairs2[18][18];
 
int main(){
   string s; cin >> s;
   string t; cin >> t;
   vl count1(18), count2(18);
   forn(i, s.length()){
       ll cur = s[i] - 'a';
       forn(j, 18){
           pairs1[cur][j] += count1[j];
       }
       count1[cur]++;
   }
   forn(i, t.length()){
       ll cur = t[i] - 'a';
       forn(j, 18){
           pairs2[cur][j] += count2[j];
       }
       count2[cur]++;
   }
   ll q; cin >> q;
   forn(i, q){
       string query; cin >> query;
       bool works = true;
       forn(i, query.length()){
           for(ll j = i; j < query.length(); j++){
               char c1 = query[i] - 'a', c2 = query[j] - 'a';
               if((pairs1[c1][c2] != pairs2[c1][c2]) || (pairs1[c2][c1] != pairs2[c2][c1])){
                   works = false;
               }
           }
       }
       if(works){
           cout << "Y";
       } else {
           cout << "N";
       }
   }
   cout << endl;
}

As always, please DM me if you have anything doesn't make sense, or you have any additional questions regarding my editorial/code.

Problem 3: COW Operations

After carefully writing out different input strings, we can observe that we can reduce a given input string down to 'C' if we get a resulting string of 'O', 'W', 'CO', 'CW', or 'CC', since there is no way to change these to a single 'C'. However, we can also notice that we can turn an 'OW' into a 'C', so we can consider each 'OW' as a 'C'. Additionally, notice that the configuration of the 'O's 'W's and 'C's don't matter as we can transform them down to the smaller substrings. All of these observations allows us to check if a string can be reduced down to a 'C' by counting the number of 'C's, 'OW's, and the remaining number of characters after all 'C's and 'OW's (or 'C') are considered separately. The following two conditions must hold true for a given string to be able to be reduced down to a 'C':

• The number of 'C's must be odd, since we can delete all but one 'C' if we decide to delete adjacent characters.
• The number of non 'C' or 'OW' characters must be even so that we can delete all of them by deleting adjacent characters.

Note that we assumed that the configuration of characters allows us to delete adjacent characters.

Given that, we can determine whether a given string can be reduced down to 'C' using only the number of 'C's, 'O's, and 'W's, we can answer each query by using prefix sums to count the frequency of each character between $$$l$$$ and $$$r$$$. My C++ code can be found below:

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
using vl = vector<ll>;
using pl = pair<ll, ll>;
using vpl = vector<pl>;
 
#define forn(i, n) for(ll i = 0; i < n; i++)
#define pb push_back
#define f first
#define s second
 
int main(){
   string s; cin >> s;
   ll q; cin >> q;
   ll n = s.length();
   vl c(n + 1), o(n + 1), w(n + 1);
   forn(i, n){
       c[i + 1] += c[i];
       o[i + 1] += o[i];
       w[i + 1] += w[i];
       if(s[i] == 'C'){
           c[i + 1]++;
       } else if(s[i] == 'O'){
           o[i + 1]++;
       } else {
           w[i + 1]++;
       }
   }
   forn(i, q){
       ll l, r; cin >> l >> r;
       ll sumC = c[r] - c[l - 1], sumO = o[r] - o[l - 1], sumW = w[r] - w[l - 1];
       ll ow = min(sumO, sumW), cons = max(sumO, sumW) - ow;
       if((sumC + ow + cons) & 1){
           if(cons % 2 == 0){
               cout << "Y";
           } else {
               cout << "N";
           }
       } else {
           cout << "N";
       }
   }
   cout << endl;
}

As always, please DM me if you have anything doesn't make sense, or you have any additional questions regarding my editorial/code.

Closing Thoughts

I hope you found my editorial helpful. I unfortunately don't qualify to write the Gold editorial, since I did significantly worse on that contest. As for everyone else, good luck, have fun and let me know if you have any questions by DMing me on CF.