COOKGAME - Editorial

[kingofnumbers]

PROBLEM LINK:

Contest
Practice

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 A_i = A_i-1 + 1 or A_i = 1, and A₁ = 1

Explanation

We know that if some number A_i is greater than 1, a previous number (at index i-1) must be equal to A_i - 1. If this number is also greater than 1, a number at index i-2 must be A_i - 2, and so on.
If we encounter inconsistency during this process (for example A_i = 17 and A_i-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 2^K 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 A_i+1 is known and is bigger than 1 then we can know the value of A_i so if A_i 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 A₁ = 1, after that we count the number of elements that are still not determined - let it be K - then output 2^K

time complexity: O(N)

Author’s and Tester’s Solutions

Setter
Tester

[rahulladda]

Though the editorial is for COOKGAME, all the links shared correspond to ADDMULT. You can check by clicking on it. Please update the links. Thank you.

[kingofnumbers]

it’s Fixed.