PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Hasan
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Basic Geometry, Trigonometry, Prefix sums/Segment Tree.
PROBLEM:
The Chefland city consists of the infinite two-dimensional grid, and all the junctions form a hexagonal grid, as depicted in the image.
- Two junctions are at positions (0, 0) and (0, 1) in grid.
- Each junction J is connected by line segments with six other junctions. These junctions are the vertices of a regular hexagon with side length 1 and their distances from J are also all equal to 1.
Chef created a robot that can traverse the junctions. Initially, it is in some junction and oriented towards another junction which is connected to it by a line segment. The robot accepts a string of instructions — decimal digits 0 through 5. It executes the instructions one by one and stops after executing the final instruction. When the robot executes an instruction denoted by a digit d,
- It first rotates by 60 \cdot d degrees counterclockwise.
- It moves 1 unit forward, to the junction, it is oriented towards.
There is a string S of length N containing instructions written by Chef, you need to answer Q queries, each query giving a substring of S and you are required to print the final position of Robot, assuming Robot starts at junction (0, 0) facing towards junction (0, 1). Queries are independent from each other.
QUICK EXPLANATION
- We can notice that If we can find the displacement in terms of x and y coordinate for a subarray of steps, and the start direction for the same subarray, we can rotate the axes by specified angle in opposite direction.
- In order to compute displacement, we can simulate the process once and store positions and directions after each instruction. For any subarray [L, R], We can remove displacement caused by the first L-1 instructions from the displacement after R steps. Directions can also be similarly calculated.
EXPLANATION
There are multiple approaches to this problem, (Setter, Tester, and Editorialist all used different ways to do the same thing).
For each query, the coordinates of Robot before instructions are (0, 0) and angle with the positive x-axis is 0 \degree
From trigonometry, we know that moving d units in direction \theta with positive x changes x-coordinate by d*cos(\theta) and y-coordinate by d*sin(\theta)
If you don't believe the above statement
First assume \theta \leq 90\degree, you can make a right triangle with hypotenuse length d and one angle \theta, say \triangle ABC such that \angle ABC = 90\degree and \angle CAB = \theta, |AC| = d and AB parallel to x-axis, then it can be proven that |AB| gives displacement along positive x-axis and |BC| gives displacement along y-axis.
Now, in the instructions, we always move 1 unit, so d is always 1 for rest of this editorial. Suppose we know, that we need to move in direction \theta\degree from positive x-axis, coordinates by (cos(\theta), sin(\theta)).
So, Initially we have \theta = 0\degree and current position (0, 0) and instructions x is
- Set \theta = \theta+60*x\degree
- Move one step in direction \theta
We can simulate the above process for each query, which results in O(Q*N) time complexity, which isn’t fast enough here.
Let us suppose the robot already executed all N instructions, and we know the position as well as the direction it is facing after each instruction. This we can easily compute using the above process for instructions from 1 to N in order.
Now, let us suppose the position of Robot and angle from positive x-axis after instruction L-1 to be (x_1, y_1) and \theta' and position of after instruction R to be (x_2, y_2)
Now, let us shift origin to point (x_1, y_1) to eliminate the effect of first L-1 instructions. Position (x_2-x1, y_2-y1) in new coordinate system is the position of the robot starting from position (0, 0) and facing direction \theta' and executing directions from L to R.
The only thing needs to be corrected here is the initial direction, and we can achieve it by rotating of axes by -\theta' \degree anti-clockwise direction, hence obtaining the final position after executing the instructions from L to R
Rotation of axes
Keeping Origin as a fixed point, if we rotate axes by \theta, new coordinates of point (x, y) is (x*cos(\theta)-y*sin(\theta), x*sin(\theta)+y*cos(\theta)). You can find the details here
Setter’s idea
Setter used the segment tree where a node corresponding to range [L, R] denote the findal position of robot if instruction [L, R] is executed on robot from initial position. The merge function rotates the right node by final angle after all instructions in left node and shift right node displacement to end position after left node displacement.
Time complexity O((Q+N)*log(N))
Tester’s idea
Let’s number the directions from 0 to 5. He computed the number of moves in each direction assuming instructions from 1 to N and direction after each instruction. If the direction after instruction L-1 is di, then number of steps in direction dd is the number of steps in direction (dd-di) \pmod 6 in range [L, R]. We already know how to compute the shift for each direction. Apply it for each direction separately.
Time complexity O(N+Q)
Editorialist’s idea
Let’s compute the positions and direction robot is facing after each instruction, assuming start direction is d*6\degree for each 0 \leq d < 6 separately.
The idea is, for a query (L, R), find the initial direction for which after L-1 instructions, the final direction would be 0\degree. We have completely avoided rotation of axis and if we shift origin to the position of the robot after L-1 instructions, position after instruction R in the new coordinate system gives the required position of the robot.
Time complexity O(N+Q)
TIME COMPLEXITY
The time complexity is O(N+Q) or O((Q+N)*log(N)) per test case depending upon implementation.
SOLUTIONS:
Setter's Solution
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
#include <assert.h>
using namespace std;
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
assert(cnt>0);
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
struct sgt{
int rot[3];
int head;
};
void rotate(sgt & a){
a.head = (a.head +1)%6;
int re = -a.rot[2];
a.rot[2] = a.rot[1];
a.rot[1] = a.rot[0];
a.rot[0] = re;
}
sgt merge(sgt a, sgt b){
for(int i=0;i<a.head;i++){
rotate(b);
}
sgt ret;
ret.head = b.head;
for(int i=0;i<3;i++){
ret.rot[i] = a.rot[i] + b.rot[i];
}
return ret;
}
sgt seg[1001001];
int T;
int n,q;
int sm_n=0;
int sm_q= 0;
string s;
void build(int nd,int l,int r){
if(l==r){
seg[nd].rot[0] =1;
seg[nd].rot[1]= 0;
seg[nd].rot[2] = 0;
seg[nd].head = 0;
for(int j=0;j<s[l]-'0';j++){
rotate(seg[nd]);
}
return;
}
int mid=(r+l)/2;
build(2*nd,l,mid);
build(2*nd+1,mid+1,r);
seg[nd] = merge(seg[2*nd],seg[2*nd+1]);
}
sgt query(int nd,int l,int r,int s,int e){
if(s<= l && r<= e){
return seg[nd];
}
int mid=(r+l)/2;
sgt ret;
ret.rot[0] = ret.rot[1]= ret.rot[2]= 0;
ret.head = 0;
if(s<= mid){
ret= query(2*nd,l,mid,s,e);
}
if(mid+1<=e){
ret = merge(ret,query(2*nd+1,mid+1,r,s,e));
}
return ret;
}
int main(){
//freopen("02.txt","r",stdin);
//freopen("02o.txt","w",stdout);
//cout.precision(13);
//cout<<fixed;
T=readIntLn(1,1000);
while(T--){
n=readIntSp(1,200000);
q=readIntLn(1,200000);
sm_n += n;
sm_q += q;
assert(sm_n<=1000000);
assert(sm_q<=1000000);
s=readStringLn(n,n);
for(int i=0;i<n;i++){
assert('0'<=s[i] && s[i] <='5');
}
build(1,0,n-1);
while(q--){
int l,r;
l=readIntSp(1,n);
r=readIntLn(l,n);
l--;
r--;
sgt a = query(1,0,n-1,l,r);
double y= sqrt(3.0)/2;
double x= 1/2.0;
x *= 2 * a.rot[0] + a.rot[1] - a.rot[2];
y *= a.rot[1] + a.rot[2];
//cout<<x<<" "<<y<<endl;
printf("%.8lf %.8lf\n",x,y);
}
}
assert(getchar()==-1);
}
Tester's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// find_by_order() // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
int cnter[212345][6];
long double xx[12],yy[12];
int curpos[212345];
int haha[12],wow[12];
int main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
long double pi3 = atan(1.0)*4.0/3;
while(t--){
int n,q;
cin>>n>>q;
int i;
rep(i,6){
xx[i]=cos(i*pi3);
yy[i]=sin(i*pi3);
}
string s;
cin>>s;
int j;
int sofar=0;
f(i,1,n+1){
rep(j,6){
cnter[i][j]=cnter[i-1][j];
}
sofar+=s[i-1]-'0';
sofar%=6;
curpos[i]=sofar;
cnter[i][sofar]++;
}
int l,r;
long double x,y;
rep(i,q){
cin>>l>>r;
rep(j,6){
haha[j]=cnter[r][j]-cnter[l-1][j];
}
sofar=curpos[l-1];
sofar=6-sofar;
rep(j,6){
wow[(j+sofar)%6]=haha[j];
}
x=0.0;
y=0.0;
rep(j,6){
x+=xx[j]*wow[j];
y+=yy[j]*wow[j];
}
cout<<setprecision(10)<<x<<" "<<y<<endl;
}
}
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class ROBOTS{
//SOLUTION BEGIN
int[][] d = new int[][]{
{2, 0},
{1, 1},
{-1, 1},
{-2, 0},
{-1, -1},
{1, -1}
};
void pre() throws Exception{}
void solve(int TC) throws Exception{
int n = ni(), q = ni();
int[][][] pos = new int[6][1+n][];
int[][] dir = new int[6][1+n];
for(int di = 0; di< 6; di++){dir[di][0] = di;pos[di][0] = new int[]{0, 0};}
String s = n();
hold(s.length() == n);
for(int i = 1; i<= n; i++){
for(int di = 0; di < 6; di++){
dir[di][i] = (dir[di][i-1]+(s.charAt(i-1)-'0'))%6;
pos[di][i] = new int[]{pos[di][i-1][0]+d[dir[di][i]][0], pos[di][i-1][1]+d[dir[di][i]][1]};
}
}
double fx = 0.5, fy = Math.sqrt(0.75);
while(q-->0){
int l = ni(), r = ni();
int dd = -1;
for(int di = 0; di < 6; di++)if(dir[di][l-1] == 0)dd = di;
int[] pp = new int[]{pos[dd][r][0]-pos[dd][l-1][0], pos[dd][r][1]-pos[dd][l-1][1]};
pn(df.format(pp[0]*fx)+" "+df.format(pp[1]*fy));
}
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
DecimalFormat df = new DecimalFormat("0.0000000");
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new ROBOTS().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 