You are not logged in. Please login at www.codechef.com to post your questions!

×

SEACO - Editorial

4
8

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.

This question is marked "community wiki".

asked 17 Aug '17, 18:06

r_64's gravatar image

7★r_64
261924
accept rate: 16%

edited 11 Sep '17, 17:15

admin's gravatar image

0★admin ♦♦
19.8k350498541


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 Code

link

answered 11 Sep '17, 15:55

taran_1407's gravatar image

5★taran_1407
4.0k31104
accept rate: 22%

Hii! Can u please elaborate why did u do the following steps for type 2:

if(command[i][0] == 2){ range[command[i][2]]+=t+1; range[command[i][1]-1] -= t+1; }
I mean I am not able to get why you add t+1 to range[command[i][2]] and subtract it from range[command[i][1]-1] and why not like you did in query of type 1!

Thanks :)

(15 Sep '17, 23:07) dishant_185★

Here, variable t is keeping the track how many times this particular command is to be executed within the previously processed commands of type 2.

In the problem, we are supposed to execute all the commands exactly once, so 1 is added for that execution in third loop.

Please UPVOTE, much needed...

Hope its clear now...

Feel free to ask anything..

(16 Sep '17, 00:00) taran_14075★
1

For example N = 3, M = 3

1 1 1

2 1 1

2 1 2

initially range array 0 0 0 0

During first loop

when i == 3

t is 0

we added (t+1) = 1 to range[2]

subtracted 1 from range[1-1]

range array becomes -1 0 1 0

i == 2

t = 1 (0 + range[2])

we added (t+1) = 2 to range[1]

subtracted 2 from range[0]

range array becomes -3 2 1 0

ignore i == 1

final range array -3 2 1 0

sum array 0 3 1 0 (using reverse loop)

From here, we can ignore commands of type 2 and see, command 1 is to be executed 3 times because of other commands + 1 time for its own, as i mentioned above.

Answer array is 4 0 0

(16 Sep '17, 00:02) taran_14075★

Thanks for the detailed explanation. But can u pls tell me how u came up with such a solution. I mean is this any standard algorithm? If yes, pls link some material where I can read more about it.
Thanks again :)

(16 Sep '17, 15:16) dishant_185★

@dishant_18

You can read more about difference arrays at

http://www.geeksforgeeks.org/prefix-sum-array-implementation-applications-competitive-programming/

example problem mentioned on that page is just the same...

(17 Sep '17, 05:50) taran_14075★

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

link

answered 11 Sep '17, 15:50

abx_2109's gravatar image

4★abx_2109
275111
accept rate: 0%

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

link

answered 11 Sep '17, 15:28

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066
accept rate: 18%

@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.

link

answered 11 Sep '17, 22:32

ash_maurya's gravatar image

4★ash_maurya
2374
accept rate: 0%

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

link

answered 07 Sep '17, 20:40

kingofnumbers's gravatar image

6★kingofnumbers ♦
204824
accept rate: 12%

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

link

answered 11 Sep '17, 15:08

akulgoel96's gravatar image

3★akulgoel96
1086
accept rate: 12%

2

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.

(11 Sep '17, 15:13) mathecodician6★
1

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

(11 Sep '17, 15:21) akulgoel963★

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

(11 Sep '17, 16:40) vijju123 ♦♦5★

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

link

answered 11 Sep '17, 15:18

devu_1234's gravatar image

1★devu_1234
584
accept rate: 0%

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

(11 Sep '17, 15:22) divik5444★

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

link

answered 11 Sep '17, 15:56

phben's gravatar image

6★phben
1493
accept rate: 9%

1

The editorial solution is O(n+m).

(12 Sep '17, 05:53) eugalt3★

Oh right. I misread the alternative solution.

(12 Sep '17, 06:07) phben6★

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.

link

answered 11 Sep '17, 18:14

rohitthapliyal's gravatar image

3★rohitthapliyal
319110
accept rate: 5%

edited 11 Sep '17, 18:19

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

link

answered 11 Sep '17, 19:05

shubham_raj199's gravatar image

5★shubham_raj199
621
accept rate: 0%

You need to use modulo arithmetic when implementing BIT.

(12 Sep '17, 06:02) eugalt3★

I used that but may not be correctly

(12 Sep '17, 17:43) shubham_raj1995★

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

link

answered 11 Sep '17, 19:30

cope's gravatar image

3★cope
1
accept rate: 0%

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

link

answered 11 Sep '17, 21:31

gauss14's gravatar image

4★gauss14
0
accept rate: 0%

How to solve this question using segment tree ?

link

answered 11 Sep '17, 23:22

kapildeshpande's gravatar image

2★kapildeshpande
1
accept rate: 0%

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.

link

answered 12 Sep '17, 00:08

jayantjain001's gravatar image

3★jayantjain001
1
accept rate: 0%

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

link

answered 12 Sep '17, 01:56

harsh24's gravatar image

3★harsh24
11
accept rate: 0%

@harsh24 I have used the same approach and got 100 points. I have added explanation just above, alongwith a link to my code.

Ask me anything if required..

Hers's the link

https://discuss.codechef.com/questions/108189/seaco-editorial/110993

Please upvote if u find that helpful..

(13 Sep '17, 12:42) taran_14075★

I saw your code . The last part of your approach is the same as mine.But I haven't yet found out the mistake in my code.Please tell me if you find any bug in my code. Thank you

(13 Sep '17, 18:57) harsh243★

Can anyone show some light on why we need the difference array? Thanks in advance!!

link

answered 12 Sep '17, 08:02

kunnu120's gravatar image

2★kunnu120
5189
accept rate: 5%

Because the alternative is to update the actual array, which will result in O (N) complexity per command, thus O (N^2) comolexity for whole task, giving TLE.

using difference array, u apply update in constant time.

I have used difference arrays only and got 100 points. I have added explanation just above, alongwith a link to my code.

Ask me anything if required..

Hers's the link

https://discuss.codechef.com/questions/108189/seaco-editorial/110993

Please upvote if u find that helpful..

(13 Sep '17, 12:47) taran_14075★

Can someone tell me what's wrong in my code? I used a 2-d array to store the array after each command. The command 1 executes normally. But for command 2, (2 l r) the array after last executed command is added with the array after command number 'r' and then subtracted with the array before command number 'l', hence adding the result of all the commands executing in [l, r] index to the current array. I know using a 2-d array won't work for higher test cases in c++, and not using a difference array would maybe take too much time but I couldn't get my program to work for even the second sub task (I got WA) while it worked fine for first sub-task. I just need to know what's wrong with this approach. And just for clarity, I also tried this approach with difference array. Still didn't work.

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <inttypes.h>
using namespace std;
#define max 1000000007

int main()
{
    int t;
    scanf("%d", &t);
    for(int i=0; i<t; i++)
    {
        int n, m;
        scanf("%d%d", &n, &m);
        int com[m][n];
        memset(com, 0, sizeof(com));
        for(int j=0; j<m; j++)
        {
            int c, a, b;
            cin>>c>>a>>b;
            if(c==1)
            {
                if(j==0)
                {
                    com[j][a-1]++;
                    com[j][b]--;
                }
                else
                {
                    for(int k=0; k<n; k++)
                    {
                        com[j][k]=com[j-1][k];
                    }
                    com[j][a-1]=(com[j-1][a-1]%max+1)%max;
                    com[j][b]=com[j-1][b]-1;
                }
            }
            else
            {
                if(a<2)
                {
                    for(int k=0; k<n; k++)
                    {
                        com[j][k]=(com[j-1][k]%max + com[b-1][k]%max)%max;
                    }
                }
                else
                {
                    for(int k=0; k<n; k++)
                    {
                        com[j][k]=(com[j-1][k]%max + com[b-1][k]%max - com[a-2][k]%max)%max;
                    }
                }
            }
            /*for(int k=0; k<n; k++)
            {
                printf("%d ", com[j][k]);
            }
            cout<<endl;*/
        }

        printf("%d ", com[m-1][0]);
        for(int j=1; j<n; j++)
        {
            com[m-1][j]=(com[m-1][j]%max+com[m-1][j-1]%max)%max;
            printf("%d ", com[m-1][j]);
        }
        printf("\n");
    }
}
link

answered 12 Sep '17, 10:04

sagrikak's gravatar image

3★sagrikak
1
accept rate: 0%

I was getting RZEC in python while the same logic in c++ was passing the first 2 subtasks...

link

answered 12 Sep '17, 11:50

viru_57's gravatar image

3★viru_57
-31
accept rate: 0%

Hi ,if any one knows why submission for SEACO is not allowed now?

link

answered 12 Sep '17, 19:54

bhagirathi08's gravatar image

3★bhagirathi08
01
accept rate: 0%

The contest has ended.

Now submission is not allowed for contest. U may solve the question in practice section using following link

This is the contest problem link.

Codechef.com/SEPT17/problems/SEACO

Just remove the contest name and ull be able to submit solution..

Following link

Codechef.com/problems/SEACO

(13 Sep '17, 12:50) taran_14075★

I coded according to the editorial only but getting WA in subtask 2 and 3, Can anyone tell me why? Here is the link to my code - Code

link

answered 13 Sep '17, 11:15

k1s6313's gravatar image

4★k1s6313
111
accept rate: 0%

can anyone provide an easy editorial for this problem...

link

answered 13 Sep '17, 18:58

mahendra25's gravatar image

3★mahendra25
102
accept rate: 0%

I did this problem in a different way. I used two segment trees with lazy propagation on both of them. My solution passed in 0.30 secs. segment tree for queries - segQ
segment tree for array - segA
First, I updated segQ with a val=1 (as every operation will be executed at least once). Then I ran a loop from m-1 to 0 and updated all the queries of type 2. Like for example for the 3rd sample test case of the problem, if the query was 2 1 5, then first I got the initial value on that node by doing query on segQ to get the no. of times this operation will be executed (say x) in future then with that value I updated the operations from 1 to 5 (i.e. l and r of the query) which means operations from 1 to 5 will be called x more times so add.
Then after that I ran a second loop from 0 to m-1 but this time for queries of type 1 and updated segA with the values for that particular command on my segQ. This is my full code

link

answered 13 Sep '17, 21:40

hemakshis's gravatar image

3★hemakshis
11
accept rate: 0%

edited 13 Sep '17, 21:41

If for commands we build the difference sequence in backward order, as the editorial does, but for the array we build it in forward order, then it is sufficient to just keep the running totals (without actually restoring the corresponding sum sequences).

Here is python solution.

link

answered 15 Sep '17, 23:14

eugalt's gravatar image

3★eugalt
2827
accept rate: 4%

edited 16 Sep '17, 06:33

Well, the essential point is given in the question itself,

"It's guaranteed that r is strictly less than the enumeration/number of the current command."

So, we run a loop in backward order, keeping track which command is to be executed how many times...

Well, a restore to actual sum sequence is required because after that, we are to provide for command type 1 also.

I have discussed my implementation in detail in the following link

https://discuss.codechef.com/questions/108189/seaco-editorial/110993

Please UPVOTE if you find this helpful...

(15 Sep '17, 23:31) taran_14075★

I am not sure what you are trying to say. You can see my code that just uses running totals of the difference arrays. Both command types are handled in a single pass starting from the last command.

(16 Sep '17, 00:42) eugalt3★

Well,

I don't really understand what you are missing here, because i code in java and not used to C language, so don't understand your code...

I think it depends upon the approach we are following. In your approach, as your code proved, There's no need to restore sum sequences...

But in my approach, you need to restore sum array atleast once to find number of executions of command 1...

So, in short, restoring sum array is dependent upon approach followed.

Hope that helps....

Please UPVOTE...

Feel free to ask anything...

(16 Sep '17, 01:24) taran_14075★

Illiteracy in popular programming languages does not justify your condescending attitude. ;)

(16 Sep '17, 09:02) eugalt3★

Well,

I'm a new programmer with just one year in java programming mate...

I meant to co-operate as much as i can...

I tried my best explaining to you my code, the query you asked as well as the difference in our approaches...

But when i cannot understand a code, how can i explain what's going on in the loop and statements...

Well, if you found my explanation / approach / effort or code, anything, Please Upvote...

Feel free to ask anything....

I'll be pleased to clarify your doubts... :)

(17 Sep '17, 00:41) taran_14075★

May be it is some kind of misunderstanding, but I honestly don't care about your code and have never asked you to explain to me anything about it. This is the editorial thread, in case you have not noticed. :)

(17 Sep '17, 01:54) eugalt3★

Oh Sure,

I merely tried to help.. :)

(17 Sep '17, 05:54) taran_14075★
showing 5 of 7 show all

can someone explain how to solve this using fenwick tree?

link

answered 18 Sep '17, 01:04

nikmul19's gravatar image

1★nikmul19
325
accept rate: 0%

can anyone explain hw dis can be solved using seg trees ??

link

answered 18 Sep '17, 01:38

msd_007's gravatar image

1★msd_007
3178
accept rate: 5%

Can anyone give similar problem like this?

link

answered 18 Sep '17, 17:37

parth_patel15's gravatar image

3★parth_patel15
123
accept rate: 0%

Sqrt decomposition technique works fine...AC in 0.33s

link

answered 20 Sep '17, 18:24

v_k_pandey98's gravatar image

4★v_k_pandey98
1
accept rate: 0%

link

answered 26 Sep '17, 20:02

garvitlnmiit's gravatar image

2★garvitlnmiit
1
accept rate: 0%

Finally was able to solve this after learning from the editorial about difference array. Here is my solution: Yay! AC <3

link

answered 03 Oct '17, 01:53

orlon's gravatar image

4★orlon
404
accept rate: 0%

Please, someone tells how to solve this problem using fenwick tree(Binary Index Tree). Share methods, not code. :)

link

answered 13 Oct '17, 22:51

python_rider's gravatar image

3★python_rider
1
accept rate: 0%

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∼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. Can anyone explain this.I am completely unable to understand.

link

answered 16 Nov '17, 05:26

gautamcse27's gravatar image

2★gautamcse27
375
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×1,723
×286
×171
×8

question asked: 17 Aug '17, 18:06

question was seen: 7,827 times

last updated: 16 Nov '17, 05:26