MAKEART - Editorial

PROBLEM LINK:

Contest
Practice

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 100011 instead of 100000. This is to preempt off-by-one errors. In this problem, using 100000 is 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..else construct so we don’t need a found flag. Also, we use the property that ==, and other comparison operators, can be chained, e.g. a == b == c == d or a < 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_prev and C_curr to 0 because according to the constraints, all input values C_i are positive. Then after every check, we update their values. Finally, we removed the break statement, otherwise you’ll stop before reading all N values, which is problematic for the next test case!

Time Complexity:

O(N)

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter
Tester 1
Tester 2

1 Like

I had compared my logic with many people and have found the same logic on all codes. Then why my code was giving wrong answer? Can I have the testcases that were run so as to know what had i missed? You may send it to me in private at email: bhatia2akshit@gmail.com

Even you have explained the same thing which i have implemented. I am naive hence this is not motivating me. Even in the last round the same thing had happened for k-good words. You must share the testcases at the end.

In Python, we use the for…else construct so we don’t need a found flag. Also, we use the property that
==, and other comparison operators, can be chained, e.g. a == b == c == d or a < b <= c == d > e. In some languages, comparisons can’t be
changed (or they don’t work as you might expect).

Changed should be chained??

1 Like

very naive though

@akshit21 Please provide the link of your code.

Yes, I also think so.

Thanks. Fixed!

https://www.codechef.com/viewsolution/10334835
This is the link of my code.
Thanks in advance…