Digraphs

Sizden kare şeklinde bir tablo doldurmanız isteniliyor. Bu tablo küçük harflerden oluşacak ve max 20x20'lik bir kare olabilecek. Bu tabloyu doldururken tabi ki bazı kurallara uymanız gerek.

Size n tane 2 küçük harften oluşan stringler verilecek. Örneğin stringlerden biri "xy" olsun. Sizin dolduracağınız tabloda y, x'in bir sağında veya x'in bir altında olamaz.

Amacınız olabildiğince büyük bir kare tablo oluşturmak. Ayrıca bu kare çok büyük olabileceği için sizden max 20x20'lik bir kare istenmektedir.

Input Format
İlk satırda T:Test Case sayısı
Case'in ilk satırı n: Yasaklı string sayısı
Sonraki n satırda yasaklı stringler

Output Format
Kurallara uyan ve size'i max 20x20 olan bir kare tablo

Constraints
0 <= n <= 676

Input
2
628
aa
az
ba
bb
bc
...
by
ca
cb
cc
...
cy
...
...
ya
yb
yc
...
yy
za
zb
zc
...
zy
zz
2
aa
bb

Output
aw
wz
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
_______________________________

Linkler

Soru: http://codeforces.com/gym/100299 (K sorusu)
pdf: http://codeforces.com/gym/100299/attachments/download/2035/20132014-acm-icpc-central-european-regional-contest-cerc-13-en.pdf
Solutions: http://cerc.tcs.uj.edu.pl/2013/data/cerc2013solutions.pdf
_______________________________

Çözüm

Alfabenin 26 harfini birer node kabul edelim. Başlangıçta tüm nodelar arasında yol olan tam graph oluşturalım. Yasaklı stringler verildikçe yolları silelim. Oluşan graph'ımızda 2 farklı ihtimal vardır. Ya cycle buluncak ya da bulunmayacak. Bu 2 ihtimale göre farklı tablo oluşturma stratejileri izleyeceğiz.

Cycle varsa

Herhangi bir cycle'i kullanarak kolaylıkla 20x20'lik kare şeklinde bir tablo oluşturabiliriz. Sırasıyla "abc" diye bir cycle olduğunu düşünelim. İlk satırı "abcabc..." şeklinde oluştururuz ve her sonraki satırda ilk karakterimizi bir kaydırırız. 2.satırda "bcabca...", 3.satıtda "cabcab...", 4.satırda tekrar "abcabc..." olur. Peki cycle'i nasıl bulabiliriz?
Yanlış yaklaşım: Akla ilk gelen SCC yapmak oluyor ki kodlaması yapacağımız işe göre uzun. SCC kodlamanın diğer bir problemi elimize gelen SCC'nin sıralı bir şekilde olmaması. Örneğin cycle sırasıyla "abc" olsun. Bizim elimize "acb" şeklinde geçebilir. Bunun için ekstradan SCC'yi gezme sırasına göre sıralamamız gerekecek ki işimiz uzayacak ve kod bazen patlayacak.( Ben ve Kamil beceremedik :( )
Cycle bulma: Dfs'i kodlarken mark array'ini 0-1 şeklinde tutarız. Burada array'i 0-1-2 şeklinde tutacağız ve ek olarak Stack kullanacağız. Bir node'a ilk kez geldiysek node'un mark'ini 2 yapacağız ve stack'e atacağız. Fonksiyondan çıkarken mark'i 1 yapacağız ve stack'ten çekeceğiz. Eğer ki bu node'a önceden gelindiyse ve mark'i 2 ise bu node hala stack'tedir ve cycle vardır. Stack'ten bu node gelene kadar node'ları çekeriz ve her gelen node'ları cycle listemizin başına atarız. Bundan sonra geriye kalan tek şey tabloyu oluşturmak.

Cycle yoksa

DP kullanarak en uzun yolu buluruz. Amacımız KxK'lık kare oluşturmak ve bunu oluştururken 2*k-1 uzunluğunda bir yol bulmak. Eğer en uzun yolumuz 2*k uzunluğunda ise ilk veya son karakterini sileriz. Stratejimiz şöyle olacak... Tablonun ilk satırını en uzun yolumuzun ilk k karakteri ile dizelim. Ardından gelen her satırda ilk karakteri bir kaydıralım. Örneğin yolumuz "abcdef" ise uzunluk çift olduğu için son karakteri sileriz. "abcde" stringi kalır. İlk satır "abc", sonraki satır"bcd", ondan sonraki satır "cde" olur.
_______________________________

Kod

#include <algorithm>

#include <string.h>

#include <stdio.h>

#include <vector>

#include <stack>

#define  pb       push_back

using namespace std;

int T,n;

int dp[26];

int best[26];

int mark[26];

int ar[26][26];

vector<int>v;

stack<int>sta;

void Cycle()

{

  int sz=v.size();

  for(int i=0 ; i<20 ; i++)

  {

    int bas=i%sz;

    for(int j=bas ; j<bas+20 ; j++)

      printf("%c",v[j%sz]+'a');

    printf("\n");

  }

}

int f(int node)

{

  if(v.size())      return dp[node];

  if(mark[node]==1) return dp[node];

  if(mark[node]==2)

  {

    while(sta.top()!=node)

    {

 v.pb(sta.top());

 sta.pop();

}

v.pb(node);

reverse(v.begin(),v.end());

Cycle();

return dp[node];

  }

  dp[node]=1;

  mark[node]=2;

  sta.push(node);

  for(int i=0 ; i<26 ; i++)

    if(!ar[node][i])

    {

 int x=f(i)+1;

 if(v.size())   break;

 if(x>dp[node]) dp[node]=x,best[node]=i;

}

  if(!sta.empty()) sta.pop();

  mark[node]=1;

  return dp[node];

}

void Reset()

{

  v.clear();

  memset(ar,0,sizeof(ar));

  memset(mark,0,sizeof(mark));

  while(!sta.empty()) sta.pop();

}

int main()

{

  scanf("%d",&T);

  while(T--)

  {

Reset();

    scanf("%d",&n);

    for(int i=0 ; i<n ; i++)

    {

 char s[5];

 scanf("%s",s);

 ar[s[0]-'a'][s[1]-'a']=1;

}

int b1=0,b2=0;

for(int i=0 ; i<26 ; i++)

 if(!mark[i])

 {

   int x=f(i);

   if(x>b1) b1=x,b2=i;

 }

if(v.size()) continue;

if(b1%2==0)  b1--;

v.pb(b2);

for(int i=1,x=b2 ; i<b1 ; i++)

{

 x=best[x];

 v.pb(x);

}

for(int i=0 ; i<(b1+1)/2 ; i++,printf("\n"))

 for(int j=0 ; j<(b1+1)/2 ; j++)

   printf("%c",'a'+v[i+j]);

  }

  return 0;

}