t0nyukuk's blog

By t0nyukuk, 9 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

»
9 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)

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

    can you publish your source code

    • »
      »
      »
      9 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;

      }