[Logo] Mendo Judge Discussion Board - Forums
  [Search] Search   [Recent Topics] Recent Topics   [Hottest Topics] Hottest Topics   [Members]  Member Listing   [Groups] Back to home page 
Messages posted by: longhi
Forum Index » Profile for longhi » Messages posted by longhi
Author Message
Croatian Open Competition in Informatics - COCI 2020/2021
Internet online contest series

Over the next six months we will organize seven online contests as a warm-up for the 2021 season of high school programming competitions. Everyone is welcome to participate! Each contest will be three hours long and will feature five tasks. The contestants will also have full feedback with at most 50 submissions per task. The tasks will be of widely varying difficulty; we hope that many beginner or up-and-coming contestants will participate, as well as the more experienced ones.

The first contest will be held this Saturday, October 17, starting at 14:00 (GMT/UTC). Check out your local times at https://hsin.hr/coci/next_contest.html
You may use Python, Pascal, C/C++ or Java as your programming language of choice.
The contest will also be featured on a newly-developed judging system. If your students wish to get a bit more familiar with the system, we have uploaded the last 14 COCI seasons for them to practice on. Most problems (except for the very easy ones) have English translations.


The two relevant websites are:
https://hsin.hr/coci/ - information about the contest
https://evaluator.hsin.hr/ - judging system

We hope that you will join us or encourage your students to do so!
This is the fifteenth year in a row that we are hosting the COCI series. You can find the tasks (statements, test data and solutions) from the previous years at https://hsin.hr/coci/. There are over 600 original tasks for students to practice on!

With regards,
Kresimir Malnar
Croatian Computer Science Association
Treba da se dodadat natprevarite za 2020 godina, za da gi ima i na MENDO.
COCI 2019/2020
Internet online contest series
Direct link: http://hsin.hr/coci/

Over the next six months we will organize seven online contests as a warm-up for the 2020 season of high school programming competitions. Everyone is welcome to participate!
Each contest will be three hours long and will feature five tasks. The tasks will be of widely varying difficulty; we hope that many beginner or up-and-coming contestants will participate, as well as the more experienced ones.

The first contest will be held on Saturday, 19 October 2019, starting at 14:00 (GMT/UTC). You may use Python, Pascal, C/C++ or Java as your programming language of choice.

Instructions, problems and the contest system will be located at http://evaluator.hsin.hr

This web page will be available for registration 48 hours before the contest.
You can find problems, test data and solutions from previous Croatian competitions in informatics here: http://hsin.hr/coci/
BATIR wrote:Raboti na 6/20. Ne znam kade pravam greska. Kje mi pomogne nekoj?


Кога рагледуваш некое пиано, треба да одбереш едно негово поле (на пример, она кое е најлево и најдолу) и тоа да го користиш за означување на посетените локации во vis[][].

Инаку, замисли го овој пример:



Твоето решение нема да може воопшто да тргне надесно, бидејќи ги имаш означено сите 4 полиња кои се наоѓаат лево за посетени.
Еве го твојот код со споменатите поправки (сега работи на сите тест случаи):
MODDI wrote:Кодов ми работи на првите 8 случаеви, на останатите ми паѓа на време, како да го убрзам кодов?

Твојот алгоритам има преголема сложеност. Оваа задача може да се реши во линеарно време O(N). Така да, не може секогаш да се "убрза" некој почнат код, и треба да се внимава да направиме анализа на алгоритамот пред да почнеме да решаваме (за да не изгубиме време на пишување на решение кое нема да освои онолку поени колку што очекуваме, па да почнеме од почеток со куцање на нешто друго).

Е сега, во однос на задачата. Размисли дали можеме да пресметаме неколку работи однапред, за да не ги правиме при секоја ротација. Еве еден начин како може да се реши задачава со тој пристап:
    Нека имаме низа frontSum[i] која што ни го памети збирот на првите i броеви - т.е. A[1] + A[2] + A[3] + ... + A[i].
    Нека имаме низа backSum[i] која што ни го памети збирот на сите броеви од i-тиот до N-тиот - т.е. A[i] + A[i+1] + ... + A[N]
    Нека имаме низа frontMin[i] која што го памети најмалиот збир од последователни броеви завршувајќи со i - т.е. min(A[1], A[1]+A[2], ... A[1] + A[2] + ... + A[i])
    Нека имаме низа backMin[i] која што го памети најмалиот збир од последователни броеви почнувајќи со i - т.е. min(A[i], A[i]+A[i+1], A[i]+A[i+1]+A[i+2], ...)


Со овие низи, проверките се доста едноставни за секоја ротација. На пример, ако решиме да ја разгледуваме i-тата ротација (онаа која почнува со i-тиот број), треба само да провериме дали се исполнети овие два услови:
    1) backMin[i] >= 0 (со ова го проверуваме потребниот услов за сите броеви од i-тиот до N-тиот, т.е. дали A[i] >= 0, дали A[i] + A[i+1] >= 0, итн)
    2) backSum[i] + frontMin[i-1] >= 0 (ако ротацијата почнува од i-тиот елемент, тогаш таа по броевите A[i], A[i+1], ... A[N] ќе заврши со броевите A[1], A[2], А[i-1], па со овој чекор го проверуваме условот за тие следни броеви. Види како истиот е сличен на првиот, но додаваме backSum[i]).

За првата ротација не мора да го проверуваме вториот услов, бидејќи таму нема прелевање (т.е. броевите се A[1], A[2], ... A[N]). Еве и код ако уште не е јасно:

Scratcher wrote:Немам никаква друга идеја за решавање на оваа задача освен со рекурзија(backtracking)


Втората акција што може да ја направи роботот (две вреќи да се спојат во една) е многу поедноставна од првата (бидејќи таму треба да одлучуваме колку подароци да префрлиме).
Ова може да го средиме така што првата операција воопшто нема да ја правиме, туку ќе ја правиме само втората - но во две насоки, т.е. почнувајќи и од почетната состојба (како што се ќесите спакувани на почеток) и од крајната состојба (како што треба да бидат спакувани). Ова има логика бидејќи едната акција на роботот е слична на втората - само обратно - наместо да спојуваме две вреќи во една, делиме една вреќа на две.

Значи, можеме да напишеме програма која што ќе користи неколку идеи
1) Да пресметаме со колку акции може да се стигне од една состојба до сите други со спојување на вреќи (за тоа може да се искористи queue - слична идеја како кај алгоритамот BFS)
2) Ако од почетната состојба можеме да дојдеме до некоја состојба X, и од крајната состојба може да дојдеме до истата таа состојба X - тогаш може да се стигне од почетната состојба до крајната состојба. Притоа, ако требаат A чекори за да се стигне од почетната состојба до X, и B чекори за да се стигне од крајната состојба до X, тогаш за доаѓање од почетната до крајната состојба преку X требаат вкупно (A+B) чекори.

Ако е уште нејасно, еве решение
BATIR wrote:Dali pod bitmaski, mislis za site kombinacii da gledame kolku sme potrosile, pri toa da e validno? I da go barame maksimumot?

Максимум градови во кои може да се направат митинзи - тоа што се бара во задачата.
Инаку, ако не ме разбра, тоа зборував дека "Постојат и други решенија за добивање на делумни поени" - едно е решението што беше напишано горе (greedy), може со bfs и битмаски (бидејќи има и помали тест случаи на кои се оценуваат решенијата), итн.
ThePopivanov wrote:Вчера на натпреварот кога ја решавав оваа падна на скоро сите тест примери освен на 3.
Денеска изменив нешто ситно сега на 23 поминува а само на 7 паѓа.


Ова е greedy решение и е доста логично, па ќе добие дел од поените (инаку, како што излезе, сите ќе имаа 0 на таа задача).
Но, оваа задача е најдобро да се решава со помош на динамичко програмирање.

Идејата е доста едноставна, ќе користиме матрица dp[c][n] која ќе ни памети во колку најмногу градови може да се направи митинг ако веќе сме разгледале [c] градови и имаме уште [n] средства на располагање.
Сега, ќе ги поминуваме градовите еден по еден и ќе ја пополнуваме матрицава (како и други слични задачи кои се решаваат на ваков начин) и истата ќе содржи некаков резултат.
Но, по кој редослед да ги поминуваме градовите? Од кога ќе ни текне дека единствениот начин да добиеме пари е од организацијата на митинг (инаку само трошиме), тогаш може да забележиме дека е најдобро да ги сортираме во опаѓачки редослед според R[x]. За се друго ќе се погрижи динамичкото програмирање. И тоа е решението.

(Постојат и други решенија за добивање на делумни поени, dfs, битмаски, итн)
forelax wrote:Фала, разбрав А и ги погледнав тестовите, random ми изгледаат. Инаку твоето решение има многу повеќе смисла

Мора да се прават од некој граф (добро, со некоја random должина на ребра - ама тоа и не е толку важно), и потоа да се направи матрицата, инаку голем број од резултатите ќе биде "GRESHKA".
Можеби да се додадат некои примери со слични должини, ама тоа е тешко да се погоди оти различни решенија ќе се искуцаат од натпреварувачите. Според резултатите на натпреварот, мислам дека се океј.
forelax wrote:Не очекував решението да работи. Како ефективната временска комплексност не стига до n^4 (бидејќи не добивам надминат временски лимит)? Дали е тоа до лоши тестови?
Еден пример би било кога матрицата на влез ќе е целосно исполнета со единици (освен на дијагоналата). Тогаш што би било поефикасно решение?


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

Инаку, постои доста едноставно решение на задачава, кое отприлика оди вака:
floreloriz123 wrote:http://mendo.mk/Task.do?id=704

Знае ли некој зошто не ми поминува на 1/10 тест случаи (на 4тиот мојот код дава резултат 1 23, а треба 1 21)?



Ај види го следниот код (таму каде што е поправено) и размисли зошто овој работи на сите примери.
Хинт: И зошто тоа има врска со ова "Цревата на системот не може да поминат преку полињата со бетонски плочи, но слободно може да поминуваат преку сите други полиња.", и фактот што долу за секое 'C' викаш graph[i][j] = 0; visited[i][j] = true;

P.S. Пробав да променам најмалку работи во кодот, па затоа само сменив во функцијата bfs(), инаку ова може да се поедностави.


MODDI wrote:Ја решавав задачава, кодов ми работи на 6 тест примери, на останатите ми враќа прогрешен резултат, хелп


Има повеќе работи за поправање. Види кодот подолу:
David_Gorgiev wrote:Овој код е за задачата „Точка“ од Научи С++
Може ли некој да ми каже што имам грешка во кодот?


Прво, не мора да проверуваш (како со првиот if) дали податоците се соодветни (ако пишува во текстот дека ќе бидат помеѓу 0 и 1000, на пример, тогаш ќе бидат).
Второ, можеш да симнеш тест случај од МЕНДО и да го извршиш на компјутер за да видиш што е проблемот.

Еве што забележав јас:
1) каде што имаш (by=dx+b) треба наместо dx да е dy.
2) каде што имаш (ax=px+a) треба да имаш само (ax=px), инаку A и B ти се истата точка (види кај B дека користиш dx,dy).

Со тие промени работи на сите тест случаи.
>
MODDI wrote:Ја решавав задачата Зајак од МОИ 2015, ми работи на 3/25 , помош околу кодов.


Не е баш така, кодов како да е за некоја друга задача.
Јас вака би поправил, имаш коментари во програмата ако нешто не е јасно.

MODDI wrote:Ја решавав задачава и ми вади 8/40, може малку помош околу кодов.

Имаш точно решение погоре ако бараш нова идеја.

Инаку, околу кодов, би ти препорачал да почнеш од почеток оти мислам дека малку се имаш измешано со even, noneven и како се тоа го користиш.
На пример, додади го делот што го имам ставено под коментар во твојата програма, и на пример изврши ја кај тебе на компјутер (за пример од текстот на задачата), ќе видиш печати "error", а во тој дел pom треба да е помало од even.size(), бидејќи низата е дефинирана вака: visited_even[even.size()]

 
Forum Index » Profile for longhi » Messages posted by longhi
Go to:   
Powered by JForum 2.1.8 © JForum Team