Cpal

Se observa ca intr-un palindrom fiecare cifra apare de un numar par de ori, sau avem un palindrom continand o singura cifra care apare de un numar impar de ori. Asa ca pentru fiecare test vom numara cate F[x] sunt impare, pentru 1 ≤ x ≤ 9 si daca avem maximum o cifra care apare de un numar impar de ori atunci putem forma un palindrom cu cifrele date. Vom avea grija si ca palindromul sa fie numar natural, adica sa contina cel putin o cifra.

Pitagora2

A*A+N*N=C*C
N*N=C*C-A*A
N*N=(C-A)*(C+A)

De aici se observa ca (C-A) si (C+A) sunt perechi de divizori ai lui N2. Pentru a afla divizorii lui N2 vom afla prima data divizorii lui N pe care ii vom inmulti fiecare cu fiecare. Apoi vom parcurge acesti divizori si pentru fiecare divizor X ≤ N vom avea:

Y=N*N/X
A=(Y-X)/2
C=(Y+X)/2

Daca A, N, C sunt triplete pitagorice si respecta inegalitatea triunghiului, atunci vom actualiza solutia. Vom avea grija sa afisam cel mai mic A posibil, pentru a obtine un triunghi de arie minima.

Shuffle

Ne vom folosi de faptul ca shuffle-ul din enunt este o permutare, iar aplicarea shuffle-ului de K ori inseamna ridicarea permutarii la puterea K. Avand in vedere asociativitatea compunerii functiilor, putem construi un algoritm O(N log K) ridicand permutarea la putere in timp logaritmic. Aceasta solutie nu ar trebui sa se incadreze in timp, insa nu este imposibil :). O solutie O(N) se poate obtine analizand ciclurile permutarii. Observam ca aplicand o singura data shuffle-ul, fiecare element dintr-un anumit ciclu se muta cu o pozitie mai la dreapta, iar ultimul vine pe prima pozitie. Astfel, devine evident ca avem nevoie doar de restul impartirii lui K la lungimea ciclului pentru a afla pozitia finala a elementelor din ciclul respectiv.

Siret

Sa analizam mai atent constructia grafului. O muchie (i , j) exista doar daca capetele inferioare ale sireturilor i si j apar in ordine inversa fata de capetele superioare. Astfel, e natural sa vizualizam capetele inferioare ca o permutare: Muchia (i , j) exista daca si numai daca numerele i si j creeaza o inversiune in permutarea respectiva.

Aici urmeaza momentul de "ahaa" al problemei. O clica in graf reprezinta de fapt un subsir descrescator in permutare. Pentru a demonstra acest lucru, ganditi inductiv: ce faceti cand incercati sa extindeti o clica de dimensiune N cu un nou nod X. X trebuie sa aiba muchie catre toate cele N elemente deja existente in clica, adica trebuie sa fie mai la dreapta si mai mic decat toate N in permutare.

Pentru a obtine permutarea vom construi un graf complet pe baza celui din input: Daca muchia (x , y) exista in graful initial, atunci ducem un arc de la max(x , y) la min(x , y). Altfel ducem arcul invers. Sortand topologic acest graf, obtinem permutarea dorita.

Astfel, avand permutarea, putem folosi algoritmul trivial in O(N ^ 2) pentru cel mai lung subsir descrescator.