Potyczki Algorytmiczne 2011: Zadanie „Wieże”.

Mój algorytm: Najgorszy czas 0.02s dla testu 8.

#include
#include
using namespace std;

int main(int argc, char** argv) {

   ios_base::sync_with_stdio(0);
   int n;

   cin >> n;

   string szachownica[n];
   string wieza("W");

   for(int i = 0; i > szachownica[i];
   }  

   int CzyRzadPusty[n];
   int m = 0;
   int h = 0;
   int PustyRzad[n];
   int PustyWiersz[n];

   for(int i = 0; i < n; ++i){
       CzyRzadPusty[i] = 0;
   }

   // Start algorytmu

   for(int i = 0; i < n; ++i){
       for(int j = 0; j < n; ++j){
            if(szachownica[i][j] != wieza[0]){
                CzyRzadPusty[j]++;
                m++;
            }
        }
       if(m==n){
            PustyWiersz[h] = i;
            h++;
         }
       m = 0;
   }
   h = 0;

   for(int j = 0; j < n; j++){
       if(CzyRzadPusty[j]==n){
            PustyRzad[h] = j;
            h++;
       }
   }

   for(int i = 0; i < h; ++i){
       szachownica[PustyWiersz[i]][PustyRzad[i]] = wieza[0];
   }
   for(int i = 0; i < n; ++i){
        cout << szachownica[i] << "\n";
   }
   return 0;
}

Kodem z zadania wspinaczka się nie pochwale, bo dostał 0 punktów(na 17 testów 3 odpowiedzi poprawne :P).

Mój najgorszy to 0,1s dla testu 9. Wszystkie testy <7 mają 0,0s. Dzięki za kod, będzie stanowił podstawę do ciekawej analizy porównawczej. Chociaż generalnie widzę, że myślałeś podobnie. Najgorszy wynik, jaki uzyskałem to 0,7s dla szachownicy 1000x1000 - test z forum.
Potyczki Algorytmiczne 2011- Zadanie próbne „Tulipany”

Ja Wieże napisałem na dwa sposoby, najpierw na ile potrafiłem czasowooptymalnie, a potem zauważając, że to zżera trochę za dużo pamięci i będzie się mieścić w limicie tylko do n około 5700 (tak, udało mi się nie doczytać, że n?1000), napisałem drugą wersję która ostatecznie miała max 0.01 w 8 teście. Wybacz kod w C a nie C++, brak komentarzy i coś-mówiących-nazw-zmiennych ;)
Wersja pierwsza (lepsza):

#include
#include
#include 

#define COL_USED  1
#define ROW_EMPTY 2

int main() {
  char *buf, *p;
  char *c, k;
  int n, i, j;

  scanf("%d\n", &n);
  buf = malloc(n * (n+1));
  c = calloc(n, sizeof*c);
  fread(buf, n, n+1, stdin);

  p = buf;
  for (i = 0; i < n; i++, p++) {
    k = 0;
    for (j = 0; j < n; j++, p++)
      if (*p == 'W')
        k = c[j] |= COL_USED;
    if (!k)
      c[i] |= ROW_EMPTY;
  }

  j = 0;
  for (i = 0; i < n; i++)
    if (c[i] & ROW_EMPTY) {
      while (c[j] & COL_USED) j++;
      buf[(n+1)*i+j] = 'W';
      j++;
    }

  fwrite(buf, n, n+1, stdout);
  return 0;
}

Wersja druga, jest minimalnie (ledwo mierzalnie dla n powyżej kilku tysięcy u mnie) wolniejsza, gdyż czyta dane w mniejszych kawałkach, a I/O zawsze jest najdroższe. Algorytm zasadniczo identyczny (nb. liniowy, tylko format danych wymusza kwadratowe ich wczytywanie).

#include
#include
#include 

#define COL_USED 1

int main() {
  int *r;
  char *buf, *c;
  int n, i, j;

  scanf("%d\n", &n);
  buf = malloc(n+2);
  r = calloc(n, sizeof*r);
  c = calloc(n, sizeof*c);

  for (i = 0; i < n; i++) {
    fgets(buf, n+2, stdin);
    for (j = 0; j < n; j++)
      if (buf[j] == 'W') {
        r[i] = j+1;
        c[j] = COL_USED;
      }
  }

  if (r[n-1])
    buf[r[n-1]-1] = '.';
  j = 0;
  for (i = 0; i < n; i++) {
    if (r[i]) {
      buf[r[i]-1] = 'W';
      fwrite(buf, n+1, 1, stdout);
      buf[r[i]-1] = '.';
    }
    else {
      while (c[j]) j++;
      buf[j] = 'W';
      fwrite(buf, n+1, 1, stdout);
      buf[j] = '.';
      j++;
    }
  }

  return 0;
}

Ostatecznie drugą wersję wysłałem, ale gdybym doczytał, że n?1000 to zostawiłbym pierwszą, jest imo lepsza. Na moim kompie czasy dla 1000 mam rzędu 0.006s przy obu.

Jeśli chodzi o drugą rundę to zrobiłem tylko Pecha.
Wymagał sporo (jak dla mnie) kombinowania, żeby wyznaczyć co i jak trzeba policzyć. A potem to już tylko trochę magii z floatami (straightforward implementacja daje spore błędy i złe wyniki.

#include
#include 

int main() {
  long double s, w, d, st = 0;
  int k, n;
  scanf("%Lf %Lf %d", &s, &w, &k);
  if (w  floor(w/k)) {
    d = (w - n*k) / (2*n-1);
    w = floor(w/k)*k;
    st = d;
  }
  do {
    d = (double) k / (2*n-1);
    if (st+d > s) {
      printf("%.3Lf\n",
          (2*n-1)*st + (1-2*n)*s + k*n);
      return 0;
    }
    st += d;
    n--;
  } while (n);
  printf("NIE\n");
  return 0;
}

Ten program zdobył 10/10, najgorszy czas miał 0.14s dla 10c i 0.13s dla 10d, w pozostałych 0.00. Dla testów z forum nie chce mi się sprawdzać.
Algorytm nie jest oczywisty (przynajmniej dla mnie ;p) więc mogę później spróbować wyjaśnić mój tok rozumowania jeśli chcesz.

To ja może trochę inne spojrzenie na to zadanie. Program napisany w pythonie i poddany dość silnej optymalizacji ;)

from sys import stdin
pom=[]
pop=pom.pop
append=pom.append
n=int(stdin.readline())
kolumny=range(-n, -0)

def f(x, y):
    x=x.find("W")
    if x > -1:
        kolumny[x]=y
    else:
        append(y)
    return x

def g(x,y):
    if x < 0:
        return (pop(), y)
    else:
        return (x, y)

def h(x):
    y=x[1]
    return "."*y+"W"+"."*(n-y-1)

map(f, stdin, xrange(n))
kolumny=map(g, kolumny, xrange(n))
kolumny.sort(key=lambda x:x[0])
print "\n".join(map(h, kolumny))

Algorytm opiera się na tym że tworzy na początku tablicę kolumn w której jako wartości zapisane są numery wierszy lub jakaś wartość ujemna w przypadku braku wieży. Tworzy też pomocniczą listę wierszy w których nie ma wieży. Następnie przechodzi przez listę z kolumn i w miejsce liczb ujemny wstawia numer wiersza, pobrany jako kolejna wartość z listy pomocniczej. Następnie zamienia tak aby tablica była indeksowana wierszami a nie kolumnami i wyświetla gotowy wynik.

Co do czasu wykonywania to w wypadku n=1000 czas wynosi ok 0,4.
Nawiasy w Java- Python lambda

Z tego co widzę to zmienił mi wordpress znaczki cudzysłowowa na inne i kod przestał być podświetlany. Jeśli by się dało to sformatować tak aby były odpowiednie wcięcia. Jeśli ktoś by chciał zobaczyć kod to dodałem go tutaj: http://pastebin.pl/41976
Nawiasy w Java- Python lambda

Jak patrzę na taki kod, to tylko czuję wewnętrzny respekt dla autora. Dzięki wielkie za obszerny komentarz z wyjaśnieniami – teraz będę to studiował parę dni. ;] Przy okazji – oczywiście, że jestem zainteresowany dokładniejszymi wyjaśnieniami, bo jak na razie, to dla mnie wygląda jak kupa znaczków. Może to przez zarwaną noc – ale wydaje mi się, że skończyłem „Przejście dla pieszych”. Może byłbyś zainteresowany napisaniem wpisu gościnnego z wyjaśnieniem zawiłości własnych programów? Chętnie opublikuję tutaj taki tekst – oczywiście wraz z informacją o autorze, jeśli będziesz sobie życzył.
Potyczki Algorytmiczne 2011- Zadanie próbne „Tulipany”

Wiedziałem, że da się to zrobić bez przejeżdżania po całej tablicy, tylko jakoś nie mogłem tego napisać, bo zawsze coś się wykładało. Dzięki wielkie, spróbuję sobie w wolnej chwili przenieść to do C++. ;]

Co do kolorowania kodu – trzeba ludziska czytać dokładnie wpis, bo widzę, że fragment z {code} każdy zauważył, ale dalszy fragment o tym, że trzeba zamienić nawiasy klamrowe na kwadratowe już nie. Zaraz pogrubię i przeredaguję ten kawałek tekstu.
Potyczki Algorytmiczne 2011- Zadanie próbne „Tulipany”

int main(int argc, const char* argv[])
{
    size_t n;
    ios_base::sync_with_stdio(false);

    cin >> n;

    string line[n];
    vector xproj = vector(n, false);
    vector yproj = vector(n, false);

    for (size_t i = 0; i != n; ++i) {
        size_t found;

        cin >> line[i];
        found = line[i].find('W');
        if (found != string::npos) {
            yproj[i] = true;
            xproj[found] = true;
        }
    }

    size_t xpos = 0;
    for (size_t i = 0; i != n; ++i) {
        if (! yproj[i]) {
            while( xproj[xpos] ) {
                xpos++;
            }
            line[i][xpos++] = 'W';
        }
        cout << line[i] << "\n";
    }
}

Dzięki. Mateuszu. Widzę, że wyprodukowałeś nieco prostszy kod niż ja. Teraz jestem zajęty, ale wieczorem przeanalizuję sobie to, co naskrobałeś. ;]
Potyczki Algorytmiczne 2011- Zadanie próbne „Tulipany”

Sorry, że nie doczytałem, że nawiasy mają być kwadratowe, ale może i lepiej, że nie zmieniałem bo jeszcze bym zmienił „cpp” na „c89″ i też byłoby źle. Nb, Twój blog zeżarł wszystkie include i nawet całego ifa razem z ciałem, zapewne przez < i >. Co to, komentujący ma ręcznie escape’ować wszystko w kodzie?
wie.c http://dpaste.org/CTiz/
wie2.c http://dpaste.org/852A/
pec.c http://dpaste.org/3a3O/

A i zawiłości nie ma aż takich znowu nadzwyczajnych. Zastanawiam się gdzie moje wyprowadzenie napisać, bo chyba w komentarzu tutaj nie da się normalnej notacji matematycznej zastosować ;)
(Przy okazji, weź popraw w moim komentarzu „literówkę” w „wieże”, bo to nie jest śmieszne i aż mnie samego razi. kthx)

Nie ma sprawy – napisałem przecież, że poprawię, jak ktoś zrobi źle. Jeśli chodzi o deklaracje include – faktycznie, WordPress ma problemy z tymi „tagami” i pomimo tego, że zainstalowałem mu odpowiednie rzeczy, żeby sobie z tym radził, to nadal są problemy. Wszystko przez to, że jeśli WordPress nie wychwyci tagów {code}, to traktuje to jako normalny tekst, a nie „fragment specjalny”.

Aczkolwiek z tego, co widzę po swoim komentarzu we wpisie o Tulipanach, jeśli ktoś od razu wstawi dobre znaczniki {code}, to wszystko jest ok. Ja teraz nawet nie mam w komentarzu tych includów, także nic nie zrobię. Myślę jednak, że jak ktoś będzie chciał wykorzystać ten kod, to domyśli się, czego brakuje. ;] Jeśli zmieniłbyś cpp na c89 to skrypt wyświetliłby poprawnie całą ramkę, ale bez kolorowania.

Może faktycznie „zawiłości” to złe słowo, aczkolwiek zachęcam do napisania tego w formie wpisu, który mógłbym tutaj opublikować – będzie to dostępne i bardziej widoczne dla szerszego grona Czytelników. Jeśli chcesz używać wzorów matematycznych, mogę zainstalować dla Ciebie wtyczkę do LaTeXa [powinno coś takiego być ;]], wtedy bez problemu będziesz mógł napisać takie wzory, jakie Ci się żywnie spodobają. Stworzę Ci konto w panelu administracyjnym, to będziesz mógł „wyżyć się” matematycznie. ;]

BTW. Błąd poprawiony. Dodałem Ciebie i Mateusza do whitelisty komentujących – zapraszam do częstszego udzielania się w komentarzach. ;]
Potyczki Algorytmiczne 2011- Zadanie próbne „Tulipany”

Szkoda zachodu.
http://tumblr.com/xt72hydiw4
Mam nadzieję, że daje się zrozumieć. Na pewno da się do tego dojść prościej, ale nie mam czasu żeby jeszcze raz się zastanawiać ;)

Jeśli opisujesz to na swoim blogu – wystarczyło powiedzieć, jeszcze tam nie byłem. ;]
Potyczki Algorytmiczne 2011- Zadanie „Wieże”

Podsyłam moją wersję napisaną w C. Jest trochę zoptymalizowana, przez co mało moim zdaniem czytelna, ale zawsze może się przydać przy analizie porównawczej ;)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
        int n, i, j;

        int *tab, *pom, *pom2;
        char *buf;

        scanf("%d\n", &n);
        buf=(char *) malloc(n+2+sizeof(int)*n*2);
        tab = (int *) (buf+n+2);
        pom =tab+n;
        memset(tab, -1, sizeof(int)*n*2);
        for(i=0; i<n; i++)
        {
               fread(buf, 1, n+1, stdin);
               for(j=0; j<n; j++)
               {
                        if(*(buf+j) == 'W')
                        {
                                *(tab+j) = i;
                                break;
                        }
               }
               if(j==n)
               {
                  *pom=i;
                  pom++;
               }
        }

        pom =tab+n;
        pom2=tab;
        for(i=0; i<n; i++)
        {
                if(*pom2 ==-1)
                {
                        *pom2=*pom;
                        pom++;
                }
                pom2++;
        }
        pom=tab+n;
        pom2=tab;

        for(i=0; i< n; i++)
        {
                *(pom+*(pom2))=i;
                pom2++;
        }

        for(i=0; i<n; i++)
        {
                //wyczysczenie buforu z poprzedniej wartosci
                *(buf+j)='.';
                j=*pom;
                *(buf+j)='W';
                pom++;
                fwrite(buf, 1, n+1, stdout);
        }
        free(buf);
        return 0;
}

Nawiasy w Java- Python lambda