[Logo] Mendo Judge Discussion Board - Forums
  [Search] Search   [Recent Topics] Recent Topics   [Hottest Topics] Hottest Topics   [Members]  Member Listing   [Groups] Back to home page 
Задача Градежен Бум од регионален 2019  XML
Forum Index » Задачи од национални натпревари
Author Message
forelax



Joined: 12/07/2017 15:19:42
Messages: 2
Offline

Не очекував решението да работи. Како ефективната временска комплексност не стига до n^4 (бидејќи не добивам надминат временски лимит)? Дали е тоа до лоши тестови?
Еден пример би било кога матрицата на влез ќе е целосно исполнета со единици (освен на дијагоналата). Тогаш што би било поефикасно решение?

longhi



Joined: 16/01/2019 22:52:02
Messages: 18
Offline

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


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

Инаку, постои доста едноставно решение на задачава, кое отприлика оди вака:
forelax



Joined: 12/07/2017 15:19:42
Messages: 2
Offline

Фала, разбрав А и ги погледнав тестовите, random ми изгледаат. Инаку твоето решение има многу повеќе смисла
longhi



Joined: 16/01/2019 22:52:02
Messages: 18
Offline

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

Мора да се прават од некој граф (добро, со некоја random должина на ребра - ама тоа и не е толку важно), и потоа да се направи матрицата, инаку голем број од резултатите ќе биде "GRESHKA".
Можеби да се додадат некои примери со слични должини, ама тоа е тешко да се погоди оти различни решенија ќе се искуцаат од натпреварувачите. Според резултатите на натпреварот, мислам дека се океј.
 
Forum Index » Задачи од национални натпревари
Go to:   
Powered by JForum 2.1.8 © JForum Team