SEACO - Editorial

PROBLEM LINK:

Practice

Contest

Author: Sergey Nagin

Tester: Jingbo Shang

Editorialist: Hanlin Ren

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Fenwick tree, difference array

PROBLEM:

You’re given an array a consisting of n zeros initially. You need to perform two kinds of commands:

  • Add 1 to a[l\sim r];
  • Perform all commands whose indices are in [l,r], where r<(the index of current command)

After performing these commands, output the final array.

QUICK EXPLANATION:

For each command, we need to count how many times it’s executed during the whole process, denoted by cnt[i]. We can iterate the commands backwards, and every time we meet a command 2\ l\ r which is executed k times, we add k to cnt[l\sim r]. When we know cnt[i] for every command i of type 1, we can easily figure out the answer by maintaining the difference array of a.

EXPLANATION:

subtask 1

brute force

We have n,m\le 10 and we can use brute force. We just write a procedure op(i) that performs the i-th operation, and do what the problem asks us to do:

op(i) :
	if type[i] == 1 then
		for j = l[i] to r[i] do
			a[j] += 1
	else //type[i] == 2
		for j = l[i] to r[i] do
			op(j)

a faster algorithm

Let f_{i,j} be the number of time that a[j] was increased when performing operation i.

For the first type, f_{i,j} is very easy to compute: if l_i\le j\le r_i, then f_{i,j}=1, otherwise f_{i,j}=0.

For the second type, a single operation i should be equivalent to the sum of all operations indexed in [l_i,r_i]. So for any j, f_{i,j} is the sum of f_{k,j}'s where l_i\le k\le r_i.

Once we know for every command, how many contribution it does to every element in array, we can compute the answer. Pseudocode:

f = [empty array of m*n]
for i = 1 to m do
	if type[i] == 1 then
		for j = l[i] to r[i] do
			f[i][j] = 1
	else
		for k = l[i] to r[i] do
			for j = 1 to n do
				f[i][j] = f[i][j] + f[k][j]
	//perform this operation
	for j = 1 to n do
		a[j] = a[j] + f[i][j]

The total time complexity is O(nm^2).

subtask 2

Let cnt[i] be the number of times that command i is executed. If we know cnt[1\sim m], this problem will become much easier.

How to compute cnt[]? We don’t know cnt[1] but we know cnt[m] must be 1. If the command m is of the form 2\ l_m\ r_m, then cnt[l_m\sim r_m] will increase by 1. Then we look at command m-1: originally its cnt is 1, however if it’s executed by command m then its cnt should be 2. Also this command might influence other cnt[]'s as well: if it’s of the form 2\ l_{m-1}\ r_{m-1}, then cnt[l_{m-1}\sim r_{m-1}] will increase by cnt[m-1]. Next we can consider cnt[m-2] and the same things happen again and again…

This gives us an algorithm to compute cnt[]. Initially all cnt[i]'s should be 1. Let’s then iterate the commands backwards. When we process a command i, if it’s of the form 2\ l\ r, we add cnt[i] to cnt[l\sim r]. Pseudocode:

cnt = [array of 1's]
for i = m downto 1 do
  if type[i] == 2 then
    for j = l[i] to r[i] do
      cnt[j] += cnt[i]

Once we know all cnt[]'s, for any command i of the form 1\ l\ r, we simply add cnt[i] to a[l\sim r].

The overall time complexity is O(nm).

subtask 3

We need to optimize the code above. When we need to add the same value on a segment, we may consider maintaining its difference sequence. Formally, let dcnt[i]=cnt[i]-cnt[i+1], then adding c to cnt[l\sim r] is equivalent to:

  • dcnt[r] \gets dcnt[r]+c;
  • dcnt[l-1]\gets dcnt[l-1]-c.

When we’re dealing with command i, cnt[i\sim M] is fixed(there won’t be modifications on them anymore). Thus we can calculate cnt[i] immediately, using the formula cnt[i]=dcnt[i]+cnt[i+1]. As we obtained cnt[i], we can update the array dcnt[] when i-th operation is type 2. Pseudocode:

dcnt = [array of 0's]
cnt[m + 1] = 1
for i = m downto 1 do
  cnt[i] = dcnt[i] + cnt[i + 1]
  if type[i] == 2 then
    dcnt[r[i]] += cnt[i]
    dcnt[l[i] - 1] -= cnt[i]

This gives an O(m) algorithm for computing cnt[].

We can use the same trick to obtain the final array: let da[i]=a[i]-a[i+1], then adding c to a[l\sim r] is equivalent to:

  • da[r]\gets da[r]+c;
  • da[l-1]\gets da[l-1]-c.

After all modifications are done, we calculate the suffix sum of da, and that’s the array a we want. Pseudocode:

da, a = [array of 0's]
for i = 1 to m do
  if type[i] == 1 then
    da[r[i]] += cnt[i]
    da[l[i] - 1] -= cnt[i]
for i = n downto 1 do
  a[i] = a[i + 1] + da[i]

The overall complexity is O(n+m).

ALTERNATIVE SOLUTION:

To maintain cnt[], you need to support two operations: adding on a segment and querying on one position. Since this problem has some special structure, it can be done in linear time. Generally such kind of problems can be solved in time O(m(\log m+\log n)), if you use data structures such as segment trees or Fenwick trees.

If your solution is different with ours, feel free to leave a comment.

AUTHOR’S AND TESTER’S SOLUTIONS:

Tester’s solution can be found here.
Editorialist’s solution can be found here.

4 Likes

For each command of type 1, we need to count how many times it’s executed, denoted by cnt[i]

actually we need to know that for operations of both types

You can also solve it by segment tree using lazy propagation for updating a range.

lazy propagation is an overkill here actually. Normal segtree would work. I used a segtree but now am realising that there was an even easier way using a difference array.

2 Likes

Access denied for tester’s and editorialist’s solution @r_64

yes, i realised that while solving it. There was no way 2k people would be able to solve it using segtrees.

1 Like

it usually happens they will just rectify it soon you must wait for sometime

The T\le3 allowed me to use square root decomposition here. Loved the feeling of AC. My solution is here

1 Like

The problem had extremely weak testcases.I initially wrote a brute force solution (O(n*m)) and it passed.


[1]


  [1]: https://www.codechef.com/viewsolution/15219911
3 Likes

I used an entirely different technique, no Trees, just using sum arrays and difference arrays.

First i used a loop from last command to first, only processing query type 2, maintaining a record how many times a query of type 1 is to be applied. For maintaining a record, i used a difference array, which you may see from my code.

After that, it’s a simple matter of applying query x of type 1, adding n[x] to range[left[x]] and subtracting n[x] from range[right[x]+1], where n[x] is the number of times a query is applied found in first loop and left[x] and right[x] are the left and right of given command.

The answer is simply a sum array of difference array made in second loop.

I know i have not explained this very well, so, feel free to ask me anything.
Please upvote if u find this helpful.

Here’s a link to my


[1]


  [1]: https://www.codechef.com/viewsolution/15202645
4 Likes

Actually there is an O(M+N) solution. You can see my code here.

Honestly I didnt expect it to cross 2k when I got AC for my sqrt decomposition method.

I did this question using frequency array for the commands. I used square-root decomposition to create the frequency array.

To add 1 to a specific range (for Query 1), I used a O(1) method. It is prefix array.

The logic is -

To add 1 in the range of l…r ->
Add 1 at index l, subtract 1 from index r+1.

Example :

Array : 0 0 0 0 0

l = 2, r = 4.

After operation :

Array : 0 1 0 0 -1

Prefix Sum array : 0 1 1 1 0 (Can be calculated at last)

l = 1, r = 4.

After operation :

Array : 1 1 0 0 -2

Prefix Sum array : 1 2 2 2 0

This way we can do the Query 1 operation in constant time.

You can visit this article for more applications on Prefix Sum Array : http://www.geeksforgeeks.org/prefix-sum-array-implementation-applications-competitive-programming/

The solution is here.

Can someone tell me ,why I am getting WA for last cases, I used BIT for both queries:
SOLUTION

I would be really thankful if someone tells me what is wrong with my code
Code : https://ideone.com/FUTR56

can anyone tell me why is my code wrong (link) and this is right (link), there is only one minor change.

@shubham_raj199 You just had to make a few changes. Hint : ( A - B ) MOD = ( A MOD - B MOD + MOD ) MOD . I’ve made a few changes to your code , here : https://www.codechef.com/viewsolution/15406455 . I’ve myself solved this problem using Fenwick Trees and I was also doing this same mistake.

1 Like

How to solve this question using segment tree ?

https://www.codechef.com/viewsolution/15316099
PLEASE CHECK MY CODE IT SHOWS RUNTIME ERROR AFTER 50 PTS.
I AM NOT ABLE TO GET ANY IDEA.

Can someone help me out and tell me what is wrong with my code.What I did was I iterated through all the commands backwards and for any command of type 2,first I did the query operation on the segment tree to find how many times that command was getting executed and then I performed an update operation on the segment tree in the range l to r of the type 2 command.And for all the type 1 commands if it was from l to r , all I did was first the query operation to get how many times it was getting executed(val) and then arr[l]+=val;ar[r+1]-=val; using the mod.

I was able to pass only subtask 1.
Here’s my code:

https://www.codechef.com/viewsolution/15378534