Jump to content

SUBIECTE NOI
« 1 / 5 »
RSS
Tehnologia DSL la Orange?

conectare navigație auto la ...

Care e pretul corect pe mp?!

Auto 200-250km/zi autostrada, fia...
 Idei noi? Ce verificam la o masin...

Încarcare acumulatori LiPo de 1,5v...

cel mai ieftin generator trifazic

Iti place sa mananci iute?
 cum il cheama pe acest SSD?

Trec ITP-ul daca am montat alt mo...

Problema mesaj supraincalzire tel...

Recuperare Cont Yahoo mail
 Legislatie ambiguua/incompatibili...

Radio Argon 1 se aude foarte incet

Nu gasesc optiunea de a afisa(nu ...

Glafuri interioare mozaic
 

Problema: sa se gasesca numarul de subarrays din array

- - - - -
  • Please log in to reply
11 replies to this topic

#1
wolfenste

wolfenste

    Member

  • Grup: Members
  • Posts: 529
  • Înscris: 02.05.2018
Se da un array foarte mare (deci o rezolvare naiva nu va functiona din cauza performantei) si se cere numarul de subarray-uri in care fiecare element continut sa se repete de un numar impar de ori. Subarray-urile trebuie sa fie continue, adica formate din elemente consecutive din array-ul de input.

Cu ce se mananca (pardon rezolva) asta? Ce tip de algoritm trebuie aplicat?

De exemplu:
Input [1, 2, , 1, 1, 6]
Output: 11

[1], [2], [1], [1], [6], [1, 2], [1, 2, 1, 1], [1, 2, 1, 1, 6], [2, 1], [1, 1, 6], [1, 6]

#2
wolfenste

wolfenste

    Member

  • Grup: Members
  • Posts: 529
  • Înscris: 02.05.2018
LE: fara [1, 1, 6] ca se repeta 1 de un nr par de ori, deci output 10
LE2: este utila greseala asta ca explica si mai bine problema :)

Edited by wolfenste, 11 July 2022 - 12:32.


#3
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 28,806
  • Înscris: 10.08.2005
La cum ai formulat si expus problema exista ai urmatoarea problema matematica
o multime de elemente contine x submultimi.
o multime de elemente poate contine multimea vida.
Este multimea vida submutime ?
Poate o submultime contine multimea vida?
Daca ai o multime cu un singur element, acesta se repeta de zero ori, deci par.
Deci n-am incredere in exemplu tau.


#4
wolfenste

wolfenste

    Member

  • Grup: Members
  • Posts: 529
  • Înscris: 02.05.2018
Mai bine ai incredere in exemplu. Sa lasam multimile. Sa revenim la arrays.

Este multimea vida submutime ?
Da in matematica, in problema noastra cu arrays nu ne incurcam cu multimea vida.

Poate o submultime contine multimea vida?
Nu. Nu ca element. Nici macar in matematica. Pentru ca multimea vida nu e element in multimea de baza. Este multimea fara element inclusa in orice multime.

Daca ai o multime cu un singur element, acesta se repeta de zero ori, deci par.
Ehm... sa apara in subarray de un numar impar de ori. Nu mai am cum sa editez, sa speram ca cititorul ia comentariile la rand si nu e daltonist.

Nu cer sa-mi rezolvati problema. Dar cineva avansat in algoritmica poate sa identifice ce gen de problema e aceasta si ce fel de algoritm se preteaza. Asta vreau sa aflu. Detaliile problemei pot sa difere, modul de rezolvare fiind asemenator. DEci detaliile conteaza mai putin.

Edited by wolfenste, 11 July 2022 - 13:17.


#5
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 28,806
  • Înscris: 10.08.2005
pai eu pe exemplu ma uit
la tine, la input, se poate sa contina multimea vida.
[1,2,,1,1,6]
intre 2 si 1 ai multimea vida


#6
wolfenste

wolfenste

    Member

  • Grup: Members
  • Posts: 529
  • Înscris: 02.05.2018
E typo..

Am postat pe aria C++ pentru ca nu prea am unde sa pun intrebari generice ce nu tin de un limbaj dar sunt totusi de programare mai exact algoritmica.

#7
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 28,806
  • Înscris: 10.08.2005
Intrebarile generice merg in aria generala.

#8
darkangel2

darkangel2

    Active Member

  • Grup: Members
  • Posts: 1,919
  • Înscris: 26.01.2019
As incerca programare dinamica (babeste = rezolvarea problemei "din aproape in aproape").
Din pacate, programarea dinamica nu este un algoritm propriuzis, ci o modalitate de abordare a unei probleme care genereaza un algoritm foarte specific problemei date.
Programarea dinamica functioneaza doar daca problema are anumite caracteristici speciale, nu functioneaza cu orice problema.
La prima vedere, pare ca problema data s-ar preta la programare dinamica (s-ar putea sa ma insel).

Edited by darkangel2, 11 July 2022 - 13:33.


#9
MarianG

MarianG

    be that as it may

  • Grup: Moderators
  • Posts: 28,806
  • Înscris: 10.08.2005
[ https://www.youtube-nocookie.com/embed/bOXCLR3Wric?feature=oembed - Pentru incarcare in pagina (embed) Click aici ]

#10
wolfenste

wolfenste

    Member

  • Grup: Members
  • Posts: 529
  • Înscris: 02.05.2018
Ok, sa zicem ca o generating function as sti sa fac dar pana acolo imi trebuie un pattern pe care nu il gasesc. E mult mai complicat decat pare la prima vedere, multa imbarligatura. Posted Image

#11
dani.user

dani.user

    Guru Member

  • Grup: Senior Members
  • Posts: 29,390
  • Înscris: 24.02.2007
Suna a ceva unde s-ar preta un prefix array, gen https://www.geeksfor...ve-programming/

#12
Mosotti

Mosotti

    Geniu umil

  • Grup: Senior Members
  • Posts: 33,279
  • Înscris: 21.04.2004
Ce inseamna array foarte mare?

Anunturi

Chirurgia cranio-cerebrală minim invazivă Chirurgia cranio-cerebrală minim invazivă

Tehnicile minim invazive impun utilizarea unei tehnologii ultramoderne.

Endoscoapele operatorii de diverse tipuri, microscopul operator dedicat, neuronavigația, neuroelectrofiziologia, tehnicile avansate de anestezie, chirurgia cu pacientul treaz reprezintă armamentarium fără de care neurochirurgia prin "gaura cheii" nu ar fi posibilă. Folosind tehnicile de mai sus, tratăm un spectru larg de patologii cranio-cerebrale.

www.neurohope.ro

0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users

Forumul Softpedia foloseste "cookies" pentru a imbunatati experienta utilizatorilor Accept
Pentru detalii si optiuni legate de cookies si datele personale, consultati Politica de utilizare cookies si Politica de confidentialitate