002 Jocul Flip

[•daniel_scaparici]

  Am 3 erori care ma dispera si nu imi dau seama

[•proflaurian]

@ Usurelu Daniel

Am cautat printre sursele trimise recent la problema si nu am gasit niciuna trimisa de tine. Da un nr de Job al sursei tale daca vrei sa primesti sfaturi.

[•gabitzish1]

Salut Daniel,

Te rog sa ai putin grija la calitatea posturilor tale. Azi ai postat de doua ori cam aiurea:

Numere prime :

Chiar asa de grea e .Incat sa iei 0 puncte

Nu ajuti pe nimeni, nici nu ceri ajutor. Nu e nici macar o remarca cat de cat inteligenta.

Am 3 erori care ma dispera si nu imi dau seama

Ceri ajutor? Spune care sunt erorile, nu are nimeni de unde sa stie ce erori ai tu devreme ce nu ai submitat nicio sursa la problema asta.

Pe viitor te rog sa gandesti putintel mai mult inainte sa postezi.

[•@Lyn]

am facut un back da nu iau decat 20 pe el imi da timp depasit...cum las putea face mai eficient?



PS
vedeti daca macar am facut codu sursa corect

[•@Lyn]

 :winner1:am facuto yeeeeeeee!!! am fost gresita la faptu ca faceam back si din linie si din coloana si atunci imi lua prea mult

[•lsorin_94]

as avea si eu o intrebare... o linie/coloana se poate schimba o singura data nu ? adica nu poti sa inmultesti o linie cu -1 de mai multe ori nu ?.... (daca ai putea, atunci suma maxima ce se poate obtine este suma numerelor in modul )

[•Magnus]

daca inmultesti o coloana cu -1 de ori e ca si cum n-ai fi inmultit-o deloc ( (-1)*(-1)=1 ), prin urmare nu are sens sa o inmultesti mai mult de o data.

[•costyrazvy]

  E mai bun .campion asta e prea simplu. 

[•tzoky07]

In primul rand, buna ziua.
Ieri m-am hotarat sa ma apuc de niste programare serioasa, astfel incat am inceput sa iau arhiva de probleme la rost si am dat peste problema flip.
Dupa ceva munca, a rasarit un algoritm care functioneaza pe toate cazurile prezentate aici pe forum insa problema e ca iau doar 30 de puncte din cauza rezultatelor eronate, ceea ce mi se pare ciudat, deci m-am hotarat sa va cer ajutorul.

Ideea de implementare a fost discutata si mai devreme pe forum asa ca o sa prezint un pseudocod simplu

backtracking dupa numar de linii
daca iteratorul depaseste returnez sol
in caz contrar
pentru linia normala (not flipped)
pentru fiecare coloana verific daca valoarea flipped este mai mare decat val normala
in cazul in care val normala este mai mare, adaug la total si trec la urmatoarea coloana
in cazul in care val flipped este mai mare, adaug la total, inmultesc val coloanei cu -1 si trec la urmatoarea coloana

pentru linia inmultita cu -1, acelasi lucru, doar ca... in cazul in care totalul liniei inmultite cu -1 este mai mare decat totalul liniei normale, modific matricea

orice ajutor este binevenit, mai jos este linkul catre ultima verificare
http://infoarena.ro/job_detail/648742

[•Eby7]

ideea e usoara,eu zic ca trebuie facut asa:
1:calculez suma de pe fiecare linie(linia i) si verific daca suma<suma*(-1).daca e asa inmultesti fiecare din termenii de pe linia i cu (-1);
2:calculez suma de pe fiecare coloana(coloana j) si verific daca suma<suma*(-1).daca e asa inmultesti fiecare din termenii de pe coloana j cu (-1);
3.explicatie:daca (-a)+b+(-c)=s,atunci a+(-b)+c=s*(-1);(s=(-a)+b+(-c);daca il inmultesti pe s cu (-1) este clar ca suma relatiei *(-1) este s(s cel nou))
acum nu stiu cat de rapid e acest algoritm,cred ca face mai mult de 60-70 de puncte(sper)

Exact asta a fost si ideea mea si am luat 20 de puncte pe ea...

[•PlayLikeNeverB4]

Dupa cum vezi, iti da raspuns gresit. Asta fiindca nu e corect algoritmul. Vezi posturile anterioare.

[•ColinCJ]

Sunt nou pe site, as dori putin ajutor din partea celor veterani daca se poate.Rulez problema si rezultatul imi da 28.Cu toate acestea, cand am trimis problema la verificat, am luat 0 puncte, insa problema merge si nici ca si algoritm(dpdv al corectitudinii) nu e gresit.Tin sa mentionez ca am rezolvat problema in Borland Pascal, si nu in Free.Sa fie acesta impedimentul?
Va multumesc frumos pentru atentie

[•PlayLikeNeverB4]

Numele fisierului nu e cu F mare.

[•sebinsteanu]

buna sunt mai incepator in informatica si ..
am o mica rugaminte la tine..ai putea sa-mi explici ce fac mai exact urmatoarele secvente din program?
lim=1<<n;
if(i & (1<<(j-1)))
P.S: ti-am inteles in totalitate si-ti apreciez logica cu exceptia celor mentionate..deci daca mi-ai explica putin ti-as fi recunoscator

[•vendetta]

E vorba despre operatii pe biti. Iti recomand sa cauti pe infoarena/google ce sunt. a << b <=> a * 2^b; iar secventa "i & (1<<(j-1))" verifica daca al (j-1) bit din configuratia binara a lui i are valoarea 1.

[•Mihai96]

Dupa ce am trecut singur prin toate etapele discutate aici (greedy -20pct, back simplu-40pct) am ajuns la backul optimizat care ar trebui sa dea 100 de pct, dar imi da 70 si chiar nu pot sa-mi dau seama de ce... 
Vazand ca nu gasesc nimic in neregula, am aruncat un ochi pe sursele de 100 de pct trimise si e exact aceiasi idee... Deci nu inteleg de ce nu merge...
Va rog, daca se poate uita cineva pe sursa pe care am trimis-o si sa-mi zica daca vede ceva gresit...

[•PlayLikeNeverB4]

Cod:

for(int j = 0;j < tabla.m;j++){
  sumaLinie += linie[j] * tabla.a[i][j];
}

Cred ca voiai sa scrii linie[i].

[•Mihai96]

Pai in algoritmul meu, "linie[16]" reprezinta o linie cu "m" componente, care contine semnele pentru fiecare
coloana  (generate de backtracking). Daca parcurg fiecare coloana din fiecare linie a matricei, cu "j",
atunci si vectorul cu semne pentru fiecare coloana il parcurg tot cu acelasi "j".

[•Mihai96]

Gata  , am rezolvat, a fost o problema de neatentie din partea mea  , in back-ul in care generam linia eu foloseam ca numar de coloane pe "n".

Mersi George Marcus pentru ca ti-ai aratat interesul in a ma ajuta. 

[•PlayLikeNeverB4]

A fost cam confuz ca ai numit vectorul linie desi era pentru coloane

[•rzvnden]

#include <fstream>
 
using namespace std;
 
int main()
{
    int a[100][100],n,m,sl1=0,sl2=0,smax=0,i,j;
    ifstream f("flip.in");
    ofstream g("flip.out");
    f>>n>>m;
    for(i=0;i<n;i++)for(j=0;j<m;j++)f>>a[j];
    for(i=0;i<n;i++)for(j=0;j<n;j++){sl1=sl1+a[j];
                                      sl2=sl2+(a[j]*(-1));}
                                      if(sl2>sl1)for(j=0;j<n;j++)a[j]=a[j]*(-1);
    for(i=0;i<n;i++)for(j=0;j<n;j++)smax=smax+a[j];
    g<<smax;
    f.close();
    g.close();
    return 0;
}

Imi baga in g 16 in loc de 28. Deci rezultatul evaluarii: 0 puncte. Any help?  

[•Cristian1997]

Cod:

using namespace std;
#include <fstream>
#include <vector>
ifstream fin("flip.in");
ofstream fout("flip.out");

int m, n, max1=0; // n linii    m coloane
int l[16];
int t[16][16];
vector <bool> v(17, 0);


int main()
{
    int i, j, k, gata=0, s, s1;
    fin>>m>>n;
    for(i=0; i<n; i++)
        for(j=0; j<m; j++)
            {fin>>t[i][j]; l[i]+=t[i][j];}
    while(!gata)
    {
        s=0;
        for(j=0; j<m; j++)
        {   //calculam fiecare coloana
            s1=0;
            for(i=0; i<n; i++)
                if(v[i]==1) s1-=t[i][j];
                else s1+=t[i][j];
            if(s1<0) s1=-s1;
            s+=s1;
        }
        if(s>max1) max1=s;
        for(i=n-1; i>=0 && v[i]==1; i--) v[i]=0;
        if(i>=0) v[i]=1;
        else gata=1;
    }
    fout<<max1;
    return 0;
}

imi da 50 puncte si nu stiu unde gresesc, o idee?

[•ovidiuz98]

am trimis din greseala sursa unei alte probleme si evaluatorul imi arata "in asteptare" si nu pot sa mai trimit surse 
Ma poate ajuta cineva?

[•breahnadavid]

bună, am citit tot acest topic și m-am apucat să rezolv problema..
n-am luat decît 10/20 puncte,,, m-am săturat să tot caut greșeală și nu înțeleg unde-i în algoritm sau în implementare...

Algroritmul..
1. Fac combinări de n(linii).
2. La fiecare combinare fac flip liniile din combinari si flip doar la coloanele mai mici ca 0.
3. Daca suma obtinuta e mai mare ca precedenta o salvez..

Uita-ti si codul.. care e destul de mare ))
Pot sa spun ca intra lejer in timp dar imi da raspuns gresit..

Cod:

#include <iostream>
#include<fstream>
 
 
 
using namespace std;
 
ifstream f;
ofstream g;
 
int i,j,n,m,t[20][20],a[20];

long long sss;
 
void suma()
        {
        int i,j;
        for(i=1;i<=n;i++){t[m+1]=0;
        for(j=1;j<=m;j++)t[m+1]+=t[j];}
 
        for(i=1;i<=n;i++){t[n+1]=0;
        for(j=1;j<=m;j++)t[n+1]+=t[j];}
        }
 
int sumat()
        {
 
        int qw=0;
        for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)qw+=t[j];
        return qw;
        }
 
void linie(int mn)
        {
        for(int i=1;i<=m;i++)t[mn]*=-1;
         }
void coloana(int mn)
        {
        for(int i=1;i<=n;i++)t[mn]*=-1;
        }

void afis(int k,int t[20][20])
        {
         for(int i=1;i<=k;i++)linie(a);
         suma();
         for(int i=1;i<=m;i++)if(t[n+1]<0){coloana(i);}
         int zxc;
         zxc=sumat();
         if(zxc>sss)sss=zxc;
        }
void back(int k)
        {
        if(k<=n){
        afis(k,t);
        for(int i=a[k];i<=n;i++)
                {
                int ok=1;
                int j=1;
                while(j<=k&&ok){if(i==a[j])ok=0;j++;}
 
                if(ok){
                        a[k+1]=i;
                        back(k+1);
                        }
                }
        }}
 
long long k;
 
 
int main()
{
 
f.open("flip.in");
g.open("flip.out");
 
f>>n>>m;
 
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)f>>t[j];
 
sss=sumat();
a[0]=1;
back(0);
 
g<<sss;
g.close();
}

Va rog mult,,

[•IuliaCristianaM]

Buna ziua!
Cum sunt incepatoare in acest domeniu, sigur nelamurirea mea vi se va parea o banalitate, doar ca pe mine ma calca pe nervi de ceva vreme...
Valoarea care se afla la intersectia dintre linia si coloana care trebuie inmultite cu (-1), va avea valoarea sa de la inceput? Sau va ramane la cea inmultita doar o data cu (-1)?
Acesta este codul meu:
#include <fstream>
using namespace std;
ifstream fin("flip.in");
ofstream fout("flip.out");
int x[18][18];
int main()
{
    int n,m,i,j,butc=0,butl=0,s=0,sc=0,sl=0,min1,min2;
    fin>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            fin>>x[j];
    for(j=1;j<=m;j++)
    {
        sc=0;
        for(i=1;i<=n;i++)
            sc+=x[j];
        if(j==1)
            min1=sc;
        if(sc<min1)
        {
            min1=sc;
            butc=j;
        }
    }
    for(i=1;i<=n;i++)
    {
        sl=0;
        for(j=1;j<=m;j++)
            sl+=x[j];
        if(i==1)
            min2=sl;
        if(sl<min2)
        {
            min2=sl;
            butl=i;
        }
    }
    for(i=1;i<=n;i++)
       x[butc]*=(-1);
    for(j=1;j<=m;j++)
        x[butl][j]*=(-1);
    x[butl][butc]*=(-1);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            s+=x[j];
    fout<<s;
    return 0;
}
Nu pot sa imi dau seama din ce cauza punctajul meu este 0, chiar daca am trimis 2 "tipuri" de surse: una in care valoarea aceea de la intersectie era inmultita de 2 ori cu (-1) si una in care era inmultita doar o singura data.
Va multumesc pentru timpul acordat!