h1. Solutii preONI 2006 - Runda a 2-a

(Categoria _Competitii_, autor(i) _Echipa info-arena_)

(Categoria _Competitii_, autor(i) _Echipa infoarena_)

Runda a 2-a concursului preONI 2006 s-a incheiat. Acest articol va prezinta solutiile oficiale ale celor 7 probleme propuse.
Fiecare grupa a avut spre rezolvare 3 probleme, fiecare fiind catalogata de catre comisie ca fiind usoara, medie sau grea. Batalia pentru calificarea la finala este in toi!

Pentru mai multe detalii despre finala, cat si despre concursul preONI 2006 si sponsorii nostri va rugam sa consultati pagina "preONI-2006":http://infoarena.ro/preONI-2006.

Pentru mai multe detalii despre finala, cat si despre concursul preONI 2006 si sponsorii nostri va rugam sa consultati pagina "preONI-2006":preONI-2006.

Rezultatele finale sunt disponibile la:

* "Clasa a 9-a":http://infoarena.devnet.ro/index.php?page=stats&conid=preoni62a&smod=top
* "Clasa a 10-a":http://infoarena.devnet.ro/index.php?page=stats&conid=preoni62b&smod=top
* "Clasele 11-12":http://infoarena.devnet.ro/index.php?page=stats&conid=preoni62c&smod=top
 
Clasamente generale sunt disponibile aici:
http://infoarena.devnet.ro/clasament/preoni2006.php

* "Clasa a 9-a":preoni-2006/runda-2/clasament-9
* "Clasa a 10-a":preoni-2006/runda-2/clasament-10
* "Clasele 11-12":preoni-2006/runda-2/clasament-11-12

Dificultatea problemelor nu a lasat nici de aceasta data de dorit. Desi ne-am fi asteptat la punctaje mai mari, rezultatele concurentilor au fost decente. Provocarile oferite de Infoarena sunt intr-adevar dificile, iar obtinerea unui punctaj apropiat de cel maxim nu este usor de realizat. In editiile ce vor urma vom tine cont de acest aspect. Pana atunci va invitam sa discutati despre aceasta runda de concurs pe "forum-ul infoarena":http://forum.infoarena.ro/index.php/board,20.0.html.

Ca de obicei, problemele din acest concurs au fost puse si in "Arhiva de probleme":http://infoarena.ro/arhiva-probleme, disponibile pentru rezolvare 24 de ore din 24. Va asteptam cu forte proaspete la runda a 3-a din 21 ianuarie 2006 !!!

Ca de obicei, problemele din acest concurs au fost puse si in "Arhiva de probleme":arhiva, disponibile pentru rezolvare 24 de ore din 24. Va asteptam cu forte proaspete la runda a 3-a din 21 ianuarie 2006 !!!

h2. Dame

In primul rand, numarul maxim de dame este $N$ pentru $N = 1$ si {$N ≥ 4$}, si $N-1$ pentru {$N = 2, 3$}. Putem codifica solutia ca o permutare de la $1$ la {$N$}, astfel asigurand ca nu exista doua dame pe aceeasi linie sau coloana. O solutie clasica care foloseste metoda backtracking si face verificarea daca o dama este atacata sau nu in $O(1)$ va obtine $30$ de puncte.
Verificarea in $O(1)$ se face pastrand doi vectori pentru fiecare diagonala in functie de orientare, in care se marcheaza daca o diagonala este ocupata. O "imbunatatire" la backtracking este randomizarea ordinii in care se incearca completarea solutiei la fiecare pas. O astfel
de solutie merge usor si pentru $N = 200$ si ar fi obtinut cel putin $60$ de puncte.

Exista mai multe metode prin care s-ar fi putut obtine $100$ de puncte. O solutie greedy este urmatoarea: se incepe cu o solutie oarecare si cat timp exista doua dame care, daca s-ar interschimba coloanele lor, se imbunatateste solutia, se aplica interschibarea. Daca
nu s-a obtinut o solutie buna, se reinitializeaza solutia initiala si se reaplica algoritmul. In practica, complexitatea algoritmului tinde la {$O(N lg N)$}, desi teoretic este {$O(N^3^)$}. De asemenea pe masura ce $N$ este mai mare, numarul necesar de reinitializari ale algoritmului tinde catre {$0$}. Mai multe detalii gasiti "aici":http://www.cit.gu.edu.au/~sosic/nqueens.html

Exista mai multe metode prin care s-ar fi putut obtine $100$ de puncte. O solutie greedy este urmatoarea: se incepe cu o solutie oarecare si cat timp exista doua dame care, daca s-ar interschimba coloanele lor, se imbunatateste solutia, se aplica interschimbarea. Daca
nu s-a obtinut o solutie buna, se reinitializeaza solutia initiala si se reaplica algoritmul. In practica, complexitatea algoritmului tinde la {$O(N log N)$}, desi teoretic este {$O(N^3^)$}. De asemenea pe masura ce $N$ este mai mare, numarul necesar de reinitializari ale algoritmului tinde catre {$0$}. Mai multe detalii gasiti "aici":http://www.cit.gu.edu.au/~sosic/nqueens.html

O alta solutie , matematica, se bazeaza pe un sablon de construire a solutiei in functie de restul lui $N$ la {$12$}.
* Se insereaza numerele pare de la $2$ la $N$ intr-o lista

Daca se deplaseaza inspre $N$ sau {$S$}, cautarea se va face in {$vx$}, altel, in {$vy$}. Diferenta dintre cele doua valori returnate de cautarile binare furnizeaza numarul de celule afectate prin care Chidil trece la acea mutare.

Pentru un timp de executie bun, se recomanda folosirea functiei $sort()$ din STL pentru sortare si a containerului $pair<int, int>$ pentru pastrarea coordonatelor in cei doi vectori.

Pentru un timp de executie bun, se recomanda folosirea functiei $sort()$ din STL pentru sortare si a containerului @pair<int, int>@ pentru pastrarea coordonatelor in cei doi vectori.

h2. Grupuri

* $A{~i~} = A{~i-1~} + A{~i-3~} + 2$
* $B{~i~} = B{~i-1~} + A{~i-2~}$

Mai facem urmatoarea observatie: {$A{~i~} - B{~i-1~} = (A{~i-1~} + A{~i-3~} + 2) - (B{~i-2~} + A{~i-3~}) = A{~i-1~} - B{~i-2~} + 2$}, ceea ce inseamna ca {$A{~i~} - B{~i-1~} = 2 * (i - 1)$} (demonstratie prin inductie, tinand cont de faptul ca {$A{~2~} + B{~1~} = 2$}).

Mai facem urmatoarea observatie: {$A{~i~} - B{~i-1~} = (A{~i-1~} + A{~i-3~} + 2) - (B{~i-2~} + A{~i-3~}) = A{~i-1~} - B{~i-2~} + 2$}, ceea ce inseamna ca {$A{~i~} - B{~i-1~} = 2 * (i - 1)$} (demonstratie prin inductie, tinand cont de faptul ca {$A{~2~} - B{~1~} = 2$}).

In sfarsit, sa calculam sirul {$T{~i~} = A{~i~} + B{~i~}$}.
{$T{~i~} = A{~i~} + B{~i~} = A{~i-1~} + A{~i-3~} + 2 + B{~i-1~} + A{~i-2~} = (A{~i-1~} + A{~i-3~}) + (B{~i-1~} + B{~i-3~}) + (A{~i-2~} - B{~i-3~}) + 2 = T{~i-1~} + T{~i-3~} + (A{~i-2~} - B{~i-3~}) + 2$}. Dupa cum am observat mai devreme $A{~i-2~} - B{~i-3~} = 2 * (i - 3)$ => {$T{~i~} = T{~i-1~} + T{~i-3~} + 2 * (i - 2)$}, ceea ce ne propusesem sa demonstram.

Pentru a afla si minimul pe portiuni se procedeaza similar.

In plus, pentru o oferta vom procesa atat perechea ({$DX, DY$}), cat si ({$DY, DX$}), daca si numai
daca {$DX$} diferit de {$DY$}. Altfel, vom proceda doar ({$DX, DY$}).
 
 

In plus, pentru o oferta vom procesa atat perechea ({$DX, DY$}), cat si ({$DY, DX$}), daca si numai daca {$DX$} diferit de {$DY$}. Altfel, vom procesa doar ({$DX, DY$}).

h2. Camera

Problema pare la prima vedere destul de complicata. O solutie posibila ar fi sa pornim cu poligonul initial si sa il intersectam cu cate o dreapta determinata de fiecare din laturile lui. Aceasta rezolvare ar putea parea destul de complicata pentru ca implica intersectii de drepte cu poligoane concave. Zona din care toate laturile poligonului sunt vizibile este cunoscuta sub numele de nucleu sau kernel in engleza. Pentru ca dintr-un punct sa fie vizibila o latura a poligonului, acest punct trebuie sa fie in semiplanul determinat de aceasta latura. De aici deducem ca nucleul poligonului este de fapt intersectia celor $N$ semiplane determinate de laturile poligonului. Pornim la inceput cu o zona patrata care contine toate punctele poligonului, astfel ea va contine si nucleul poligonului. Vom taia pe rand cu semiplane acest patrat. Poligonul intermediar va fi tot timpul convex, ceea ce ne usureaza cu mult rezolvarea. Vedem in urmatoarea imagine un exemplu al pasilor algoritmului:

!http://infoarena.ro/preoni-2006/runda-2/solutii?action=download&file=nucleu1.jpg!

!preoni-2006/runda-2/solutii?nucleu1.jpg!

Parcurgem laturile poligonului intr-o ordine oarecare. Vom avea doi pointeri $cur$ si $next$ care vor reprezenta doua varfuri consecutive de pe poligonul care e solutia curenta. Daca ambele puncte sunt in interiorul semiplanului, atunci solutiei urmatoare ii adaugam punctul urmator. Daca punctul curent e in interior si punctul urmator este in exterior atunci solutiei ii adaugam punctul de intersectie {$p$}. Daca ambele puncte sunt in exterior procesam urmatoarea pereche. Daca punctul curent e in exterior si urmatorul punct este in interior atunci solutiei ii adaugam punctul de intersectie $p$ si punctul urmator. Astfel obtinem un algoritm de complexitate {$O(n^2^)$}. Mentionam ca acest algoritm poate fi folosit si la determinarea intersectiei a doua poligoane convexe.

!http://infoarena.ro/preoni-2006/runda-2/solutii?action=download&file=nucleu2.jpg!

!preoni-2006/runda-2/solutii?nucleu2.jpg!