SEACO - Editorial

editorial
, , , ,
15

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

16

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

17

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");
	}
}
18

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

19

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

20

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 -


[1]


  [1]: https://www.codechef.com/viewsolution/15414725
21

can anyone provide an easy editorial for this problem…

1 Like
22

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

23

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.

24

can someone explain how to solve this using fenwick tree?

25

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

26

Can anyone give similar problem like this?

27

Sqrt decomposition technique works fine…AC in 0.33s

28

Solution using BIT. CodeChef: Practical coding for everyone

29

Finally was able to solve this after learning from the editorial about difference array. Here is my solution: [Yay! AC <3][1]
[1]: CodeChef: Practical coding for everyone

30

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

1 Like
31

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.

32

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
33

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

1 Like
34

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