Face The Right Way [Jeffrey Wang, 2007]

Farmer John has arranged his N (1 <= N <= 5,000) cows in a row and many of them are facing forward, like good cows, Some of them are facing backward, though, and he needs them all to face forward to make his life perfect. Fortunately, FJ recently bought an automatic cow turning machine. Since he purchased the discount model, it must be irrevocably preset to turn K (1 <= K <= N) cows at once, and it can only turn cows that are all standing next to each other in line. Each time the machine is used, it reverses the facing direction of a contiguous group of K cows in the line (one cannot use it on fewer than K cows, e.g., at the either end of the line of cows). Each cow remains in the same *location* as before, but ends up facing the *opposite direction*. A cow that starts out facing forward will be turned backward by the machine and vice-versa. Because FJ must pick a single, never-changing value of K, please help him determine the minimum value of K that minimizes the number of operations required by the machine to make all the cows face forward. Also determine M, the minimum number of machine operations required to get all the cows facing forward using that value of K. PROBLEM NAME: cowturn INPUT FORMAT: * Line 1: A single integer: N * Lines 2..N+1: Line i+1 contains a single character, F or B, indicating whether cow i is facing forward or backward. SAMPLE INPUT (file cowturn.in): 7 B B F B F B B INPUT DETAILS: There are seven cows and they are facing backward, backward, forward, backward, forward, backward, and backward, respectively. OUTPUT FORMAT: * Line 1: Two space-separated integers: K and M SAMPLE OUTPUT (file cowturn.out): 3 3 OUTPUT DETAILS: For K = 3, the machine must be operated three times: turn cows (1,2,3), (3,4,5), and finally (5,6,7): B > F F F B > F F F F > B > F F B B > F F F F > B > F B B B > F B B B > F

სახით წინ – ნიკოლოზ დონაძის თარგმანი

ფერმერმა ჯონმა თავისი N(1<=N<=5,000) ძროხა ერთ მწკრივში დალაგა. ბევრი მათგანი იყურება წინ, ანუ ისე, როგორც კარგ ძროხას შეეფერება, მაგრამ ზოგიერთი დგას ზურგით. ჯონს უნდა, რომ ყველა წინ იყურებოდეს. საბედნიეროდ, ფერმერმა ჯონმა იყიდა ძროხების ავტომატური მომტრიალებელი მანქანა. რადგან მან შეიძინა ფასდაკლებული მოდელი, მას აქვს შემდეგი შეზღუდვები: წინასწარ უნდა განისაზღვროს, რამდენ ძროხას მოატრიალებს ერთდროულად და შემდეგ ეს რიცხვი აღარ უნდა შეიცვალოს, თან შეუძლია მხოლოდ მიმდევრობით მდგომი ძროხების მოტრიალება. ყოველ ჯერზე, მანქანა ატრიალებს K ძროხისგან შემდგარ ჯგუფს (შეუძლებელია მისი გამოყენება K-ზე ნაკლებ ძროხაზე, მაგალითად ძროხების მწკრივის რომელიმე ბოლოში). ყოველი ძროხა რჩება თავდაპირველ "პოზიციაზე", მაგრამ იყურება "საწინააღმდეგო მიმართულებით". ძროხა, რომელიც იდგა სახით წინ, დადგება სახით უკან და პირიქით. ფერმერმა ჯონმა უნდა აირჩიოს K რიცხვის ერთი კონკრეტული მნიშვნელობა, რომელსაც ვეღარ შეცვლის. გთხოვთ, დაეხმაროთ მას, იპოვოს მინიმალური K, რომელიც მოგვცემს შესაძლებლობას, მინიმალური რაოდენობის ოპერაციებში მოვატრიალოთ ყველა ზურგით მდგომი ძროხა. ასევე, დაადგინეთ M, ანუ ყველა ძროხის "გასწორებისთვის" საჭირო ოპერაციების მინიმალური რაოდენობა K-სთვის. ამოცანის სახელი: cowturn შემომავალი მონაცემების ფორმატი: * პირველი ხაზი: ერთი ნატურალური რიცხვი: N * მე-2...N+1-ე ხაზები: i+1-ე ხაზზე წერია ერთი სიმბოლო, F(სახით წინ) ან B(სახით უკან) და აღწერს i-ური ძროხის მდგომარეობას. შემომავალი მონაცემების მაგალითი (ფაილი cowturn.in): 7 B B F B F B B განმარტება: არის 7 ძროხა და იყურებიან ასე: უკან, უკან, წინ, უკან, წინ, უკან და უკან, შესაბამისად. გამომავალი მონაცემების ფორმატი: * პირველი ხაზი: სფეისით გამოყოფილი ორი ნატურალური რიცხვი: K და M გამომავალი მონაცემების მაგალითი (ფაილი cowturn.out): 3 3 განმარტება: K = 3-სთვის, მანქანამ უნდა შეასრულოს სამი ოპერაცია: მოატრიალოს (1,2,3) ინდექსების მქონე ძროხები, შემდეგ (3,4,5) და ბოლოს (5,6,7): B > F F F B > F F F F > B > F F B B > F F F F > B > F B B B > F B B B > F

cowturn

We reduce the problem to finding whether we could reverse all cows given a preset turn length of k. We consider turns by the the position of the leftmost cow they affect. The 1st cow can only be turned by the first turn, so the first turn is uniquely determined. The 2nd cow can only be turned by the 1st and 2nd turn, but the 1st turn is already uniquely determined, so the 2nd turn is also fixed. If we proceed 'up' the sequence this way, we could see all the turns are uniquely determined by the configurations of the cows and the turns before them. We now need to track how many times a cow is turned by the flips before it. This is equivalent to a XOR sum of all the turn bits within k of it. This can be tracked using the standard method of keeping a pointer of whether the sequence start and moving that pointer accordingly as the location of the 'current' cow moves. This runs in O(n) time per iteration, which gives a O(n^2) algorithm in the worst case. Code by Brian Dean: #include <stdio.h> #define MAX_N 5000 int Boundary[MAX_N+1], Parity[MAX_N+1], N; int check(int k) { int i, count=0; for (i=0; i<N; i++) Parity[i] = Boundary[i]; for (i=0; i<=N-k; i++) { count += Parity[i]; Parity[i+k] ^= Parity[i]; } while (i<N) if (Parity[i++]) return MAX_N+1; return count; } int main(void) { FILE *fp = fopen("cowturn.in", "r"); int i, v, minmoves = MAX_N+1, best_k; char c, dir='F'; fscanf (fp, "%d", &N); for (i=0; i<N; i++) { fscanf (fp, " %c", &c); if (c!=dir) { dir=c; Boundary[i] = 1; } } if (dir=='B') Boundary[N] = 1; fclose (fp); for (i=1; i<=N; i++) { v = check(i); if (v < minmoves) { best_k = i; minmoves = v; } } fp = fopen ("cowturn.out", "w"); fprintf (fp, "%d %d\n", best_k, minmoves); fclose (fp); return 0; }

ნიკოლოზ დონაძის თარგმანი

ამოცანა შევამციროთ შემდეგნაირად: მოცემული K-სთვის გავიგოთ, შეგვიძლია, თუ არა, რომ ყველა ძროხა საჭირო მიმართულებით მოვატრიალოთ. მოტრიალებისას ყურადღება მივაქციოთ მხოლოდ ყველაზე მარცხნივ მდგომ ძროხას. ასევე, გავითვალისწინოთ, რომ ეს "მარცხენა" ძროხა ზუსტად განსაზღვრავს ოპერაციას და ასევე, თითოეული ძროხით დაწყებული მონაკვეთის ერთზე მეტჯერ მოტრიალებას აზრი არ აქვს(ორჯერ ერთი და იმავე ოპერაციის შესრულება არაფერს არ შეცვლის). გარდა ამისა, მნიშვნელობა არ აქვს ოპერაციების თანმიმდევრობასაც და პირობითად შეგვიძლია ვთქვათ, რომ მანქანა დგება პირველ ძროხასთან, ატრიალებს, ან არ ატრიალებს მონაკვეთს და გადადის შემდეგ ძროხაზე(ანუ, თუ მონაკვეთებს მარცხენა ძროხების მიხედვით დალაგებულად განვიხილავთ, პასუხი არ შეგვეცვლება). ამის გათვალისწინებით, შეგვიძლია ვთქვათ, რომ პირველი ძროხა შეიძლება მოტრიალდეს მხოლოდ პირველი ოპერაციით. შესაბამისად, ეს პირველი ოპერაცია ცალსახადაა განსაზღვრული პირველი ძროხის საწყისი მდგომარეობით. ანალოგიურად, მეორე ძროხა თეორიულად შეიძლება მოატრიალოს პირველმა ორმა ოპერაციამ. პირველი ოპერაცია რადგან ცალსახად განსაზღვრულია, მეორე ოპერაციის შესრულება, ან "გამოტოვება" განისაზღვრება მეორე ძროხის მდგომარეობით პირველი ოპერაციის შემდეგ და მეორე მოტრიალებაც ცხადადაა განსაზღვრული და ა.შ... გამოდის, რომ მოცემული K-სთვის ყველაფერი "ცხადია". ამის შემდეგ, მხოლოდ იმის გაგება დაგვრჩა, ძროხა რა მდგომარეობაშია წინა ოპერაციების შემდეგ. ეს ბოლო K ოპერაციის(იგულისხმება გამოტოვებაც და მოტრიალებაც) XOR-ის ექვივალენტურია(ანუ, თუ ვატრიალებთ, ოპერაციის "მნიშვნელობა" რომ იყოს 1, წინააღმდეგ შემთხვევაში-0 ). ამის გაგების სტანდარტული მეთოდია მონაკვეთს დასაწყისის შენახვა და ძროხის ინდექსთან ერთად გადაადგილება.(ანუ, იტერაციისას, ცვლილება რომ მოვნიშნოთ შესაბამისი მონაკვეთის ბოლოსთვის, იმ წერტილამდე რომ მივალთ, უკვე "დაგვხვდება" ძროხის მდგომარეობა წინა ოპერაციების შემდეგ(მექანიზმი კოდში შედარებით უკეთესად ჩანს)) ეს მუშაობს O(n) დროში ერთ იტერაციაზე და რადგან სულ არის n ცალი შესაძლო k, უარეს შემთხვევაში ალგორითმის მუშაობის დრო იქნება O(n^2).

Code by Brian Dean

#include <stdio.h>
#define MAX_N 5000

int Boundary[MAX_N+1], Parity[MAX_N+1], N;

int check(int k)
{
  int i, count=0;
  for (i=0; i<N; i++) Parity[i] = Boundary[i];
  for (i=0; i<=N-k; i++) {
    count += Parity[i];
    Parity[i+k] ^= Parity[i];
  }
  while (i<N) if (Parity[i++]) return MAX_N+1;
  return count;
}
  
int main(void)
{
  FILE *fp = fopen("cowturn.in", "r");
  int i, v, minmoves = MAX_N+1, best_k;
  char c, dir='F';

  fscanf (fp, "%d", &N);
  for (i=0; i<N; i++) {
    fscanf (fp, " %c", &c);
    if (c!=dir) { dir=c; Boundary[i] = 1; }
  }
  if (dir=='B') Boundary[N] = 1;
  fclose (fp);

  for (i=1; i<=N; i++) {
    v = check(i);
    if (v < minmoves) { best_k = i; minmoves = v; }
  }
  
  fp = fopen ("cowturn.out", "w");
  fprintf (fp, "%d %d\n", best_k, minmoves);
  fclose (fp);
  return 0;
}