### t0nyukuk's blog

By t0nyukuk, 9 years ago,

How can i solve ioi 2013 practice task problems specially citizen task

• +9

 » 9 years ago, # | ← Rev. 2 →   +11 I have a solution to the citicen task, but unfortunately I can't proof it.My Algorithm is: sort due to a special rule and than go threw the sorted array and take all elements, which are possible in attention to the previously taken ones. (i.e. Q < min(taken P))To compare two countries on smaller, you use the following function.P1 < Q2 && P2 > Q1 -> country 1 is not smallerP2 < Q1 && P1 > Q2 -> country 1 is smallerP1 > Q2 && P2 > Q1 -> country 1 is smaller if: Q1 > Q2else country 1 is smaller if: P1 > P2 Can anyone proof this... (due to tests with more than 1 Million of test data i think it is correct)
•  » » 9 years ago, # ^ |   +3 can you publish your source code
•  » » » 9 years ago, # ^ | ← Rev. 5 →   +5 Please proof or disproof it — I had this problem, when i had to explain my solution in the training programm for the IOI.struct T { T() { } T(int P, int Q) { p = P, q = Q; } int p, q; bool operator < (const T& t) const { if(p < t.q && t.p > q) return false; if(t.p < q && p > t.q) return true; if(p > t.q && t.p > q) return q > t.q; return p > t.p; } };int countries(int N, int *pP, int *pQ) { vector v; for(int i = 0; i < N; i++) v.push_back(T(pP[i], pQ[i])); sort(v.begin(), v.end()); int mi = INT_MAX; int cnt = 0; for(int i = 0; i < N; i++) { if(v[i].p < mi) { mi = min(mi, v[i].q); cnt++; } } return cnt;}