i have tried this problem several years....while preparing for contests and it's always WA and it's not at all the heardest of problems..... i made an O (n log n) alg using heaps ....as usual it's WA at test 2 could someone put some tests around??? i ageve my self some and nothing....bad could somebody explain why??????????????: 1 2 3 2 3 my result: 1: 2 4 2: 1 3 6 3: 2 5 4: 1 5: 3 6: 2 AC result: 1: 2 4 2: 1 3 6 3: 2 5 4: 1 5: 1 //5 is not even conected to 1??????? 6: 3 Edited by author 13.10.2006 04:08 Edited by author 13.10.2006 04:40 Is this input legal? It seems that the last number will always be N, or the sequence itself is not legal. It's incorrect input, you cannot find a tree that satisfies your input i have tried this problem several years....while preparing for contests and it's always WA and it's not at all the heardest of problems..... i made an O (n log n) alg using heaps ....as usual it's WA at test 2 could someone put some tests around??? i ageve my self some and nothing....bad could somebody explain why??????????????: 1 2 3 2 3 my result: 1: 2 4 2: 1 3 6 3: 2 5 4: 1 5: 3 6: 2 AC result: 1: 2 4 2: 1 3 6 3: 2 5 4: 1 5: 1 //5 is not even conected to 1??????? 6: 3 Edited by author 13.10.2006 04:08 Edited by author 13.10.2006 04:40 I checked everything 100 times but still can not understand what the problem is.(i wrote on Java) Perhaps, you don't sort the result? The same problem! What is the Test 2? Can anybody help with test 2 please? I have got this problem because i forgot to sort neighbours of vertices. has anyone done it in O(n)? But this solution is O(n^2) becouse of ... 7 for each value i in a 8 for each node j in T ... maybe I don't understand whi it is O(n) so I ask you tell me why please. Sorry for bad English. Никто с форума не знает решение O(N), т.к. в рейтинге решений у всех время 0.015, которое соответствует N*logN (я сам так решил). Идея задачи проста-на очередном шаге находить ещё не использованные вершинки (а также отсутствующие в оставшемся списке),и среди всех таких вершины с минимальным номером. Это как раз и будут "очередные" в "оставшемся" дереве висячие вершины. Стандартное решение с использованием кучи работает O(N*logN). Если кто-нибудь ДЕЙСТВИТЕЛЬНО знает решение за O(N), то напишите на общем форуме. Edited by author 28.08.2015 00:24 I'm implemented O(N) algo, and got 0.001s AC!. You can easily do it in O(N) with counting sort. HELP!My algo:find the minimum,add the edge,sort and print,the first and the third step I use the heap.I don't think these matter. My code: #include<iostream> using namespace std; const int maxn = 7500; int heap_size = 0, now = 0; int heap[maxn + 1]; struct edge { int neighbour; edge *pre; }e[maxn + 1]; edge *tail[maxn + 1]; inline void swap(int i, int j) { int temp; temp = heap[i]; heap[i] = heap[j]; heap[j] = temp; return; } void heap_up(int i) { if (i == 1) return; int father = i / 2; if (heap[i] < heap[father]) { swap(i, father); heap_up(father); } return; } void heap_down(int i) { int left = i * 2; int right = left + 1; int least = i; if (left <= heap_size && heap[left] < heap[least]) least = left; if (right <= heap_size && heap[right] < heap[least]) least = right; if (least != i) { swap(i, least); heap_down(least); } return; } inline void heap_delete(int i) { swap(i, heap_size--); heap_down(i); return; } inline void heap_insert(int key) { heap[++heap_size] = key; heap_up(heap_size); return; } inline void connect(int u, int v) { e[++now].neighbour = v; e[now].pre = tail[u]; tail[u] = e + now; return; } int main() { int son[maxn + 1] = { 0 }, code[maxn]; int n = 1, i, u, v, temp; do { temp = 0; cin >> temp; if (temp) { code[n++] = temp; son[temp]++; } } while (temp); for (i = 1; i <= n; i++) if (!son[i]) heap_insert(i); for (i = 1; i <= n; i++) tail[i] = nullptr; for (i = 1; i < n; i++) { v = heap[1]; heap_delete(1); u = code[i]; if (!(--son[u])) heap_insert(u); connect(u, v); connect(v, u); } edge *p; heap_size = 0; for (i = 1; i <= n; i++) { cout << i << ":"; for (p = tail[i]; p != nullptr; p = p->pre) heap_insert(p->neighbour); for (; heap_size; heap_delete(1)) cout << " " << heap[1]; cout << endl; } return 0; } Edited by author 06.02.2015 21:40 Edited by author 07.02.2015 08:44 Somewhere there should be bad indexing. Try to increase arrays size from maxn + 1 to maxn + 50 and check what results judge gives. As I said before I think java programs should get higher time limit. My java program gets TLE on test #4 or #5 285ms. In my opinion my program runs in O(nlogn). Below I gave the code that gets TLE: import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); ArrayList<Integer> lst = new ArrayList<>(); int[] sorted; PriorityQueue<Integer>[] g; int[] degree = new int[8000]; Arrays.fill(degree, 0);
// O(n) while (sc.hasNextInt()) { int tt = sc.nextInt() - 1; lst.add(tt); degree[tt]++; } g = new PriorityQueue[lst.size() + 1]; sorted = new int[lst.size() + 1]; // O(n) for (int i = 0; i < lst.size() + 1; i++) { sorted[i] = i; g[i] = new PriorityQueue<>(); } // find initial leaves O(nlogn) PriorityQueue<Integer> leaves = new PriorityQueue<>(); for (Integer y : sorted) { if (degree[y] == 0) { leaves.add(y); } } // O(nlogn) for (int x : lst) { degree[x]--; int y = leaves.poll(); g[x].add(y); g[y].add(x);
if(degree[x] == 0){ leaves.add(x); } }
// O(nlogn) for (int i = 0; i < g.length; i++) { System.out.print((i + 1) + ":"); while (!g[i].isEmpty()) { System.out.print(" " + (g[i].poll() + 1)); } System.out.println(""); } } } Edited by author 12.12.2014 23:17 Oh gosh, I used buffered reader instead of Scanner.nextInt() and got AC, micro-optimizing your code for I/O is not the right thing for this problem IMO: BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] input = br.readLine().split(" "); - Do you know test 4 ? - Any helpful tests ? - If not, please pick bugs from my code. My algo: Find minimal, adjacent list, output sorted list. Tks a loooottttttt Program Prufer_Code; Type pnode = ^node; node = Record data:Longint; next:pnode; End; Var adjList:Array[0..7500] of pnode; temp:pnode; A,C,minS:Array[0..7500] of Longint; n,i,j,s,p,q,m:Longint; fi:Text; Procedure add(k:Longint;var x:pnode); Var y,z:pnode; Begin If (x=nil) then Begin new(x); x^.data:=k; End Else Begin new(y); y^.data:=k; y^.next:=x; x:=y; End; End; Begin n:=0; While not seekeof do Begin inc(n); Read(A[n]); End; For i:=1 to n+1 do Begin inc(C[i]); inc(C[A[i]]); End; dec(C[A[n+1]],2); p:=0; For i:=1 to n+1 do If C[i]=1 then Begin inc(p); minS[p]:=i; End; For i:=1 to n do Begin q:=minS[1]; m:=1; For j:=2 to p do If minS[j]<q then Begin q:=minS[j]; m:=j; End; j:=q; minS[m]:=99999; add(j,adjList[A[i]]); add(A[i],adjList[j]); dec(C[A[i]]); If C[A[i]]=1 then Begin inc(p); minS[p]:=A[i]; End; End; For i:=1 to n+1 do Begin FillChar(C,sizeof(C),0); temp:=adjList[i]; p:=0; while temp<>nil do Begin inc(C[temp^.data]); temp:=temp^.next; End; Write(i,': '); For j:=1 to 7500 do If C[j]=1 then Write(j,' '); Writeln; End; End. I receive Access violation it test 4 too. :( Do anyone know the test? I was crashed on this test, because i forget to fill inf in cells of heap, before i start to solve. Also you can try this test: input: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 output: is obvious Are you store the double edge but didn't double the edge memory? I've written the program for many times,but when I submited it,I always see "MLE" or "Wrong Answer",I've submitted it for more than 10 times!!! Finally Accepted!!! OK I've found that my heap is error,and I got MLE then. Edited by author 04.03.2013 19:32 Edited by author 04.03.2013 19:32 Well, i got WA on it and then modified something and got Memory Limit Exceeded. I'm using a matrix of 7501*7501. I think i should make lists of neighbours? Got AC with vectors of neighbours. I got WA on test 3. I wonder that: Are there any special tests in this problem? OR Is there anything special in the output task? Just ask: If n=10, Can I output like this: ('...' Stands for some digits) 1: ... ... 9: ... 10: ... Must I leave a space before '9' in order to make ':' in the same column? Could anyone help me, please? Edited by author 09.05.2004 21:43 Thanks so much for helping me. But, if I shouldn't leave a ' ' before, then my program seems to have no errors. Can you give me some SPECIAL tests. Thanks very much again. I want the tests for this problem, but I haven't receive them yet. I got WA at test 29. Will anyone who have all the tests help me? Thanks. Sorry, I have something wrong. I got WA just at test 3. I WAed on test #3, too. Could anybody gimme some tests? Edited by author 11.06.2004 12:24 There is test, helped for me 8 7 4 6 3 6 8 and answer 1: 8 2: 7 3: 6 7 4: 5 6 5: 4 6: 3 4 8 7: 2 3 8: 1 6 Good luck! It's really good test. It helped me to get AC some minutes ago :) Really a good test...Thanx very much. good! i have crashed on test3# but i don't know why oh ,it answered me I have a huge Wrong Answer, but my code work for this test case, are some test case more difciult than this ?? I don t know what happend I need help right now !! greetings ! salu-DoS I got wa on test 2 I want to know if input is : 2 2 what should I output? sorry my English is very poor Hi, In the question they said that the last vertex left (or last vertex of given prufer code) should be equal to N or number of nodes in the graph. But its not like that somehow, so I changed N to total numbers in prufer code + 1. Then no more WA 1. Varun Edited by author 08.03.2010 06:55 I use a very simple algorithm..my code is very short.. *just (for i:=1 to n do)check if the number appears in the A set of numbers after i. *set down the father of each number. *Just output. (i'm sorry that my English is really bad..) var con,temp,i,j:longint; fin:array[1..7500]of boolean; b,a,fa:array[1..7500]of integer; begin {$IFNDEF ONLINE_JUDGE} assign(input,'input.in');reset(input); assign(output,'output.out');rewritE(output); {$ENDIF} reaD(temp); con:=0; while temp<>0 do begin inc(con); a[con]:=temp; inc(b[temp]); read(temp); end; for i := 1 to con do for j := 1 to con+1 do if (not fin[j])and(b[j]=0) then begin fin[j]:=true; fa[j]:=a[i]; deC(b[a[i]]); break; end; for i := 1 to con+1 do begin write(i,':'); for j := 1 to con+1 do if (fa[j]=i)or(fa[i]=j) then write(' ',j); writeln; end; end. Edited by author 13.10.2009 15:09 Can you tell me an idea how to solve it in O(N) or in O(N*logN) Thanks for example for test: 8 7 4 6 3 6 8 my program writes: 1: 8 2: 7 3: 7 6 4: 5 6 5: 4 6: 4 3 8 7: 2 3 8: 1 6 which is correct, but i got WA#2 if i sort the result: 1: 8 2: 7 3: 6 7 4: 5 6 5: 4 6: 3 4 8 7: 2 3 8: 1 6 i get TL#5 i have got AC Edited by author 18.06.2009 02:45 Edited by author 18.06.2009 05:09 Edited by author 18.06.2009 05:42 Edited by author 14.03.2009 00:58 Prufer code is not N-1!!! Its should be N-2, because the last number always N. For example if I will get the numbers: 1 1 1 1 1, its impossible to build this graph. About this possible to read here: http://en.wikipedia.org/wiki/Pr%C3%BCfer_sequenceyou are absolutely right What does it change to a solution to the problem? |
|