Натпревари 2009

[LePianiste]

Овој натпревар не го ценам многу. Прво некои луѓе воопшто не се консултираат со менторите и сами си ги решаваат задачите, што е многу коректно. На останатиот дел други им ги решаваат. Филип Талимџиоски што се наоѓа на првата позиција е дете втора година. Дали ви се верува дека со втора година може да знае факториели, матрици, логаритми, експоненти, комбинации, растојание меѓу две точки =) и сл. ?
Друга работа, колку професорите на ПМФ се искомплексирани? Колку се исплати да се запишеш на ПМФ? Да не одам оф топик, тоа е веќе друга тема.
Заклучок: Aleks и останатите кој учествувате во натпреварот, решавајте ги задачите за да развивате логика и решавајте ги за вас и за на крај сфатете го натпреваров само како чиста забава. Толку од мене.

Не треба за својот неуспех се тешиме со оспорување на туѓиот успех.

 

[loverboy]

@WhizKid

Немам право на учество пошто не сум средношколец Ама задачата е binary search и greedy. Малку и теоретски треба предзнаење кои се овие алгоритми. Инаку пошто димензиите се мали, можеш и без binary seacrh, иако поопримално е со binary search. Немам време многу да објаснувам ама ќе ви дадам мал hint.

Како би се решила задачата ако
Даден ти е проблем во една група да можеш да сместиш збир на елементи <= M каде што M е фиксен број. Пронајди го во овој случај максималниот број на групи што може да се формираат.

И како решението на овој проблем можеш да го искористиш за откривање на решението на целата задача. Не знам колку ме сфативте... Ај помачете го малце мозокот, па ако треба пак некој hint ќе ви помогнам.

 

[loverboy]

П.С. Поради малите димензии (1 <= N <= 15) задачата може да се реши и со обичен brute force, тоа е испитување на сите можни комбинации. Бројот на комбинации и не е толку голем, од ред 2^15 па може брзо да се изгенерира (со начин на кој вас нај ви одговара, да речеме со рекурзија).

Погорниот начин со binary search и greedy е најоптимален и најдобар, работи за многу поголеми димензии на N, дури и ако N е од ред на 1,000,000 и ви советувам на тој начин да размислувате.

 

[MetalGear]

а може ли да прашам во која просторија правевте

пред недела имав предавање во Мал физички Амфи
гледам на вратата пишување"натпревар по информатика за основни и средни училишта"
си велам од толку простории во најзабегана ве ставиле :ua: за нив

 

[delix]

@ loverboy: moznite kombinacii se 15^15 zatoa sto imas 15 ciklusi, i 15 moze da se vo komisijata.
mislam deka ne e greedy, zatoa sto ima uslov ciklusite koi se zemaat od strana na eden clen od komisijata mora da bidat posledovatelni.
a za spremnosta na filip, ne znam koja bese budalata koja go osporuvase. filip veke 3 godini po red odi na internacionalna olimpijada i denes saat ipol pred krajot na natprevarot gi imase reseno zadacite,

 

[loverboy]

@delix

Прво
Грешка си. Комбинациите се 2^15. Пресметај си сам и добро размисли, а јас не реков само greedy туку greedy со binary search.

А второ
Задачата е прост пример на употреба да бинарно пребарување. Знам од каде им е најдена идејата за задачата и решена ми е таа оригиналната задача на овој начин, и тоа ми ги даде сите можни поени.

И уште една работа, Филип го почитувам многу но не може до сега 3 пати да бил на олимпијада затоа што ова му е трета год па математиката кажува дека можел двапати максимално до сега да одел. А пред две години кога јас се натпреварував и освоив златен медал на Македонската Олимпијада по Информатика (ќе ги отворам картите и не сакам да помислиш дека сум фалбаџија туку само да не ме потценуваш и да го почитуваш моето мислење) тој не беше во тимот за Интернационална Олимпијада што се одржуваше во Хрватска, но сепак за негови години беше солиден имајќи во предвид дека двајца од тие што бевме во тимот за Олимпијада учат во САД во МИТ и Принстон сега, само да ти кажам за големата конкуренција која беше тогаш. Значи секоја чест за Филип, навивам за него и за другите квалитети како него и се надевам дека ќе освои годинава медал на светско, не се сомневам дека ќе успее да влезе во тимот.

Уште еднаш размисли за математиката дали се 15^15 комбинации или 2^15.

Еве ти и линк http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch

Извини ако мислиш дека на груб тон ти пишувам, но мораш да бидеш поотворен и да бидеш спремен да разгледаш и други опции освен твојот начин на решавање. Ова е многу важно во програмирањето. Секогаш да се сомневаш, никогаш да не кажеш дека си сто посто сигурен додека не пробаш на хартија дека сигурно работи и тоа го искодираш и притоа системот ти кажува честито, ти помина на сите тест примери.

 

[eldiablo]

Јавно се извинувам за Филип Талимџиоски. Ок, инаку јас ја решив задачата на многу поелегантен начин. Прво ги подредуваш по големина членовите на низата. Оптималното поделување е кога ќе ги собереш сите броеви и кога ќе го поделиш по бројот на членови на комисијата. После собираш се додека не дојдеш то тој пресек или така нешто.

@LePianiste
Не учествувам на натпреварот. )

 

[delix]

@loverboy: не ти се лутам, моја грешка, не те разбрав убаво во првиот пост, сепак не може убаво да се објасни начин на решавање во 2-3 реда, а и за Филип бев грешка, би требало трета да му оваа година на олимпијада.

 

[VASJA]

FILIP ZVER samo toa da kazam . Inace filip mi spomna dinamicko za zadackata

 

[ac1d]

Абе луѓе воопшто не е битно дали некој препишувал или не, се слагам дека препишувањето не е фер али во секој случај вас ако ве бива ке решите све one way or another. На крај краева на ваквите натпревари не се натпреваруваме едни против други туку се натпреваруваме ние против задачите поставени таму А ако некој препишувал ке му дојде крајот на државен што се секирате

 

[GigaC]

Абе луѓе воопшто не е битно дали некој препишувал или не, се слагам дека препишувањето не е фер али во секој случај вас ако ве бива ке решите све one way or another. На крај краева на ваквите натпревари не се натпреваруваме едни против други туку се натпреваруваме ние против задачите поставени таму А ако некој препишувал ке му дојде крајот на државен што се секирате

Потполно се согласувам со тебе.
Но консултирање со ментор и добивање хинтови од негова страна, не е препишување. Супер ќе биде да го знаеш одговорот на задачите и сам да ги решиш, ама доколку ти требе помош за нешто, тука е менторот, и тоа не е препишување. Али јас не стасав да се консултирам со него и затоа кикснав . Али секоја чест на сите вие кои ги решивте и стасавте до овде, честитки

 

[vik]

Во врска со менторите... играат некоја улога или се таму само за лепе очи?

Мислам идат со вас на државен натпревар или така нешто или јок?

 

[Alexandar]

Па да, идеше со мене, барем за превоз не се секирав

 

[eldiablo]

Абе луѓе воопшто не е битно дали некој препишувал или не, се слагам дека препишувањето не е фер али во секој случај вас ако ве бива ке решите све one way or another. На крај краева на ваквите натпревари не се натпреваруваме едни против други туку се натпреваруваме ние против задачите поставени таму А ако некој препишувал ке му дојде крајот на државен што се секирате

Да се согласувам. Чувството кога ќе си решиш сам некоја тешка задача е многу добро. Поентата ми беше дека не е фер игра доколку некој ти ги решава задачите, не препишување. Сепак е ова натпревар меѓу учесниците од средните школи . Инаку државниот натпревар не е електронски да решиме уште некоја задачка? )

 

[GigaC]

Ха ха...дефинитивно таму ќе се види.
Али немора да значи. Може ќе ти се падне некоја задача што на крај памет нема да ти падне како требе да се реши и да кикснеш, па некој трет ќе ти зборува од зад грб дека на електронските некој друг ти ги решавал. Затоа не е убаво да делиме такви предрасуди за тоа кој колку знае
Секој си решава за себе, мислам дека овие натпревари треба да ни бидат лекција за понатаму и се од многу голема корист

 

[delix]

stvarno ako utnes na mala greska na drzaven ili drug natprevar mozes da izgubis premnogu vreme i da ispadne i da gi znaes zadacite da ne uspees da reses

 

[ac1d]

stvarno ako utnes na mala greska na drzaven ili drug natprevar mozes da izgubis premnogu vreme i da ispadne i da gi znaes zadacite da ne uspees da reses

Ако си доволно извежбан нема да си дозволиш да направиш таква грешка, а ако ја направиш тогаш повеќе вежбање следниот пат

 

[vik]

stvarno ako utnes na mala greska na drzaven ili drug natprevar mozes da izgubis premnogu vreme i da ispadne i da gi znaes zadacite da ne uspees da reses

Shit happens.

 

[delix]

Shit happens.

and then you die.

ama uste poglupa greska (koja i na mene mi se ima sluceno) e da ne zabelezis ogranicuvanjeto vo zadacata i greska promenlivi da opnes

 

[ac1d]

and then you die.

ama uste poglupa greska (koja i na mene mi se ima sluceno) e da ne zabelezis ogranicuvanjeto vo zadacata i greska promenlivi da opnes

Заради тоа ги немав сите бода односно наместо 170 бода јас имам 152 бидејки задачата ТРАЈКО ми паѓа на последните 3 примера поради користење на ЛОНГИНТ наместо ИНТ64

 

[delix]

na toa utnaa mislam 50% od natprevaruvacite, imam dva soklasnika vo osnovnata grupa koi ne presmetaa deka mozniot rezultat e 3 na stepen 29, i stavija longint isto

 

[LePianiste]

na toa utnaa mislam 50% od natprevaruvacite, imam dva soklasnika vo osnovnata grupa koi ne presmetaa deka mozniot rezultat e 3 na stepen 29, i stavija longint isto

2^50 e maksimumot koj moze da se dobie kako rezultat. [50 x duplo]

 

[ac1d]

LePianiste vo pravo si

 

[delix]

auuu da, jas smetav samo za troduplo kolku pati moze da se pojavi sto samoto po sebe e pregolemo za longint, a duplo moze da se pojavi poveke pati, i uste pogolem rezultat da se dobie.

Ej a znae li nekoj kade ke bide drzavniot, znam prvo pisuvase vo gostivar pa go smenija

 

[ac1d]

Некаде во Македонија