ADVITIYALOCK - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author:
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

Elementary combinatorics

PROBLEM:

Toofan has an array A, with elements between 0 and K. Each 0 can be replaced by an integer from 1 to K to obtain a candidate passcode.
Toofan will try every possible passcode that matches A. However, there’s no need to try both a passcode and its reverse.
How many passcodes must be tried in the worst case?

EXPLANATION:

Let c denote the number of zeros in A.
Clearly, there are K^c ways of replacing these zeros and obtaining a valid array B that matches A at the non-zero position.

Not all of these need to be counted. In particular, we can classify the arrays we obtain into three classes:

  1. B matches A, but \text{reverse}(B) doesn’t match A.
    Such arrays must be counted once, and are indeed counted only once.
  2. B matches A, \text{reverse}(B) matches A, and B = \text{reverse}(B), i.e. B is a palindrome.
    Such arrays must also be counted once, and are counted once currently.
  3. B matches A, \text{reverse}(B) matches A, but B \neq \text{reverse}(B).
    Here, only one of B and \text{reverse}(B) needs to be counted, but currently both of them are.

So, our goal is to count arrays of the third type, and subtract them from K^c to get the answer.
That is, we want to count the number of non-palindromic arrays such that the array and its reverse both match A.
This is equivalent to saying that B matches both A and \text{reverse}(A), so let’s see what such arrays look like.

Let R = \text{reverse}(A).
Then,

  • If R_i and A_i are both non-zero for some i, but R_i \neq A_i, then no array B matches both A and R.
    If this happens then there’s nothing to subtract, the answer is just K^c.
    This is case is trivial, so we proceed assuming it isn’t the case.
  • If either A_i or R_i is non-zero, the value of B_i is fixed to this non-zero value and we have no choice.
  • If both A_i and R_i are zero, B_i can technically take any of K choices.
    However, we need to ensure that palindromes aren’t counted, and that if B is counted, \text{reverse}(B) is not (since our aim is to subtract exactly one of them, not both).

There are a couple of ways of doing this, here’s one of them.
First, observe that after fixing the elements of B that are constrained by A and R = \text{reverse}(A), B will look something like a palindrome: if B_i is fixed, B_{N+1-i} will also be fixed to the same value.
For convenience, let’s just ignore such palindromic fixed positions, and pretend that B is filled with zeros - this is an equivalent problem since in practice we can just reduce N by the number of filled positions.

Now, we want B to not be a palindrome - so it must have some index i such that B_i \neq B_{N+1-i}.
Let’s fix the leftmost such index i.
Note that i must satisfy 2 i \leq N to be a valid leftmost differing index.
Then,

  • For indices j = 1, 2, 3, \ldots, i-1, B_j = B_{N+1-j} must hold, since i is the first differing position.
    • There are K^{i-1} ways to choose values for the prefix, which then also fixes the last i-1 elements.
  • B_i \neq B_{N+1-i} must hold.
    Further, to ensure that we don’t count both B and \text{reverse}(B), we can enforce B_i \lt B_{i+1}.
    • There are (K-1) + (K-2) + (K-3) + \ldots + 1 = \frac{K\cdot (K-1)}{2} ways to fix the values of B_i and B_{N+1-i} satisfying this.
      This is because B_i can be anything from 1 to K, and then B_{N+1-i} has K - B_i choices to be greater than it; so the above expression comes from trying all values of B_i.
  • There are N - 2i positions yet unfilled - they can take any value since we’ve already ensured that B is different from its reverse, and only one of them is being counted.

So, for each i such that 2i \leq N, we want to subtract K^{i-1}\cdot K^{N - 2i}\cdot \frac{K\cdot (K-1)}{2} = \frac{K\cdot (K-1)}{2} \cdot K^{N-1-i} from the answer.
Note that this is after reducing N to the number of zeros in the constrained B.

This is simple enough to do by just iterating through all values of i; and after performing all subtractions, we have our answer.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Tester's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

void solve(int test_case){
    ll n,k; cin >> n >> k;
    vector<ll> a(n+5);
    rep1(i,n) cin >> a[i];

    ll tot = 1, both_ways = 1, pal_ways = 1;
    rep1(i,n/2){
        ll j = n-i+1;
        ll x = (a[i]!=0), y = (a[j]!=0);
        if(x+y == 0){
            both_ways = both_ways*k%MOD*k%MOD;
            pal_ways = pal_ways*k%MOD;
            tot = tot*k%MOD*k%MOD;
        }
        else if(x+y == 1){
            tot = tot*k%MOD;
        }
        else{
            if(a[i] != a[j]){
                both_ways = pal_ways = 0;
            }
        }
    }

    if(n&1){
        if(a[ceil2(n,2)] == 0){
            tot = tot*k%MOD;
            both_ways = both_ways*k%MOD;
            pal_ways = pal_ways*k%MOD;
        }
    }

    ll sub = (both_ways-pal_ways+MOD)*((MOD+1)/2)%MOD;
    ll ans = (tot-sub+MOD)%MOD;
    cout << ans << endl;
}

int main()
{
    fastio;

    int t = 1;
    cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}
Editorialist's code (PyPy3)
mod = 10**9 + 7

for _ in range(int(input())):
    n, k = map(int, input().split())

    a = list(map(int, input().split()))
    b = a[::-1]
    yes, free = 1, 0
    for i in range(n):
        if a[i] + b[i] == 0:
            free += 1
        if a[i] == 0 or b[i] == 0: continue
        if a[i] != b[i]: yes = 0
    
    ans = pow(k, a.count(0), mod)
    if yes:
        pw = 1
        ways = (k * (k - 1) // 2) % mod
        for i in range(n):
            if a[i] > 0 or a[n-1-i] > 0: continue
            if i >= n-1-i: break
            
            free -= 2
            if free < 0: break

            ans -= ways * pw * pow(k, free, mod)
            pw = (pw * k) % mod
    print(ans % mod)
1 Like
mod=10**9+7
for _ in range(int(input())):
    n,k=map(int,input().split())
    arr=[int(i) for i in input().split()]
    x=y=0
    for i in range(n//2):
        if arr[i]==arr[n-i-1]:
            x+=(arr[i]==0)
        elif 0 in (arr[i],arr[n-i-1]):
            y+=1
        else:
            x=0
            break
    z=arr.count(0)
    # z -> total no. of zeros
    # x -> palindromic pair (both are 0s)
    # y -> palindromic pair (only one is 0)
    if x!=0:
        # if x is more than 0, we can reduce some pairs
        print((pow(k,z,mod)-pow(k,z-y-2*x,mod)*(pow(k,2*x,mod)-pow(k,x,mod))*500000004)%mod)
        # pow(k,z,mod) -> Total no. of ways
        # pow(k,z-y-2*x,mod) -> ways to decide non-palindromic 0s
        # 500000004 -> mod inverse of 2 (used for division by 2)
        # pow(k,2*x,mod) -> ways to decide 2*x zeros
        # pow(k,x,mod) -> no. of palindromes of 2*x digits
        # pow(k,2*x,mod)-pow(k,x,mod)-> This will give us all ways where the the resulting number was not a palindrome
        # Dividing this by 2 will give us all the ways that were repeated twice.
        # let's say we have 4 0s and each can be replaced by 1 or 2.
        # now, numbers of form 1111 or 2222 or 1221 or 2112 that are palindromes, will only occur once.
        # Rest all the numbers will occur twice
    else:
        print(pow(k,z,mod))
1 Like

“Further, to ensure that we don’t count both B and reverse(B), we can enforce B_i < B_(i+1)”

Looking at the follow-up to the above quote, it seems the statement should be B_(i) < B_(N+1-i)

Someone Please Help!!
https://www.codechef.com/viewsolution/1127787993
This is my solution for the problem , ofc everything is the same , the logic is the same , palindromic and non palindromic digit counting and then adding them up , the main issue i have is , in my code clearly tot >= palin (always) right ??
at most tot = palin , but tot can never be less than palin , so in line number 95 of my code , when i write (tot - palin)%mod and (tot - palin + mod)%mod , it shouldn’t create any difference right?? , but when i dont write + mod in there, the code gives wrong answer , else gets accepted . Any Explanations ??

The statement tot >= palin is not true.
Let’s say number k is raised by x.
Then (k power x) % MOD is always in between 0 and MOD - 1.
The following statement is not true (it is worth considering the following):
x > y => (k power x) % MOD > (k power y) % MOD
Hope it helps!

It is worth noting that (z - y - 2*x) <= 1.

Adding to the editorial

The summation can be further simplified as follows:

For code, see this:
submission

It helps a lot , later i figured it out actually once i used assert and got a RTE , but thanks for the explanation anyways !!!