Problem Info
High Card Low Card
Question
Include a specific question if you have one. USACO
What I’ve Tried
I read and understand the editorials solution. However, my solution is slightly different. The intuition is to add all of the cards to a number line between 1 and t*2, and in order to solve the first half we sweep from the right side and in order to solve the second half we sweep from the left. This solution works for every testcase except for WAs on 6, 8, 11, 14. I cannot for the life of me understand how it is wrong. Please help!
My Work
import java.util.*;
import java.io.*;
public class HighCardLowCard {
public class IO extends PrintWriter {
private BufferedReader r;
private String line, token;
private StringTokenizer st;
public IO () {
super(new BufferedOutputStream(System.out));
r = new BufferedReader(new InputStreamReader(System.in));
}
public IO (String name) throws IOException {
super(name+".out");
r = new BufferedReader(new FileReader(name+".in"));
}
public boolean hasNext() { return peekToken() != null; }
public int nextInt() { return Integer.parseInt(nextToken()); }
public double nextDouble() { return Double.parseDouble(nextToken()); }
public long nextLong() { return Long.parseLong(nextToken()); }
public String next() { return nextToken(); }
String nextLine() {
String str = "";
try {
str = r.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
public void println (Object... args) {
for (Object a : args) {
print(a);
}
print('\n');
}
private String nextToken() {
String ans = peekToken();
token = null;
return ans;
}
private String peekToken() {
if (token == null)
try {
while (st == null || !st.hasMoreTokens()) {
line = r.readLine();
if (line == null)
return null;
st = new StringTokenizer(line);
}
token = st.nextToken();
}
catch (IOException e) {}
return token;
}
}
public static void main(String[] args) throws IOException {
new HighCardLowCard().run();
}
public int LEFT = 1, RIGHT = 2, USED = 3, UNUSED = 0;
public void run () throws IOException {
IO f = new IO("cardgame");
int t = f.nextInt();
int[] a = new int[t*2];
for (int i = 0; i < t; i++) {
a[f.nextInt()-1] = i<t/2?RIGHT:LEFT;
}
int ans = 0;
int front = t/2;
int used = 0;
for (int i = t*2-1; i >= 0; i--) {
if (a[i] == RIGHT) {
if (used > 0)
used--;
else
front--;
} else if (a[i] == UNUSED && front > 0) {
a[i] = USED;
front--;
used++;
ans++;
}
}
front = t/2;
used = 0;
for (int i = 0; i < t; i++) {
if (a[i] == LEFT) {
if (used > 0)
used--;
else
front--;
} else if (a[i] == UNUSED && front > 0) {
a[i] = USED;
front--;
used++;
ans++;
}
}
f.println(ans);
System.out.println(ans);
f.close();
}
}
Pretty straighforward code, I add the cards to a number line and then do my sweeps while keeping track of how many of my opponents cards are in front of me.