Online Course Discussion Forum

USACO: Is there a java type that has a big capacity and can do the bitwise shift operator?

 
 
Picture of Jialin Wang
USACO: Is there a java type that has a big capacity and can do the bitwise shift operator?
by Jialin Wang - Thursday, 26 January 2023, 10:51 PM
 

USACO: Is there a java type that has a big capacity and can do the bitwise shift operator?


Hello,  

I am doing a practice problem on the USACO website. (2022 OPEN Contest bronze #1)

Farmer John, desperate to win the award for best cow photographer at the county fair, is trying to take the perfect photograph of his N cows (2N21052≤�≤2⋅105N even).

Farmer John owns cows of two potential breeds: Guernseys and Holsteins. To make his photo as aesthetic as possible, he wants to line up his cows so that as many Guernseys are in even-numbered positions in the line as possible (the first position in the line is an odd position, the next is an even position, and so on). Due to his lack of strong communication with his cows, the only way he can achieve his goal is by asking even length "prefixes" of his cows to reverse themselves (a prefix consists of the range of cows from the first cow up to the jth cow for some position j).

Please count the minimum number of reversals required for Farmer John to achieve his goal.

The code is attached to the post. How the algorithm work is commented out. It basically revolves around the bitwise complement and shift operators, since it's the only way to get around turning all 1 to 0 and vice versa without loops. 



Code:



import java.util.*;

import java.io.*;

public class Photoshooting

{

  public static void main(String[] args) throws IOException

  {


    BufferedReader in  = new BufferedReader(new InputStreamReader(System.in));

    int N = Integer.parseInt(in.readLine());

    String cows = in.readLine();

    

    String binary = "";

    int result = 0;

    //generates a string of 1's and 0's, with 2 cows each pair. GG's and HH's don't matter since they don't change anything if reversed

    //GH is represented by 1, and HG is represented by 0. 0 is ideal since the G is at the even place

    //if  you reverse the  cows, all 0's become 1's and vice versa

    //this is done by the bitwise  complement operator, the most important thing in this code

    //

    for(int i = 0; i < cows.length(); i+=2)

    {

      if(cows.substring(i, i+2).equals("GH"))//

      {

        binary = binary + "1";

      }

      if(cows.substring(i, i+2).equals("HG"))

      {

        binary = binary + "0";

      }

    }

    //bin is used to store all the 1's and 0's of this

    //bin is initially a Long type, but if the String is like 1000 digits of 0 and 1, even a long won't fit all these numbers

    //however, the bitwise complement operator, which is the core of this code, doesn't work if it's changed to byte.

    

    byte bin = Byte.parseByte(binary, 2);

 

    while(bin != 0)

    {


      if(bin % 2 == 0)

      {

        bin = bin>>1;

      }

      else


        bin = ~bin;

        result++;

      }

    System.out.println(result-1); 

    }

    


   

  

}




 
Picture of Dr. Kevin Wang
Re: USACO: Is there a java type that has a big capacity and can do the bitwise shift operator?
by Dr. Kevin Wang - Friday, 27 January 2023, 2:07 PM
 

Be careful when the length of the reversal is odd; the result may be different from what you think.

If the bitwise operation for long strings of 0s and 1s is critical to your algorithm, you could write a helper class to represent that data type. In the helper class, represent the big capacity string with an array of long, and write methods for add digit, shift, complement, bitwise AND, bitwise OR, etc.