Блог пользователя t0nyukuk

IOI practice task
Автор t0nyukuk, 11 лет назад, По-английски

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

  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

»
11 лет назад, # |
← 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 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)

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    can you publish your source code

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
      ← 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<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;

      }

      → Ответить