372C - Watching Fireworks is Fun

EDIT : Please scroll through the page for latest comment.

I have read DEGwer's editorial and tried to understand his code. But I can't figure out the sliding window part :(

As far I understood:

• if i is the order of firework ( i Can be Maximum m)
• and j is my position on main road ( At most 150000 positions)

if I am at State DP[ i ][ j ] I need to find out the maximum value between the interval from DP[ i-1 ][ j-x ] ... through .... DP[ i-1 ][ j ] .... to .... DP[ i-1 ][ j+x ]

Where x= available time(i.e t[ i ]- t[ i-1 ]) * D i.e DEGwer represents x as interval in his code

My Questions are:

• How the sliding window is used in this problem ?
• How the DQ is used to mentain the sliding window?
• The code segmented below is taken from DEGwer's code, in it he is poping out dq if dp[1 - p][dq[dq.size() - 1]] <= dp[1 - p][(int)j] I don't get this part :/

// Line 32-34 of the code linked in the editorial

 for (lint j = 1; j <= interval; j++){
            while (dq.size() && dp[1 - p][dq[dq.size() - 1]] <= dp[1 - p][(int)j]) dq.pop_back();
            dq.push_back((int)j);
        }

368C - Sereja and Algorithm

Given input: zyxxxxxxyyz query no 4 is: 1 4 which implies zyxx and answer for this query is YES

As far I understood:

• The string on which algorithm runs is zyxx
• I have to Find any continuous subsequence (substring) of three characters from zyxx which doesn't equal to either string "zyx", "xzy", "yxz"

But I don't understand:

• If I take yxx (i.e: last three characters) and permute it randomly, and again take last 3 characters which is nothing but a combination of y , x , x . I can run this process infinite times. So should not my ans will be NO .

• And I also can not understand Author Sereja's solution

Any suggestion will be a great hand :)

372C - Watching Fireworks is Fun

This comment is bulky and I apologize for that :)

/// This is the main part of Author's solution

for (int i = 0; i < M; i++)
     {
          deque<int> dq;
          lint interval = min((lint)N, (lint)(t[i] - pT) * D);

          for (lint j = 1; j <= interval; j++)
          {
               while (dq.size() && dp[1 - p][dq[dq.size() - 1]] <= dp[1 - p][(int)j]) dq.pop_back();
               dq.push_back((int)j);
          }

          for (lint j = 1; j <= (lint)N; j++)
          {
               lint k = j + interval;
               if (k <= (lint)N)
               {
                    while (dq.size() && dp[1 - p][dq[dq.size() - 1]] <= dp[1 - p][(int)k]) dq.pop_back();
                    dq.push_back((int)k);
               }
               dp[p][j] = dp[1 - p][dq[0]] + (lint)(b[i] - abs(a[i] - j));
               while (dq.size() && dq[0] <= (int)(j - interval)) dq.pop_front();
          }
          pT = t[i];
          p = 1 - p;
     }

I have a some confusions and allow me to describe them in order,

• How I am making the window ?

So as far I understand, my window must contain the index in which DP array holds the maximum value. So, It's obvious that when I am at state DP[ i ][ j ] , Best answer comes from the range of DP[ i-1 ][ j-interval ] .......... DP[ i-1 ][ j+interval ] . So, when I make the window I have to iterate through j-interval .... j+interval this range. But Author is iterating through only from 1 to interval for (lint j = 1; j <= interval; j++)

If I illustrate my thinking through an example, let

• I am at i th firework
• my position on main road is 15
• I have 1 sec time and my D value is 3

So, DP[ i ][ 15 ] must contain the maximum value from DP[ i ][ 12 ] .... DP[ i ][ 18 ] . So as my dq. But Sereja is making the dq in range from 1 to 3

 for (lint j = 1; j <= interval; j++)
          {
               while (dq.size() && dp[1 - p][dq[dq.size() - 1]] <= dp[1 - p][(int)j]) dq.pop_back();
               dq.push_back((int)j);
          }

How he is insuring that maximum value stay in this index range? What if maximum value stays at index 17? Please help me to understand