002 Jocul Flip

[•benny]

Poate sa imi explice si mie cineva ce trebuie sa faca problema asta? ca stau de 3 zile la ea si nu reusesc. Pe ex dat imi ruleaza corect dar tot 0 pct iau. SE pot  face flip pe mai multe coloane si mai multr linii sau doar pe o linie si o coloana?

[•pauldb]

Se poate face flip pe oricate linii si/sau coloane.

[•benny]

Imi explica si mie cineva cum s-ar face prb asta, ca nu reusesc sa iau pct maxim si nu stiu ce am gresit.

[•toni2007]

Citeste tot topicul, sigur o sa te lamuresti.

[•vladtarniceru]

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)

[•Florian]

Nu e corect. Citeste toate paginile topicului ca sa vezi de ce si ca sa vezi cum se face!

[•KosmynC64]

Nu se precizeaza cate comutari face Gigel. Daca avem la dispozitie o infinitate de comutari pe tabla, din cate stiu eu ar trebui sa ajungem la orice aranjament, astfel ar trebui sa facem doar suma valorilor absolute numerelor de pe tabla. Doresc sa stiu, cate comutari face Gigel, doar una?

[•wefgef]

Oricate. Un exemplu pentru rationamentul tau:

Cod:

-1 1
1 -1

[•Oancea.Catalin]

Pai pentru testul
-1 1
1 -1
suma maxima este 4

Eu am verificat pe linii si pe coloane in acelas timp suma si vedeam ce se intampla daca inmultesc una dintre ele cu -1 si tot nu e bine ( imi da doar 30 puncte )

[•deneo]

nu te-ai exprimat bn cu acest "vedeam ce se intampla" - poti sa dai o exemplificare?
probabil algoritmul tau sare niste cazuri care duc la solutia optima...indiciu - iei 100p cu backtraking

[•SpiderMan]

Daca ai fi citit bine enuntul, ai fi vazut ca se pot inmulti o coloana sau o linie de mai multe ori, nu doar odata.

[•Oancea.Catalin]

Cat va da pentru testul :

5 14
7 -6 -1 0 0 0 0 1 100 -175 3 18 25 0
-2 1 100 105 3 -2 1 0 -175 100 18 3 25 2
1 -2 0 100 -2 3 0 1 100 100 100 18 -1000 35
0 0 1 800 632 -34 0 -100 -175 75 3 100 -100
100 -100 100 -100 100 -100 100 -100 100 -100 100 -100 100 -100

  

[•SpiderMan]

Cu sursa de 100 pct. :

Cod:

4519

[•Oancea.Catalin]

mie imi da 4577
ciudat... pentru ca me imi da mai mult
poate cineva sa mai bage testul ala?

o sa ma apuc sa il rezolv 

[•Patrunjel]

Salut,am incercat si eu ceva,insa nustiu unde am gresit... am cotrobait umpic si prin celelalte surse,insa nu prea am inteles mare lucru...ma poate ajuta cineva?
Pe treaba asta am scos 20 de puncte:

Cod:

#include<fstream.h>
int main(){
	int N,M,i,j,Sneg,Spoz,S=0;
	ifstream fin("flip.in");
	ofstream fout("flip.out");
	fin>>N>>M;
	int v[N][M];
	for(i=0;i<N;i++)
		for(j=0;j<M;j++)
			fin>>v[i][j];
	for(i=0;i<N;i++){
		Spoz=0;
		Sneg=0;
		for(j=0;j<M;j++){
			if(v[i][j]>0)
				Spoz+=v[i][j];
			else
				Sneg+=v[i][j];}
		if(-Sneg>Spoz)
			for(j=0;j<M;j++)
				v[i][j]=-v[i][j];}
	for(i=0;i<M;i++){
		Sneg=0;
		Spoz=0;
		for(j=0;j<N;j++){
			Spoz+=v[j][i];
			Sneg+=v[j][i];}
		if(-Sneg>Spoz)
			for(j=0;j<N;j++)
				v[j][i]=-v[j][i];}
	for(i=0;i<N;i++)
		for(j=0;j<M;j++)
			S+=v[i][j];
	fout<<S;
	return 0;}

Dupa asta,m-am enervat,si am zis sa calculeze suma pozitiva,negativa,si asa mai departe,pana ii ies ochii (pixelii,vorbim de calculator).Deci am pus un while,si a iesit asta:

Cod:

#include<fstream.h>
int main(){
	int N,M,i,j,Sneg,Spoz,S=0,ok=0;
	ifstream fin("flip.in");
	ofstream fout("flip.out");
	fin>>N>>M;
	int v[N][M];
	for(i=0;i<N;i++)
		for(j=0;j<M;j++)
			fin>>v[i][j];
	while(ok++<10000){
		for(i=0;i<N;i++){
			Spoz=0;
			Sneg=0;
			for(j=0;j<M;j++){
				if(v[i][j]>0)
					Spoz+=v[i][j];
				else
					Sneg+=v[i][j];}
			if(-Sneg>Spoz)
				for(j=0;j<M;j++)
					v[i][j]=-v[i][j];}
		for(i=0;i<M;i++){
			Sneg=0;
			Spoz=0;
			for(j=0;j<N;j++){
				Spoz+=v[j][i];
				Sneg+=v[j][i];}
			if(-Sneg>Spoz)
				for(j=0;j<N;j++)
					v[j][i]=-v[j][i];}}
	for(i=0;i<N;i++)
		for(j=0;j<M;j++)
			S+=v[i][j];
	fout<<S;
	return 0;}

cu care am mai "stors" inca 10 puncte (30 in total).Insa mai sunt 70 pana la 100,si eu nustiu unde am abordat gresit problema.Ma poate ajuta cineva?
PS:Imi poate da cineva un link(preferabil in romana) de pe care sa invat backtracking(macar elementele de baza,sa zic asa).Si, eventual, sa-mi spuneti daca trebuie sa cunosc mai stiu eu ce tehnici de programare,ca sa poat intelege backtracking(recursivitate stiu,insa nu sunt "doxa").

[•petro]

dc iau 20 de puncte daca pun liniile in stiva si iau 100 daca pun coloanele? k doar e la fel scris, am modificat unde trebuia n cu m, l cu c...

[•vladtarniceru]

la ce te referi cand zici "sa le pui in stiva" ?

[•petro]

ma refer cand pun valorile 1/-1

[•paunmatei7]

trebuie sa luam toate nr pozitive asa iei 100

[•vladtarniceru]

trebuie sa luam toate nr pozitive asa iei 100

nu-i adevarat deloc (cum adica sa iei toate numerele pozitive? scrie in enunt ca trebuie sa inmultesti un rand cu -1 sau 1, deci daca iei, iei tot randul, nu doar numerele pozitive....). nu mai da hinturi care nu sunt bune si nu mai da hinturi daca nu-ti cere nimeni (adica eu vad ca nu ai facut problema, nici macar nu ai trimis-o, deci de unde poti fi sigur ca asta e solutia?)

hint : se face cu backtracking ...

succes si mai atent pe viitor

[•maritim]

Salut la toata lumea! Vreau si eu sa stiu cu ce gresesc. Fac un backtracking recursiv de n+m elemente. Multimea variabilelor pe care poate sa le ia e 1/-1, cum trebuie sa fac ca sa il optimizez, deoarece imi depaseste timpul pe 5 teste. Multumesc!

LE : Am reusit s-o fac facand backtracking de n elemente si calculand maximul dintre coloane : 100 pct !

[•scipianus]

Se tot chinuia un coleg sa faca problema si i-a iesit numai de 20-30pct si de asta am stat aseara sa ma uit pe forum(gandindu-ma ca oricum n-as scoate mai mult de atat) si dupa ce am citit tot(foarte multe replici comice,contre intre greedy si backtracking,etc.) am zis aseara sa incerc si eu o idee sa vad daca imi iese 
Ideea mea era sa fac toate posibilitatile pentru linii,simuland adunarea in baza 2 pentru maxim 16 linii,adica 2^16,apoi la fiecare posibilitate,dupa ce faceam flip la liniile marcate cu 1,parcurgeam toata matricea noua(pe cea initiala o pastram altundeva) si calculam suma de pe fiecare coloana in modul si o adaugam la suma si comparam cu maximul si actualizam,apoi copiam din nou matricea initiala in cea de "lucru",mai goleam vectorul cu sumele de pe coloane si generam urmatoarea posibilitate,avand o singura functie in program,anume cea pentru FlipLinie 
Deci va spun sincer ca mai mult de 10 puncte nu credeam sa iau,mai ales gandindu-ma si la timp,desi acum imi dau seama ca la 16*16 nu e asa mult,iar daca stau sa ma gandesc mai bine ce am facut eu acopera totusi toate variantele de matrice intr-un mod mai rapid 
Oricum am ramas cu gura cascata dupa ce dintr-o singura trimitere pe infoarena(si mi-a luat 10 minute sa fac problema,fiind clasa a IX-a) am luat 100 

Multumesc pentru sfaturile de pe acest topic  Cei care inca nu v-ati prins cum se face chiar ar trebui sa cititi mai atent forumul

PS : sper ca n-am facut ceva rau postand ideea destul de completa aici 

[•robert.badea]

Ce e faza cu 2 ridicat la numărul de coloane/linii ? Că tot nu mă prind.

EDIT: Gata, m-am prins, nu mai este nevoie.

[•narcis2007]

mia dat rezultatul din exemplu dar iau doar 0 puncte...dc? ...eu vad care coloana are nr de elemente negative mai mare si retin nr coloanei si vad la fiecare linie suma minima si retin nr liniei,de aici cand intalnesc coloana si linia retinuta inmultesc cu -1...ce e gresit?

[•gabitzish1]

Ai aici 7 pagini pline cu indicii, trebuie doar sa citesti putin mai mult.