Sunday 11 June 2017

KQUERYO

K-Query Online


Link to the question : KQUERYO

HINT :

Question can be easily solved with Segment Trees with vector.  Read more about it here :  http://codeforces.com/blog/entry/15890

RECOMMENDED QUESTION :

Try your hands on this question : QUEEN


SOLUTION :

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define mod 1000000007
using namespace std;

int n,q, ar[30005];
std::vector<int> v[100005];

void build(int id ,int l ,int r )
{
if(r == l )
{
v[id].push_back(ar[l]);
return ;
}
int mid = (l+r)/2;
build(2 * id, l, mid);
build(2*id+1, mid+1, r);
merge(v[2 * id].begin(), v[2 * id].end(), v[2 * id + 1].begin(), v[2 * id + 1].end(), back_inserter(v[id]));
}

int query(int x,int y,int k,int id ,int l ,int r )
{

if(x > r || l > y)
return 0;
if(x <= l && r <= y)
{
return v[id].size() - (upper_bound(v[id].begin(), v[id].end(), k) - v[id].begin());
}
int mid = (l+r)/2;

return query(x, y, k, 2 * id, l, mid) +
  query(x, y, k, 2*id+1, mid+1, r) ;
}


int main()
{
scanf("%d", &n);
for(int i=0; i<n; i++)
scanf("%d", &ar[i]);

build(1,0,n-1);
scanf("%d", &q);

int prev = 0;
while(q--)
{
int a,b,c;
scanf("%d%d%d", &a, &b, &c);
int i = a^prev;
int j = b^prev;
int k = c^prev;

prev = query(i-1,j-1,k,1,0,n-1);
printf("%d\n", prev);
}
return 0;
}

Wednesday 7 June 2017

QUEEN

Wandering Queen


Link to the question : QUEEN

HINT :

This question requires bfs as can be clearly understood from the tag. We start doing bfs from the position of the queen. And push into the queue all the squares which can be visited by the queen from that position and update their distance by 1 and mark it visited. For eg :
S..
 ..F
when starting from S we push into the queue positions (0,1), (0,2), (1,0), (1,1), consider 0 based indexing, update their position and mark them visited.
But while pushing into the queue just checking whether that position has been visited wont do.
Because consider the case
S..
XX.
..F
here, from (0,1) you can visit (1,2) and update its distance and mark it visited, and when you check for (0,2) you will see (1,2) is visited and not check further. This is incorrect because for optimal solution you must visit (1,2) and (2,2) from here. Hence even if the square is visited you should visit it again if it can be reached from the current position in 1 move.
Look code for further details.

RECOMMENDED QUESTION :

Try your hands on this question : Headshot



SOLUTION :

    #include <iostream> #include <stdio.h> #include <queue> using namespace std; struct point { int x,y; }; int X[] = {-1, -1, -1, 0, 0, 1, 1, 1}; int Y[] = {-1, 0, 1, -1, 1, -1, 0, 1}; int n,m; char str[1005][1005]; int dist[1000][1000]; bool check(point t) { if(t.x >=0 && t.x <n && t.y >=0 && t.y <m && str[t.x][t.y] != 'X') return true; return false; } int main() { int t; scanf("%d", &t); while(t--) { scanf("%d %d", &n, &m); for(int i=0; i<n; i++) scanf("%s", str[i]); queue<point> q; point start, final; for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { dist[i][j] = 0; if(str[i][j] == 'S') { start.x = i; start.y = j; dist[i][j] = 1; } else if(str[i][j] == 'F') { final.x = i; final.y = j; } } } q.push(start); while(!q.empty()) { point temp = q.front(); q.pop(); for(int i=0; i<8; i++) { point copy = temp; copy.x += X[i]; copy.y += Y[i]; while(check(copy)) { if(dist[copy.x][copy.y] == 0) { dist[copy.x][copy.y] = dist[temp.x][temp.y] + 1; q.push(copy); } else if(dist[copy.x][copy.y] != dist[temp.x][temp.y]+1) break; copy.x += X[i]; copy.y += Y[i]; } } } cout << dist[final.x][final.y]-1 << endl; } return 0; }