PROBLEM LINK:
Author: Kevin Atienza
Testers: Sergey Kulik and Vasya Antoniuk
Translators: Vasya Antoniuk (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza
DIFFICULTY:
Cakewalk
PREREQUISITES:
Loops
PROBLEM:
You need to paint an N-millimeter-long 1D picture so that the i th millimeter has color C_i. You can only paint three consecutive millimeters at a time with the same color. When you color a section that already has a color, the old color is completely replaced by the new one. Is it possible to paint the picture?
QUICK EXPLANATION:
If there are three consecutive positions with the same colors, the answer is Yes, otherwise it is No.
EXPLANATION:
First off, you can’t just color entirely from left to right, or right to left, because that doesn’t always work! For example, if your target array is [1, 2, 2, 2, 3], then you can’t do it from left to right or right to left, but you can do it by first painting the first three positions 1 (to yield [1, 1, 1, 0, 0]), then the last three positions 3 (to yield [1, 1, 3, 3, 3]), and then the middle three positions 2 to yield the desired [1, 2, 2, 2, 3].
A crucial insight: There’s a particular class of target arrays that we can prove to be unachievable. Our operation always paints three consecutive positions at a time with the same color. Thus, after doing every operation, there must always be three consecutive positions with the same color. So if the target array doesn’t contain any three consecutive positions with the same color, then the answer is automatically No.
But what if there are three consecutive positions? It turns out that the answer is yes, and we can describe an algorithm that achieves the target array by coloring these three positions last!
Here’s an example: suppose our target array is [1, 9, 5, 5, 7, 2, 1, 1, 1, 3, 4, 2, 4]. Notice that there are three consecutive positions of the same color: [1, 1, 1], and so we can achieve this array as follows:
0 0 0 0 0 0 0 0 0 0 0 0 0
| | |
1 1 1 0 0 0 0 0 0 0 0 0 0
| | |
1 9 9 9 0 0 0 0 0 0 0 0 0
| | |
1 9 5 5 5 0 0 0 0 0 0 0 0
| | |
1 9 5 5 5 5 0 0 0 0 0 0 0
| | |
1 9 5 5 7 7 7 0 0 0 0 0 0
| | |
1 9 5 5 7 2 2 2 0 0 0 0 0
| | |
1 9 5 5 7 2 2 2 0 0 4 4 4
| | |
1 9 5 5 7 2 2 2 0 2 2 2 4
| | |
1 9 5 5 7 2 2 2 4 4 4 2 4
| | |
1 9 5 5 7 2 2 3 3 3 4 2 4
| | |
1 9 5 5 7 2 1 1 1 3 4 2 4
So the answer is now pretty simple: If there are three consecutive positions with the same colors, the answer is Yes, otherwise it is No. This can be coded as follows:
C++
#include <iostream>
using namespace std;
int C[100011];
int main() {
int z;
cin >> z;
for (int cas = 1; cas <= z; cas++) {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> C[i];
}
bool found = false;
for (int i = 2; i < n; i++) {
if (C[i-2] == C[i-1] && C[i-1] == C[i]) {
found = true;
break;
}
}
cout << (found ? "Yes" : "No") << endl;
}
}
Python
for cas in xrange(input()):
n = input()
a = map(int, raw_input().strip().split())
for i in xrange(2,n):
if a[i-2] == a[i-1] == a[i]:
print 'Yes'
break
else:
print 'No'
Implementation notes:
-
In the C++ code, we allocated the array before processing any queries. This is to save some time allocating and deallocating, which are expensive operations. Reusing the same array is faster.
-
Also, we allocated
100011instead of100000. This is to preempt off-by-one errors. In this problem, using100000is fine, but in some problems you sometimes need, for example, one more than necessary. Thus, adding a few extra cells in the array can sometimes save you a WA/RTE verdict. -
In Python, we use the
for..elseconstruct so we don’t need afoundflag. Also, we use the property that==, and other comparison operators, can be chained, e.g.a == b == c == dora < b <= c == d > e. In some languages, comparisons can’t be chained (or they don’t work as you might expect). -
It’s possible to not allocate any array at all and just compute the answer on the fly, like in the following:
#include <iostream> using namespace std; int main() { int z; cin >> z; for (int cas = 1; cas <= z; cas++) { int n; cin >> n; int C_prev = 0, C_curr = 0; bool found = false; for (int i = 0; i < n; i++) { int C_next; cin >> C_next; if (C_prev == C_curr && C_curr == C_next) { found = true; } C_prev = C_curr; C_curr = C_next; } cout << (found ? "Yes" : "No") << endl; } }Note that we initialized
C_prevandC_currto0because according to the constraints, all input values C_i are positive. Then after every check, we update their values. Finally, we removed thebreakstatement, otherwise you’ll stop before reading all N values, which is problematic for the next test case!
Time Complexity:
O(N)