t0nyukuk's blog

IOI practice task
By t0nyukuk, 11 years ago, In English

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

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
11 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

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 smaller

P2 < Q1 && P1 > Q2 -> country 1 is smaller

P1 > Q2 && P2 > Q1 -> country 1 is smaller if: Q1 > Q2

else 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)

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    can you publish your source code

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 5   Vote: I like it +5 Vote: I do not like it

      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<T> 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;

      }

      → Reply