KiAsaGibona's blog

My Unsolved Problems From Round#(215 — 221)
By KiAsaGibona, 11 years ago, In English

Hi, I posted some comments on each of the following problem's tutorial blogs, but maybe those comments were not noticed ( As I understand maybe people normally not go to blogs of those problems which they already have solved ). So this is my attempt to get some help from you guys :) . I will posts my problems in comment section on this blog, so that I can get some help in reply section .

Thank you all. Have a nice day :)

The problems I am seeking help is

(This blog will be edited frequently )

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
11 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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);
        }
→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    First question: Use this anagram "xzyx" then you will only find the good substrings.

    The idea is to arrange a string in the form of xzyxzyxzy... After playing around with some test cases, you will notice that one can arrange such string, iff max{Cx, Cy, Cz} - min{Cx, Cy, Cz} ≤ 1, where Ci denotes the occurrences of character i. One can calculate Ci in some range [l, r] in O(1) by using prefix sum.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks GaryYe for your explanation.. Specially The idea is to arrange a string in the form of xzyxzyxzy << This part helped me to understand clearly :)

      → Reply
»
11 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

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

→ Reply