128 Curse de cai

[•DITzoneC]

Cred ca ar trebui sa dea

600

Ii pui sa concureze asa:

6 4 4 4 4 2 2 2 1
4 4 4 4 2 2 1 1 4

[•gabitzish1]

am verificat toate exemplele de pe forum + vreo 2 de'ale mele.. toate imi dau cat ar trebui (ma refer la cele de pe forum.. )... totusi.. iau incorect.... .. vreo sugestie?

[•coderninu]

Toate testele de pe forum si exemplu imi dau bine. Sortez crescator si fol doua deque.
Are cineva timp sa se uite peste sursa mea si sa imi dea un exemplu pe care nu merge?

[•Marius]

Nu ştiu unde ai folosit deque. Se poate şi fără.

[•miculprogramator]

Fara dinamica/greedy nu se poate? Merita incercat un brute ? 

[•wefgef]

Nu prea sunt probleme pe infoarena care sa mearga cu brute .

[•miculprogramator]

Am inteles...

[•Marius]

Fara dinamica/greedy nu se poate? Merita incercat un brute ? 

Pentru ca unul să joace cât mai bine, celălalt trebuie să joace cât mai prost. Ţin minte că jucând cât mai prost am reuşit să rezolv foarte uşor problema cu Greedy.

[•miculprogramator]

Eu m-am gandit sa sortez caii crescator. Compar primul cal al lui Gigel cu armasarul lui Ionel. Daca este mai mare Gigel +200,daca este egal 0, daca este mai mic -200.

Si asa aflu profitul lui Gigel. Nu cred ca este varianta cea mai optima,dar asta mi-a venit in minte.

Eu Greedy si dinamica nu stiu...

[•c_e_manu]

Nu cred ca e chiar corect ce ai spus tu, dar sa stii ca modalitatea ta de rezolvare e o tehnica greedy. Pe scurt in asta consta greedy: alegerea variantei optime (ce pare optima) la fiecare pas si de multe ori sortezi intr-un anumit mod datele. Sper ca nu m-am bagat in seama degeaba Bafta!

PS:Esti fana LP? 

[•miculprogramator]

Mersi pentru indicatii. O sa revin la problema asta dupa ce citesc cate ceva despre greedy. 


P.S: Linkin Park rocks. 

[•Patrunjelu]

Hi, thread necromancer here. All jokes aside, asta-i rezolvarea mea:

Cod:

 #include <stdio.h>
#include <algorithm>
using namespace std;
const long infi = 2147483647;
long t, n, suma;

long caiA[1010];
long caiB[1010];

int main()
{
    freopen("cai.in", "r", stdin);
    freopen("cai.out", "w", stdout);
    scanf("%d", &t);
    bool fweaker;
    bool fequal;
    int retinequal;
    int retincmm;
    for (int i = 0; i < t; ++i)
    {
        suma = 0;
        scanf("%d", &n);
        for (int j = 0; j < n; ++j) //Citim caii lui gigel
        {
            scanf("%d", &caiA[j]);
        }
        for (int j = 0; j < n; ++j) //Si caii lui ionel
        {
            scanf("%d", &caiB[j]);
        }
        sort(caiA, caiA + n); //Ordine crescatoare
        sort(caiB, caiB + n); //Ordine crescatoare
        for (int j = 0; j < n; ++j) //Pentru fiecare cal de-al lui Gigel, pornind de la cel mai slab
        {
            fequal = false; //Presupunem ca nu poate face remiza cu nici un cal de la Ionel
            fweaker = false; //Presupunem ca nu exista cal de-al lui Ionel mai slab decat calul curent de la Gigel
            retinequal = 0; //Retine pozitia pe care se afla calul cu care poate face remiza
            retincmm = -1; //Retine pozitia celui mai puternic cal de la Ionel. La fiecare cursa, presupunem ca nu am gasit inca
            for (int q = n-1; q >= 0; --q) //Pentru fiecare cal de-al lui Ionel, de la cel mai puternic in jos
            {
                if (caiA[j] > caiB[q]) //Daca calul curent al lui Gigel il poate bate pe cel al lui Ionel
                {
                    suma += 200; //Marim suma deoarece a obtinut o victorie
                    caiB[q] = infi; //Calul curent al lui Ionel a fost invins (nu va mai concura)
                    fweaker = true; //Am gasit un cal mai slab decat al lui Gigel
                    break; //Oprim for-ul
                }
                else //Altfel
                {
                  if ((caiA[j] == caiB[q]) && (fequal == false)) //Daca puterea celor doi este identica si nu am gasit inca o astfel de pereche
                  {
                      fequal = true; //Mentionam ca am gasit o pereche
                      retinequal = q; //Retinem pozitia pe care se afla calul pt. remiza @ Ionel
                  }
                  else //Altfel, calul lui este mai puternic decat al lui gigel
                  {
                       if ((caiB[q] != infi) && (retincmm == -1)) //Daca calul nu a participat deja la curse si nu am gasit deja un cal mai puternic la Gigel
                         retincmm = q; //Retinem pozitia pe care se afla calul cel mai puternic
                  }
                }
            }
            //Gata for-ul
            if (fweaker == false)
            {
               if ((fequal == true) && (retincmm == -1)) //Daca putem face remiza
               {
                caiB[retinequal] = infi; //Facem
                //continue;
               }
               else
               {
               //altfel...
                suma-=200;
                caiB[retincmm] = infi; //Si il scoatem din joc pe cel mai puternic cal de-al lui Ionel
               }
            }
        }
        printf("%d\n", suma);
    }
    return 0;
}

Mai exact, eu sortez crescator caii (retinuti in 2 siruri) si incepand cu primul cal al lui Gigel (cel mai slab), verific cu fiecare cal de-al lui Ionel (incepand cu cel mai puternic -> parcurg descrescator) care-i situatia. Fiecare cal de-al lui Gigel incearca sa bata un cal cat mai puternic de la Ionel. Daca nu poate asta, atunci il scoate pe cel mai puternic cal de-al lui Ionel din joc (din multimea de cai care nu au participat inca la curse), pentru a face viata mai usoara cailor ce urmeaza. Daca cumva nu poate bate un cal si nici nu-i unul mai puternic disponibil, face remiza.
infi marcheaza un cal care a participat deja la cursa.

Pe toate exemplele mele da bine. La fel si pe cele de pe forum. Nu prea imi vine nimic in minte in momentul asta. In caz ca e cineva de pe aici dispus sa se uite la vechile surse de 100p  pentru mine, ar fi super Sau daca greseala mea se observa usor, astept sugestii.

[•Master011]

Cat de mare poate sa fie T-ul (numarul de teste)? 

[•Schumi]

Numarul de teste nu influenteaza in nici un fel algoritmul de rezolvare

[•pauldb]

Conteaza, daca vrei sa stii ca algoritmul tau are complexitatea buna. T <= 20, am completat si enuntul.

[•Master011]

Mersi mult  Eu stiu sa fac problema in O(T*n^2)  dar este cam la limita... care este complexitatea buna?

[•pauldb]

Da, e ok.

[•andreiiii]

Testul nu este suficient de bun. Iau 100 dar pe testul:
2
20 20
20 30
imi da 0 , ar trebui sa-mi dea -200.

[•japjappedulap]

Pe absolut toate testele care le-am facut imi da bine (si pe cele de pe forum), si tot primesc 0 puncte . Va rog, veniti cu niste cazuri particulare.

Uitati-va va rog si pe sursa http://www.infoarena.ro/job_detail/1232853?action=view-source

[•xtreme77]

Nu cred ca ai vreo sansa sa scoti problema asta de 100 cu o complexitate mai buna de O ( n ^ 2 ) . Poti incerca o varianta cu dinamica sau o varianta cu un greedy care se vrea a fi mai degraba un brut.  Numai bine si succes . Solutia oferita de tine nu cred ca este optima . Cred ca greseala e la nivelul conceptual,nu la nivelul care tine de implementare.

[•andrei.arnautu]

Frumoasa problema!