Div. 4 rounds are usually about getting the implementation right the first time rather than finding a clever trick, and the opening problems of Round 806 fit that pattern closely. What follows is a walkthrough of A through F: the idea behind each one and the C++ that gets it accepted.
A. YES or YES?
The task is to decide whether a given string spells yes, ignoring letter case. Read the string, and only if its length is exactly 3 check the three characters one by one against both cases. Any mismatch — wrong letter or wrong length — means the answer is NO.
#include <bits/stdc++.h>
using namespace std;
void solve(){
string s;
cin >> s;
bool flag = 1;
if(s[0] != 'y' && s[0] != 'Y') flag = 0;
if(s[1] != 'e' && s[1] != 'E') flag = 0;
if(s[2] != 's' && s[2] != 'S') flag = 0;
if(s.size() == 3 && flag) cout << "YES" << endl;
else cout << "NO" << endl;
}
int main(){
int _;
cin >> _;
while(_--){
solve();
}
return 0;
}
B. ICPC Balloons
Each letter from A to Z stands for one problem. The first time a problem is solved, the team receives two balloons; every later solve of the same problem brings just one. So the total is simply two per distinct letter plus one per repeat.
Keep a boolean array indexed by character: when a letter shows up for the first time, add 2 and mark it; otherwise add 1. Summing over the input string in a single pass is enough.
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
typedef long long LL;
bool vis[N];
void solve(){
memset(vis,0,sizeof vis);
int n;
cin >> n;
LL cnt = 0;
while(n--){
char a;
cin >> a;
if(!vis[a]){
cnt += 2;
vis[a] = 1;
}
else cnt ++;
}
cout << cnt << endl;
}
int main(){
int _;
cin >> _;
while(_--){
solve();
}
return 0;
}
C. Cypher
There are n wheels, each showing a digit from 0 to 9. For every wheel the input gives the digit currently displayed and the sequence of moves that produced it, and the goal is to recover the starting digits. Nothing needs to be replayed step by step — only the net shift matters.
For each wheel, walk through its moves and accumulate an offset: a D contributes +1, a U contributes −1. Adding that offset to the final digit and reducing modulo 10 gives the original value. Writing the modulo as (digit + offset % 10 + 10) % 10 keeps the result non-negative even when the offset is negative.
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n;
int ans[N];
void solve(){
cin >> n;
for(int i = 1; i <= n; i ++) cin >> ans[i];
for(int i = 1; i <= n; i ++){
int m;
cin >> m;
int flag = 0;
while(m--){
char op;
cin >> op;
if(op == 'D') flag ++;
else flag --;
}
ans[i] = (ans[i] + flag % 10 + 10) % 10;
}
for(int i = 1; i <= n; i ++) cout << ans[i] << " ";
cout << endl;
}
int main(){
int _;
cin >> _;
while(_--){
solve();
}
return 0;
}
D. Double Strings
Given n strings of length at most 8, a string is marked 1 if it can be written as the concatenation of two other strings from the same collection, and 0 otherwise. A large n rules out comparing strings pairwise, but the short length is a gift.
Store every string in a set. Then, for each string, try each of its internal split points: the prefix is s[0..j-1], the suffix is s[j..end], with j running from 1 to len - 1. If both halves are found in the set, the string is marked 1 and the split loop stops. Strings of length 1 are skipped outright, since they cannot be split into two non-empty parts. The final verdicts are printed as one line of digits.
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n;
cin >> n;
bool vis[n + 10];
memset(vis,0,sizeof vis);
set<string> st;
string s[n + 1];
for(int i = 0; i < n; i ++){
cin >> s[i];
st.insert(s[i]);
}
for(int i = 0; i < n; i ++){
if(s[i].size() == 1) continue;
for(int j = 1; j <= s[i].size() - 1; j ++){
string s1 = s[i].substr(0,j), s2 = s[i].substr(j,s[i].size() - j);
if(st.count(s1) == 1 && st.count(s2) == 1){
vis[i] = 1;
break;
}
}
}
for(int i = 0; i < n; i ++){
if(vis[i]) cout << 1;
else cout << 0;
}
cout << endl;
}
int main(){
int _;
cin >> _;
while(_--){
solve();
}
return 0;
}
E. Mirror Grid
The grid is square and filled with 0s and 1s, and rotating it by 90, 180 and 270 degrees must produce exactly the same picture. Bits may be flipped to make that true, and the number of flips has to be minimal.
Rotating a cell (i, j) three times sends it to (j, n+1-i), then (n+1-i, n+1-j), then (n+1-j, i) before returning home, so the grid decomposes into groups of four cells that are forced to agree. Visit each group once, count how many of its four entries are 1 (call it cnt), and flipping the group costs either cnt flips to clear it or 4 - cnt flips to fill it — take the smaller. A visited array prevents a group from being counted more than once, and the centre cell of an odd-sized grid is skipped since it maps only to itself.
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
char mp[N][N];
bool st[N][N];
void solve()
{
int n;
cin >> n;
memset(st, 0, sizeof st);
for (int i = 1; i <= n; i++) cin >> mp[i] + 1;
int ans = 0;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
if(i == j && n % 2 == 1) continue;
if(!st[i][j]){
int cnt = 0;
if(mp[i][j] == '1') cnt++;
st[i][j] = 1;
if(mp[j][n - i + 1] == '1') cnt++;
st[j][n - i + 1] = 1;
if(mp[n - i + 1][n - j + 1] == '1') cnt++;
st[n - i + 1][n - j + 1] = 1;
if(mp[n - j + 1][i] == '1') cnt++;
st[n - j + 1][i] = 1;
ans += min(cnt, 4 - cnt);
}
}
}
cout << ans << endl;
}
int main(){
int _;
cin >> _;
while(_--){
solve();
}
return 0;
}
F. Yet Another Problem About Pairs Satisfying an Inequality
Count index pairs 1 <= i, j <= n with a[i] < i < a[j] < j. The double inequality splits neatly: the left part depends only on i, the right part only on j, and the middle link is i < a[j].
The first condition means a position can only serve if a[i] < i, so anything with a[i] >= i is dropped and never entered into the pool. Positions that survive are kept in a list in increasing order of index, which makes the list sorted for free. Now scan the array treating each position as j: the number of valid partners is the number of stored indices smaller than a[j], obtained with a lower_bound on the list. Add that count to the total, then insert the current index into the list and move on. Each insertion costs O(log n) and each query O(log n), well within bounds.
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 3;
int a[N];
typedef long long LL;
LL cnt;
vector<int> st;
void solve(){
int n;
cin >> n;
st.clear();
cnt = 0;
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 1; i <= n; i ++){
if (a[i] >= i) continue;
cnt += (lower_bound(st.begin(), st.end(), a[i]) - st.begin());
st.push_back(i);
}
cout << cnt << endl;
}
int main(){
int _;
cin >> _;
while(_--){
solve();
}
return 0;
}
One pattern runs through all six: the input size tells you where the cost has to go. Problems D and F look expensive until you notice that the strings are tiny in one case and that a single split point fixes the other, while E is only hard if you try to rotate the grid literally instead of tracking where each cell travels.