COOKGAME - Editorial

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 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)

Author’s and Tester’s Solutions

Setter
Tester

1 Like

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.

1 Like

it’s Fixed.