PROBLEM LINK:
Author: Hasan Jaddouh
Testers: Kamil Debowski
Editorialist: Hasan Jaddouh
Difficulty:
Easy-medium
Pre-requisites:
combinatorics
Problem Statement:
Given an array A of length N, some of its elements are missing and they are replaced with -1, you are required to count number of ways to fill missing elements such that Ai = Ai-1 + 1 or Ai = 1, and A1 = 1
Explanation
We know that if some number Ai is greater than 1, a previous number (at index i-1) must be equal to Ai - 1. If this number is also greater than 1, a number at index i-2 must be Ai - 2, and so on.
If we encounter inconsistency during this process (for example Ai = 17 and Ai-1 = 10), there are 0 ways (we can print 0 and proceed to the next test case).
in addition we can determine that first element is equal to 1.
now after we determined the values of all elements that can be determined we count the number of elements that can’t be determined and let’s say their number is K then the answer is simply 2K that’s because every element of them can have two possibilities, either it is equal to previous element+1 or it’s equal to 1
determining the value of all elements that can be determined in O(N)
We iterate over the array from the end to the beginning when we are at index i, if Ai+1 is known and is bigger than 1 then we can know the value of Ai so if Ai is equal to -1 we just set its new value, otherwise if it’s known from the input we should make sure that it’s consistent
the last thing is to make sure A1 = 1, after that we count the number of elements that are still not determined - let it be K - then output 2K
time complexity: O(N)