|
|
back to boardProbably 10th test has a bug! I used the following O(m) algorithm, where 'a' - teacher's list, 'b' - student's list. I got WA on test 10. After sorting _teacher's_(!) list as well, program was accepted. Therefore, it seems that 10th test has a bug. Am I right, or maybe missed smth? It seems this bug wasn't mentioned before, 'cause general approach is not O(m), but O(m*ln(n)) solution, which uses O(n) memory. And that approach may work somehow.. Arrays.sort(b); int c = 0; int j = 0; for (int i = 0; i < a.length; i++) { if (i > 0 && a[i] == a[i - 1]) continue; while (j < b.length && b[j] < a[i]) { j++; } while (j < b.length && b[j] == a[i]) { c++; j++; } } cout.println(c); Re: Probably 10th test has a bug! Argument follows.. This program craches on test 10. cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); PrintWriter cout = new PrintWriter(System.out); int a [] = new int[readInt()]; for (int i = 0; i < a.length; i++) { a[i] = readInt(); } for (int i = 1; i < a.length; i++) { if (a[i] < a[i - 1]) throw new RuntimeException("10th test is wrong."); } Re: Probably 10th test has a bug! You are right! Test is fixed now. 9 authors got AC. Thank you for help. |
|
|