Author |
Message |
10/03/2019 19:24:07
|
forelax
Joined: 12/07/2017 15:19:42
Messages: 2
Offline
|
Не очекував решението да работи. Како ефективната временска комплексност не стига до n^4 (бидејќи не добивам надминат временски лимит)? Дали е тоа до лоши тестови?
Еден пример би било кога матрицата на влез ќе е целосно исполнета со единици (освен на дијагоналата). Тогаш што би било поефикасно решение?
|
|
|
10/03/2019 19:52:10
|
longhi
Joined: 16/01/2019 22:52:02
Messages: 18
Offline
|
forelax wrote:Не очекував решението да работи. Како ефективната временска комплексност не стига до n^4 (бидејќи не добивам надминат временски лимит)? Дали е тоа до лоши тестови?
Еден пример би било кога матрицата на влез ќе е целосно исполнета со единици (освен на дијагоналата). Тогаш што би било поефикасно решение?
Немам време да го разгледам подетално твоето решение, но колку што дискутиравме денес дел од оценувањето е намерно (greedy на четвртата носи дел од поените, тука, итн), за да нема огромен скок во тежината и дека е регионален натпревар (и секако голем број ќе продолжат на државен натпревар).
Инаку, постои доста едноставно решение на задачава, кое отприлика оди вака:
|
|
|
10/03/2019 20:16:00
|
forelax
Joined: 12/07/2017 15:19:42
Messages: 2
Offline
|
Фала, разбрав А и ги погледнав тестовите, random ми изгледаат. Инаку твоето решение има многу повеќе смисла
|
|
|
10/03/2019 20:23:35
|
longhi
Joined: 16/01/2019 22:52:02
Messages: 18
Offline
|
forelax wrote:Фала, разбрав А и ги погледнав тестовите, random ми изгледаат. Инаку твоето решение има многу повеќе смисла
Мора да се прават од некој граф (добро, со некоја random должина на ребра - ама тоа и не е толку важно), и потоа да се направи матрицата, инаку голем број од резултатите ќе биде "GRESHKA".
Можеби да се додадат некои примери со слични должини, ама тоа е тешко да се погоди оти различни решенија ќе се искуцаат од натпреварувачите. Според резултатите на натпреварот, мислам дека се океј.
|
|
|
|
|
|