You can also solve it by segment tree using lazy propagation for updating a range.
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
5 Likes
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 : Prefix Sum Array - Implementation and Applications in Competitive Programming - GeeksforGeeks
The solution is here.
I would be really thankful if someone tells me what is wrong with my code
Code : FUTR56 - Online C++ Compiler & Debugging Tool - Ideone.com
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 : CodeChef: Practical coding for everyone . 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:
Can anyone show some light on why we need the difference array?
Thanks in advance!!
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");
}
}I was getting RZEC in python while the same logic in c++ was passing the first 2 subtasks…
Hi ,if any one knows why submission for SEACO is not allowed now?
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/15414725can anyone provide an easy editorial for this problem…
1 Like