Twenty Percent Knowledge: July 2016

Saturday, July 30, 2016

Xor Sequence

Glad that I observed the pattern and come up a solution based on the observation. You feel confident when your thoughts are executed and worked the problem out.

An array,

, is defined as follows:

A0=0
Ax=Ax-1^x for x>0 , where ^ is the symbol for XOR

You must answer

questions. Each

question, is in the form

, and the answer is

(the Xor-Sum of segment

).
Print the answer to each question.

Input Format

The first line contains

(the number of questions).
The

subsequent lines each contain two space separated integers,

and

, respectively. Line contains

and

.
Constraints

Subtasks
For

score:

Output Format

On a new line for each test case

, print the exclusive-or of

's elements in the inclusive range between indices

and

Sample Input

Sample Output

7
9
15

Explanation

The beginning of our array looks like this: A=[0,1,3,0,4,1,7,0,8,1,11,0...]

Test Case 0: 3^0^4=7

Test Case 1:3^0^4^1^7^0^8=9

Test Case 2:1^7^0^8^1=15

Observation:
for every 4 of A, is repeated by this pattern: 0+n*4,1,3+n*4,0
and their XOR is always 2 no matter what n is.
So the calculation is ^ of numbers before a segment start point, ^ with 2 if there are odd number of segment of 4(or do nothing with even number of segment of 4, because their ^ result is 0, and XOR with 0 is still itself), then ^ with numbers in last incomplete segment.

With 0+n*4,1,3+n*4,0, I can come up a formula for every single number easily. that is getAi function. That function is further used to calculate left and right part of numbers which are in partial segments. so maximum 6 getAi need to be invoked no matter how many numbers between the two given numbers.

package bitwise;

import java.util.Scanner;

public class XOR {
 public static long getAi(long i){
        long firstFour[] =new long[]{0,1,3,0};//rest will be 0+n*4,1,3+n*4,0. each 4 of these
        int position = (int)(i%4);//i is 0 based
        
        long times = i/4;

        if(position==0 ||position==2){
            return (long)(firstFour[position]+ times*4);
        } 
        else if(position==1){
            return 1;
        }
        else
            return 0;
    }
 public static void main(String[] args) {
  // TODO Auto-generated method stub
//  for (long i=0;i<12;i++)
//   System.out.println(getAi(i));
  Scanner in = new Scanner(System.in);
        
        int Q = in.nextInt();
        for(int a0 = 0; a0 < Q; a0++){
            long L = in.nextLong();
            long R = in.nextLong();
           
            long result = 0;
            long l=L;
            while(l<=R && l%4!=3){
                result=result^getAi(l);
                l++;
            }
//            while(l<=R && (l+1)%4!=0){
//                result=result^getAi(l);
//                l++;
//            }
            //the forth is always 0, so not need to calculate with it
            long numSectionsBetweenThem = (R-l)/4;
            int reminder=(int)((R-l)%4);
            if(reminder==0&& numSectionsBetweenThem%2==0){
                //do not need to do anything
            }else if(reminder==0 &&numSectionsBetweenThem%2==1){
                result=result^2;//one segment's xor is 2
            }
            else if(reminder>0){
                if(numSectionsBetweenThem%2==1){
                    result = result^2;
                }
                long r=R;
                while(l<=r&& (r+1)%4!=0){
                    result = result^getAi(r);
                    r--;
                }
                //result = result^getAi(r);
            }
            System.out.println(result);
        }
                      
 }

}

Thursday, July 28, 2016

Nearest Locker Distance

Practice on loops.

public class NearestLockerDistance {
 static int[][] rotateMatrix(int[][] matrix) {
  int[][] result = new int[matrix[0].length][matrix.length];
  for (int r = 0; r < matrix.length; r++) {
   for (int c = 0; c < matrix[0].length; c++) {
    result[c][r] = matrix[r][c];
   }
  }
  return result;
 }

 static int[][] getLockerDistanceGrid(int cityLength, int cityWidth,
   int[] lockerXCoordinates, int[] lockerYCoordinates) {
  if (lockerXCoordinates == null || lockerYCoordinates == null
    || lockerXCoordinates.length != lockerYCoordinates.length)
   return null;
  int[][] city = new int[cityWidth][cityLength];
  // initialize city to biggest numbers
  for (int i = 0; i < city[0].length; i++)
   // x
   for (int j = 0; j < city.length; j++)
    // y
    city[j][i] = Integer.MAX_VALUE;

  // mark the locker's distance. it also remembers the location of lockers
  for (int i = 0; i < lockerXCoordinates.length; i++)
   city[lockerYCoordinates[i] - 1][lockerXCoordinates[i] - 1] = 0;
  // calculate for each locker
  for (int i = 0; i < lockerXCoordinates.length; i++) {
   calcDistance(city, lockerYCoordinates[i], lockerXCoordinates[i]);
  }
  city = rotateMatrix(city);
  return city;
 }

 static void calcDistance(int[][] city, int y, int x) {
  y = y - 1;
  x = x - 1; // this is place can be optimized
  for (int i = 0; i < city[0].length; i++)
   // x
   for (int j = 0; j < city.length; j++)// y
   {
    if (city[j][i] != 0) {
     city[j][i] = Math.min(city[j][i], Math.abs(j - y) + Math.abs(i - x));
    }
   }

 }

}