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

Автор 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;

      }