After my last AtCoder post, my performance in AtCoder did not improve as wished. I remained on doing the first three problems and failing on the fourth. I did get lucky with ABC295, and I was planning an article on that, but writing fun articles is time consuming. However, after the previous ABC, I had no excuse to not write an article on it. Records were broken that day, be prepared.
A – Treasure Chest and B – Trick Taking
There really isn’t a lot to say here, so I’ll just put the code here.
A
#include <iostream>
using namespace std;
int n, a = -1, b, pos;
string s;
int main() {
cin >> n >> s;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '*') pos = i;
if (s[i] == '|') {
if (a == -1) a = i;
else b = i;
}
}
if (pos > a && pos < b) cout << "in";
else cout << "out";
return 0;
}B
#include <iostream>
using namespace std;
int n, t, c[200001], r[200001], ans1, ans2, val1, val2;
bool x;
int main() {
cin >> n >> t;
for (int i = 1; i <= n; i++) cin >> c[i];
for (int i = 1; i <= n; i++) cin >> r[i];
for (int i = 1; i <= n; i++) {
if (c[i] == t) {
x = true;
if (r[i] > val1) {
ans1 = i;
val1 = r[i];
}
} if (c[i] == c[1] && r[i] > val2) {
val2 = r[i];
ans2 = i;
}
}
cout << (x ? ans1 : ans2);
return 0;
} C – Dango
In a string of length N made up of ‘-‘ and ‘o’, find the longest substring of length ≥2, consisting of entirely ‘o’s except for one end which is a ‘o’. The answer is the number of ‘o’s in this substring.
Well, this problem equates to finding the longest string of ‘o’s that is next to a ‘-‘. We can do this by enumerating all characters of the string and updating a counter depending on the character. If both ‘o’ and ‘-‘ exist, print the answer, otherwise print -1.
C
#include <iostream>
using namespace std;
int n, k = 0, ans;
string s;
bool x;
int main() {
cin >> n >> s;
for (int i = 0; i < n; i++) {
if (s[i] == 'o') k++;
else {
x = true;
ans = max(ans, k);
k = 0;
}
}
if (ans && x) cout << ans;
else cout << -1;
return 0;
}I also do like the problem proposer’s implementation, as it’s just very short and simple:
N, S = input(), input()
print(max(map(len, S.split('-'))) if 'o' in S and '-' in S else -1)D – Find By Query
There is an unknown binary string up to \(2\times 10^5\) characters in length. You only know that the first character is a 0 and the last character is a 1. You are given at most 20 queries: each query you can ask for the value at one index of the string. Print any index such that the character there and the character following it are different.
When I first saw this problem, I’ll admit, I went into a rage for 5 minutes. “What? They give you only 20 queries for a string that can be 20,000 characters long? Seriously?” Then I sat down and started to think. Then I solved it in my first try.
You see, if the first character is a 0, and the final character is a 1, there must be a change somewhere. Let’s assume that there’s just one place where the characters change, a ‘flip point’ you might say. Suppose our string is 001001011100001, but you don’t know that. You ask for the value of a character somewhere in the middle, and it’s a 1. Then, our string looks like this:
0——1——1
In the right half, we don’t know if there is a change or not, but in the left half, one is guaranteed. So, our next query should be in the left half. Continuing in this logic, we find our answer is 5:
0–0—1——1
0–0-1-1——1
0–001-1——1
In general, our query should be in the interval where the ends are distinct, and this will find our answer in a maximum of \(\lceil log_2(20,000)\rceil = 18\) queries. Thus the problem is solved quite simply.
#include <iostream>
using namespace std;
int n, l = 1, r, val;
int main() {
cin >> n;
r = n;
while (l + 1 < r) {
int mid = (l + r) / 2;
cout << "? " << mid << endl;
cin >> val;
if (val == 0) l = mid;
else r = mid;
}
cout << "! " << l;
return 0;
}At this point, with my 1000 points all racked up, I could have closed my computer and had a good night’s sleep. However, I was determined to push my limits, tackling, for the first time, problem
E – Nearest Black Vertex
There is a simple (no multi-edges or self-loops) connected undirected graph with N vertices and M edges. The \(i\)th edge connects vertices \(u_i \text{ and } v_i\). A person wants to colour each vertex black or white while satisfying K constraints. The \(i\)th constraint contains 2 numbers: \(p_i \text{ and } d_i\), meaning that the minimum distance between vertex \(p_i\) and a black-coloured vertex is exactly \(d_i\).
Input format:
\(N\ M\)
\(u_1\ v_1\)
\(\vdots\)
\(u_m\ v_m\)
\(K\)
\(p_1\ d_1\)
\(\vdots\)
\(p_k\ d_k\)
Once again, I lapsed into a state of deep thought and contemplation, which is virtually indistinguishable from depression. After nearly twenty minutes, I chanced upon the solution:
You see, if we assume that all nodes are painted black, if node 5 has to have a black node, say, a distance of 3 away, we can run a BFS function to simply paint all the nodes less than that distance white. Then we can check if any nodes at the correct distance are still black, as they might have been marked white by some other node’s constraints. Here is my cod–
DISCLAIMER: My code fails one test case which I don’t understand why. Therefore you will have to solve a puzzle to unlock it. Har har! Also sorry about the text colour being nearly unreadable in the answer.
#1. Five people check identical suitcases before boarding an airplane. At the baggage claim, each person takes one of the five suitcases at random. What is the probability that every person ends up with the wrong suitcase? Enter your answer as a fraction in simplest form.
The Twist
I had done better than ever before this contest. Although I fell short at the fifth problem, my rating would no doubt still skyrocket. But what’s this? A DDoS attack on the servers causing it to be down for 20 minutes? They’re declaring the contest unrated? NNNNNNNOOOOOOOOOOOOOOOO!!!!!!!!!
