infoarena informatica de performanta
info
arena
b
log
f
orum
calendar
autentificare
inregistrare
infoarena
>
infoarena - concursuri, probleme, evaluator, articole
>
Concursuri
> Subiect:
[Concurs] Google Codejam Online Round 2
Pagini: [
1
]
În jos
« mesajul precedent
următorul mesaj »
Imprimă
Ajutor
Subiect: [Concurs] Google Codejam Online Round 2 (Citit de 2841 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
•
pauldb
Nu mai tace
Karma: 821
Deconectat
Mesaje: 1.901
[Concurs] Google Codejam Online Round 2
«
:
Iulie 26, 2008, 17:39:42 »
Sambata, 2 august, de la ora 19:00 va avea loc concursul
Google Codejam Online Round 2
.
Memorat
Am zis
•
mariusdrg
Client obisnuit
Karma: 70
Deconectat
Mesaje: 59
Răspuns: [Concurs] Google Codejam Online Round 2
«
Răspunde #1 :
August 03, 2008, 10:36:58 »
Nu ar fi bine sa se discute problemele care au trecut, daca nu pentru mai mult, macar pentru curiozitatea participantilor? Daca ar fi mai multa lume de acord cu asa ceva s-ar putea face dupa fiecare concurs un topic cu idei.....
Memorat
•
wefgef
Nu mai tace
Karma: 1049
Deconectat
Mesaje: 3.008
razboinicu' luminii
Răspuns: [Concurs] Google Codejam Online Round 2
«
Răspunde #2 :
August 03, 2008, 10:40:35 »
Mi se pare o idee foarte buna sa se discute problemele pe forum. Am putea sa le discutam chiar in topicurile din aceasta sectiune, si asa majoritatea au 0 posturi
Memorat
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
•
mariusdrg
Client obisnuit
Karma: 70
Deconectat
Mesaje: 59
Răspuns: [Concurs] Google Codejam Online Round 2
«
Răspunde #3 :
August 03, 2008, 11:02:03 »
Ok.. pai atunci ii dam bice?
Ideile mele
La prima aia cu arborele boolean... Se putea face o dinamica pe arbore a[ i ][0/1]....
La a 2a e destul de clar ca un punct dintre cele trei ale triunghiului trebuie sa fie intr-un varf din cele 4 ale dreptunghiului mare... si consideram punctul asta primul punct (x1,y1) cu coordonate fie(0,0), fie(0,m)(n,0) sau (n,m). Prin tranzlatie putem sa facem punctul x1,y1 sa fie (0,0)(pt a face calculele mai usoare) si atunci avem 3 puncte (0,0), (y2,x2) si (x3,y3)... deci daca facem determinantul ne da ca aria este 0*y2 + x2 * y3 + y3 * 0 - 0 * x2 - y2 * x3 - 0 * y3 = A * 2; deci x2 * y3 - y2 * x3 = A * 2. Deci iteram cu x2 prin toate cele n posibilitati si cautam binar y2 astfel incat punctul x3,y3 sa ne dea in interiorul dreptunghiului(daca un segment toate punctele care alese ca al 3lea punct sa dea arie egala se afla pe o dreapta, asta din cauza ca inaltime * segm dat e constant).
Si la a4a pt 5 puncte faci toate permutarile.
Daca are cineva alte idei sau poate solutii la ultimele 2 probleme ar fi foarte apreciate.
«
Ultima modificare: August 05, 2008, 09:46:06 de către Bogdan Tataroiu
»
Memorat
•
alexthero
De-al casei
Karma: 121
Deconectat
Mesaje: 129
Răspuns: [Concurs] Google Codejam Online Round 2
«
Răspunde #4 :
August 03, 2008, 18:13:20 »
La a 4a fixezi caracterul care se afla pe prima pozitie in fiecare grup si cel care se afla pe ultima pozitie in fiecare grup (K^2). Apoi faci o dinamica in 2^(K - 2) * N. A[ i ][ j ] = alea minime aparute daca am trecut de primele i pozitii (i <= k) si cu configuratia j (ce permutari mai am voie sa folosesc).
Complexitate totala: O(K^2 * 2 ^ (K - 2) * N).
Sper sa fie ok, nu am implementat.
«
Ultima modificare: August 03, 2008, 18:23:59 de către Tandrau Alexandru
»
Memorat
Tine minte ca mintea conduce pumnu, nu invers
•
pauldb
Nu mai tace
Karma: 821
Deconectat
Mesaje: 1.901
Răspuns: [Concurs] Google Codejam Online Round 2
«
Răspunde #5 :
August 04, 2008, 18:17:30 »
Pentru problema a 4-a se poate mai bine: O(N*K + K^3 * 2^K).
Initial precalculcam A[ i ][ j ][0 / 1] = cu cat este influentata lungimea totala daca intr-o permutare oarecare urmeaza pozitia i dupa pozitia j si i si j sunt sau nu in acelasi grup de K. => complexitate K^2 * N/K => K*N
Apoi facem o dinamica C[ i ][ j ][ k ] = care este lungimea totala minima daca pentru permutarea cu configuratia binara k prima cifra este i si ultima cifra este j. Recurenta este O(K) (iteram cifra precedenta) => K^3 * 2^K.
Daca se poate si mai bine, as fi curios sa aflu.
Memorat
Am zis
•
blasterz
Nu mai tace
Karma: 92
Deconectat
Mesaje: 255
Răspuns: [Concurs] Google Codejam Online Round 2
«
Răspunde #6 :
August 05, 2008, 11:31:36 »
La a 3a (Star Wars) merge Simulated Annealing
Memorat
Pagini: [
1
]
În sus
Imprimă
infoarena
>
infoarena - concursuri, probleme, evaluator, articole
>
Concursuri
> Subiect:
[Concurs] Google Codejam Online Round 2
« mesajul precedent
următorul mesaj »
Schimbă forumul:
Selectează o destinaţie:
-----------------------------
infoarena - concursuri, probleme, evaluator, articole
-----------------------------
=> Concursuri
===> Junior Challange 2023
===> Algoritmiada 2022
=====> Runda 1
=====> Runda 2
=====> Runda 3
=====> Runda 4
===> Summer Challenge 2021
===> Junior Challenge 2021
===> FMI No Stress 10
===> Winter Challenge 2020
===> Autumn WarmUp 2020
===> Summer Challenge 2020
===> Junior Challenge 2020
===> Concurs de incalzire 2020
===> FMI No Stress 9
===> Autumn WarmUp 2019
===> Summer Challenge 2019
===> Junior Challange 2019
===> Algoritmiada 2019
===> Info Oltenia 2019
===> Arhiva concursuri
=====> Info Oltenia 2018
=====> Junior Challenge 2018
=====> Algoritmiada 2018
=====> AGM 2018
=====> Grigore Moisil 2018
=====> RCPC 2018
=====> Fmi No Stress 8
=====> Urmasii lui Moisil 2017
=====> Grigore Moisil 2017
=====> Prosoft @ NT
=====> Algoritmiada 2017
=====> PreOJI 2017
=====> FMI No Stress 2017
=====> AGM 2017
=====> Lot 2017
=====> ACM ICPC Faza Nationala 2017
=====> PreOJI 2016
=====> ONIS 2016
=====> Grigore Moisil 2016
=====> Urmasii lui Moisil 2016
=====> AGM 2016
=====> Algoritmiada 2016
=====> FMI No Stress 6
=====> Urmasii lui Moisil 2015
=====> FMI No Stress 5
=====> ONIS 2015
=====> Concursul National de Soft Grigore Moisil Lugoj
=====> ACM-ICPC Faza Nationala 2014-2015
=====> Infoarena Monthly 2014
=====> Concurs Mihai Patrascu 2013
=====> Algoritmiada 2015
=====> AGM 2015
=====> Junior Challenge 2015
=====> ONIS 2014
=====> Algoritmiada 2014
=====> FMI No Stress 4
=====> preONI 2006
=====> .com 2012
=====> Infoarena Monthly 2012
=====> Code Pandas
=====> Algoritmiada 2013
=====> FMI No Stress 3
=====> FMI No Stress 2012
=====> Junior Challenge 2012
=====> Algoritmiada 2012
=====> .com 2011
=====> Girls Programming Camp 2011
=====> Algoritmiada 2011
=====> F11 Competition 2011
=====> Tiberiu Popoviciu 2011
=====> Grigore Moisil 2011
=====> RMMS 2011
=====> FMI No Stress 2010
=====> Grigore Moisil 2010
=====> .com 2009
=====> Stelele Informaticii 2009
=====> Stelele Informaticii 2010
=====> Algoritmiada 2009
=====> Algoritmiada 2010
=====> Grigore Moisil 2009
=====> CCEX 2009
=====> Summer Challenge 2009
=====> All You Can Code 2008
=====> Selectie echipe ACM ICPC, UPB 2008
=====> Junior Challenge 2008
=====> Happy Coding 2008
=====> preONI 2008
=====> Grigore Moisil 2008
=====> Winter Challenge 2008
=====> Happy Coding 2007
=====> Autumn Warmup 2007
=====> preONI 2007
=====> Summer Challenge 2007
=====> Junior Challenge
=====> Winter Challenge 1
=====> Unirea 2007
=====> Happy Coding 2006
=====> Autumn WarmUp 2006
=====> Summer Challenge Doi
=====> Summer Challenge
=====> Happy coding
=====> Grigore Moisil
=====> Happy Birthday Infoarena
===> RCPC 2019
===> Summer Challenge Trei
=> Arhiva de probleme
===> Probleme pentru bacalaureat
=> Arhiva Infoarena Monthly
=> Arhiva ACM
=> Arhiva educationala
=> Concursuri virtuale
=> Informatica
===> Teme
=> Articole
===> Downloads
=> Probleme externe
===> .CAMPION
===> SGU
===> TIMUS
===> UVA
===> SPOJ
===> PKU
===> TJU
-----------------------------
Comunitate - feedback, proiecte si distractie
-----------------------------
=> Implica-te!
===> Arhiva educationala
===> Imbunatatire teste
===> Development
===> Scrie articole
===> Extinde arhiva
=> Blog
=> Feedback infoarena
===> Sondaje
===> Arhiva
===> IAP (Infoarena Proposal)
=> Off topic
Se încarcă ...