Ranking the Cows [Richard Ho, 2006]

Each of Farmer John's N cows (1 <= N <= 1,000) produces milk at a different positive rate, and FJ would like to order his cows according to these rates from the fastest milk producer to the slowest. FJ has already compared the milk output rate for M (1 <= M <= 10,000) pairs of cows. He wants to make a list of C additional pairs of cows such that, if he now compares those C pairs, he will definitely be able to deduce the correct ordering of all N cows. Please help him determine the minimum value of C for which such a list is possible. PROBLEM NAME: ranking INPUT FORMAT: * Line 1: Two space-separated integers: N and M * Lines 2..M+1: Two space-separated integers, respectively: X and Y. Both X and Y are in the range 1...N and describe a comparison where cow X was ranked higher than cow Y. SAMPLE INPUT (file ranking.in): 5 5 2 1 1 5 2 3 1 4 3 4 INPUT DETAILS: FJ is comparing 5 cows and has already determined that cow 2 > cow 1, cow 1 > cow 5, cow 2 > cow 3, cow 1 > cow 4, and cow 3 > cow 4 (where the '>' notation means "produces milk more quickly"). OUTPUT FORMAT: * Line 1: A single integer that is the minimum value of C. SAMPLE OUTPUT (file ranking.out): 3 OUTPUT DETAILS: From the information in the 5 test results, Farmer John knows that since cow 2 > cow 1 > cow 5 and cow 2 > cow 3 > cow 4, cow 2 has the highest rank. However, he needs to know whether cow 1 > cow 3 to determine the cow with the second highest rank. Also, he will need one more question to determine the ordering between cow 4 and cow 5. After that, he will need to know if cow 5 > cow 3 if cow 1 has higher rank than cow 3. He will have to ask three questions in order to be sure he has the rankings: "Is cow 1 > cow 3? Is cow 4 > cow 5? Is cow 5 > cow 3?"

ძროხების დალაგება – ალექსანდრე კახიძის თარგმანი

ფერმერი ჯონის N ცალი ძროხიდან (1 <= N <= 1,000) ყველა იწველება ერთმანეთისგან განსხვავებული, დადებითი სიჩქარით რძეს. მას უნდა, რომ დაალაგოს თავისი ძროხები, ყველაზე მეწველიდან ყველაზე ცუდად მეწველამდე. ფერმერმა უკვე შეადარა M ცალი (1 <= M <= 10,000) ძროხების წყვილის წველისუნარიანობა. მას უნდა, რომ გააკეთოს C ცალი დამატებითი წყვილის სია, რომლების შედარების შემდეგაც ის უეჭველად შეძლებს ყველა ძროხის სწორად დალაგებას. მოდი დავეხმაროთ ჯონის C-ს ისეთი მინიმალური მნიშვლელობის პოვნაში, რომლისთვისაც შესაძლებელი იქნება ამ სიის შედგენა. ამოცანის სახელი: დალაგება შესაყვანი მნიშვნელობები: *ხაზი 1: ორი, ჰარით (“სფეისით”) გამოყოფილი რიცხვი N და M *ხაზები 2-დან M+1 -მდე: ორი, ჰარით გამოყოფილი რიცხვი, შესაბამისად X და Y, სადაც ორივე არის 1-დან N-მდე შუალედში. ესეთი ჩანაწერი ნიშნავს, რომ X ძროხა იწველება უფრო სწრაფად ვიდრე Y. შესაყვანი მნიშვნელობების ნიმუში (ფაილი ranking.in): 5 5 2 1 1 5 2 3 1 4 3 4 შესაყვანი მინშვნელობების დეტალები: ფერმერი ჯონი ადარებს 5 ძროხას, და მან უკვე იცის, რომ ძროხა 2>ძროხა 1, ძროხა 1>ძროხა 5, ძროხა 2 >ძროხა 3, ძროხა 1 >ძროხა 4 და ძროხა 3 >ძროხა 4 (სადაც '>' სიმბოლო ნიშნავს “იწველება უფრო სწრაფი ტემპით”). გამოსატანი მნიშვნელობების ფორმატი: *ხაზი 1: ერთირიცხვი - C-სმინიმალურიმნიშვნელობა. ნიმუშის გამოსატანი მნიშვნელობა (ფაილი ranking.out): 3 გამოსატანი მნიშვნელობის დეტალები: 5 ტესტის პასუხებისგან მიღებული ინფორმაციით, ფერმერმა ჯონმა უკვე იცის, რომ რადგან ძროხა 2 >ძროხა 1 >ძროხა 5 დაძროხა 2 >ძროხა 3 >ძროხა 4, ძროხა 2-ს უჭირავს პირველი ადგილი სიაში. ახლა მას აინტერესებს არის თუ არა ძროხა 1 >ძროხა 3, მეორე ადგილოსანი ძროხის გასარკვევად. მას კიდევ დასჭირდება დამოკიდებულების გაგება ძროხა 4-სა და ძროხა 5-ს შორის. ამის შემდეგ, ჯონმა უნდა გაიგოს არის თუ არა ძროხა 5 >ძროხა 3, იმ შემთხვევაში თუ ძროხა 1 უფრო წინ დგას სიაში ვიდრე ძროხა 3. მას დასჭირდება სამი კითხვის დასმა: “არის თუ არა ძროხა 1 >ძროხა 3? ძროხა 4 >ძროხა 5? დაძროხა 5 >ძროხა 3?”

ranking

To simplify notation, we use X->Y to denote the existence of a path of queries leading from a to b, from which we could deduce cow X is ranked higher than cow Y. An obvious upper bound for the number of queries to ask is the number of pairs of cows for which we have neither of X->Y and Y->X. It's slightly less obvious that this is also the lower bound. Suppose there exist a set of queries in which the relationship between X and Y is not queried and from the original data we could not deduce X->Y or Y->X. Then we could answer the queries in a way so X and Y's ranking end up being adjacent to each other (by making all other cows rank either lower or higher than both of X and Y). In such a case, it's clear a comparison between X and Y is necessary as otherwise, we could switch the position of X and Y without altering the results of the queries. The code for this problem is straight forward DFS to check which cows can be 'reached' by a set of information already given for each cow. Each round of DFS runs in O(M) time, giving a runtime of O(MN) Here is Brian Dean's code: #include <stdio.h> #define MAX_N 1000 #define MAX_M 10000 typedef struct { int dest; int next_edge; } Edge; char TC[MAX_N][MAX_N]; char beenthere[MAX_N]; int N, M, first_edge[MAX_N]; Edge edges[MAX_M]; void DFS(int s, int i) { int e; TC[s][i] = 1; beenthere[i] = 1; e = first_edge[i]; while (e != -1) { if (!beenthere[edges[e].dest]) DFS(s, edges[e].dest); e = edges[e].next_edge; } } int main(void) { int i, j, k, m; FILE *fp; fp = fopen ("ranking.in", "r"); fscanf (fp, "%d %d", &N, &M); for (i=0; i<N; i++) first_edge[i] = -1; m = 0; for (k=0; k<M; k++) { fscanf (fp, "%d %d", &i, &j); TC[i-1][j-1] = 1; edges[m].dest = j-1; edges[m].next_edge = first_edge[i-1]; first_edge[i-1] = m++; } fclose (fp); for (i=0; i<N; i++) { for (j=0; j<N; j++) beenthere[j] = 0; DFS(i, i); } k = 0; for (i=0; i<N; i++) for (j=i+1; j<N; j++) if (TC[i][j]==0 && TC[j][i]==0) k++; fp = fopen ("ranking.out", "w"); fprintf (fp, "%d\n", k); fclose (fp); return 0; }

ranking – ალექსანდრე კახიძის თარგმანი

ამოხსნა: ჩანაწერის გასამარტივებლად, X→Y ნიშნავდეს, რომ უკვე დაისვა ისეთი კითხვები, რომლების მეშვეობითაც შეგვიძლია გავიგოთ არის თუ არა X Y-ზე წინ სიაში. ცხადია, შეკითხვების რაოდენობის ზედა ზღვარი არის ძროხათა ისეთი წყვილების რაოდენობა, რომლისთვისაც არ ვიცით არც X→Y და არც Y→X. ნაკლებად ცხადია ის, რომ ეს არის შეკითხვების რაოდენობის ქვედა ზღვარიც. ვთქვათ, არსებობს კითხვების სიმრავლე, რომელშიც X-ის და Y-ის დამოკიდებულებაზე არ დაგვისამს შეკითხვა და არც მოცემული ინფორმაციიდან შეგვიძლია გავარკვიოთ X→Y ან Y→X. მაშინ შესაძლებელია ვუპასუხოთ კითხვებს ისე, რომ X და Y აღმოჩდნენ მეზობლები (სხვა ძროხები ან X-ის ზევითაც იქნებიან და Y-ისაც, ან იქნებიან ორივეს ქვევით. ამის გაკეთება შეგვიძლია, რადგან წინააღმდეგ შემთხვევაში ჩვენ ცალსახად განვსაზღვრავდით დამოკიდებულებას X-სადა Y-სშორის). ამ შემთხვევაში, ჩვენ დაგვჭირდება X-სდა Y-ის შედარება, რადგან ამის გარეშე ჩვენ შეგვიძლია X-სდა Y-ის ადგილების გაცვლა ისე, რომ კითხვების პასუხები იგივე დარჩეს. ამ ამოცანი სკოდი არის პირდაპირ სიღრმეში ძებნა (DFS), იმის შესამოწმებლად, თუ რომელ ძროხებს შეიძლება “მივწვდეთ” თითოეულ ძროხაზე მოცემული ინფორმაციით. სიღრმეში ძებნის თითო ციკლი მუშაობს O(M) დროში, ამოცანის სრული დრო გამოდის O(MN).

Here is Brian Dean's code

#include <stdio.h>
#define MAX_N 1000
#define MAX_M 10000

typedef struct
{
  int dest;
  int next_edge;
} Edge;

char TC[MAX_N][MAX_N];
char beenthere[MAX_N];
int N, M, first_edge[MAX_N];
Edge edges[MAX_M];

void DFS(int s, int i)
{
  int e;
  TC[s][i] = 1;
  beenthere[i] = 1;
  e = first_edge[i];
  while (e != -1) {
    if (!beenthere[edges[e].dest])
      DFS(s, edges[e].dest);
    e = edges[e].next_edge;
  }
}

int main(void)
{
  int i, j, k, m;
  FILE *fp;

  fp = fopen ("ranking.in", "r");
  fscanf (fp, "%d %d", &N, &M);
  for (i=0; i<N; i++) first_edge[i] = -1;
  m = 0;
  for (k=0; k<M; k++) {
    fscanf (fp, "%d %d", &i, &j);
    TC[i-1][j-1] = 1;
    edges[m].dest = j-1;
    edges[m].next_edge = first_edge[i-1];
    first_edge[i-1] = m++;
  }
  fclose (fp);

  for (i=0; i<N; i++) {
    for (j=0; j<N; j++) beenthere[j] = 0;
    DFS(i, i);
  }

  k = 0;
  for (i=0; i<N; i++)
    for (j=i+1; j<N; j++) 
      if (TC[i][j]==0 && TC[j][i]==0) k++;

  fp = fopen ("ranking.out", "w");
  fprintf (fp, "%d\n", k);
  fclose (fp);
  return 0;
}