Checklist
Make sure to read all of How to ask for help on a problem before asking for help.
Problem Info
(https://usaco.org/index.php?page=viewproblem2&cpid=1352)
Question
Following the logic explained in the solution but missing a few test cases. Test case 6 should have answer 55, I am getting 53
What I’ve Tried
FOllowed the solution logic detailed in the USACO site
My Work
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.Arrays;
import java.util.Scanner;
public class targetPr4 {
static int[] tArray;
//static String cArray;
static String command;
static int[] prefixArray;
static int[] suffixArray;
public targetPr4() {
// TODO Auto-generated constructor stub
}
public static void main(String[] args) throws FileNotFoundException {
// TODO Auto-generated method stub
FileReader reader;
Scanner scanFile;
reader = new FileReader("6.in");
scanFile = new Scanner(reader);
//Scanner scanFile = new Scanner(System.in);
int T = scanFile.nextInt();
int C = scanFile.nextInt();
tArray = new int[2*C+5];
prefixArray = new int[2*C+5];
suffixArray = new int[2*C+5];
for (int i = 0; i< T; i++)
{
int x = scanFile.nextInt();
tArray[x+C] = 1;
}
command = scanFile.next();
int position = C;
int hitCount = 0;
int[] hitArray = new int[2*C+5];
int[][] hitArrayL = new int[2*C+5][5];
Arrays.fill(hitArray, -1);
for (int i = 0; i<2*C+5; i++)
{
Arrays.fill(hitArrayL[i], -1);
}
int[][] hitArray2 = new int[2*C+5][5];
//int[][] hitArray22 = new int[C][2*C+1];
for(int i = 0; i < command.length(); i++)
{
if (i == 0)
{
prefixArray[i] = 0;
}
else
{
prefixArray[i] = prefixArray[i-1];
}
switch(command.charAt(i))
{
case 'L':
position--;
//hitArray22[i][position] = hitArray[position];
break;
case 'R':
position++;
//hitArray22[i][position] = hitArray[position];
break;
case 'F':
if (tArray[position] == 1 && hitArray[position] == -1)
{
hitArray[position] = i;
hitCount++;
prefixArray[i]++;
//hitArrayL[position] = (i > hitArrayL[position] ? i : hitArrayL[position]);
//hitArray22[i][position] = 1;
}
if (prefixArray[i] == 27)
{
//System.out.println("i = "+i);
}
//hitArray22[i][position] = hitArray[position];
break;
}
//hitArray22[i][position] = hitArray[position];
}
/*
for (int i = 0; i<prefixArray.length; i++)
{
System.out.print(prefixArray[i]+" ");
}
*/
//build suffix array
int[][]suffArray2 = new int[C+2][5];//0 is -2, 4 is +2
//int[][]deductArray2 = new int[C+2][5];
int tempHit = 0;
int finalHit = 0;
for(int i = command.length()-1; i >= 0; i--)
{
suffArray2[i][0] = suffArray2[i+1][0];
suffArray2[i][1] = suffArray2[i+1][1];
suffArray2[i][2] = suffArray2[i+1][2];
suffArray2[i][3] = suffArray2[i+1][3];
suffArray2[i][4] = suffArray2[i+1][4];
if (i == 512)
{
//System.out.println("Position = " + position);
}
/*
check this. When doing final calcs - if F changes to L - we lose a hit. When building suffic array,
we would have not added that hit as the index of hit was earlier. We need to track if the target is also hit
at a later time then add it.
*/
switch(command.charAt(i))
{
case 'L':
//stays
//no change
tempHit = (i>0 ? prefixArray[i-1]:0) + suffArray2[i+1][2];
finalHit = (tempHit > finalHit ? tempHit : finalHit);
//L->F
tempHit = (i>0 ? prefixArray[i-1]:0) + suffArray2[i+1][3];
if (tArray[position] == 1 && (hitArray[position] >= i || hitArray[position] == -1))//target and not already in prefix
{
if (hitArrayL[position][3] == -1)//not included in suffix
{
tempHit++;
//hitArrayL[position][3] = i;
//suffArray2[i][3] += 1;
}
}
finalHit = (tempHit > finalHit ? tempHit : finalHit);
//L -> R
tempHit = (i>0 ? prefixArray[i-1]:0) + suffArray2[i+1][4];
finalHit = (tempHit > finalHit ? tempHit : finalHit);
if (finalHit == 53 && i == 512)
{
//System.out.println("LR1");
//System.out.println(prefixArray[i-1]+ " " +suffArray2[i+1][4] );
//finalHit = 88;
}
position++;
break;
case 'R':
//stays
tempHit = (i>0 ? prefixArray[i-1]:0) + suffArray2[i+1][2];
finalHit = (tempHit > finalHit ? tempHit : finalHit);
//R->F
tempHit = (i>0 ? prefixArray[i-1]:0) + suffArray2[i+1][1];
if (tArray[position] == 1 && (hitArray[position] >= i || hitArray[position] == -1))//target and not already in prefix
{
if (hitArrayL[position][1] == -1)//not included in suffix
{
tempHit++;
//hitArrayL[position][1] = i;
//suffArray2[i][1] += 1;
}
}
finalHit = (tempHit > finalHit ? tempHit : finalHit);
//R -> L
tempHit = (i>0 ? prefixArray[i-1]:0) + suffArray2[i+1][0];
finalHit = (tempHit > finalHit ? tempHit : finalHit);
position--;
break;
case 'F':
//F stays = 2
//if target hit before this index
tempHit = (i>0 ? prefixArray[i-1]:0) + suffArray2[i+1][2];
//add hit if target hit
if (hitArray[position] == -1 || hitArray[position] >= i)//not in prefix
{
if (hitArrayL[position][2] == -1)//not is suffix
{
//suffArray2[i][2] += (tArray[position] == 1 ? 1 :0);
tempHit+= (tArray[position] == 1 ? 1 :0);
//hitArrayL[position][2] = (tArray[position] == 1 ? i :-1);
}
}
finalHit = (tempHit > finalHit ? tempHit : finalHit);
//hitArrayL[position][2] = (i > hitArrayL[position][2] ? i : hitArrayL[position][2]);
//F->L
tempHit = (i>0 ? prefixArray[i-1]:0) + suffArray2[i+1][1];
finalHit = (tempHit > finalHit ? tempHit : finalHit);
//F->R
tempHit = (i>0 ? prefixArray[i-1]:0) + suffArray2[i+1][3];
finalHit = (tempHit > finalHit ? tempHit : finalHit);
if (position > C)
{
//continue;
}
int II = i-2;
//keep F as is
if (hitArray[position] == -1 || hitArray[position] > II)//not in prefix
{
if (hitArrayL[position][2] == -1)//not in suffix
{
suffArray2[i][2] += (tArray[position] == 1 ? 1 :0);
//tempHit+= (tArray[position] == 1 ? 1 :0);
hitArrayL[position][2] = (tArray[position] == 1 ? i :-1);
}
}
//move one unit left
if(position > 0 && (hitArray[position-1] == -1 || hitArray[position-1] > II))//not in prefix
{
if (hitArrayL[position-1][1] == -1)//not in suffix
{
suffArray2[i][1] += (tArray[position-1] == 1 ? 1 :0);
hitArrayL[position-1][1] = (tArray[position-1] == 1 ? i :-1);
}
}
//move 2 units left
if(position > 1 && (hitArray[position-2] == -1 || hitArray[position-2] > II))//not in prefix
{
if (hitArrayL[position-2][0] == -1)//not in suffix
{
suffArray2[i][0] += (tArray[position-2] == 1 ? 1 :0);
hitArrayL[position-2][0] = (tArray[position-2] == 1 ? i :-1);
}
}
//move one unit right
if(hitArray[position+1] == -1 || hitArray[position+1] > II)//not in prefix
{
if (hitArrayL[position+1][3] == -1)//not in suffix
{
suffArray2[i][3] += (tArray[position+1] == 1 ? 1 :0);
hitArrayL[position+1][3] = (tArray[position+1] == 1 ? i :-1);
}
}
// if (i == 513)
// {
// System.out.println("F " +position+" "+suffArray2[i][4] + " " + hitArray[position+2]+" "+ hitArrayL[position+2][4]);
// }
//move 2 units right.
if(hitArray[position+2] == -1 || hitArray[position+2] > II)//not in prefix
{
if (hitArrayL[position+2][4] == -1)//not in suffix
{
suffArray2[i][4] += (tArray[position+2] == 1 ? 1 :0);
hitArrayL[position+2][4] = (tArray[position+2] == 1 ? i :-1);;
}
}
break;
}
}
/*
int sum = 0;
for (int i = 0; i < newHitArray.length; i++)
{
sum += newHitArray[i];
}
System.out.println(sum);
*/
System.out.println(finalHit);
}
}
Add explanation of code here
- Build prefix Array of target hits
- STart backward and build a suffix array
At position i if = ‘F’ then check if the target has been hit in prefix array at or after this position AND if the suffix array has NOT already hit this target → then add to suffix array