You can avoid the additional logM if you push all the points beforehand instead of adding in the map in each query. It is guaranteed that the number of ranges having different values is of the order M.
Solution
1 Like
Oh, yeah, silly me 
How can we maintain dirction vector?
Iām done with all except the expected value one. I kind of know its to be done using FFT but Idk how. Can someone give a hint?
Yes, I could haveā¦but just thought I could save some spaceā¦
Cool ! I just thought to save some penulty minutes by writing simple code 
Thanks for the help.
Well, wow. The first link points to a 3300 rated problem 
. And somehow it seems 201 people solved it during the 2-hr contest (!!!). I have one question. HOW?
Second one Iāll tackle.
Here is a paper on a technique called āSliding Fast Fourier Transformā. It seems to be the closest thing I can get to an āonlineā fourier transform mentioned by @aryanc403 .
Does anyone have an āeasyā solution to BLWHTREE? My approach is very complicated.
I did something like this:
First for all nodes, maintain level link pointers (for binary lifting). This helps in finding the LCA. But also, maintain the level link pointers of only black nodes for each node. This helps in answering stuff like "If you have a node a and a node b which is a's ancestor, find the black node with least depth, in the a-b path (in fact letās denote this by \text{black}(a,b) to simplify our notation).
As a byproduct of the above, we can also query \text{last}(a) (the ālastā black node which is ancestor of a) in constant time.
Now, for each node store quantities v1,v2,v3. These are basically the answers for the given query for the root-node path, and having 1,2,3 (instead of 3 as in the question) nodes to be selected respectively.
Itās a bit clumsy but we can compute these values for a node from the values of its parent node and \text{last}(a) in \mathcal O (1) time (pretty obvious).
Also, if we have two nodes x,y such that y is an ancestor of x and is black, then we can calculate these above values for the x-y path from the values of x and y (what goes wrong if y is not black?)
So for any query, do this:
- Find P \equiv\text{LCA}(a,b) where a,b are the given nodes. Also, designate (and find) c = \text{black}(a,P) and d = \text{black}(b,P).
- Now find v1,v2,v3 for the a-c, c-d, d-b paths. For the first and last we can calculate it as shown above. For c-d note that all nodes on this path are white and their number is calculated from the depths of c,d,P. Now its just ^n C_r kind of stuff.
- Now from the above values compute your answer in \mathcal O (1) time. I didnāt write it out because it has 10 terms, clumsy.
I havenāt implemented it in code, but it should work.
Preprocessing takes \mathcal O(N \log N) time. For each query we take \mathcal O (\log N) time.
Overall: \mathcal O((N+Q) \log N) time.
can anyone share the code behind ROBOTS problem. I am having troubling taking into account the initial direction of the robot at (l)th point
Heyy, can you just explain what is the function of āelseā part in the shiftcomp function ? (where the index i+r or j+c is out of bounds)
If youāre using segment tree, then along with (x,y) store the angular shift caused by the set of commands and that due to commands 1...i as well. This will help you get rid of the issue.
If index (i+r) or (j+c) is out of bounds, the question says assume the cell to be 0(zero).
So, if (index within bounds) check if arr[i][j] == brr[i+r][j+c]
else check if arr[i][j] == 0.
Iāve just replaced brr[i+r][j+c] by zero, as per the problem statement.
To avoid this confusion, you can do as @ritesh1340 has done, declare a larger array so that you never go out of bounds, and initialize it to zero. That way you donāt need the if else conditions.
I am not using segment tree. hereās my code
#include <bits/stdc++.h>
using namespace std;
int main()
{
int tt;
cin >> tt;
for (int yy=0;yy<=tt-1;yy++)
{
int n,q;
cin >> n >> q;
char temp[n];
cin >> temp;
int arr[n];
for (int i=0;i<=n-1;i++)
{
arr[i]=int(temp[i])-48;
}
double x=0;
double y=0;
pair <double,double> position[n+1];
int orientation[n+1];
orientation[0]=0;
for (int i=0;i<=n-1;i++)
{
orientation[i+1]=(orientation[i]+arr[i])%6;
if (orientation[i+1]==0)
{
x=x+1;
}
if (orientation[i+1]==1)
{
x=x+0.5;
y=y+0.86602540;
}
if (orientation[i+1]==2)
{
x=x-0.5;
y=y+0.86602540;
}
if (orientation[i+1]==3)
{
x=x-1;
}
if (orientation[i+1]==4)
{
x=x-0.5;
y=y-0.86602540;
}
if (orientation[i+1]==5)
{
x=x+0.5;
y=y-0.86602540;
}
position[i+1].first=x;
position[i+1].second=y;
}
for (int i=0;i<=q-1;i++)
{
int l,r;
cin >> l >> r;
double x=position[r].first-position[l-1].first;
double y=position[r].second-position[l-1].second;
// deconfigure orientation[l-1];
int theta=orientation[l-1];
double x_real=(x*cos(theta))+(y*sin(theta));
double y_real=(y*cos(theta))-(x*sin(theta));
cout << fixed << setprecision(6) << x_real << " " << fixed << setprecision(6) << y_real << endl;
}
}
return 0;
}Well you can do this: instead of taking cases on the orientation declare a 2 x 6 array for the movements, and also have a separate array or vector for storing angle (like you have stored x and y).
At any moment take the two values at ((orientation number) + angle/60)%6 as you x and y displacement. As for updating the angle, you take that above expression and multiply by 60 which will give you current angle.
Oohhhā¦ I seeā¦ Sorry I overlooked the statement in the questionā¦
@rajs123 I have used brute force for all -n < dr < n, -m < dc < m but i am getting wrong answer can you please tell where i am wrong
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main(){
ll t; cin>>t;
while(tā){
int n,m; cin>>n>>m;
int a[n][m],b[n][m];
string s;
for(int i=0;i<n;i++){
cin>>s;
for(int j=0;j<m;j++){
a[i][j] = (s[j] - ā0ā);
}
}
for(int i=0;i<n;i++){
cin>>s;
for(int j=0;j<m;j++){
b[i][j] = (s[j] - ā0ā);
}
}
int dr = -n, dc = -m;
int ans = INT_MAX, r , c, cmp, tp;
while(dr < n){
dc = -m;
while(dc < m){
tp = 0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
r = i + dr;
c = j + dc;
if(r < 0 || r > n || c < 0 || c > m){
cmp = 0;
}
else{
cmp = b[r][c];
}
if(cmp != a[i][j]){
tp++;
}
}
}
ans = min(ans,tp);
dc++;
}
dr++;
}
cout<<"ANS "<<ans<<endl;
}
return 0;
}
You can look at this soln:
eCUP9U - Online C++0x Compiler & Debugging Tool - Ideone.com
It calculates number of moves made in each direction for [l, r] range and maps direction accordingly.
E.g: If arr is [2, 1, 0, 3, 2, 5] and range is [3, 4].
Total degrees before 3rd index = 3*60 . So for 3rd index, (3*60) degree turn is done on top of initial 3*60, so total degrees moved = 6*60 == 0*60
1 Like
You can check this:
2talgN - Online C++0x Compiler & Debugging Tool - Ideone.com
Also just a tip for sharing code, you can use: https://ideone.com/