Try 7 10 1 2 1 3 1 4 5 6 5 7 8 9 8 10 8 11 12 13 12 14 This test changed my solution totally. Hope it helps you:) Test: 6 5 1 2 4 3 2 9 2 4 4 1 Ans: IMPOSSIBLE Thank you very mutch!!! It's very helpfull if somebody get WA7. (We just cann't paint this graph on 2 colors. ) A very good test, thanks. I had WA7 and now I have AC, using this one 3 4 1 2 1 3 4 5 4 6 ans: 1 5 6 2 3 4 Edited by author 03.09.2019 09:23 Many people has already written about it, but... I really don't understand why I get WA. My program pass all tests here. Please, help to find bug. -- Edited by author 29.07.2016 15:52 Contact me and maybe i'll have some suggestions to help you out~ Edited by author 26.07.2016 17:05 Hi! My code has complexity O(2^N) and it had AC in 0.001 sec. A friend of mine noted this: when I run my program in this case: 50 50 1 2 3 4 5 6 ... Same pattern here 95 96 97 98 99 100 And it will give TLE. Please, add this case! 50 50 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 Try this test: 2 1 1 3 answer: 2 3 1 4 I have wa#9,but my program does well in your data The case given here helped me. Notice that when you are selecting whether white part is to be selected or black part, and pushing the result in a vector or queue, due to DP, last part gets inserted first. So you have to consider that first result in the vector/queue is for the last pair of partition. May be this will help... 2 4 1 2 2 1 1 2 2 1 answer: 1 3 2 4 answer 1 2 3 4 is correct too. But I have wa3 Help me. I got WA7. Give me some test. I was failing this test because I printed stuff after IMPOSSIBLE (restoring solution even though I found there shouldn't be one). My programm passes all my tests, but WA#3. Please, help. Thanks a lot. How you here have applied Dinamic Prog.? I the ambassador aside graph. Hi, Taras. I use simple method: I read two variables ot and ku. If ot and ku are in the same group, I Output('IMPOSSIBLE'); If they are in the different groups then I Continue else I put one variable into the first group and other into the second group. After that I divide "free" tasks between the groups... I hoped that It would get more than two tests... May be I should try to use graphs... BTW, tell me youre ICQ number, I cann't find you... Edited by author 02.05.2006 13:17 try this test, maybe will help you: 4 6 1 2 2 3 3 4 4 5 6 7 7 8 ANS: 1 3 5 7 2 4 6 8 You can use it. I used it as well. First you must paint the graph with black and white (use BFS) so that two vertices with the same edge are of different colors. After that you have pairs of integers and you have to combine them so that you have N in each round (that's not always possible). how I should combine them ?? I've tested all inputs from other themes, but still got wa in 3rd. Help, please! The algorithm based on the half-invariant idea. #include <iostream> #include <fstream> #include <string> #include <math.h> #include <sstream> using namespace std; int main(){ int n, m; cin >> n >> m; bool **e = new bool*[2*n]; for (int i=0; i<2*n; i++){ e[i] = new bool[2*n]; for (int j=0; j<2*n; j++){ e[i][j] = false; } } int v1, v2; for (int i=0; i<m; i++){ cin >> v1 >> v2; int tmp; if (v1 > v2){ tmp = v1; v1 = v2; v2 = tmp; } e[v1-1][v2-1] = true; e[v2-1][v1-1] = true; } int inv=0; for (int i=0; i<n; i++){ for (int j=i+1; j<n; j++){ if (e[i][j]) inv++; if (e[n+i][n+j]) inv++; } } int *t =new int[2*n]; for (int i=0; i<2*n; i++){ t[i] = i; } while (inv > 0){ int s = 0; for (int i=0; i<n; i++){ int i_out = 0; int i_in = 0; for (int k=0; k<n; k++){ if (e[t[i]][t[k]] || e[t[k]][t[i]]){ i_in++; } if (e[t[i]][t[k+n]] || e[t[k+n]][t[i]]){ i_out++; } } for (int j=n; j<2*n; j++){ int j_out = 0; int j_in = 0; for (int k=0; k<n; k++){ if (e[t[k+n]][t[j]] || e[t[j]][t[k+n]]){ j_in++; } if (e[t[k]][t[j]] || e[t[j]][t[k]]){ j_out++; } } if (e[t[i]][t[j]] || e[t[j]][t[i]]){ j_out--; j_out--; } if (i_in + j_in > i_out + j_out){ s++; inv -= (i_in + j_in - i_out - j_out); int tmp = t[i]; t[i] = t[j]; t[j] = tmp; } if (s == 1) break; } if (s == 1) break; } if (s == 0){ cout << "IMPOSSIBLE\n"; return 0; } } string tour1, tour2; tour1 = ""; tour2 = ""; for (int i=0; i<n; i++){ for (int j=i+1; j<n; j++){ if (t[i]>t[j]){ int tmp = t[i]; t[i] = t[j]; t[j] = tmp; } if (t[i+n]>t[j+n]){ int tmp = t[i+n]; t[i+n] = t[j+n]; t[j+n] = tmp; } } } for (int i=0; i<n; i++){ std::ostringstream ostr; ostr << (t[i]+1); std::string theNumberString = ostr.str(); tour1 = tour1 + theNumberString + " "; } for (int i=0; i<n; i++){ std::ostringstream ostr; ostr << (t[n+i]+1); std::string theNumberString = ostr.str(); tour2 = tour2 + theNumberString + " "; } cout << tour1 << endl << tour2 << endl; return 0; } I had WA#8 and miraculously found a bug in my backtracking&memorization with the following test: > 50 2 > 99 100 > 98 99 The problem was in printing a solution, when N tasks for the first round are prepared properly, but the other N are contradictory (because I quit from backtracking too soon). We probably wouldn't have experienced this if we had written a proper DP solution instead. :-) Edited by author 08.07.2012 18:21 if you use brute search and got TLE then try to sort the input. :-D Thank you very much! I got accepted after sorting pairs with their sum. What test is it? This test help me. 7 10 1 2 1 3 1 4 5 6 5 7 8 9 8 10 8 11 12 13 12 14 Edited by author 04.02.2009 17:56 Thanks! It really helped me a lot on WA7! Actually, it was because I used an array color[100], but I forgot to set them to -1! It would be very hard to find that out without your help... I tried all tests given here (also in other forum messages) and always get correct answer. I have no idea, what's wrong with this: #include <iostream> #include <cmath> using namespace std; class Task { public: int arrSameTasks[101], lastIndex; bool IsInTour; Task() { IsInTour = false; lastIndex = 0; }
void AddSameTask(int someTask) { lastIndex++; arrSameTasks[lastIndex] = someTask; } void Show() { for (int i = 1; i <= lastIndex; i++) cout << arrSameTasks[i] << " "; cout << endl; } bool SameTasksFounded(int arrToCheck[], int n) { for (int i = 1; i <= lastIndex; i++) { for (int j = 1; j <= n; j++) { if (arrSameTasks[i] == arrToCheck[j]) return true; } } return false; } }; class TempTours // промежуточные расположения задач в турах { public: TempTours() {} int tempTour1[101], tempTour2[101], tempIndex1, tempIndex2; void CreateData(int tour1[], int tour2[], int index1, int index2) { for (int i = 1; i <= index1; i++) tempTour1[i] = tour1[i]; for (int i = 1; i <= index2; i++) tempTour2[i] = tour2[i]; tempIndex1 = index1; tempIndex2 = index2; } int IndDifference() { return abs (tempIndex1 - tempIndex2); } void Show() { cout << "\ntempTour1:\n"; for (int i = 1; i <= tempIndex1; i++) cout << tempTour1[i] << " "; cout << "\ntempTour2:\n"; for (int i = 1; i <= tempIndex2; i++) cout << tempTour2[i] << " "; } }; bool MakeArrays(Task allTasks[], int n, int tour1[], int tour2[], int &index1, int &index2, int freeTasks[], int &indexFree) { bool ListsChanged; // будем проверять, сделаны ли изменения в списках туров for (;;) { indexFree = 1; ListsChanged = false; for (int i = 1; i <= 2*n; i++) { if (!(allTasks[i].IsInTour)) // поиск первой свободной задачи { if (!(allTasks[i].SameTasksFounded(tour1, index1))) // если в 1-ом туре не найдено подобных задач,... { // ...а во 2-ом туре такие есть или число задач в командах сейчас равно if (allTasks[i].SameTasksFounded(tour2, index2) || index1 == index2) { if (index1 > n) // а тут мы превысили число задач в одном туре { cout << "IMPOSSIBLE"; return false; } tour1[index1] = i; index1++; allTasks[i].IsInTour = true; // помещаем ее в 1-ый тур ListsChanged = true; } else // а если нет "врагов" ни там, ни там + индексы не равны { freeTasks[indexFree] = i; indexFree++; } } else // если в 1-ом туре есть подобные задачи,... { if (!(allTasks[i].SameTasksFounded(tour2, index2))) // ...а во 2-ом их нету { if (index2 > n) // тут мы опять превысили число задач в одном туре { cout << "IMPOSSIBLE"; return false; } tour2[index2] = i; index2++; allTasks[i].IsInTour = true; // помещаем ее во 2-ой тур ListsChanged = true; } else // а если "враги" повсюду { cout << "IMPOSSIBLE"; return false; } } } } if (!ListsChanged) // наконец, когда списки перестали меняться return true; } } int Max(int arr[], int n) { int max = arr[0], maxIndex = 0; for (int i = 1; i < n; i++) if (arr[i] > max) { max = arr[i]; maxIndex = i; } return maxIndex; } int main() { freopen("input.txt", "r", stdin); int n, m; cin >> n >> m; Task * allTasks = new Task[2*n+1]; // массив всех задач int task1, task2; for (int i = 1; i <= m; i++) { cin >> task1 >> task2; allTasks[task1].AddSameTask(task2); allTasks[task2].AddSameTask(task1); } /*for (int i = 1; i <= 2*n; i++) { cout << "Same tasks for task " << i << ": \n"; allTasks[i].Show(); }*/
int tour1[51], tour2[51]; // задачи 1-ого тура, задачи 2-ого тура int index1 = 1, index2 = 1; // индексы, указывающие, куда вставлять очередную задачу int freeTasks[101], indexFree = 1; // здесь будут храниться временно незанятые задачи, у которых на момент проверки не будет "врагов" ни в одном туре TempTours * arrTempTours = new TempTours[2*n+1]; int indexTemp = 0; // Проход по всем задачам и генерация временных пар массивов задач for (;;) { indexFree = 1; index1 = 1; index2 = 1; if (!MakeArrays(allTasks, n, tour1, tour2, index1, index2, freeTasks, indexFree)) return 0; index1--; index2--; arrTempTours[indexTemp].CreateData(tour1, tour2, index1, index2);
//cout << "\narrTempTours[" << indexTemp << "]:"; //arrTempTours[indexTemp].Show(); indexTemp++; if (indexFree == 1) break; } indexFree = 1; index1 = 1; index2 = 1; int * arrDiff = new int[2*n+1]; for (int i = 0; i < indexTemp; i++) arrDiff[i] = arrTempTours[i].IndDifference(); for (int i = 0; i < indexTemp; i++) { int tempInd1 = arrTempTours[Max(arrDiff, indexTemp)].tempIndex1; int tempInd2 = arrTempTours[Max(arrDiff, indexTemp)].tempIndex2; if (index1 == index2) { for (int j = index1; j < index1 + tempInd1; j++) tour1[j] = arrTempTours[Max(arrDiff, indexTemp)].tempTour1[j-index1+1]; index1 += tempInd1; for (int j = index2; j < index2 + tempInd2; j++) tour2[j] = arrTempTours[Max(arrDiff, indexTemp)].tempTour2[j-index2+1]; index2 += tempInd2; } else { if (index1 < index2) { if (tempInd1 > tempInd2) { for (int j = index1; j < index1 + tempInd1; j++) tour1[j] = arrTempTours[Max(arrDiff, indexTemp)].tempTour1[j-index1+1]; index1 += tempInd1; for (int j = index2; j < index2 + tempInd2; j++) tour2[j] = arrTempTours[Max(arrDiff, indexTemp)].tempTour2[j-index2+1]; index2 += tempInd2; } else { for (int j = index1; j < index1 + tempInd2; j++) tour1[j] = arrTempTours[Max(arrDiff, indexTemp)].tempTour2[j-index1+1]; index1 += tempInd2; for (int j = index2; j < index2 + tempInd1; j++) tour2[j] = arrTempTours[Max(arrDiff, indexTemp)].tempTour1[j-index2+1]; index2 += tempInd1; } } else { if (tempInd1 < tempInd2) { for (int j = index1; j < index1 + tempInd1; j++) tour1[j] = arrTempTours[Max(arrDiff, indexTemp)].tempTour1[j-index1+1]; index1 += tempInd1; for (int j = index2; j < index2 + tempInd2; j++) tour2[j] = arrTempTours[Max(arrDiff, indexTemp)].tempTour2[j-index2+1]; index2 += tempInd2; } else { for (int j = index1; j < index1 + tempInd2; j++) tour1[j] = arrTempTours[Max(arrDiff, indexTemp)].tempTour2[j-index1+1]; index1 += tempInd2; for (int j = index2; j < index2 + tempInd1; j++) tour2[j] = arrTempTours[Max(arrDiff, indexTemp)].tempTour1[j-index2+1]; index2 += tempInd1; } } } if (index1-1 > n || index2-1 > n) // переполнение числа задач в одном туре { cout << "IMPOSSIBLE"; return 0; } arrDiff[Max(arrDiff, indexTemp)] = -1; } for (int i = 1; i <= n; i++) cout << tour1[i] << " "; cout << "\n"; for (int i = 1; i <= n; i++) cout << tour2[i] << " ";
return 0; } I've been trying to get AC with this program for 2 days and... yes, it's rather big. Somebody, if you've got a heart, please give me test #3! )) Edited by author 17.09.2010 02:31 #include<stdio.h> #include<iostream> using namespace std; int a,b,n,m,g[1000][1000]; int _max = -1000; int main() { scanf("%d %d",&n,&m); for(int i = 1;i<=m;i++) { scanf("%d %d",&a,&b); g[a][b]=1; g[b][a]=1; } for(int k = 1;k<=2*n;k++) { for(int l = 1;l<=2*n;l++) { if(k==l){continue;} else if(g[k][l]==1) { g[k][l]=2; g[k][l]=2; } } } for(int k = 1;k<=2*n;k++) { for(int l = 1;l<=2*n;l++) { if(k==l){continue;} else if(g[k][l]==0) { g[k][l]=1; g[k][l]=1; } } } int key = 0; for(int k = 1;k<=2*n;k++) { for(int l = 1;l<=2*n;l++) { if(key>=2){return 0;} else if(k==l){continue;} else if(g[k][l]==1) { printf("%d %d\n",k,l); key++; } } } printf("IMPOSSIBLE"); } Very strange... I tried all tests here and they all worked well. It's a DP,right? But I always get wa4. I added this to my code: when I worked out my answer, I'll check them myself. If there are some shouldn't be in the same pair,then while(1). As a result I got TLE4. So it obviously I've made a wrong answer. BUT HOW COULD IT HAPPEN!!! Well, it was because of my wrong algo. And I've got WA7 later, that's because I misspelled IMPOSSIBLE in dfs. (There were two of this word in my prog, one is in dfs and the other is after DP) It took me an hour to debug for this! Whoa-a! it seems that my program has no bug. it pass all test on board and all my tests. I bicolored graph. then used DP to find answer but I got WA3. *** I have found mistake. AC now! this test helped me very much: 50 2 99 100 98 99 Edited by author 25.02.2007 19:13 This test is really helpful to me. Thx a lot. thanks:) ((( my DP get WA3 but brute force get AC There is no testdata like this! I didn't Consider it and ACed now. So I think the problem number is in [1,2n] For all those who got WA#3 with dfs and DP, The case given here didn't help me but 2 1 1 3 helped me. Notice that when you are selecting whether white part is to be selected or black part, and pushing the result in a vector or queue, due to DP, last part gets inserted first. So you have to consider that first result in the vector/queue is for the last pair of partition. May be this will help... Edited by author 04.01.2009 19:08 Edited by author 04.01.2009 19:08 If you think your algorithm is correct and still got WA , try to use adj-matrix,don't use adj-list I use adj-matrix but I still got WA |
|