fork download
copy 
  1. /*
  2.     Problem: Sum of Travel Times with Toggling Lights
  3.     Company Tag: Infosys OA
  4.  
  5.     Problem Statement:
  6.         We are given a binary array v of length n.
  7.  
  8.         v[i] = 1 means light is initially ON.
  9.         v[i] = 0 means light is initially OFF.
  10.  
  11.         There are positions from 0 to n.
  12.  
  13.         To move from position x to x + 1:
  14.             light at position x + 1 must be ON.
  15.  
  16.         Each move takes 1 second.
  17.         Each wait also takes 1 second.
  18.  
  19.         After every second:
  20.             all lights toggle.
  21.  
  22.         For every pair (i, j), where 0 <= i < j <= n:
  23.             calculate minimum travel time from i to j.
  24.  
  25.         Return sum of all travel times modulo 1e9 + 7.
  26.  
  27.     Constraints:
  28.         Exact constraints were not mentioned.
  29.         This solution is O(n), so it works for large n.
  30.  
  31.     Brute Force:
  32.         For every pair, simulate movement and toggling.
  33.  
  34.     Why Brute Force Fails:
  35.         There are O(n^2) pairs.
  36.         Simulation for each pair is too slow.
  37.  
  38.     Optimized Idea:
  39.         Every pair (i, j) represents one substring of lights.
  40.  
  41.         For first light:
  42.             ON  -> cost 1
  43.             OFF -> cost 2
  44.  
  45.         For next lights:
  46.             If current light is different from previous light -> cost 1
  47.             Otherwise -> cost 2
  48.  
  49.     Explanation Block:
  50.         Instead of simulating every substring, I calculate contribution.
  51.  
  52.         Contribution types:
  53.             1. First light of every substring.
  54.             2. Adjacent transition inside substrings.
  55.  
  56.         For transition between i - 1 and i:
  57.             It appears in i * (n - i) substrings.
  58.  
  59.     Dry Run:
  60.         v = [1, 0]
  61.  
  62.         Pairs:
  63.             (0, 1): time = 1
  64.             (1, 2): time = 2
  65.             (0, 2): time = 2
  66.  
  67.         Total = 5
  68.  
  69.     Time Complexity:
  70.         O(n)
  71.  
  72.     Space Complexity:
  73.         O(1)
  74. */
  75.  
  76. #include <bits/stdc++.h>
  77. using namespace std;
  78.  
  79. using ll = long long;
  80.  
  81. const ll MOD = 1000000007LL;
  82.  
  83. long long sumOfTravelTimes(vector<int>& v) {
  84.     int n = v.size();
  85.  
  86.     long long ans = 0;
  87.  
  88.     // Contribution of first light of every substring.
  89.     for (int i = 0; i < n; i++) {
  90.         // If first light is ON, move directly.
  91.         // If OFF, wait once and then move.
  92.         long long cost = (v[i] == 1 ? 1 : 2);
  93.  
  94.         // Number of substrings starting at i.
  95.         long long count = n - i;
  96.  
  97.         ans = (ans + cost * count) % MOD;
  98.     }
  99.  
  100.     // Contribution of adjacent transitions.
  101.     for (int i = 1; i < n; i++) {
  102.         // If current light differs from previous,
  103.         // movement takes 1 second.
  104.         // Otherwise, wait + move = 2 seconds.
  105.         long long cost = (v[i] != v[i - 1] ? 1 : 2);
  106.  
  107.         // Transition between i - 1 and i appears in i * (n - i) substrings.
  108.         long long count = 1LL * i * (n - i);
  109.  
  110.         ans = (ans + cost * (count % MOD)) % MOD;
  111.     }
  112.  
  113.     return ans;
  114. }
  115.  
  116. int main() {
  117.     vector<int> v = {1, 0};
  118.  
  119.     cout << sumOfTravelTimes(v) << endl;
  120.  
  121.     return 0;
  122. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
5
https://ideone.com/mx8qgX
language:
C++14 (gcc 8.3)
created:
1 day 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!