fork download 
  1. /*
  2.     Problem: Count Ways to Replace Missing Values and Make Adjacent Differences Valid
  3.     Company Tag: UI
  4.  
  5.     Problem Statement:
  6.         We are given an array arr.
  7.  
  8.         Some values are missing and are represented by 0.
  9.  
  10.         Every missing value can be replaced with a non-negative integer.
  11.  
  12.         The final array is good if:
  13.  
  14.             abs(arr[i] - arr[i - 1]) <= 1
  15.  
  16.         for every adjacent pair.
  17.  
  18.         Return the number of valid arrays modulo 1e9 + 7.
  19.  
  20.     Constraints:
  21.         1 <= n <= 500
  22.         0 <= arr[i] <= 10^9
  23.         At least one element in arr is non-zero.
  24.         Missing values are represented by 0.
  25.  
  26.     Simple Brute Force:
  27.         Try every possible value for every zero.
  28.  
  29.     Why Brute Force Fails:
  30.         Values can be very large, and there can be many zeros.
  31.  
  32.     Better Idea:
  33.         At least one value is fixed.
  34.  
  35.         Between two fixed values, the zero segment behaves like a walk:
  36.             from left fixed value to right fixed value,
  37.             where each step can change by -1, 0, or +1.
  38.  
  39.         Since n <= 500, the number of reachable values around a fixed value
  40.         is small enough for map-based DP.
  41.  
  42.     Dry Run:
  43.         arr = [2, 0, 3]
  44.  
  45.         The missing value must be close to both 2 and 3.
  46.  
  47.         Valid arrays:
  48.             [2, 2, 3]
  49.             [2, 3, 3]
  50.  
  51.         Answer = 2
  52.  
  53.     Time Complexity:
  54.         O(n^2)
  55.  
  56.     Space Complexity:
  57.         O(n)
  58. */
  59.  
  60. #include <bits/stdc++.h>
  61. using namespace std;
  62.  
  63. const long long MOD = 1000000007LL;
  64.  
  65. long long countFreeSide(long long fixedValue, int steps) {
  66.     /*
  67.         This handles zeros before the first fixed value
  68.         or after the last fixed value.
  69.  
  70.         We start from the fixed value and move step by step.
  71.     */
  72.     unordered_map<long long, long long> dp;
  73.  
  74.     dp[fixedValue] = 1;
  75.  
  76.     for (int step = 0; step < steps; step++) {
  77.         unordered_map<long long, long long> nextDp;
  78.  
  79.         for (auto item : dp) {
  80.             long long value = item.first;
  81.             long long ways = item.second;
  82.  
  83.             for (long long nextValue = value - 1; nextValue <= value + 1; nextValue++) {
  84.                 if (nextValue >= 0) {
  85.                     nextDp[nextValue] += ways;
  86.                     nextDp[nextValue] %= MOD;
  87.                 }
  88.             }
  89.         }
  90.  
  91.         dp = nextDp;
  92.     }
  93.  
  94.     long long totalWays = 0;
  95.  
  96.     for (auto item : dp) {
  97.         totalWays = (totalWays + item.second) % MOD;
  98.     }
  99.  
  100.     return totalWays;
  101. }
  102.  
  103. long long countBetweenFixedValues(long long leftValue, long long rightValue, int zeroCount) {
  104.     /*
  105.         This counts the ways to fill zeroCount values between:
  106.             leftValue ... rightValue
  107.     */
  108.     unordered_map<long long, long long> dp;
  109.  
  110.     dp[leftValue] = 1;
  111.  
  112.     for (int step = 0; step < zeroCount; step++) {
  113.         unordered_map<long long, long long> nextDp;
  114.  
  115.         for (auto item : dp) {
  116.             long long value = item.first;
  117.             long long ways = item.second;
  118.  
  119.             for (long long nextValue = value - 1; nextValue <= value + 1; nextValue++) {
  120.                 if (nextValue >= 0) {
  121.                     nextDp[nextValue] += ways;
  122.                     nextDp[nextValue] %= MOD;
  123.                 }
  124.             }
  125.         }
  126.  
  127.         dp = nextDp;
  128.     }
  129.  
  130.     long long totalWays = 0;
  131.  
  132.     for (auto item : dp) {
  133.         long long lastValue = item.first;
  134.         long long ways = item.second;
  135.  
  136.         // The last filled value must also be valid with the right fixed value.
  137.         if (llabs(lastValue - rightValue) <= 1) {
  138.             totalWays = (totalWays + ways) % MOD;
  139.         }
  140.     }
  141.  
  142.     return totalWays;
  143. }
  144.  
  145. int countGoodArrays(vector<int> arr) {
  146.     int n = arr.size();
  147.  
  148.     vector<int> fixedPositions;
  149.  
  150.     for (int i = 0; i < n; i++) {
  151.         if (arr[i] != 0) {
  152.             fixedPositions.push_back(i);
  153.         }
  154.     }
  155.  
  156.     long long answer = 1;
  157.  
  158.     int firstFixedPosition = fixedPositions[0];
  159.  
  160.     // Fill zeros before the first fixed value.
  161.     answer = (answer * countFreeSide(arr[firstFixedPosition], firstFixedPosition)) % MOD;
  162.  
  163.     // Fill zero segments between fixed values.
  164.     for (int i = 0; i + 1 < (int)fixedPositions.size(); i++) {
  165.         int leftPosition = fixedPositions[i];
  166.         int rightPosition = fixedPositions[i + 1];
  167.  
  168.         int zeroCount = rightPosition - leftPosition - 1;
  169.  
  170.         long long ways =
  171.             countBetweenFixedValues(arr[leftPosition], arr[rightPosition], zeroCount);
  172.  
  173.         answer = (answer * ways) % MOD;
  174.     }
  175.  
  176.     int lastFixedPosition = fixedPositions.back();
  177.  
  178.     // Fill zeros after the last fixed value.
  179.     answer =
  180.         (answer * countFreeSide(arr[lastFixedPosition], n - 1 - lastFixedPosition)) % MOD;
  181.  
  182.     return (int)answer;
  183. }
  184.  
  185. int main() {
  186.     int n;
  187.     cin >> n;
  188.  
  189.     vector<int> arr(n);
  190.  
  191.     for (int i = 0; i < n; i++) {
  192.         cin >> arr[i];
  193.     }
  194.  
  195.     cout << countGoodArrays(arr) << endl;
  196.  
  197.     return 0;
  198. }
Runtime error #stdin #stdout 0.04s 5308KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/7fZdge
language:
C++14 (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!